A lexicographic minimax approach to the vehicle routing problem with load balancing

Autor: Fabien Tricoire, Olivier Péton, Fabien Lehuédé
Přispěvatelé: Systèmes Logistiques et de Production (SLP ), Laboratoire des Sciences du Numérique de Nantes (LS2N), Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Département Automatique, Productique et Informatique (IMT Atlantique - DAPI), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institute for production and logistics management, Johannes Kepler Universität Linz (JKU), Universität Wien, Université de Nantes - Faculté des Sciences et des Techniques, Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - Faculté des Sciences et des Techniques, Johannes Kepler Universität Linz
Jazyk: angličtina
Rok vydání: 2020
Předmět:
large neighborhood search
workload balancing
Mathematical optimization
Information Systems and Management
502017 Logistik
General Computer Science
Computer science
Heuristic (computer science)
0211 other engineering and technologies
02 engineering and technology
Management Science and Operations Research
Industrial and Manufacturing Engineering
0502 economics and business
Vehicle routing problem
Local search (optimization)
multi-directional local search
Duration (project management)
050210 logistics & transportation
021103 operations research
business.industry
Heuristic
05 social sciences
equity in route duration
Workload
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Minimax
Lexicographical order
Modeling and Simulation
502017 Logistics
vehicle routing problem
business
Social choice theory
Zdroj: European Journal of Operational Research
European Journal of Operational Research, Elsevier, 2020, 282 (1), pp.129-147. ⟨10.1016/j.ejor.2019.09.010⟩
ISSN: 0377-2217
DOI: 10.1016/j.ejor.2019.09.010⟩
Popis: International audience; Vehicle routing problems generally aim at designing routes that minimize transportation costs. However, in practical settings, many companies also pay attention at how the workload is distributed among its drivers. Accordingly, two main approaches for balancing the workload have been proposed in the literature. They are based on minimizing the duration of the longest route, or the difference between the longest and the shortest routes, respectively. Recently, it has been shown on several occasions that both approaches have some flaws. In order to model equity we investigate the lexicographic minimax approach, which is rooted in social choice theory. We define the leximax vehicle routing problem which considers the bi-objective optimization of transportation costs and of workload balancing. This problem is solved by a heuristic based on the multi-directional local search framework. It involves dedicated large neighborhood search operators. Several LNS operators are proposed and compared in experimentations.
Databáze: OpenAIRE
Externí odkaz: