article

The pickup and delivery traveling salesman problem with first-in-first-out loading

Authors:

Güneş Erdoğan,

Jean-François Cordeau,

Gilbert LaporteAuthors Info & Claims

Computers and Operations Research, Volume 36, Issue 6

Pages 1800 - 1808

https://doi.org/10.1016/j.cor.2008.05.005

Published: 01 June 2009 Publication History

Abstract

This paper addresses a variation of the traveling salesman problem with pickup and delivery in which loading and unloading operations have to be executed in a first-in-first-out fashion. It provides an integer programming formulation of the problem. It also describes five operators for improving a feasible solution, and two heuristics that utilize these operators: a probabilistic tabu search algorithm, and an iterated local search algorithm. The heuristics are evaluated on data adapted from TSPLIB instances.

References

[1]

Cordeau, J.-F., Laporte, G., Potvin, J.-Y. and Savelsbergh, M.W.P., Transportation on demand. In: Barnhart, C., Laporte, G. (Eds.), Transportation, handbooks in operations research and management science, vol. 14. Elsevier, Amsterdam. pp. 429-466.

[2]

Hauptmeier D, Krumke SO, Rambau J, Wirth H-C. Euler is standing in line: dial-a-ride problems with fifo-precedence-constraints, Preprint SC 99-06, Konrad-Zuse-Zentrum fur Informationstechnik Berlin, 1999.

[3]

Levitin, G. and Abezgaouzb, R., Optimal routing of multiple-load AGV subject to LIFO loading constraints. Computers & Operations Research. v30. 397-410.

Digital Library

[4]

Kalantari, B., Hill, A.V. and Arora, S.R., An algorithm for the traveling salesman problem with pickup and delivery requests. European Journal of Operational Research. v22. 377-386.

[5]

Fischetti, M. and Toth, P., An additive bounding procedure for combinatorial optimization problems. Operations Research. v37. 319-328.

[6]

Savelsbergh, M.W.P., An efficient implementation of local search algorithms for constrained routing problems. European Journal of Operational Research. v47. 75-85.

[7]

Healy, P. and Moll, R., A new extension of local search applied to the dial-a-ride problem. European Journal of Operational Research. v83. 83-104.

[8]

Ruland, K.S. and Rodin, E.Y., The pickup and delivery problem: faces and branch-and-cut algorithm. Computers and Mathematics with Applications. v33. 1-13.

[9]

Renaud, J., Boctor, F.F. and Ouenniche, J., A heuristic for the pickup and delivery traveling salesman problem. Computers & Operations Research. v27. 905-916.

Digital Library

[10]

Renaud, J., Boctor, F.F. and Laporte, G., Perturbation heuristics for the pickup and delivery traveling salesman problem. Computers & Operations Research. v29. 1129-1141.

Digital Library

[11]

Dumitrescu I, Ropke S, Cordeau J-F, Laporte G. The traveling salesman problem with pickup and deliveries: polyhedral results and branch-and-cut algorithm. Technical report CIRRELT-2008-01, 2007.

[12]

Berbeglia, G., Cordeau, J.-F., Gribkovskaia, I. and Laporte, G., Static pickup and delivery problems: a classification scheme and survey. TOP. v15. 1-31.

[13]

Cordeau, J.-F., Laporte, G. and Ropke, S., Recent models and algorithms for one-to-one pickup and delivery problems. In: Golden, B.L., Raghavan, S., Wasil, E.A. (Eds.), Vehicle routing: latest advances and challenges, Kluwer, Boston.

[14]

Ladany, S.P. and Mehrez, A., Optimal routing of a single vehicle with loading and unloading constraints. Transportation Planning and Technology. v8. 301-306.

[15]

Pacheco JA. Problemas de rutas con ventanas de tiempo. PhD thesis, Department of Estadistica and Investigation Operativa, Universitad Complutense de Madrid, 1994.

[16]

Pacheco, J.A., Problemas de rutas con carga y descarga en sistemas LIFO: solutiones exactas. Estudios de Economia Aplicada. v3. 69-86.

[17]

