Open Access Open Access  Restricted Access Subscription or Fee Access

A Lexi-Search Algorithm for Double Traveling Salesman Problem with Multiple Stacks with LIFO

Dr.K. Sobhan Babu

Abstract


The double traveling salesman problem with multiple stacks is a variant of the pickup and delivery traveling salesman problem in which all pickups must be completed before any of the deliveries. In addition, items can be loaded on multiple stacks in the vehicle and each stack must obey the last-in-first-out policy. The problem consists in finding the shortest Hamiltonian cycles covering all pickup and delivery locations while ensuring the feasibility of the loading plan. We formulate the problem as two traveling salesman problems linked by infeasible path constraints. We also introduce several strengthening of these constraints which are used within a Lexi-Search algorithm.


Keywords


Traveling Salesman Problem, Pickup and Delivery, LIFO Loading, Lexi-Search.

Full Text:

PDF

References


N. Ascheuer. M. Fischetti , and M.Grotschel. A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks, 36:69- 79, 2000.

F. Bonomo, S.Mattia, and G.Oriolo. Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem. Technical Report 6, DEIS, Sapienza universita di Roma, Italy, 2010.

F. Carrabs, R. Cerulli, and J-F.Cordeau. An additive branch-and-bound algorithm for the pickup and delivery traveling salesman problem with LIFO or FIFO loading. INFOR, 45:223-238, 2007a

F. Carrabs, R.Cerulli, and M.G. Speranza. A branch-and-bound algorithm for the double TSP with two stacks. Technical Report 4, DMI, Universit di Salerno, Italy, http://www.dmi.jniksa.it/people/carrabs/www/,2010.

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

M. Casazza, A.Ceselli, and MlNunkesser. Efficient algorithms for the double TSP with multiple stacks. In Proceedings of 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW09), pages 7-10, Paris, 2009.

J. -F. Corndeau, M.Lori. G.Laporte, and J.J. Salazar-Gonzalez. Branch-and-cut for the pickup and delivery traveling salesman problem with LIFO loading. Networks 55:46-59, 2010.

J. -F.Cordeau, G.Laporte, J.-Y. Potvin, and M.W.P. Savelsbergh. Transportation on demand. In C.Barnhart and G.Laporte, editors, Transportation, Handbooks in Operations Research and management science 14, pages 429-466. Elservier, Amsterdam, 2007.

J. -F. Cote,M.Gendreau, and J. –Y. Potvin. Large neighborhood search for the single vehicle pickup and delivery problem with multiple loading stacks. Technical Report CIRRELT- 2009-47, University of Montreal, 2009.

A. Felip, M.T.Ortuno, and G.Tirado. The double traveling salesman problem with multiple stacks: A variable neighborhood search approach. Computers & Operations Research, 36:2983-2993, 2009a.

A. Felipe, M.T.Ortuno, and G.Tirado. New neighborhood structures for the double traveling salesman problem with multiple stacks. TOP, 17:190-213, 2009b.

P. Hansen, A. Hertz, and j.Kuplinsky. Bounded vertex colorings of graphs. Discrete Mathematics, 111:305-312, 1993

M. Iori and S.Martello. Routing, problems with loading constrants TOP, 18:4-27, 2010.

J. Kelley. Critical path planning and scheduling: Mathematical basis. Operations Research, 9:296-320, 1961.

R. M.Lusby, J.Larsen, M.Ehrgoot, and d.Ryan, an exact method for the double TSP with multiple stacks. International Transactions on Operations Research, 17:637-652, 2010.

H. L. Petersen, C. Archentti, and M.G.Speranza. Exact solutions to the double travelling salesman problem with multiple stacks. Networks, 2010. To appear.

H. L.Peterson and O.B.G. Madsen. The double travelling salesman problem with multiple stacks. European Journal of Operational Research, 198:139-147, 2009.

S. Toulouse. Approximability of the multiple stack TSP. Electronic Notes in Discrete Mathematics, 336:813-820, 2010.

S. Toulouse and R.Wolfler Calvo. On the complexity of the multiple stack TSP, kSTSP. Lecture Notes in Computer Science, Theory and Applications of Models of Computation, 5532/2009:360-369, 2009.


Refbacks

  • There are currently no refbacks.