Solving vehicle routing problem with time windows using simulated annealing

Marcin Woch


Article describes a new version of function generating solutions in simulated annealing algorithm for vehicle routing problem with time windows. A goal of this method is to find solutions being a good approximation of the set of efficient solutions in the short time. A method used in this paper is a modification of sequentional simulated annealing algorithm.


simulated annealing; vehicle routing problem with time windows

Full Text:

PDF (Polski)


Cerny V.: A thermodynamical approach to traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applic., 1985, 45, s. 41-45.

Czarnas P.: Problem komiwojażerów z oknami czasowymi. Rozwiązanie metodą symulowanego wyżarzania. Uniwersytet Wrocławski, Wrocław 2001.

Czech Z. J., Czarnas P.: A Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows. Proc. 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, 2002, Canary Islands, Spain, s. 376-383.

Kirkpatrick S., Gellat C.D., Vecchi M.P.: Optimization by simulated annealing. 1983, Science, 220, s. 671-680.

Metropolis N., Rosenbluth A.W., Rosenbluth M.N., Teller A.H., Teller E.: Equation of state calculation by fast computing machines. Journal of Chem. Phys., 1953, 21, s. 1087-1091.

Parks G.T., Suppapitnarm A., Seffen K.A., Clarkson P.J., Liu J.S.: Design by multi-objective optimization using simulated annealing. 12th International Conference in Engineering Design, 1999, 3, s. 1395-1400.

Reeves C.R.: Modern heuristic techniques for combinatorial problems. McGraw-Hill, 1995.

Solomon M.: Algorithms for the Vehicle Routing and Scheduling Problem with Time Windows Constraints. Oper. Res., 1987, 35, s. 254-265.

Solomon M., Desrosiers J.: Time windows constrained routing and scheduling problems. Transp. Sci., 1988, 22, s. 1-13.

Suppapitnarm A.: A Simulated Annealing Algorithm for Multiobjective Design Optimization. MPhil. Thesis, University of Cambridge, Cambridge 1998.

Ulungu E.L., Teghem J.: Multi-objective combinatorial optimization problems: a survey. Journal of multiple-criteria decision analysis, 1994, Vol. 3, s. 83-104.

Ulungu E.L., Teghem J.: The two phases method: an efficient procedure to solve bi-oobjective combinatorial optimization problems. Foundations of Computing and Decision Sciences, 1995, Vol. 20, No. 2, s. 149-165.

Ulungu E.L., Teghem J., Fortemps P.: Heuristics for multi-objective combinatorial optimization by simulated annealing. Multiple Criteria Decision Making: Theory and applications. Proceedings of the 6th International Conference on MCDM, 1995, Beijing, China, s. 228-238.