Hybrid optimization approach based on gravitational analogy and particle swarm for solving single vehicle pickup and delivery problem
The Pickup and delivery problem (PDP) with single vehicle (SPDP) with capacity constraints is considered. The problem requires constructing the shortest cyclic route for delivery of homogeneous cargo (e.g. passengers) from all the producers to specific customers with one capacitated vehicle. A heuristic procedure, based on the gravitational analogy, for finding approximate solution is developed. A particle swarm optimization procedure is combined with the developed heuristics. Efficiency of developed procedures is empirically analyzed and compared with each other.
Download file
Counter downloads: 150
Keywords
vehicle routing, optimization, metaheuristics, транспортная маршрутизация, оптимизация, метаэвристикиAuthors
| Name | Organization | |
| Gindullin Ramiz V. | Bashkir State University | ramizgindullin@gmail.com |
References
Danzig, G. & Ramser, J. (1959) The Truck Dispatching Problem. Management Science. 6(6). pp. 80-91. DOI: 10.1287/mnsc.6.1.80
NEO Research Group. (n.d.) Vehicle Routing Problem. [Online] Available from: http://neo.lcc.uma.es/vrp/ (Accessed: 13th February 2018).
Parragh, S., Doerner, K. & Hartl, R. (2008) A survey on pickup and delivery problems. Part II: Transportations between customers and depot. Journal fur Betriebswirtschaft. 58. pp. 21-51.
Ruland, K.S. & Rodin, E.Y. (1997) The pickup and delivery problem: Faces and branch-and-cut algorithm. Computers and Mathematics with Applications. 33(12). pp. 1-13. DOI: 10.1016/S0898-1221(97)00090-4
Renaud, J., Boctor, F.F. & Ouenniche, J. (2000) A heuristic for the pickup and delivery traveling salesman problem. Computers and Operations Research. 27(9). pp. 905-916. DOI: 10.1016/S0305-0548(99)00066-0
Renaud, J., Boctor, F.F. & Laporte, G. (2002) Perturbation heuristics for the pickup and delivery traveling salesman problem. Computers and Operations Research. 29(9). pp. 1129-1141. DOI: 10.1016/S0305-0548(00)00109-X
Shareef, H., Ibrahim, A.A. & Mutlag, A. H. (2015) Lightning search algorithm. Applied Soft Computing. 36. pp. 315-333. DOI: 10.1016/j.asoc.2015.07.028
El Majdouli, M.A. & El Imrani, A.A. (2015) Lightning inspired search algorithm: Introduction & application to the traveling salesman problem. 10th Int. Conf. on Intelligent Systems: Theories and Applications (SITA), Rabat. pp. 165-171. DOI: 10.1109/SITA.2015.7358401
Rostami, A.S., Mohanna, F., Keshavarz, H. & Hosseinabadi, A.A.R. (2015) Solving Multiple Traveling Salesman Problem using the Gravitational Emulation Local Search Algorithm. Applied Mathematics & Information Sciences. 2. pp. 699-709. DOI: 10.12785/amis/090218
Bronshtein, E.M., Gindullina, E.V. & Gindullin, R.V. (2017) Formalization of pickup and delivery problem. Vestnik Yuzhno-Ural'skogo universiteta. Seriya: Matematika. Mekhanika. Fizika. 9(1). pp. 13-21. DOI: 10.14529/mmph170102
MP-TESTDATA-The TSPLIB Symmetric Traveling Salesman Problem Instances. [Online] Available from: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/ (Accessed: 10th February 2019)
PDP-Algorithms. [Online] Available from: https://github.com/RamizGindullin/PDP-Algorithms (Accessed: 26th May 2020).
Hybrid optimization approach based on gravitational analogy and particle swarm for solving single vehicle pickup and delivery problem | Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitelnaja tehnika i informatika – Tomsk State University Journal of Control and Computer Science. 2020. № 52. DOI: 10.17223/19988605/52/6
Download full-text version
Counter downloads: 276