An Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading

REFERENCES

• Ahuja, R., Magnanti, T., Orlin, J. Network Flows. Prentice Hall, 1993.
   Google Scholar
• Camerini, P.M., Fratta, L., Maffioli, F. A note on finding optimum branchings. Networks, 9: 309–312, 1979.
   Web of Science ®Google Scholar
• Carpaneto, G., Fischetti, M., Toth, P. New lower bounds for the symmetric travelling salesman problem. Mathematical Programming (Series B), 45: 233–254, 1989.
   Web of Science ®Google Scholar
• 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: 618–632, 2007
   Web of Science ®Google Scholar
• Cassani, L. Algoritmi euristici per il TSP with rear-loading. qDegree Thesis, Universit di Milano, Italy. http://www.crema.unimi.it/~righini/Papers/Cassani.pdf, 2004.
   Google Scholar
• Chu, Y.J., Liu, T.H. On the shortest arborescence of a directed graph. Science Sinica, 14: 13961400, 1965.
   Google Scholar
• Cordeau, J.-F., lori, M., Laporte, G., Salazar-Gonzalez, J.-J. A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading. Networks, 2008. Forthcoming.
   Google Scholar
• Cordeau, J.-F., Laporte, G., Potvin, J.-Y., Savelsbergh, M.W.P. Transportation on demand. In Barnhart, C., Laporte, G. editors, Transportation, Handbooks in Operations Research and Management Science, Volume 14, 429–466. Elsevier, Amsterdam, 2007
   Google Scholar
• Edmonds, J. Optimum branching. Journal Research of the National Bureau of Standards, 71B: 233–240, 1967.
   Google Scholar
• Erdogan, G., Cordeau, J.-F., Laporte, G. The pickup and delivery traveling salesman problem with first-in-first-out loading. Technical Report CIRRELT-2007-61, HEC Montreal, 2007
   Google Scholar
• Ficarelli, F. Mathematical programming algorithms for the TSP with rear-loading. Degree Thesis, Universitá di Milano, Italy. http://optlab.dti.unimi.it/Papers/Ficarelli.pdf, 2005.
   Google Scholar
• Fischetti, M., Toth, P. An additive bounding procedure for combinatorial optimization problems. Operations Research, 37: 319–328, 1989.
   Web of Science ®Google Scholar
• Fischetti, M., Toth, P. An additive bounding procedure for the asymmetric travelling salesman problem. Mathematical Programming, 53: 173–197, 1992.
   Web of Science ®Google Scholar
• Fischetti, M., Toth, P. An efficient algorithms for the min-sum arborescence problem on complete digraph. ORSA Journal on Computing, 5(4): 426–434, 1993.
   Google Scholar
• Gabow, H., Galil, Z., Spencer, T., Tarjan, R.E. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, 6 (2): 109–122, 1986.
   Web of Science ®Google Scholar
• Gabow, H.N., Galil, Z., Spencer, T.H. Efficient implementation of graph algorithms using contraction. Journal ACM, 36 (3): 540–572, 1989.
   Web of Science ®Google Scholar
• Gutin, G., Punnen, A.P., The Traveling Salesman Problem and Its Variations. Kluwer, Boston, 2002.
   Google Scholar
• Healy, P., Moll, R. A new extension of local search applied to the dial-a-ride problem. European Journal of Operational Research, 83: 83–104, 1995.
   Web of Science ®Google Scholar
• 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: 377–386, 1985.
   Web of Science ®Google Scholar
• Ladany, S.P., Mehrez, A. Optimal routing of a single vehicle with loading and unloading constraints. Trasportation Planning and Technology, 8: 301–306, 1984.
   Google Scholar
• Levitin, G. Organization of computations that enable one to use stack memory optimally. Soviet Journal of Computer & System Science, 24: 151–159, 1986.
   Google Scholar
• Levitin, G., Abezgaouz, R. Optimal routing of multiple-load AGV subject to LIFO loading constraints. Computers & Operations Research, 30: 397–410, 2003.
   Web of Science ®Google Scholar
• Little, J.D.C., Murty, K.G., Sweeney, D.W., Karel, C. An algorithm for the traveling salesman problem. Operations Research, 11: 972–989, 1963.
   Web of Science ®Google Scholar
• Or, I., Traveling salesman type combinatorial problems and their relations to the logistics of blood banking. PhD thesis, Department of Industrial Engineering and Management Sciences, Northwestern University, 1976.
   Google Scholar
• Pacheco, J.A., Problemas de rutas con ventanas de tiempo. PhD thesis, Department of Estadistica and Investigation Operativa, Universitad complutense de Madrid, 1994.
   Google Scholar
• Pacheco, J.A. Problemas de rutas con carga y descarga en sistemas LIFO: solutiones exactas. Estudios de Econimia Aplicada, 3: 69–86, 1995.
   Google Scholar
• Pacheco, J.A. Heuristico para los problemas de ruta con carga y descarga en sistemas LIFO. SORT, Statistics and Operations Research Transactions, 21: 69–86, 1997a.
   Google Scholar
• Pacheco, J.A. 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, 1997b.
   Google Scholar
• Renaud, J., Boctor, F.F., Laporte, G. Perturbation heuristics for the pickup and delivery traveling salesman problem. Computers & Operations Research, 29: 1129–1141, 2002.
   Web of Science ®Google Scholar
• Renaud, J., Boctor, F.F., Ouenniche, J. A heuristic for the pickup and delivery traveling salesman problem. Computers & Operations Research, 27: 905–916, 2000.
   Web of Science ®Google Scholar
• Ruland, K.S., Rodin, E.Y. The pickup and delivery problem: Faces and branch-and-cut algorithm. Computer and Mathematics with Applications, 33: 1–13, 1997.
   Web of Science ®Google Scholar
• Savelsbergh, M.W.P. An efficient implementation of local search algorithms for contrained routing problems. European Journal of Operational Research, 47: 75–85, 1990.
   Web of Science ®Google Scholar
• Tarjan, R.E. Finding optimum branching. Networks, 7: 25–35, 1977.
   Web of Science ®Google Scholar
• Volchenkov, S.G. Organization of computations utilizing stack storage. Engineering Cybernetics, Soviet Journal of Computer & System Science, 20: 109–115, 1982.
   Google Scholar