Heuristic solution of the single vehicle pickup and delivery problem

Е. М. Бронштейн; R. V. Gindullin

Информационные технологии интеллектуальной поддержки принятия решений, Информационные технологии интеллектуальной поддержки принятия решений 2018

Е. М. Бронштейн, R. V. Gindullin

Изменена: 2018-06-20

Аннотация

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 from all the producers to specific customers with one capacitated vehicle. Such problem, for example, could be used for transporting passengers (like taxi station). Enumeration procedure for finding approximate solution is developed. Efficiency of developed procedure is empirically analysed and compared to the efficiency of exact methods. Quality of the solution and elapsed time of that heuristic with different numbers of iterations, which don’t improve solution’s length by using that procedure, is analysed.

Ключевые слова

single vehicle pickup; delivery problem; heuristic solution

Литература

1. Danzig G., Ramser J. The Truck Dispatching Problem // Management Science, 1959, Vol. 6, Issue 1, P. 80–91.

2. Vehicle Routing Problem, NEO Research Group. Available at: http://neo.lcc.uma.es/vrp/ (accessed February 13th, 2018).

3. Parragh S., Doerner K., Hartl R. A survey on pickup and delivery problems. Part II: Transportations between customers and depot // Journal fur Betriebswirtschaft, 2008, Issue 58, P.21-51.

4. Ruland K.S., Rodin E.Y. The pickup and delivery problem: Faces and branch-and-cut algorithm // Computers and Mathematics with Applications, Volume 33, Issue 12, June 1997, P. 1-13.

5. Renaud J., Boctor F.F., Ouenniche J. A heuristic for the pickup and delivery traveling salesman problem // Computers and Operations Research, V. 27, 2000, Issue 9, P. 905-916

6. Renaud J., Boctor F.F., Laporte G. Perturbation heuristics for the pickup and delivery traveling salesman problem // Computers and Operations Research, V. 29, 2002, Issue 9, P. 1129-1141

7. Dumas Y., Desrosiers J., Soumis F. The pickup and delivery problem with time windows. European Journal of Operation Research, V.54, Issue 1, 1991, P. 7–22

8. Furtadoa M., Munaria P., Morabito R. Pickup and delivery problem with time windows: a new compact two-index formulation // Technical Report. Production Engineering Department, Federal University of São Carlos, Rod. Washington Luís, km 235 – SP-310, São Carlos – SP – CEP: 13565-905 – Brazil, July, 2015. www.optimization-online.org/DB_HTML/2015/07/5022.html (accessed February 13th, 2018)

9. Hernández-Pérez H., Salazar-González J.J. A branch-and cut algorithm for the traveling salesman problem with pickup and delivery // Discrete Applied Mathematics, Volume 145, Issue 1, 2004, P. 126-139

10. Cordeau J.-F., Laporte G. The dial-a-ride problem: models and algorithms // Annals of Operations Research, Volume 153, Number 1, 2007, P. 29—46

11. Bronshtein E.M., Gindullina E.V., Gindullin R.V. Formalizatsii zadach pogruzki i dostavki // Vestnik Yuzhno-Ural'skogo universiteta. Seriya: Matematika. Mekhanika. Fizika., Tom 9, Nomer 1, 2017, C. 13–21 (Russian)

12. Burkard R.E., Cela E., Pardalos P.M., Pitsoulis L.S. The Quadratic Assignment Problem // Handbook of Combinatorial Optimization: Vol. 1-3, Springer US, 1999, P. 1713–1809

13. Glover F. Improved linear integer programming formulations of nonlinear integer problems // Management Science, 1975, Vol. 22, P. 455–460

14. Lawler E.L. The quadratic assignment problem // Management Science. Vol. 9. 1963. P. 586-599

15. Croes G.A. A Method for Solving Traveling-Salesman Problems // Operations Research, 1958, Issue 6, P.791-812

16. Lin S. Computer solutions of the traveling salesman problem. Bell System Technical Journal. Volume 44, Issue 10, P.2245-2269

17. Hooijenga D. Perturbation heuristics for the pickup and delivery traveling salesman problem [Internet] // Econometrie. 2015. Available from: http://hdl.handle.net/2105/30373

18. MP-TESTDATA - The TSPLIB Symmetric Traveling Salesman Problem Instances. Available at: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/ (accessed February 13th, 2018)