A hybrid particle swarm optimization for the selective pickup and delivery problem with transfers

Autor: Marie-Ange Manier, Zhihao Peng, Zaher Al Chami, Hervé Manier
Přispěvatelé: Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS)
Rok vydání: 2019
Předmět:
0209 industrial biotechnology
Mathematical optimization
Profit (real property)
Linear programming
Computer science
Transportation
[INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE]
02 engineering and technology
[INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing
Set (abstract data type)
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR]
020901 industrial engineering & automation
Artificial Intelligence
Vehicle routing problem
0202 electrical engineering
electronic engineering
information engineering
Pickup
Electrical and Electronic Engineering
Constraint (mathematics)
Metaheuristic
Particle swarm optimization
[INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation
[INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA]
Control and Systems Engineering
Selective problem
[INFO.INFO-ET]Computer Science [cs]/Emerging Technologies [cs.ET]
020201 artificial intelligence & image processing
[INFO.INFO-DC]Computer Science [cs]/Distributed
Parallel
and Cluster Computing [cs.DC]
Transfers
Integer (computer science)
Zdroj: Engineering Applications of Artificial Intelligence
Engineering Applications of Artificial Intelligence, Elsevier, 2019, 85, pp.99-111. ⟨10.1016/j.engappai.2019.06.006⟩
ISSN: 0952-1976
DOI: 10.1016/j.engappai.2019.06.006
Popis: International audience; In pickup and delivery problems, all the demands should be transported from pickup points (suppliers) to delivery points (customers) by vehicles while respecting a set of constraints. Honoring all demands is sometimes impossible when taking all the constraints into account. Therefore, the selective aspect is added to relax the constraint that all the demands should be satisfied. This paper studies a variant called the selective pickup and delivery problem with transfers (SPDPT). The transfers mean that some demands can be transferred from one vehicle to another one, which gives a chance to find more solutions. A mixed integer linear program is firstly proposed to describe the studied problem. Two objectives have been considered in the paper, maximizing the profit and minimizing the distance. The model is then validated on new generated instances. Due to the complexity of the problem, large instances could not be solved to optimality in a reasonable time. As an alternative, a new metaheuristic based on a hybrid particle swarm optimization is developed to tackle this bi-objective problem. The results show that this proposed method is efficient and competitive.
Databáze: OpenAIRE
Externí odkaz: