Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints.

*(English)*Zbl 1253.90190Summary: We extend the traveling salesman problem with pickup and delivery and LIFO loading (TSPPDL) by considering two additional factors, namely the use of multiple vehicles and a limitation on the total distance that a vehicle can travel; both of these factors occur commonly in practice. We call the resultant problem the multiple pickup and delivery traveling salesman problem with LIFO loading and distance constraints (MTSPPD-LD). This paper presents a thorough preliminary investigation of the MTSPPD-LD. We propose six new neighborhood operators for the problem that can be used in search heuristics or meta-heuristics. We also devise a two-stage approach for solving the problem, where the first stage focuses on minimizing the number of vehicles required and the second stage minimizes the total travel distance. We consider two possible approaches for the first stage (simulated annealing and ejection pool) and two for the second stage (variable neighborhood search and probabilistic tabu search). Our computational results serve as benchmarks for future researchers on the problem.

##### Keywords:

traveling salesman; pickup and delivery; last-in-first-out loading; distance constraint; metaheuristic##### Software:

TSPLIB
PDF
BibTeX
XML
Cite

\textit{B. Cheang} et al., Eur. J. Oper. Res. 223, No. 1, 60--75 (2012; Zbl 1253.90190)

Full Text:
DOI

##### References:

[1] | Ahuja, R.K.; Orlin, J.B.; Pallottino, S.; Scaparra, M.P.; Scutellà, M.G., A multi-exchange heuristic for the single-source capacitated facility location problem, Management science, 50, 6, 749-760, (2004) · Zbl 1232.90257 |

[2] | Ahuja, R.K.; Orlin, J.B.; Sharma, D., Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem, Mathematical programming, 91, 1, 71-97, (2001) · Zbl 1051.90019 |

[3] | Alba, M.A., Cordeau, J.-F., Dell’Amico, M., Iori, M., in press. A branch-and-cut algorithm for the double traveling salesman problem with multiple stacks. INFORMS Journal on Computing. |

[4] | Bent, R.; Van Hentenryck, P., A two-stage hybrid local search for the vehicle routing problem with time windows, Transportation science, 38, 4, 515-530, (2004) |

[5] | Bent, R.; Van Hentenryck, P., A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows, Computers and operations research, 33, 4, 875-893, (2006) · Zbl 1079.90591 |

[6] | Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, part I: route construction and local search algorithms, Transportation science, 39, 1, 104-118, (2005) |

[7] | Carrabs, F.; Cerulli, R.; Cordeau, J.-F., An additive branch-and-bound algorithm for the pickup and delivery traveling salesman problem with LIFO or FIFO loading, INFOR: information systems and operational research, 45, 4, 223-238, (2007) |

[8] | Carrabs, F., Cerulli, R., Grazia Speranza, M., in press. A branch-and-bound algorithm for the double travelling salesman problem with two stacks. Networks. · Zbl 1269.90007 |

[9] | Carrabs, F.; Cordeau, J.-F.; Laporte, G., Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading, INFORMS journal on computing, 19, 4, 618-632, (2007) · Zbl 1241.90103 |

[10] | Cassani, L., Righini, G., 2004. Heuristic algorithms for the TSP with rear-loading. In: 35th Annual Conference of the Italian Operational Research Society (AIRO XXXV). Lecce, Italy. |

[11] | 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, 55, 1, 46-59, (2010) · Zbl 1206.90137 |

[12] | Côté, J.-F., Gendreau, M., Potvin, J.-Y., 2009. Large Neighborhood Search for the Single Vehicle Pickup and Delivery Problem with Multiple Loading Stacks. Working paper CIRRELT-2009-47. |

[13] | Dumitrescu, I.; Ropke, S.; Cordeau, J.-F.; Laporte, G., The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm, Mathematical programming, 121, 2, 269-305, (2009) · Zbl 1184.90108 |

[14] | Erdoğan, G.; Cordeau, J.-F.; Laporte, G., The pickup and delivery traveling salesman problem with first-in-first-out loading, Computers and operations research, 36, 6, 1800-1808, (2009) · Zbl 1179.90280 |

[15] | Erera, A.L.; Morales, J.C.; Savelsbergh, M., The vehicle routing problem with stochastic demand and duration constraints, Transportation science, 44, 4, 474-492, (2010) |

[16] | Felipe, A.; Ortuño, M.T.; Tirado, G., The double traveling salesman problem with multiple stacks: a variable neighborhood search approach, Computers and operations research, 36, 11, 2983-2993, (2009) · Zbl 1162.90353 |

[17] | Felipe, A.; Ortuño, M.T.; Tirado, G., New neighborhood structures for the double traveling salesman problem with multiple stacks, Top, 17, 1, 190-213, (2009) · Zbl 1170.90464 |

[18] | Felipe, A.; Ortuño, M.T.; Tirado, G., Using intermediate infeasible solutions to approach vehicle routing problems with precedence and loading constraints, European journal of operational research, 211, 1, 66-75, (2011) · Zbl 1218.90037 |

[19] | Frangioni, A.; Necciari, E.; Scutellà, M., A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems, Journal of combinatorial optimization, 8, 2, 195-220, (2004) · Zbl 1133.90337 |

