Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms

References

• Adams J., Balas E., Zawack D. The shifting bottleneck procedure for job shop scheduling. Management Sci. (1988) 34:391–401Link, Google Scholar
• Antes J., Derigs U. A new parallel tour construction algorithm for the vehicle routing problem with time windows. (1995) . Working paper, Department of Economics and Computer Science, University of Köln, GermanyGoogle Scholar
• Applegate D., Cook W. A computational study of the job-shop scheduling problem. ORSA J. Comput. (1991) 3:149–156Link, Google Scholar
• Atkinson J. B. A greedy look-ahead heuristic for combinatorial optimisation: An application to vehicle scheduling with time windows. J. Oper. Res. Soc. (1994) 45:673–684Crossref, Google Scholar
• Baker E. K., Schaffer J. R. Solution improvement heuristics for the vehicle routing and scheduling problem with time window constraints. Amer. J. Math. Management Sci. (1986) 6:261–300Crossref, Google Scholar
• Balakrishnan N. Simple heuristics for the vehicle routeing problem with soft time windows. J. Oper. Res. Soc. (1993) 44:279–287Crossref, Google Scholar
• Barr R. S., Golden B. L., Kelly J. P., Resende M. G. C., Stewart W. R. Designing and reporting on computational experiments with heuristic methods. J. Heuristics (1995) 1:9–32Crossref, Google Scholar
• Bramel J., Simchi-Levi D. Probabilistic analyses and practical algorithms for the vehicle routing problem with time windows. Oper. Res. (1996) 44:501–509Link, Google Scholar
• Bräysy O. Local search and variable neighborhood search algorithms for the vehicle routing problem with time windows. (2001) . Doctoral dissertation, University of Vaasa, FinlandGoogle Scholar
• Bräysy O. Fast local searches for the vehicle routing problem with time windows. Inform. Systems Oper. Res. (2003) 41:179–194Google Scholar
• Caseau Y., Laburthe F., Naish L. Solving small TSPs with constraints. Proc. 14th Internat. Conf. Logic Programming (1997) (MIT Press, Cambridge, MA) 316–330Google Scholar
• Caseau Y., Laburthe F. Heuristics for large constrained vehicle routing problems. J. Heuristics (1999) 5:281–303Crossref, Google Scholar
• Christofides N., Beasley J. The period routing problem. Networks (1984) 14:237–246Crossref, Google Scholar
• Clarke G., Wright J. W. Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. (1964) 12:568–581Link, Google Scholar
• Cook W., Rich J. L. A parallel cutting-plane algorithm for the vehicle routing problems with time windows. (1999) . Technical report TR99-04, Department of Computational and Applied Mathematics, Rice University, Houston, TXGoogle Scholar
• Cordeau J. F., Desaulniers G., Desrosiers J., Solomon M. M., Soumis F., Toth P., Vigo D. The VRP with time windows. The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications (2001) (SIAM, Philadelphia, PA) 157–194Google Scholar
• Cordeau J.-F., Gendreau M., Laporte G., Potvin J.-Y., Semet F. A guide to vehicle routing heuristics. J. Oper. Res. Soc. (2002) 53:512–522Crossref, Google Scholar
• Cordone R., Wolfler-Calvo R. A note on time windows constraints in routing problems. (1997) . Internal report, Department of Electronics and Information, Polytechnic of Milan, Milan, ItalyGoogle Scholar
• Cordone R., Wolfler-Calvo R. A heuristic for the vehicle routing problem with time windows. J. Heuristics (2001) 7:107–129Crossref, Google Scholar
• Crainic T. G., Laporte G. Planning models for freight transportation. Eur. J. Oper. Res. (1997) 97:409–438Crossref, Google Scholar
• De Backer B., Furnon V., Prosser P., Kilby P., Shaw P. Local search in constraint programming: Application to the vehicle routing problem. Proc. CP-97 Workshop Indust. Constraint-Directed Scheduling (1997) (Schloss Hagenberg, Austria) 1–15Google Scholar
• Desrochers M., Lenstra J. K., Savelsbergh M. W. P., Soumis F., Golden B., Assad A. Vehicle routing with time windows: Optimization and approximation. Vehicle Routing: Methods and Studies (1988) (Elsevier Science Publishers, Amsterdam, The Netherlands) 65–84Google Scholar
• Desrosiers J., Dumas Y., Solomon M. M., Soumis F., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L. Time constrained routing and scheduling. Handbooks in Operations Research and Management Science 8: Network Routing (1995) (Elsevier Science Publishers, Amsterdam, The Netherlands) 35–139Google Scholar
• Dongarra J. Performance of various computers using standard linear equations software. (1998) . Report CS-89-85, Department of Computer Science, University of Tennessee, Knoxville, TNGoogle Scholar
• Dullaert W., Maurizio B. Impact of relative route length on the choice of time insertion criteria for insertion heuristics for the vehicle routing problem with time windows. Proc. Rome Jubilee 2000 Conf. Improving Knowledge Tools Transportation Logist. (2000) (Faculty of Engineering, University of Rome, Italy) 153–156Google Scholar
• Dullaert W. and O. Bräysy. Routing with relatively few customers per route. TOP (2003) 11:325–336Crossref, Google Scholar
• Fisher M., Jaikumar R. A generalized assignment heuristic for vehicle routing. Networks (1981) 11:109–124Crossref, Google Scholar
• Foisy C., Potvin J.-Y. Implementing an insertion heuristic for vehicle routing on parallel hardware. Comput. Oper. Res. (1993) 20:737–745Crossref, Google Scholar
• Gendreau M., Hertz A., Laporte G. A new insertion and postoptimization procedures for the traveling salesman problem. Oper. Res. (1992) 40:1086–1093Link, Google Scholar
• Gillett B., Miller L. R. A heuristic algorithm for the vehicle dispatch problem. Oper. Res. (1974) 22:340–349Link, Google Scholar
• Glover F. Multilevel tabu search and embedded search neighborhoods for the traveling salesman problem. (1991) . Working paper, College of Business and Administration, University of Colorado, Boulder, COGoogle Scholar
• Glover F., Balci O., Sharda R., Zenios S. New ejection chain and alternating path methods for traveling salesman problems. Computer Science and Operations Research: New Developments in Their Interfaces (1992) (Pergamon Press, Oxford, U.K.) 449–509Crossref, Google Scholar
• Golden B. L., Assad A. A. Perspectives on vehicle routing: Exciting new developments. Oper. Res. (1986) 34:803–809Link, Google Scholar
• Golden B. L., Assad A. A.Vehicle Routing: Methods and Studies (1988) (Elsevier Science Publishers, Amsterdam, The Netherlands) Google Scholar
• Golden B. L., Wasil E. A. Computerized vehicle routing in the soft drink industry. Oper. Res. (1987) 35:6–17Link, Google Scholar
• Halse K. Modeling and solving complex vehicle routing problems. (1992) . Ph.D. thesis, Institute of Mathematical Modelling, Technical University of Denmark, Lyngby, DenmarkGoogle Scholar
• Hamacher A., Moll C., Derigs U., Gaul W., Möhring R. H., Schuster K.-P. A new heuristic for vehicle routing with narrow time windows. Oper. Res. Proc. 1996, Selected Papers Sympos. (SOR ’96) (1996) BraunschweigGermany(September 3–6(Springer Verlag, New York) 301–306Google Scholar
• Harwey W., Ginsberg M., Dean T. Limited discrepancy search. Proc. 14th IJCAI (1995) (Morgan Kaufmann, San Francisco, CA) 607–615Google Scholar
• Hong S.-C., Park Y.-B. A heuristic for bi-objective vehicle routing with time window constraints. Internat. J. Production Econom. (1999) 62:249–258Crossref, Google Scholar
• Hooker J. N. Testing heuristics: We have it all wrong. J. Heuristics (1995) 1:33–42Crossref, Google Scholar
• Ioannou G., Kritikos M., Prastacos G. A greedy look-ahead heuristic for the vehicle routing problem with time windows. J. Oper. Res. Soc. (2001) 52:523–537Crossref, Google Scholar
• Jaffar J., Lassez J.-L. Constraint logic programming. (1986) . Technical report 86/73, Department of Computer Science, Monash University, Melbourne, AustraliaGoogle Scholar
• Jaffar J., Maher M. J. Constraint logic programming: A survey. J. Logic Programming (1994) 19/20:503–581Crossref, Google Scholar
• King G. F., Mast C. F. Excess travel: Causes, extent and consequences. Transportation Res. Record (1997) 1111:126–134Google Scholar
• Kohl N. Exact methods for time constrained routing and related scheduling problems. (1995) . Ph.D. thesis, Institute of Mathematical Modelling, Technical University of Denmark, Lyngby, DenmarkGoogle Scholar
• Kohl N., Desrosiers J., Madsen O. B. G., Solomon M. M., Soumis F. 2-path cuts for the vehicle routing problem with time windows. Transportation Sci. (1999) 33:101–116Link, Google Scholar
• Koskosidis Y. A., Powell W. B., Solomon M. M. An optimization-based heuristic for vehicle routing and scheduling with soft time window constraints. Transportation Sci. (1992) 26:69–85Link, Google Scholar
• Larsen J. Parallelization of the vehicle routing problem with time windows. (1999) . Ph.D. thesis, Institute of Mathematical Modelling, Technical University of Denmark, Lyngby, DenmarkGoogle Scholar
• Lin S. Computer solutions of the traveling salesman problem. Bell System Tech. J. (1965) 44:2245–2269Crossref, Google Scholar
• Lin S., Kernighan B. An effective heuristic algorithm for the traveling salesman problem. Oper. Res. (1973) 21:498–516Link, Google Scholar
• Or I. Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. (1976) . Ph.D. thesis, Northwestern University, Evanston, ILGoogle Scholar
• Osman I. H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problems. Ann. Oper. Res. (1993) 41:421–452Crossref, Google 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
• Potvin J.-Y., Rousseau J.-M. An exchange heuristic for routeing problems with time windows. J. Oper. Res. Soc. (1995) 46:1433–1446Crossref, Google Scholar
• Prosser P., Shaw P. Study of greedy search with multiple improvement heuristics for vehicle routing problems. (1996) . Working paper, University of Strathclyde, Glasgow, ScotlandGoogle Scholar
• Russell R. An effective heuristic for the M-tour traveling salesman problem with some side conditions. Oper. Res. (1977) 25:517–524Link, Google Scholar
• Russell R. A. Hybrid heuristics for the vehicle routing problem with time windows. Transportation Sci. (1995) 29:156–166Link, Google Scholar
• Savelsbergh M. W. P. Local search in routing problems with time windows. Ann. Oper. Res. (1986) 4:285–305Crossref, Google Scholar
• Savelsbergh M. W. P. An efficient implementation of local search algorithms for constrained routing problems. Eur. J. Oper. Res. (1990) 47:75–85Crossref, Google Scholar
• Savelsbergh M. W. P. The vehicle routing problem with time windows: Minimizing route duration. J. Comput. (1992) 4:146–154Abstract, 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
• Shaw P. A new local search algorithm providing high quality solutions to vehicle routing problems. (1997) . Working paper, Department of Computer Science, University of Strathclyde, Glasgow, ScotlandGoogle Scholar
• Shaw P., Maher M., Puget J.-F. Using constraint programming and local search methods to solve vehicle routing problems. Principles and Practice of Constraint Programming—CP98, Lecture Notes in Computer Science (1998) (Springer-Verlag, New York) 417–431Crossref, Google Scholar
• Solomon M. M. On the worst-case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints. Networks (1986) 16:161–174Crossref, Google Scholar
• Solomon M. M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. (1987) 35:254–265Link, Google Scholar
• Solomon M. M., Desrosiers J. Time window constrained routing and scheduling problems. Transportation Sci. (1988) 22:1–13Link, Google Scholar
• Solomon M. M., Baker E. K., Schaffer J. R., Golden B., Assad A. Vehicle routing and scheduling problems with time window constraints: Efficient implementations of solution improvement procedures. Vehicle Routing: Methods and Studies (1988) (Elsevier Science Publishers, Amsterdam, The Netherlands) 85–106Google Scholar
• Taillard É. D. Comparison of non-deterministic iterative methods. MIC ’2001, 4th Metaheuristics Internat. Conf. (2001) Porto, Portugal(July 16–20Google Scholar
• Taillard É., Badeau P., Gendreau M., Guertin F., Potvin J.-Y. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Sci. (1997) 31:170–186Link, Google Scholar
• Thangiah S. R., Osman I. H., Vinayagamoorthy R., Sun T. Algorithms for the vehicle routing problems with time deadlines. Amer. J. Math. Management Sci. (1995) 13:323–355Google Scholar
• Thompson P. M., Orlin J. B. Theory of cyclic transfers. (1989) . Working paper, Operations Research Center, MIT, Cambridge, MAGoogle Scholar
• Thompson P. M., Psaraftis H. N. Cyclic transfer algorithms for multivehicle routing and scheduling problems. Oper. Res. (1993) 41:935–946Link, Google Scholar
• Van Landeghem H. R. G. A bi-criteria heuristic for the vehicle routing problem with time windows. Eur. J. Oper. Res. (1988) 36:217–226Crossref, Google Scholar