An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows

References

• Ahuja R. K., Ergun O., Orlin J. B., Punnen A. P. A survey of very large scale neighborhood search techniques. Discrete Appl. Math. (2002) 123:75–102Crossref, Google Scholar
• Bent R., Van Hentenryck P. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows. Lecture Notes in Computer Science, Vol. 2833. Proc. Internat. Conf. Constraint Programming (CP-2003) (2003a) 123–137Crossref, Google Scholar
• Bent R., Van Hentenryck P. A two-stage hybrid algorithm for pickup and delivery vehicle routing problem with time windows. (2003b) . Appendix available at http://www.cs.brown.edu/people/rbent/pickup-appendix.psGoogle Scholar
• Bent R., Van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Sci. (2004) 38(4):515–530Link, Google Scholar
• Cordeau J.-F., Laporte G., Mercier A. A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. (2001) 52:928–936Crossref, Google Scholar
• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.Introduction to Algorithms (2001) 2nd ed.(MIT Press, Boston, MA) Google Scholar
• Desaulniers G., Desrosiers J., Erdmann A., Solomon M. M., Soumis F., Toth P., Vigo D. The VRP with pickup and delivery. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications (2002) 9(SIAM, Philadelphia, PA) 225–242Crossref, Google Scholar
• Dumas Y., Desrosiers J., Soumis F. The pickup and delivery problem with time windows. Eur. J. Oper. Res. (1991) 54:7–22Crossref, Google Scholar
• Gendreau M., Guertin F., Potvin J.-Y., Séguin R. Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. (1998) . Tech. Rep. CRT-98-10, Centre de Recherche sur les Transport, Universite de Montreal, Montreal, CanadaGoogle Scholar
• Lau H. C., Liang Z. Pickup and delivery with time windows: Algorithms and test case generation. ICTAI-2001, 13th IEEE Conf. Tools Artificial Intelligence (2001) Dallas, TX:333–340Crossref, Google Scholar
• Li H., Lim A. A metaheuristic for the pickup and delivery problem with time windows. ICTAI-2001, 13th IEEE Conf. Tools Artificial Intelligence (2001) Dallas, TX:160–170Crossref, Google Scholar
• Lim H., Lim A., Rodrigues B. Solving the pick up and delivery problem with time windows using “squeaky wheel” optimization with local search. (2002) . Technical Report 2002, Paper 7-2002, Singapore Management University, SingaporeGoogle Scholar
• Martello S., Toth P., Brans J. P. An algorithm for the generalized assignment problem. Operational Research ’81 (1981) (North-Holland, New York) Google Scholar
• Mladenović N., Hansen P. Variable neighborhood search. Comput. Oper. Res. (1997) 24(11):1097–1100Crossref, Google Scholar
• Nanry W. P., Barnes J. W. Solving the pickup and delivery problem with time windows using reactive tabu search. Transportation Res. Part B (2000) 34:107–121Crossref, Google Scholar
• Pisinger D., Ropke S. A general heuristic for vehicle routing problems. Comput. Oper. Res. (2005) . Forthcoming. http://www.sciencedirect.comGoogle Scholar
• Potvin J.-Y., Rousseau J.-M. A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. Eur. J. Oper. Res. (1993) 66:331–340Crossref, Google Scholar
• Ropke S. Heuristics for the multi-vehicle pickup and delivery problem with time windows. (2002) . Masters Thesis 01-11-8, Department of Computer Science, University of Copenhagen, DenmarkGoogle Scholar
• Ropke S., Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. (2004) . Technical report, Department of Computer Science, University of Copenhagen, DenmarkGoogle Scholar
• Ropke S., Pisinger D. A unified heuristic for a large class of vehicle routing problems with backhauls. Eur. J. Oper. Res. (2006) 171:750–775Crossref, Google Scholar
• Shaw P. A new local search algorithm providing high quality solutions to vehicle routing problems. (1997) . Technical report, Department of Computer Science, University of Strathclyde, ScotlandGoogle Scholar
• Shaw P. Using constraint programming and local search methods to solve vehicle routing problems. Proc. CP-98 (Fourth Internat. Conf. Principles Practice Constraint Programming) (1998) Crossref, Google Scholar
• Schrimpf G., Schneider J., Stamm-Wilbrandt H., Dueck G. Record breaking optimization results using the ruin and recreate principle. J. Comput. Phys. (2000) 159:139–171Crossref, Google Scholar
• Sigurd M., Pisinger D., Sig M. The pickup and delivery problem with time windows and precedences. Transportation Sci. (2004) 38:197–209Link, Google Scholar
• SINTEF Vehicle routing and travelling salesperson problems. . http://www.sintef.no/static/am/opti/projects/top/vrp/benchmarks.htmlGoogle Scholar
• Solomon M. M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. (1987) 35:254–265Link, Google Scholar
• Toth P., Vigo D., Toth P., Vigo D. An overview of vehicle routing problems. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications (2002) 9(SIAM, Philadelphia, PA) 1–26Crossref, Google Scholar
• Trick M. A. A linear relaxation heuristic for the generalized assignment problem. Naval Res. Logist. (1992) 39:137–152Crossref, Google Scholar
• Xu H., Chen Z.-L., Rajagopal S., Arunapuram S. Solving a practical pickup and delivery problem. Transportation Sci. (2003) 37:347–364Link, Google Scholar