[20] | Gao, X.; Lim, A.; Qin, H.; Zhu, W., Multiple pickup and delivery TSP with LIFO and distance constraints: a VNS approach, Lecture notes in computer science, 6704, 193-202, (2011) |

[21] | Healy, P.; Moll, R., A new extension of local search applied to the dial-a-ride problem, European journal of operational research, 83, 1, 83-104, (1995) · Zbl 0903.90135 |

[22] | Homberger, J.; Gehring, H., A two-phase hybrid metaheuristic for the vehicle routing problem with time windows, European journal of operational research, 162, 1, 220-238, (2005) · Zbl 1132.90378 |

[23] | Ibaraki, T.; Imahori, S.; Kubo, M.; Masuda, T.; Uno, T.; Yagiura, M., Effective local search algorithms for routing and scheduling problems with general time-window constraints, Transportation science, 39, 2, 206-232, (2005) |

[24] | Iori, M.; Martello, S., Routing problems with loading constraints, Top, 18, 1, 4-27, (2010) · Zbl 1279.90146 |

[25] | Kalantari, B.; Hill, A.V.; Arora, S.R., An algorithm for the traveling salesman problem with pickup and delivery customers, European journal of operational research, 22, 3, 377-386, (1985) · Zbl 0585.90084 |

[26] | Ladany, S.P.; Mehrez, A., Optimal routing of a single vehicle with loading and unloading constraints, Transportation planning and technology, 8, 4, 301-306, (1984) |

[27] | Laporte, G.; Nobert, Y.; Desrochers, M., Optimal routing under capacity and distance restrictions, Operations research, 33, 5, 1050-1073, (1985) · Zbl 0575.90039 |

[28] | Levitin, G.; Abezgaouz, R., Optimal routing of multiple-load AGV subject to LIFO loading constraints, Computer and operations research, 30, 3, 397-410, (2003) · Zbl 1029.90012 |

[29] | Li, C.-L.; Simchi-Levi, D.; Desrochers, M., On the distance constrained vehicle routing problem, Operations research, 40, 4, 790-799, (1992) · Zbl 0758.90028 |

[30] | Li, H.; Lim, A., Local search with annealing-like restarts to solve the VRPTW, European journal of operational research, 150, 1, 115-127, (2003) · Zbl 1023.90090 |

[31] | Li, Y.; Lim, A.; Oon, W.-C.; Qin, H.; Tu, D., The tree representation for the pickup and delivery traveling salesman problem with LIFO loading, European journal of operational research, 212, 3, 482-496, (2011) · Zbl 1237.90203 |

[32] | Lim, A.; Zhang, X., A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows, INFORMS journal on computing, 19, 3, 443-457, (2007) · Zbl 1241.90051 |

[33] | Lusby, R.M.; Larsen, J.; Ehrgott, M.; Ryan, D., An exact method for the double TSP with multiple stacks, International transactions in operational research, 17, 5, 637-652, (2010) · Zbl 1220.90109 |

[34] | Mladenović, N.; Hansen, P., Variable neighborhood search, Computers and operations research, 24, 11, 1097-1100, (1997) · Zbl 0889.90119 |

[35] | Nagata, Y.; Bräysy, O., A powerful route minimization heuristic for the vehicle routing problem with time windows, Operations research letters, 37, 5, 333-338, (2009) · Zbl 1173.90358 |

[36] | Nagy, G.; Salhi, S., Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries, European journal of operational research, 162, 1, 126-141, (2005) · Zbl 1132.90380 |

[37] | Pacheco, J.A., 1997. Metaheuristic based on a simulated annealing process for one vehicle pick-up and delivery problem in LIFO unloading systems. In: Proceedings of the Tenth Meeting of the Europen Chapter of Combinatorial Optimization (ECCO X). Tenerife, Spain. |

[38] | Petersen, H.L.; Archetti, C.; Speranza, M.; Grazia, S., Exact solutions to the double travelling salesman problem with multiple stacks, Networks, 56, 4, 229-243, (2010) · Zbl 1203.90181 |

[39] | Petersen, H.L.; Madsen, O.B.G., The double travelling salesman problem with multiple stacks – formulation and heuristic solution approaches, European journal of operational research, 198, 1, 139-147, (2009) · Zbl 1163.90816 |

[40] | Pisinger, D.; Ropke, S., A general heuristic for vehicle routing problems, Computers and operations research, 34, 8, 2403-2435, (2007) · Zbl 1144.90318 |

[41] | Reinelt, G., TSPLIB - traveling salesman problem library, ORSA journal on computing, 3, 4, 376-384, (1991) · Zbl 0775.90293 |

[42] | Renaud, J.; Boctor, F.F.; Laporte, G., Perturbation heuristics for the pickup and delivery traveling salesman problem, Computers and operations research, 29, 9, 1129-1141, (2002) · Zbl 0994.90110 |

[43] | Renaud, J.; Boctor, F.F.; Ouenniche, J., A heuristic for the pickup and delivery traveling salesman problem, Computers and operations research, 27, 10, 905-916, (2000) · Zbl 0957.90030 |

[44] | () |

[45] | Tricoire, F.; Doerner, K.F.; Hartl, R.F.; Iori, M., Heuristic and exact algorithms for the multi-pile vehicle routing problem, OR spectrum, 33, 4, 931-959, (2010) · Zbl 1229.90039 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.