A unified heuristic for a large class of Vehicle Routing Problems with Backhauls

Ahuja, 2002, A survey of very large scale neighborhood search techniques, Discrete Applied Mathematics, 123, 75, 10.1016/S0166-218X(01)00338-9 Angelelli, 2002, The vehicle routing problem with time windows and simultaneous pick-up and delivery, 249 Anily, 1996, The vehicle-routing problem with delivery and back-haul options, Naval Research Logistics, 43, 415, 10.1002/(SICI)1520-6750(199604)43:3<415::AID-NAV7>3.0.CO;2-C Battiti, 1994, The reactive tabu search, ORSA Journal of Computing, 6, 126, 10.1287/ijoc.6.2.126 Casco, 1988, Vehicle routing with backhauls: Models, algorithms and case studies, 127 Cordeau, 2001, A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society, 52, 928, 10.1057/palgrave.jors.2601163 J. Crispim, J. Brandao, Reactive tabu search and variable neighbourhood descent applied to the vehicle routing problem with backhauls, in: MIC’2001 4th Metaheuristic International Conference, Porto, Portugal, July 16–20, 2001. Desaulniers, 2002, VRP with pickup and delivery, vol. 9, 225 Dethloff, 2002, Relation between vehicle routing problems: An insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls, Journal of the Operational Research Society, 53, 115, 10.1057/palgrave/jors/2601263 Dethloff, 2001, Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up, OR Spektrum, 23, 79, 10.1007/PL00013346 J.J. Dongarra, Performance of various computers using standard linear equation software, University of Tennessee Computer Science Technical Report, CS-89-85, 2004. Duhamel, 1997, A tabu search heuristic for the vehicle routing problem with back-hauls and time windows, Transportation Science, 31, 49, 10.1287/trsc.31.1.49 Gelinas, 1995, A new branching strategy for time constrained routing problems with application to backhauling, Annals of Operations Research, 61, 91, 10.1007/BF02098283 Gendreau, 1999, Heuristics for the traveling salesman problem with pickup and delivery, Computers & Operations Research, 26, 699, 10.1016/S0305-0548(98)00085-9 Ghaziri, 2003, A neural network algorithm for the traveling salesman problem with backhauls, Computers & Industrial Engineering, 44, 267, 10.1016/S0360-8352(02)00179-1 Goetschalckx, 1989, The vehicle routing problem with backhauls, European Journal of Operational Research, 42, 39, 10.1016/0377-2217(89)90057-X Ø. Halskau, I. Gribkovskaia, K.N.B. Myklebost, Models for pick-up and deliveries from depots with lasso solutions, in: Proceedings of the 13th Annual Conference on Logistics Research––NOFOMA 2001, Collaboration in logistics: Connecting Islands using Information Technology, Reykjavik, Iceland, 2001-06-14–2001-06-15, Chalmers University of Technology, Göteborg, Sweden, 2001, pp. 279–293. Hansen, 1999, An introduction to variable neighborhood search, 433 K. Halse, Modeling and Solving Complex Vehicle Routing Problems, PhD thesis, Institute of Mathematical Statistics and Operations Research (IMSOR), Technical University of Denmark, 1992. T. Hasama, H. Kokubugata, H. Kawashima, A heuristic approach based on the string model to solve vehicle routing problem with backhauls, in: Proceedings of the 5th World Congress on Intelligent Transport Systems (ITS), Seoul, 1998. Hertz, 1997, A tutorial on tabu search, 121 C. Jacobs-Blecha, M. Goetschalckx, The vehicle routing problem with backhauls: Properties and solution algorithms, Technical Report, 1992–1998, Georgia Tech Research Corporation. Kontoravdis, 1995, A GRASP for the vehicle routing problem with time windows, ORSA Journal on Computing, 7, 10, 10.1287/ijoc.7.1.10 Kruskal, 1956, On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, 7, 48, 10.1090/S0002-9939-1956-0078686-7 Min, 1989, The multiple vehicle routing problem with simultaneous delivery and pickup, Transportation Research Part A, 23, 377, 10.1016/0191-2607(89)90085-X Mingozzi, 1999, An exact method for the vehicle routing problem with backhauls, Transportation Science, 33, 315, 10.1287/trsc.33.3.315 G. Nagy, S. Salhi, Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries, European Journal of Operational Research, in press. Osman, 2002, A reactive tabu search meta-heuristic for the vehicle routing problem with backhauls, Journal of Scheduling, 5, 263, 10.1002/jos.122 Potvin, 1993, A parallel route building algorithm for the vehicle routing and scheduling problem with time windows, European Journal of Operational Research, 66, 331, 10.1016/0377-2217(93)90221-8 Reimann, 2002, Insertion based ants for vehicle routing problems with backhauls and time windows, LNCS, 2463, 135 S. Ropke, D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Technical Report 04/13, DIKU, University of Copenhagen, 2004. S. Ropke, D. Pisinger, A unified heuristic for vehicle routing problems with backhauls, Technical Report 04/14, DIKU, University of Copenhagen, 2004. Salhi, 1999, A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the Operational Research Society, 50, 1034, 10.1057/palgrave.jors.2600808 Schrimpf, 2000, Record breaking optimization results––using the ruin & recreate principle, Journal of Computational Physics, 159, 139, 10.1006/jcph.1999.6413 Sigurd, 2004, The pickup and delivery problem with time windows and precendences, Transportation Science, 38, 197, 10.1287/trsc.1030.0053 P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, in: Proceedings CP-98 (Fourth International Conference on Principles and Practice of Constraint Programming), 1998. Süral, 2003, The single-vehicle routing problem with unrestricted backhauls, Networks, 41, 127, 10.1002/net.10067 Solomon, 1987, Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35, 254, 10.1287/opre.35.2.254 Thangiah, 1996, Heuristic approaches to vehicle routing with backhauls and time windows, Computers & Operations Research, 23, 1043, 10.1016/0305-0548(96)00018-4 Tillman, 1972, An upper bound algorithm for the single and multiple terminal delivery problem, Management Science, 18, 664, 10.1287/mnsc.18.11.664 Toth, 1999, A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls, European Journal of Operational Research, 113, 528, 10.1016/S0377-2217(98)00086-1 Toth, 1997, An exact algorithm for the vehicle routing problem with backhauls, Transportation Science, 31, 372, 10.1287/trsc.31.4.372 Toth, 2002, VRP with backhauls, 195 A. Wade, S. Salhi, An ant system algorithm for the vehicle routing problem with backhauls, in: MIC’2001––4th Metaheuristic International Conference. Wade, 2002, An investigation into a new class of vehicle routing problem with backhauls, Omega, 30, 487, 10.1016/S0305-0483(02)00056-7 Web page: www.diku.dk/~sropke. Y. Zhong, M.H. Cole, A simple approach to linehaul–backhaul problems: A guided local search approach for the vehicle routing problem, Transportation Research Part E, in press.