Cassani L. Algoritmi euristici per il TSP with rear-loading. Degree thesis, Universití di Milano, Italy, 2004 {http://www.crema.unimi.it/~righini/Papers/Cassani.pdf}.

[18]

Ficarelli F. Mathematical programming algorithms for the TSP with rear-loading. Degree thesis, Universití di Milano, Italy, 2005 {http://optlab.dti.unimi.it/Papers/Ficarelli.pdf}.

[19]

Carrabs F, Cerulli R, Cordeau J-F. An additive branch-and-bound algorithm for the pickup and delivery traveling salesman problem with LIFO loading. Technical report CIRRELT-2007-12, 2007.

[20]

Carrabs, F., Cordeau, J.-F. and Laporte, G., Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading. INFORMS Journal on Computing. v19. 618-632.

[21]

Wong, R.T., Integer programming formulations of the traveling salesman problem. In: Proceedings of the IEEE International Conference of Circuits and Computers, pp. 149-152.

[22]

Gendreau, M., Laporte, G. and Vigo, D., Heuristics for the traveling salesman problem with pickup and delivery. Computers & Operations Research. v26. 699-714.

Digital Library

[23]

Gendreau, M., Hertz, A. and Laporte, G., New insertion and postoptimization procedures for the traveling salesman problem. Operations Research. v40. 1086-1094.

Digital Library

[24]

Rosenkrantz, D.J., Stearns, R.E. and Lewis II, P.M., An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing. v6. 563-581.

[25]

Reinelt, G., TSPLIB-a traveling salesman problem library. ORSA Journal on Computing. v3. 376-384.

[26]

Cordeau J-F, Iori M, Laporte G, Salazar González J-J. A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading. Networks, 2008, in press.

Digital Library

Cited By

Kong DMa YCao ZYu TXiao J(2024)Efficient Neural Collaborative Search for Pickup and Delivery ProblemsIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.345085046:12(11019-11034)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1109/TPAMI.2024.3450850
Pacheco TMartinelli RSubramanian AToffolo TVidal T(2023)Exponential-Size Neighborhoods for the Pickup-and-Delivery Traveling Salesman ProblemTransportation Science10.1287/trsc.2022.117657:2(463-481)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1287/trsc.2022.1176
Ho SSzeto W(2016)GRASP with path relinking for the selective pickup and delivery problemExpert Systems with Applications: An International Journal10.1016/j.eswa.2015.12.01551:C(14-25)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.eswa.2015.12.015
Show More Cited By

Recommendations

A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem

We address in this paper the one-commodity pickup-and-delivery traveling salesman problem, which is characterized by a set of customers, each of them supplying (pickup customer) or demanding (delivery customer) a given amount of a single product. The ...
Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading

This paper introduces a branch-and-cut algorithm for a variant of the pickup and delivery traveling salesman problem in which pickups and deliveries must obey the first-in-first-out policy. We propose a new mathematical formulation of the problem and ...
Metaheuristics for the traveling salesman problem with pickups, deliveries and handling costs

This paper studies the Traveling Salesman Problem with Pickups, Deliveries, and Handling Costs. The subproblem of minimizing the handling cost for a fixed route is analyzed in detail. It is solved by means of an exact dynamic programming algorithm with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Operations Research

Computers and Operations Research Volume 36, Issue 6

June, 2009

402 pages

ISSN:0305-0548

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2008.

Publisher

Elsevier Science Ltd.

United Kingdom

Publication History

Published: 01 June 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kong DMa YCao ZYu TXiao J(2024)Efficient Neural Collaborative Search for Pickup and Delivery ProblemsIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.345085046:12(11019-11034)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1109/TPAMI.2024.3450850
Pacheco TMartinelli RSubramanian AToffolo TVidal T(2023)Exponential-Size Neighborhoods for the Pickup-and-Delivery Traveling Salesman ProblemTransportation Science10.1287/trsc.2022.117657:2(463-481)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1287/trsc.2022.1176
Ho SSzeto W(2016)GRASP with path relinking for the selective pickup and delivery problemExpert Systems with Applications: An International Journal10.1016/j.eswa.2015.12.01551:C(14-25)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1016/j.eswa.2015.12.015
Novaes ABez EBurin PAragão D(2015)Dynamic milk-run OEM operations in over-congested traffic conditionsComputers and Industrial Engineering10.1016/j.cie.2015.07.01088:C(326-340)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.cie.2015.07.010
Wei LQin HZhu WWan L(2015)A study of perturbation operators for the pickup and delivery traveling salesman problem with LIFO or FIFO loadingJournal of Heuristics10.1007/s10732-015-9293-221:5(617-639)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/s10732-015-9293-2
Pollaris HBraekers KCaris AJanssens GLimbourg S(2015)Vehicle routing problems with loading constraintsOR Spectrum10.1007/s00291-014-0386-337:2(297-330)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s00291-014-0386-3
Ruan QZhang ZMiao LShen H(2013)A hybrid approach for the vehicle routing problem with three-dimensional loading constraintsComputers and Operations Research10.1016/j.cor.2011.11.01340:6(1579-1589)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1016/j.cor.2011.11.013
Carrabs FCerulli RSperanza M(2013)A branch-and-bound algorithm for the double travelling salesman problem with two stacksNetworks10.1002/net.2146861:1(58-75)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1002/net.21468
Erdogan GBattarra MLaporte GVigo D(2012)Metaheuristics for the traveling salesman problem with pickups, deliveries and handling costsComputers and Operations Research10.1016/j.cor.2011.07.01339:5(1074-1086)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.cor.2011.07.013
Côté JArchetti CSperanza MGendreau MPotvin J(2012)A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacksNetworks10.1002/net.2145960:4(212-226)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1002/net.21459
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents