Heuristics for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem

References

• Anily S., Bramel J. Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries. Naval Res. Logist. (1999) 46:654–670Crossref, Google Scholar
• Anily S., Hassin R. The swapping problem. Networks (1992) 22:419–433Crossref, Google Scholar
• Anily S., Mosheiov G. The traveling salesman problem with delivery and backhauls. Oper. Res. Lett. (1994) 16:11–18Crossref, Google Scholar
• Anily S., Gendreau M., Laporte G. The swapping problem on a line. SIAM J. Comput. (1999) 29:327–335Crossref, Google Scholar
• Baldacci R., Mingozzi A., Hadjiconstantinou E. An exact algorithm for the traveling salesman problem with mixed delivery and collection constraints. Networks (2003) 42:26–41Crossref, Google Scholar
• Bianco L., Mingozzi A., Riccardelli S., Spadoni M. Exact and heuristic procedures for the traveling salesman problem with precedence constraints, based on dynamic programming. INFOR (1994) 32:19–32Google Scholar
• Chalasani P., Motwani R. Approximating capacitated routing and delivery problems. SIAM J. Comput. (1999) 28:2133–2149Crossref, Google Scholar
• Fischetti M., Lodi A. Local branching. Math. Programming (2003) 98:23–47Crossref, Google Scholar
• Frederickson G. N., Hecht M. S., Kim C. E. Approximation algorithms for some routing problems. SIAM J. Comput. (1978) 7:178–193Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman and Company, San Francisco, CA) Google Scholar
• Gendreau M., Hertz A., Laporte G. An approximation algorithm for the traveling salesman problem with backhauls. Oper. Res. (1997) 45:639–641Link, Google Scholar
• Gendreau M., Laporte G., Vigo D. Heuristics for the traveling salesman problem with pickup and delivery. Comput. Oper. Res. (1999) 26:699–714Crossref, Google Scholar
• Guan D. J. Routing a vehicle of capacity greater than one. Discrete Appl. Math. (1998) 81:41–57Crossref, Google Scholar
• Healy P., Moll R. A new extension of local search applied to the dial-a-ride problem. Eur. J. Oper. Res. (1995) 83:83–104Crossref, Google Scholar
• Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. (2000) 12:106–130Crossref, Google Scholar
• 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 Appl. Math. (2004) 144Google Scholar
• Johnson D. S., McGeoch L. A., Aarts E. J. L., Lenstra J. K. The traveling salesman problem: A case study in local optimization. Local Search in Combinatorial Optimization (1997) (John Wiley and Sons, Chichester, U.K.) Google Scholar
• Kalantari B., Hill A. V., Arora S. R. An algorithm for the traveling salesman problem with pickup and delivery customers. Eur. J. Oper. Res. (1985) 22:377–386Crossref, Google Scholar
• Kubo M., Kasugai H. Heuristic algorithms for the single vehicle dial-a-ride problem. J. Oper. Res. Soc. Japan (1990) 33:354–364Google Scholar
• Lin S. Computer solutions of the traveling salesman problem. Bell System Tech. J. (1965) 44:2245–2269Crossref, Google Scholar
• Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling salesman problem. Oper. Res. (1973) 21:498–516Link, Google Scholar
• Mosheiov G. The travelling salesman problem with pick-up and delivery. Eur. J. Oper. Res. (1994) 79:299–310Crossref, Google Scholar
• Psaraftis H. Analysis of an O(n2) heuristic for the single vehicle many-to-many Euclidean dial-a-ride problem. Transportation Res. (1983) 17:133–145Crossref, Google Scholar
• Renaud J., Boctor F. F., Laporte G. Perturbation heuristics for the pickup and delivery traveling salesman problem. Comput. Oper. Res. (2002) 29:1129–1141Crossref, Google Scholar
• Renaud J., Boctor F. F., Ouenniche I. A heuristic for the pickup and delivery traveling salesman problem. Comput. Oper. Res. (2000) 27:905–916Crossref, Google Scholar
• Savelsbergh M. W. P., Sol M. The general pickup and delivery problem. Transportation Sci. (1995) 29:17–29Link, Google Scholar