Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints

References

• Ahuja R. K., Orlin J. B. A fast scaling algorithm for minimizing separable convex functions subject to chain constraints. Oper. Res. (2001) 49:784–789Link, Google Scholar
• Ahuja R. K., Orlin J. B., Sharma D. Very large-scale neighborhood search. Internat. Trans. Oper. Res. (2000) 7:301–317Crossref, Google Scholar
• 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 local search for the vehicle routing problem with time windows. (2001) . Technical Report CS-01-06, Department of Computer Science, Brown University, Providence, RIGoogle Scholar
• Berger J., Barkaoui M., Bräysy O. A route-directed hybrid genetic approach for the vehicle routing problem with time windows. INFOR (2003) 41(2):179–194Google Scholar
• Bertsekas D. P.Nonlinear Programming (1995) (Athena Scientific, Belmont, MA) Google Scholar
• Boese K. D., Kahng A. B., Muddu S. A new adaptive multi-start technique for combinatorial global optimizations. Oper. Res. Lett. (1994) 16:101–113Crossref, Google Scholar
• Bräysy O. A reactive variable neighborhood search for the vehicle-routing problem with time windows. INFORMS J. Comput (2003) 15:347–368Link, Google Scholar
• Bräysy O., Gendreau M. Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation Sci. (2005a) 39(1):104–118Link, Google Scholar
• Bräysy O., Gendreau M. Vehicle routing problem with time windows, Part II: Metaheuristics. Transportation Sci. (2005b) 39(1):119–139Link, Google Scholar
• Chvátal V.Linear Programming (1983) (Freeman, New York) Google Scholar
• Davis J. S., Kanet J. J. Single-machine scheduling with early and tardy completion costs. Naval Res. Logist. (1993) 40:85–101Crossref, Google Scholar
• De Jong C., Kant G., Van Vliet A. On finding minimal route duration in the vehicle routing problem with multiple time windows. (1996) . Manuscript, Department of Computer Science, Utrecht University, The Netherlands ( http://www.cs.uu.nl/research/projects/alcom/wp4.3.html)Google Scholar
• Desrochers M., Lenstra J. K., Savelsbergh M. W. P., Soumis F., Golden B. L., Assad A. A. Vehicle routing with time windows: Optimization and approximation. Vehicle Routing: Methods and Studies (1988) (North-Holland, Amsterdam, The Netherlands) Google 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 (1995) 8(North-Holland, Amsterdam, The Netherlands) 35–139Google Scholar
• Dongarra J. J. Performance of various computers using standard linear equations software. (2002) . Technical Report CS-89-85, Computer Science Department, University of Tennessee, Knoxville, TN ( http://www.netlib.org/benchmark/performance.ps)Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (Freeman, New York) Google Scholar
• Garey M. R., Tarjan R. E., Wilfong G. T. One-processor scheduling with symmetric earliness and tardiness penalties. Math. Oper. Res. (1988) 13:330–348Link, Google Scholar
• Gehring H., Homberger J. Parallelization of a two-phase metaheuristic for routing problems with time windows. J. Heuristics (2002) 8:251–276Crossref, Google Scholar
• Glover F. Ejection chains, reference structures and alternating path methods for traveling salesman problems. Discrete Appl. Math. (1996) 65:223–253Crossref, Google Scholar
• Hochbaum D. S., Hochbaum D. S. Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems. Approximation Algorithms for NP-Hard Problems (1997) (PWS Pub. Co., Boston, MA) 94–143Google Scholar
• Hochbaum D. S. Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations. Eur. J. Oper. Res. (2002a) 140:291–321Crossref, Google Scholar
• Hochbaum D. S. Private communication. (2002b) Google Scholar
• Hochbaum D. S., Naor J. Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput. (1994) 23:1179–1192Crossref, Google Scholar
• Hochbaum D. S., Queyranne M. Minimizing a convex cost closure set. SIAM J. Discrete Math. (2003) 16:192–207Crossref, Google Scholar
• Homberger J., Gehring H. Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR (1999) 37:297–318Google Scholar
• Homberger J., Gehring H. A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. Eur. J. Oper. Res. (2004) . ForthcomingGoogle Scholar
• Johnson D. S., Paterson M. S. Local optimization and the traveling salesman problem. Automata, Languages and Programming (1990) 443(Springer-Verlag, Berlin, Germany) 446–461Crossref, Google Scholar
• Johnson D. S., McGeoch L. A., Aarts E. H. L., Lenstra J. K. The traveling salesman problem: A case study. Local Search in Combinatorial Optimization (1997) (John Wiley & Sons, Chichester, UK) 215–310Google 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
• 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
• Martin O., Otto S. W., Felten E. W. Large-step Markov chains for the traveling salesman problem. Complex Systems (1991) 5:299–326Google Scholar
• Martin O., Otto S. W., Felten E. W. Large-step Markov chains for the TSP incorporating local search heuristic. Oper. Res. Lett. (1992) 11:219–224Crossref, Google Scholar
• Or I. Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. (1976) . Unpublished doctoral dissertation, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, ILGoogle Scholar
• Park N., Okano H., Imai H. A path-exchange-type local search algorithm for vehicle routing and its efficient search strategy. J. Oper. Res. Soc. Japan (2000) 43:197–208Crossref, Google Scholar
• Potvin J. Y., Kervahut T., Garcia B. L., Rousseau J. M. The vehicle routing problem with time windows, Part 1: Tabu search. INFORMS J. Comput. (1996) 8:158–164Link, Google Scholar
• Reiter S., Sherman G. Discrete optimizing. J. Soc. Indust. Appl. Math. (1965) 13:864–889Crossref, Google Scholar
• Rousseau L.-M., Gendreau M., Pesant G. Using constraint-based operators to solve the vehicle routing problem with time windows. J. Heuristics (2002) 8:43–58Crossref, Google Scholar
• Savelsbergh M. W. P. The vehicle routing problem with time windows: Minimizing route duration. ORSA J. Comput. (1992) 4:146–154Link, Google Scholar
• Solomon M. M. 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
• Taillard E., 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
• Tamaki H., Komori T., Abe S. A heuristic approach to parallel machine scheduling with earliness and tardiness penalties. Proc. 7th IEEE Internat. Conf. Emerging Tech. Factory Automation (ETFA’99) (1999a) Barcelona, Catalonia, Spain:1367–1370Crossref, Google Scholar
• Tamaki H., Sugimoto T., Araki M. Parallel machine scheduling problem with a non-regular objective function—Minimizing the sum of earliness and tardiness penalties (in Japanese). Trans. Soc. Instrument Control Engineers (1999b) 35:1176–1182Crossref, Google Scholar
• Thangiah S. R., Osman I. H., Sun T. Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows. (1994) . Working Paper UKC/IMS/OR94/4, Institute of Mathematics and Statistics, University of Kent, Canterbury, UKGoogle Scholar
• Thompson P. M., Orlin J. B. The theory of cyclic transfers. (1989) . Working Paper OR200-89, 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