Solano Charris, Elyn Lizeth · 2015
Cette these aborde le probleme de tournees de vehicules (VRP) adressant des incertitudes via l'optimisation robuste, en donnant le VRP Robuste (RVRP). D'abord, les incertitudes sont integrees sur les temps de trajet. Ensuite, une version bi-objectif du RVRP (bi-RVRP) est consideree en prenant en compte les incertitudes sur les temps de trajet et les demandes. Pour resoudre le RVRP et le bi-RVRP, differentes methodes sont proposees pour determiner des solutions robustes en minimisant le pire cas. Un Programme Lineaire a Variables Mixtes Entieres (MILP), six heuristiques constructives, un algorithme genetique (GA), une procedure de recherche locale et quatre strategies iteratives a demarrage multiple sont proposees : une procedure de recherche constructive adaptive randomisee (GRASP), une recherche locale iteree (ILS), une ILS a demarrage multiple (MS-ILS), et une MS-ILS basee sur des tours geants (MS-ILS-GT) convertis en tournees realisables grâce a un decoupage lexicographique. Concernant le bi-RVRP, le cout total des arcs traverses et la demande totale non satisfaite sont minimises sur tous les scenarios. Pour resoudre le probleme, differentes versions de metaheuristiques evolutives multi-objectif sont proposees et couplees a une recherche locale : l'algorithme evolutionnaire multi-objectif (MOEA) et l'algorithme genetique avec tri par non-domination version 2 (NSGAII). Differentes metriques sont utilisees pour mesurer l’efficience, la convergence, ainsi que la diversite des solutions pour tous ces algorithmes
Cited by 5
Elyn L. Solano‐Charris · theses.fr (ABES) · 2015
This work extends the Vehicle Routing Problem (VRP) for addressing uncertainties via robust optimization, giving the Robust VRP (RVRP). First, uncertainties are handled on travel times/costs. Then, a bi-objective version (bi-RVRP) is introduced to handle uncertainty in both, travel times and demands. For solving the RVRP and the bi-RVRP different models and methods are proposed to determine robust solutions minimizing the worst case. A Mixed Integer Linear Program (MILP), several greedy heuristics, a Genetic Algorithm (GA), a local search procedure and four local search based algorithms are proposed: a Greedy Randomized Adaptive Search Procedure (GRASP), an Iterated Local Search (ILS), a Multi-Start ILS (MS-ILS), and a MS-ILS based on Giant Tours (MS-ILS-GT) converted into feasible routes via a lexicographic splitting procedure. Concerning the bi-RVRP, the total cost of traversed arcs and the total unmet demand are minimized over all scenarios. To solve the problem, different variations of multiobjective evolutionary metaheuristics are proposed and coupled with a local search procedure: the Multiobjective Evolutionary Algorithm (MOEA) and the Non-dominated Sorting Genetic Algorithm version 2 (NSGAII). Different metrics are used to measure the efficiency, the convergence as well as the diversity of solutions for all these algorithms
Cited by 2Open access
Τούλης, Κωνσταντίνος, Toulis, Konstantinos · Athens University of Economics & Business · 2025
Η παρούσα διπλωματική εργασία εξετάζει το Family Capacitated Vehicle Routing Problem (F-CVRP), ένα εξειδικευμένο NP-hard πρόβλημα που ανήκει στην ευρύτερη κατηγορία των Προβλημάτων Δρομολόγησης Οχημάτων (VRP). Το F-CVRP μοντελοποιεί πραγματικές προκλήσεις στον τομέα των logistics, όπως η διαχείριση αποθηκών, όπου η βελτιστοποίηση των δρομολογίων με ακριβείς μεθόδους καθίσταται μη πρακτική λόγω του μεγέθους του προβλήματος.Διεξήχθη εκτενής βιβλιογραφική ανασκόπηση για την ανάλυση υπαρχουσών μεθοδολογιών επίλυσης του F-CVRP, αξιοποιώντας τόσο ευρετικές όσο και μεταευρετικές προσεγγίσεις. Η εργασία τεκμηριώνει την υλοποίηση διαφόρων τεχνικών επίλυσης, συμπεριλαμβανομένου ενός αλγορίθμου Ελάχιστου Κόστους Εισαγωγής για τη δημιουργία αρχικής εφικτής λύσης. Στη συνέχεια, εφαρμόζεται επαναληπτική Τοπική Έρευνα (LS) με tabu policy, η οποία βελτιώνει τα δρομολόγια μέσω μικρών τοπικών τροποποιήσεων, αποτρέποντας παράλληλα την επαναληπτική εξερεύνηση των ίδιων λύσεων. Επιπλέον, χρησιμοποιείται μία προσέγγιση Μεγάλης Γειτονιάς (LNS), ενισχυμένη με ένα Adaptive Memory framework, που εκμεταλλεύεται ποιοτικά χαρακτηριστικά των λύσεων για τη δημιουργία βελτιωμένων δρομολογίων.Οι προτεινόμενες μεθοδολογίες αξιολογήθηκαν με χρήση δεδομένων αναφοράς, συγκρίνοντας την υπολογιστική τους απόδοση και την ποιότητα των λύσεων. Τα αποτελέσματα δείχνουν ότι αυτές οι ευρετικές και μεταευρετικές τεχνικές είναι ιδιαίτερα αποτελεσματικές, παρέχοντας ανταγωνιστικές λύσεις σε εύλογους χρόνους υπολογισμού, ειδικά για μεγάλης κλίμακας περιπτώσεις προβλημάτων.
Cited by 0Open access
Repoussis, Panagiotis P. · Athens University of Economics & Business · 2008
This dissertation is entitled \Optimization Methods for Complex Vehicle Routing and Scheduling problems". The term \optimization methods" refers to hybrid methodologies that combine heuristic and metaheuristic algorithms to produce effective and robust solution methods for combinatorial optimization problems. The term \complex" denotes the computational complexity and the large-scale nature of the problems considered. Finally, the term \vehicle routing and scheduling problems" describes a subclass of problems emanating from the broader family of Vehicle Routing Problems (VRP). The VRP is the problem of finding a set of optimal routes for a fleet of vehicles to serve a given set of customers. The vehicles are often assumed to have a common home base, called the depot. The cost of traveling between each pair of customers and between the depot and each customer is given. The goal is to find the optimum \assignment" and service \schedule" of customers for each vehicle route, such that the total traveling cost is minimized and all customers are served by exactly one vehicle. Typically the solution has to satisfy several other restrictions, such as total capacity of vehicles, route durations and other operational constraints. In this thesis, the term VRP is used to describe a broad class of problems and not a specific problem with a limited set of restrictions or constraints; thus, in the remainder of the thesis the term VRP includes all problems that involve creating one or more routes, starting and ending in one or more common depots or at predefined start and end terminals, in contrast to most archival literature where VRP is mainly used for the Capacitated Vehicle Routing Problem (CVRP). A subclass of VRPs is the Vehicle Routing Problem with Time Windows (VRPTW); this is the core problem studied in this thesis along with its variants. In the VRPTW, a desired visit time (time window) at each customer is given. Also, a number of additional constraints are often enforced, e.g. heterogeneous fleets of vehicles, open routes, multiple depots, etc. The VRPTW is a classical and well-studied vehicle routing problem. It is an NP-hard combinatorial optimization problem that has attracted the interest of both researchers and practitioners. For many of the problem instances considered in this thesis, the set of feasible solutions is so large that even if we had a computer that in a systematic way could construct and evaluate the cost of a trillion (1012) solutions per second, and we had started that computer right after the big bang, 14 billion years ago, it would still not have evaluated all the feasible solutions today. Consequently we have to resort to other methods and forget simple enumeration. Engineering and technology have been continuously providing examples of difficult optimization problems, with practical as well as theoretical importance. Optimization problems are concerned with the search for the \best" configuration of a set of variables to achieve some goals. A huge collection of optimization techniques has been suggested by several researchers from different fields; an immense number of refinements has made these techniques work for specific types of applications. All these procedures are based on some common ideas, which are being characterized by additional specific features. However, for most optimization problems no procedure is known, in general, to get directly an \optimal" solution. Three types of solution methods are typically employed to solve problems such as the VRPTW: Heuristics, Approximate Algorithms and Exact Methods. Heuristics are solution methods that relatively quickly can _nd a feasible solution with reasonable quality. Approximation algorithms are special heuristics that can provide a solution and an errorquality guarantee. Exact methods guarantee that the optimal solution is found subject to sufficient time and memory space. Although in recent years significant algorithmic achievements have been reached and highly sophisticated exact methods have been proposed, heuristics remain the only reliable and viable approach for the solution of practical large-scale instances. Towards this end, a special class of heuristics that has received special attention during the last two decades is the so-called metaheuristics. Such algorithms provide general frameworks for heuristics that can be applied to different problems, while high quality solutions are often obtained within reasonable computational burdens. This PhD thesis focuses on the exploration of the computational power of metaheuristics, not only in terms of solving effectively and efficiently the VRPTW and other real-life industrial variants of the problem in a limited amount of time, but also developing cooperative and competitive optimization methods that are characterized by simplicity, exibility and robustness. The problems studied have been inspired from real-world applications and the last part of the thesis describes the application of some of the solution methods developed in a real-life industrial environment.
Cited by 0Open access
Παναγιώτης Ρεπούσης · 2008
Cited by 0
Robert Cristian Abreu · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2016
O Problema de Roteamento de Veículos (PRV) é um problema clássico de Otimização Combinatória bastante estudado na literatura devido a sua importância prática. O PRV Periódico (PRVP), abordado neste trabalho, é uma variante do PRV no qual um conjunto de clientes devem ser visitados uma ou mais vezes para atender suas demandas durante um horizonte de tempo composto de vários dias. Os dias de visita/atendimento não são fixados a priori. Uma lista de dias possíveis (agenda de visitas) é associada a cada cliente. O objetivo é determinar os dias de visita de cada cliente e as rotas dos veículos para cada dia do horizonte de tal maneira que a distância total de percurso dos veículos e os custos associados com utilização dos mesmos sejam minimizados. O PRVP é um problema que pertence à classe NP-difícil. Neste trabalho, para resolvê-lo, são desenvolvidos três métodos de otimização: Proximity Search (PS), Ite- rated Local Search (ILS) e Particle Swarm Optimization (PSO). PS é um método genérico que faz uso do modelo de Programação Inteira do problema para melhorar iterativamente uma solução inicial. Em vez de modificar as restrições do modelo com o objetivo de reduzir o espaço de busca, o PS modifica a função objetivo do modelo para tornar a busca mais fácil. Os métodos ILS e PSO são meta-heurísticas de busca em vizinhança e populacional/evolutiva, respectivamente. Os desempenhos dos métodos propostos são analisados em instâncias de pequeno e grande porte geradas neste trabalho, e também em instâncias disponíveis na literatura. O desempenho do PS é comparado com o solver CPLEX, que resolve o modelo original do problema. As meta-heurísticas desenvolvidas são comparadas entre si e também são comparadas com algumas heurísticas da literatura. Os experimentos computacionais mostram que os métodos propostos são eficientes, competitivos e rápidos.
Cited by 0Open access
Monit Sharma, Hoong Chuin Lau · Communications in computer and information science · 2026
Cited by 0
Sharma, Monit, Lau, Hoong Chuin · Zenodo (CERN European Organization for Nuclear Research) · 2025
Cited by 0Open access
Sharma, Monit, Lau, Hoong Chuin · Zenodo (CERN European Organization for Nuclear Research) · 2025
Cited by 0Open access
A. Nikolopoulou · National Archive of Doctoral Theses (National Documentation Center (Greece)) · 2016
Η διδακτορική αυτή διατριβή πραγματεύεται την ανάπτυξη μεθόδων βελτιστοποίησης για την επίλυση πολύπλοκων Προβλημάτων Δρομολόγησης Στόλου Οχημάτων Πολλαπλών Επίπεδων με Διαμετακομιστικούς Κόμβους. Ο στόχος της έρευνας είναι αφενός να μελετήσει σύνθετα ρεαλιστικά προβλήματα με διάφορους επιχειρησιακούς περιορισμούς, αφετέρου να αναπτύξει αποτελεσματικές μεθόδους βελτιστοποίησης για την επίλυση των προβλημάτων αυτών εντός ρεαλιστικών για πρακτικές εφαρμογές, υπολογιστικών χρόνων. Εξετάζονται επίσης διαφορετικές δομές δικτύων διανομής με διαμετακομιστικούς κόμβους και συγκρίνονται εναλλακτικές στρατηγικές διανομής για τη διακίνηση φορτίου. […]
Cited by 0Open access
Nikolopoulou, Amalia · Athens University of Economics & Business · 2016
Η διδακτορική αυτή διατριβή πραγματεύεται την ανάπτυξη μεθόδων βελτιστοποίησης για την επίλυσηπολύπλοκων Προβλημάτων Δρομολόγησης Στόλου Οχημάτων Πολλαπλών Επίπεδων μεΔιαμετακομιστικούς Κόμβους. Ο στόχος της έρευνας είναι αφενός να μελετήσει σύνθετα ρεαλιστικάπροβλήματα με διάφορους επιχειρησιακούς περιορισμούς, αφετέρου να αναπτύξει αποτελεσματικέςμεθόδους βελτιστοποίησης για την επίλυση των προβλημάτων αυτών εντός ρεαλιστικών για πρακτικέςεφαρμογές, υπολογιστικών χρόνων. Εξετάζονται επίσης διαφορετικές δομές δικτύων διανομής μεδιαμετακομιστικούς κόμβους και συγκρίνονται εναλλακτικές στρατηγικές διανομής για τη διακίνησηφορτίου.Το Πρόβλημα Δρομολόγησης Στόλου Οχημάτων Πολλαπλών Επίπεδων με Διαμετακομιστικούς Κόμβουςείναι ένα κλασικό επιχειρησιακό πρόβλημα που αντιμετωπίζουν οι εταιρείες logistics και μεταφορών σεκαθημερινή βάση. Ειδικότερα, ιδιαίτερο πρακτικό ενδιαφέρον παρουσιάζουν τα προβλήματα πουσχετίζονται με την παραλαβή φορτίου από προμηθευτές και την παράδοση φορτίου σε πελάτες. Ηδιακίνηση φορτίου σε αυτή την περίπτωση, γίνεται μέσω ενός στόλου οχημάτων τα οποίαπαραλαμβάνουν αρχικά φορτίο από διάφορους προμηθευτές, και στη συνέχεια το παραδίδουν στουςπελάτες.Για την αντιμετώπιση των παραπάνω προβλημάτων παραλαβής και παράδοσης φορτίου, έχουνυιοθετηθεί διάφορες στρατηγικές διανομής. Μια απλή, κλασική στρατηγική είναι η απευθείας διανομή, μετην οποία το φορτίο μεταφέρεται απευθείας από τους πελάτες παραλαβής στους πελάτες παράδοσηςμέσω ενός στόλου οχημάτων, χωρίς να μεσολαβεί το στάδιο της αποθήκευσης ή μεταφόρτωσης φορτίουσε κάποιο ενδιάμεσο σημείο/εγκατάσταση. Στη βιβλιογραφία, το παραπάνω πρόβλημα δρομολόγησηςοχημάτων ορίζεται ως το Πρόβλημα Δρομολόγησης Οχημάτων με Παραλαβή και Παράδοση (ΠΔΟΠΠ).Συγκεκριμένα, η διανομή φορτίου γίνεται σε ένα επίπεδο (echelon), στο οποίο τα οχήματα ξεκινούν απόένα κεντρικό σημείο και επιστρέφουν σε αυτό αφού ολοκληρώσουν το προγραμματισμένο δρομολόγιο,χωρίς ενδιάμεση στάση σε κάποιο σημείο μεταφόρτωσης. Επιπλέον, υπάρχει αμφιμονοσήμαντη σχέσημεταξύ των πελατών παράδοσης και πελατών παραλαβής: η απαίτηση ενός πελάτη παραλαβής δηλαδή,μπορεί να εξυπηρετηθεί από έναν μόνο πελάτη παράδοσης και αντίστροφα. Κάθε ζεύγος πελατών(πελάτης παραλαβής - πελάτης παράδοσης), θα πρέπει να εξυπηρετείται από το ίδιο δρομολόγιο μία μόνοφορά και επιπλέον ο πελάτης παραλαβής σε ένα δρομολόγιο θα πρέπει να προηγείται του πελάτηπαράδοσης. Μια εναλλακτική στρατηγική είναι αυτή της διανομής με άμεση μεταφόρτωση, με την οποία η διακίνησητου φορτίου πραγματοποιείται μέσω ενός ενδιάμεσου σημείου όπου επιτυγχάνεται η συγκέντρωση, ηανακατανομή και η άμεση μεταφόρτωση των φορτίων στα οχήματα διανομής. Στη βιβλιογραφία, τοπαραπάνω πρόβλημα δρομολόγησης οχημάτων ορίζεται ως Πρόβλημα Δρομολόγησης Οχημάτων μεΆμεση Μεταφόρτωση (ΠΔΟΑΜ). Η διαφορά σε σύγκριση με το ΠΔΟΠΠ έγκειται στο ότι στο ΠΔΟΑΜη διανομή φορτίου πραγματοποιείται σε δύο διακριτά επίπεδα. Στο πρώτο επίπεδο, τα οχήματαπαραλαβής ξεκινούν από το σημείο μεταφόρτωσης, επισκέπτονται διαδοχικά τους προμηθευτές γιαπαραλαβή φορτίου, και επιστρέφουν στο σημείο μεταφόρτωσης όπου θα γίνει η συγκέντρωση τωνφορτίων. Στο σημείο μεταφόρτωσης, τα φορτία αναδιατάσσονται και κατανέμονται ανάλογα σταοχήματα διανομής. Αυτό είναι το δεύτερο επίπεδο, όπου το φορτίο διανέμεται τελικά στους πελάτες.Η επιλογή της κατάλληλης στρατηγικής διανομής για την διακίνηση προϊόντων, είναι κρίσιμη. Με τηνβελτίωση της αποδοτικότητας ενός δικτύου διανομής, οι επιχειρήσεις logistics αποσκοπούν στη μείωσητου κόστους μεταφοράς, στην καλύτερη αξιοποίηση της πληρότητας των οχημάτων, στην καλύτερηεξυπηρέτηση των πελατών, καθώς και στη μείωση της ατμοσφαιρικής ρύπανσης και της κυκλοφοριακήςσυμφόρησης. Επομένως, ο αποτελεσματικός σχεδιασμός και διαχείριση ενός δικτύου μεταφοράς και οαποτελεσματικός προγραμματισμός των δρομολογίων μπορεί να έχει σημαντικά οικονομικά,περιβαλλοντικά και κοινωνικά οφέλη. Για το σκοπό αυτό, η επιστημονική κοινότητα τα τελευταία χρόνιαασχολείται ολοένα και περισσότερο με την ανάπτυξη μεθόδων βελτιστοποίησης, καθώς η χρήση τουςέχει αποδειχθεί καθοριστική στη μείωση του κόστους μεταφοράς, συμβάλλοντας έτσι στην εύρυθμηλειτουργία των επιχειρήσεων αλλά και της παγκόσμιας οικονομίας γενικότερα.Τα Προβλήματα Δρομολόγησης Στόλου Οχημάτων Πολλαπλών Επίπεδων με ΔιαμετακομιστικούςΚόμβους είναι προβλήματα συνδυαστικής βελτιστοποίησης και χαρακτηρίζονται από μεγάληυπολογιστική πολυπλοκότητα ακόμα και στην πιο απλή μορφή τους. Προβλήματα που περιλαμβάνουνπερισσότερους από 100 πελάτες είναι αδύνατον να επιλυθούν στην πράξη από ακριβείς αλγορίθμουςμαθηματικού προγραμματισμού βέλτιστα, και εντός λογικού υπολογιστικού χρόνου. Για το λόγο αυτό, τοενδιαφέρον της ερευνητικής δραστηριότητας έχει στραφεί στην ανάπτυξη μεταευρετικών αλγορίθμων γιατην επίλυση προβλημάτων μεγάλης κλίμακας με εκατοντάδες ή και χιλιάδες πελάτες. Οι μέθοδοι αυτέςστις περισσότερες περιπτώσεις, χαρακτηρίζονται από ευελιξία η οποία επιτρέπει την εύκολη αλγοριθμικήτροποποίηση για την αντιμετώπιση προβλημάτων με διαφορετικές επιχειρησιακές ανάγκες καιπεριορισμούς. Τα παραπάνω χαρακτηριστικά κάνουν ελκυστική την χρήση των μεθόδων αυτών για τηνεπίλυση πραγματικών προβλημάτων στο σύγχρονο επιχειρησιακό περιβάλλον. Εξετάζοντας την υπάρχουσα βιβλιογραφία διαπιστώνει κανείς πως δεν έχουν μελετηθεί επαρκώς εκδοχέςτων ΠΔΟΠΠ και ΠΔΟΑΜ με ρεαλιστικούς επιχειρησιακούς περιορισμούς. Ειδικότερα, στηβιβλιογραφία έχουν μελετηθεί μόνο εκδοχές του ΠΔΟΑΜ με αμφιμονοσήμαντη σχέση μεταξύ τωνπελατών παράδοσης και των πελατών παραλαβής. Σε πρακτικές εφαρμογές παρ’ όλα αυτά, ένας πελάτηςπαραλαβής μπορεί να παραλαμβάνει φορτίο από περισσότερους από έναν πελάτες παράδοσης. Επιπλέον,ενώ υπάρχουν εργασίες οι οποίες αναδεικνύουν τα οφέλη των τμηματικών επισκέψεων (δηλαδή ηεξυπηρέτηση ενός πελάτη με περισσότερα από ένα οχήματα) σε προβλήματα δρομολόγησης οχημάτων, ηαντίστοιχη περίπτωση για το ΠΔΠΑΜ δεν έχει μελετηθεί. Αξίζει επίσης να αναφερθεί ότι ταπλεονεκτήματα και μειονεκτήματα της απευθείας διανομής ή/και διανομής με άμεση μεταφόρτωση δενέχουν μελετηθεί επαρκώς και δεν έχουν καθοριστεί κριτήρια για την επιλογή τους. Τέλος, στηβιβλιογραφία δεν έχουν μελετηθεί επαρκώς υβριδικά μοντέλα διανομής με δυνατότητα επιλογήςεναλλακτικών στρατηγικών. Συνεπώς η ανάγκη ανάπτυξης καινοτόμων και ευφυών μεθόδωνβελτιστοποίησης για την επίλυση μεγάλης κλίμακας προβλημάτων καθίσταται προφανής.Σε μία προσπάθεια να καλυφθούν τα παραπάνω κενά της βιβλιογραφίας, η διδακτορική αυτή διατριβήστοχεύει στην εξέταση νέων συνδυασμένων προβλημάτων και στη μοντελοποίηση ρεαλιστικώνεπιχειρησιακών περιορισμών. Επίσης, στοχεύει στην ανάπτυξη μεθόδων βελτιστοποίησης για τηνεπίλυση προβλημάτων μεγάλης κλίμακας και στην εύρεση σχεδόν βέλτιστων λύσεων σε αποδεκτούςυπολογιστικούς χρόνους. Η ερευνητική προσπάθεια επικεντρώνεται στην ανάπτυξη μεταευρετικώναλγορίθμων. Έμφαση δίνεται στην ενσωμάτωση μηχανισμών εκμάθησης μέσα από κατάλληλασχεδιασμένες δομές μνήμης.Αρχικά γίνεται μια συγκριτική μελέτη επιδόσεων των δυο βασικών στρατηγικών διανομής, της απευθείαςδιανομής και της διανομής με άμεση μεταφόρτωση για διαφορετικά σενάρια. Πιο συγκεκριμένα,μοντελοποιούνται και επιλύονται γενικευμένες εκδοχές του ΠΔΟΠΠ καθώς και του ΠΔΟΑΜ. Για τηνεπίλυσή τους, προτείνεται ένας νέος αλγόριθμος Απαγορευμένης Αναζήτησης (Tabu Search) λύσεων.Αποτελέσματα σε πρότυπα προβλήματα μέτρησης επιδόσεων της βιβλιογραφίας επαληθεύουν τηναπόδοση και καταλληλότητα του αλγορίθμου. Αξίζει να σημειωθεί ότι ο νέος προτεινόμενος αλγόριθμοςπαρήγαγε αρκετές καλύτερης ποιότητας λύσεις σε σύγκριση με άλλους αλγορίθμους στη βιβλιογραφία,τόσο σε μεσαίας όσο και σε μεγάλης κλίμακας προβλήματα. Παράλληλα, προκειμένου να αξιολογηθεί ησχετική απόδοση των υπό εξέταση στρατηγικών, κατασκευάστηκαν νέα πρότυπα προβλήματα μέτρησηςεπιδόσεων τα οποία διαφέρουν ως προς την γεωγραφική κατανομή των πελατών καθώς και τιςαποστάσεις μεταξύ ζευγών πελατών παραλαβής - παράδοσης. Για τη μελέτη της επίδρασης διαφόρωνπαραμέτρων του προβλήματος όπως η χωρητικότητα των οχημάτων, ο χρονικός ορίζοντας των δρομολογίων, η θέση της κεντρικής αποθήκης και ο χρόνος μεταφόρτωσης στο συνολικό κόστος,πραγματοποιήθηκαν εκτενή υπολογιστικά πειράματα. Όπως ήταν αναμενόμενο, τα υπολογιστικάπειράματα επιβεβαίωσαν ότι οικονομικότερη στρατηγική στις περισσότερες περιπτώσεις είναι αυτή τηςαπευθείας διανομής. Ωστόσο, προέκυψε από τα υπολογιστικά πειράματα ότι υπάρχουν συγκεκριμέναχαρακτηριστικά του δικτύου διανομής και διάφορες παράμετροι του προβλήματος, και ειδικότερα α) ηχωρητικότητα των οχημάτων, β) η γεωγραφική κατανομή των πελατών, και γ) οι αποστάσεις μεταξύζευγών πελατών παραλαβής – παράδοσης, τα οποία ευνοούν την διανομή με άμεση μεταφόρτωση.Στη συνέχεια και έχοντας εξετάσει μεμονωμένα τις δύο στρατηγικές διανομής, μοντελοποιείται καιεπιλύεται ένα υβριδικό δίκτυο διανομής όπου υπάρχει η δυνατότητα απευθείας διανομής καθώς καιδιανομής με άμεση μεταφόρτωση. Για την επίλυση του προβλήματος, αναπτύχθηκε ένας αλγόριθμοςΑπαγορευμένης Αναζήτησης λύσεων. Ο προτεινόμενος αλγόριθμος εξετάστηκε σε νέα πρότυπαπροβλήματα μέτρησης επιδόσεων. Από τα υπολογιστικά πειράματα που πραγματοποιήθηκαν προέκυψεότι ο συνδυασμός των στρατηγικών απευθείας διανομής και διανομής με άμεση μεταφόρτωση σε έναδίκτυο διανομής, μπορεί να οδηγήσει σε σημαντική μείωση του κόστους μεταφοράς.Τέλος, επιχειρείται για πρώτη φορά η μοντελοποίηση και επίλυση μιας γενικευμένης εκδοχής τουΠΔΟΑΜ, με πολυσήμαντες σχέσεις μεταξύ των πελατών παραλαβής και παράδοσης καθώς καιετερογενή στόλο οχημάτων για τα δρομολόγια παραλαβής και τα δρομολόγια παράδοσης. Επίσης,μελετάται η δυνατότητα εξυπηρέτησης των πελατών παραλαβής και παράδοσης με τμηματικέςεπισκέψεις. Σε μεθοδολογικό επίπεδο, προτείνεται ένας νέος αλγόριθμος ΠρογραμματισμούΠροσαρμόσιμης Μνήμης (Adaptive Memory Programming) ο οποίος ενσωματώνει ευφυείς μεθόδους καιμηχανισμούς τόσο για την παραγωγή εφικτών λύσεων όσο και για την αποτελεσματική αναζήτηση τουχώρου των λύσεων. Η συγκριτική μέτρηση επιδόσεων του αλγορίθμου με άλλες μεθόδους της
Cited by 0Open access
Estèle Glize · theses.fr (ABES) · 2019
De nombreux problèmes réels comportent plusieurs critères à considérer simultanément. À titre d’exemple, un trajet peut se caractériser par son coût, son impact écologique, son temps de parcours ou encore sa longueur. Les problèmes mathématiques résultants relèvent de l’optimisation multi-objectif. En général, il n’existe pas de solution réalisable optimisant tous les objectifs. Ainsi, les décideurs veulent analyser le compromis entre tous les objectifs pour pouvoir choisir la solution la plus adéquate. Par conséquent, résoudre un problème multi-objectif consiste à trouver un sous-ensemble de points, dits non dominés, dans l’espace des objectifs. Ces points sont associés à des solutions réalisables pour lesquelles il n’est pas possible d’améliorer un objectif sans en détériorer un autre. Peu de méthodes exactes existent dans la littérature pour traiter les problèmes combinatoires multi-objectif NP-difficiles, en particulier ceux dont la variante mono-objectif est déjà NP-difficile. Cette thèse s’inscrit dans l’étude des méthodes exactes pour de tels problèmes multi-objectif et utilise la classe des problèmes de tournées de véhicules bi-objectif comme référence. Les travaux se concentrent sur une approche basée sur la génération de colonnes et qui vise à énumérer efficacement l’ensemble des points non dominés de ces problèmes. Nous proposons notamment d’analyser diverses techniques d’exploration de l’espace des objectifs et de les améliorer grâce à des propriétés structurelles. Afin d’en démontrer la généricité, l’approche est appliquée à plusieurs variantes bi-objectif des problèmes de tournées de véhicules : le problème de tournées de véhicules avec fenêtre de temps, le problème de tournées couvrantes et le problème de course d’orientation par équipes avec fenêtre de temps. Les multiples tests numériques soulignent l’efficacité de la méthode proposée.
Cited by 0Open access
Ángel A. Juan, Javier Faulín, Elena Pérez Bernabeu et al. · Lecture notes in business information processing · 2013
Cited by 13Open access
Lei Jia · 2015
Vehicle routing problem is a combinatorial problem, which has a practical engineering value in logistics distribution. In this paper, we intend to propose a path planning for vehicle model based on a particle swarm optimization algorithm, which aiming to achieve the optimization of path planning. The particle swarm optimization algorithm is a new swarm intelligent optimization method, which is applied to the vehicle routing problem, constructed by the particle representation methods for vehicle routing problem. The results show that the particle swarm optimization algorithm can obtain the solution for the vehicle routing problem quickly and effectively. It is a good method for solving the vehicle routing problem.
Cited by 5
Lucas Martín Prado, Tobías Grandi, Carlos A. Casanova · 2024
Solving dynamic optimization problems is always a challenging task. For this purpose, heuristic and metaheuristic methods are the preferred ones, especially in the context of real-time decision making. In this sense, it is necessary to have evaluation mechanisms for such methods, in order to assist in the selection of one of them to be applied in a particular reality. In this paper we propose metrics for the evaluation of methods that solve real-time dynamic problems that do not require complete knowledge of the search space. These metrics can be used to compare methods quantitatively in various ways. Besides, the application of the proposal on variants of Ant Systems in a classical combinatorial optimization problem such as the Vehicule Routing Problem (VRP) is studied.
Cited by 0
Hongmei Xu · 2012
Research vehicle routing problem.Logistics distribution requires the timely delivery and low transportation cost,and the vehicle routing is the key to solve the logistics distribution problem.The traditional optimization method has the defects of low searching efficiency,time-consuming and high cost.To improve the vehicle route optimization efficiency and reduce logistics cost,this paper proposed a hybrid algorithm for vehicle routing optimization method.Firstly,vehicle routing mathematical model was established,and then genetic algorithm was used to find a feasible solution quickly.Then the solution was converted into the initial pheromone of ant colony algorithm.Finally,ant colony algorithm was used to find the optimal solution from the feasible path.The simulation results show that,compared with other optimization methods,the proposed method can improve vehicle routing optimization and reduce the cost of logistics distribution effectively.
Cited by 3
Ade O. Fajemisin, David Rey, Xavier Brusset · SSRN Electronic Journal · 2024
Cited by 0Open access
Sylvain Lichau · 2026
Les drones constituent un complément prometteur pour la logistique de livraison. Ils présentent des caractéristiques fondamentalement différentes de celles des véhicules classiques : des coûts d’utilisation plus faibles et des vitesses plus élevées, au détriment d’une autonomie et d’une capacité réduite. Pour les applications où ces contraintes sont acceptables, les drones peuvent remplacer entièrement les véhicules de livraison. Cependant, dans la plupart des cas, il est nécessaire de combiner stratégiquement ces types de véhicules complémentaires afin de tirer le meilleur parti de leurs atouts opérationnels respectifs. Cette thèse propose principalement des méthodes mathématiques d’optimisation exactes pour les problèmes de routage avec drones. Le premier chapitre propose une revue de littérature consacrée aux problèmes de routage avec drones dans le domaine de la recherche opérationnelle, en mettant l’accent sur les méthodes d’optimisation exactes. Nous soulignons la diversité des problèmes abordés par les chercheurs ainsi que la nécessité d’augmenter la taille des instances résolues à l’optimale. Le deuxième chapitre rappelle brièvement les concepts de programmation mathématique nécessaires à la compréhension des algorithmes de «branch-cut-and-price». Nous décrivons également l’algorithme utilisé dans cette thèse, en détaillant ses composantes avancées ainsi que l’algorithme de «labeling» employé pour résoudre les sous-problèmes. Le troisième chapitre traite du «Two-Echelon Vehicle Routing Problem with Drones». Nous proposons un nouveau modèle de partitionnement d’ensembles, dans lequel les chemins partiels correspondant aux mouvements des drones sont énumérés à l’aide d’un programme dynamique. Nous présentons également une adaptation des «rounded capacity cuts», spécialement conçue pour résoudre ce problème. Par ailleurs, nous développons une heuristique basée sur l’algorithme exact. Les expériences numériques montrent que l’algorithme exact augmente considérablement la taille des instances résolues de manière optimale. Pour évaluer le modèle, l’algorithme est ensuite étendu pour traiter le «Park-and-Loop Routing Problem». Le quatrième chapitre traite du «Truck-based Drone Delivery Routing Problem with Time Windows». Nous développons un algorithme exact de branch-cut-and-price ainsi qu’un algorithme de «labeling» pour résoudre le sous-problème. Nous comparons deux modèles de sous-problème alternatifs définis sur des graphes distincts et montrons qu’aucun des deux ne domine l’autre : le meilleur choix dépend des caractéristiques de l’instance considérée. Les expériences numériques démontrent l’efficacité des approches proposées. Nous introduisons également de nouvelles instances plus complexes, où la capacité des drones est augmentée. Le cinquième chapitre étudie une variante du «Vehicle Routing Problem with Time Windows», qui intègre deux caractéristiques pertinentes sur le plan opérationnel : des heures de départ flexibles depuis le dépôt et des limites strictes sur la durée des routes. Bien que plus générique, ce problème peut s’apparenter à un problème de routage de drones dans lequel la portée est limitée par la durée du trajet. Nous développons un algorithme de branch-cut-and-price, dont la composante principale est un algorithme de «labeling» bidirectionnel résolvant le sous-problème. Nous montrons également comment traiter le problème connexe de minimisation de la durée totale du trajet. Les expériences numériques confirment les performances de l’algorithme.
Cited by 0Open access
Cai Li, Jianping Jia, Juan Lei · International Journal of Online and Biomedical Engineering (iJOE) · 2015
The development of autonomous unmanned vehicles is of high interest to many organizations around the world and path planning is the key point of the navigation for the autonomous unmanned vehicle. Intelligent algorithms have been applied in this field and an essential aspect of unmanned vehicles autonomy is the ability for automatic path planning. In this paper, particle swarm optimization algorithm as one of new swarm intelligent optimization methods is introduced into a path planning for autonomous vehicle, which is constructed of a particle representation methods for vehicle routing problem with fast convergence speed. The results show that the particle swarm optimization algorithm can obtain the solution of the vehicle routing problem quickly and effectively. It is a good method for solving the vehicle routing problem.
Cited by 3Open access
K. M. Dhanya, S. Kanmani · International Journal of Intelligent Systems and Applications · 2017
During past decades, several Meta-Heuristics were considered by researchers to solve Dynamic Vehicle Routing Problem.In this paper, Ant Colony Optimization integrated with Hybrid Immigrant Schemes methods are proposed for solving Dynamic Vehicle Routing Problem. Ant Colony Optimization with hybrid immigrant schemes methods namely HIACO-I, HIACO-II and HIACO-III focused on establishing the proper balance between intensification and diversification. The performance evaluation of the algorithms in which Random Immigrants and Elitism based Immigrants were hybridized in different proportions and added to Ant Colony Optimization algorithm showed that they had produced better results in many dynamic test cases generated from three Vehicle Routing Problem instances.
Cited by 4Open access