×

An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows. (English) Zbl 1231.90087

Summary: The vehicle routing problem with time windows is a complex combinatorial problem with many real-world applications in transportation and distribution logistics. Its main objective is to find the lowest distance set of routes to deliver goods, using a fleet of identical vehicles with restricted capacity, to customers with service time windows. However, there are other objectives, and having a range of solutions representing the trade-offs between objectives is crucial for many applications. Although previous research has used evolutionary methods for solving this problem, it has rarely concentrated on the optimization of more than one objective, and hardly ever explicitly considered the diversity of solutions. This paper proposes and analyzes a novel multi-objective evolutionary algorithm, which incorporates methods for measuring the similarity of solutions, to solve the multi-objective problem. The algorithm is applied to a standard benchmark problem set, showing that when the similarity measure is used appropriately, the diversity and quality of solutions is higher than when it is not used, and the algorithm achieves highly competitive results compared with previously published studies and those from a popular evolutionary multi-objective optimizer.

MSC:

90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90C29 Multi-objective and goal programming

Software:

SPEA2; VRP; Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Toth, P.; Vigo, D., The vehicle routing problem (2001), SIAM: SIAM Philadelphia, PA, USA
[2] Dantzig, G. B.; Ramser, J. H., The truck dispatching problem, Manage Sci, 6, 1, 80-91 (1956) · Zbl 0995.90560
[3] Jozefowicz, N.; Semet, F.; Talbi, E.-G., Multi-objective vehicle routing problems, Eur J Oper Res, 189, 293-309 (2008) · Zbl 1148.90338
[4] Desrochers, M.; Desrosiers, J.; Solomon, M., A new optimization algorithm for the vehicle routing problem with time windows, Oper Res, 40, 2, 342-354 (1992) · Zbl 0749.90025
[5] Cordeau, J.-F.; Desaulniers, G.; Desrosiers, J.; Solomon, M. M.; Soumis, F., VRP with time windows, (Toth, P.; Vigo, D., The vehicle routing problem (2001), SIAM: SIAM Philadelphia, PA, USA), 157-193 · Zbl 1076.90543
[6] Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, part I: route construction and local search algorithms, Transp Sci, 39, 1, 104-118 (2005)
[7] Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, part II: metaheuristics, Transp Sci, 39, 1, 119-139 (2005)
[8] Yu T, Davis L. An introduction to evolutionary computation in practice. In: Yu T, Davis L, Baydar CM, Roy R, editors. Evolutionary computation in practice, Studies in computational intelligence, vol. 88. Berlin, Germany: Springer; 2008. p. 1-8.; Yu T, Davis L. An introduction to evolutionary computation in practice. In: Yu T, Davis L, Baydar CM, Roy R, editors. Evolutionary computation in practice, Studies in computational intelligence, vol. 88. Berlin, Germany: Springer; 2008. p. 1-8.
[9] Bräysy, O.; Dullaert, W.; Gendreau, M., Evolutionary algorithms for the vehicle routing problem with time windows, J Heuristics, 10, 6, 587-611 (2004)
[10] Lenstra, J. K.; Kan, A. H.G. R., Complexity of vehicle routing and scheduling problems, Networks, 11, 221-227 (1981)
[11] Zitzler, E.; Laumanns, M.; Bleuler, S., A tutorial on evolutionary multiobjective optimization, (Gandibleux, X.; Sevaux, M.; Sörensen, K.; T’kindt, V., Metaheuristics for multiobjective optimisation (2004), Springer: Springer Berlin, Germany), 3-38 · Zbl 1134.90491
[12] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans Evol Comput, 6, 2, 182-197 (2002)
[13] Zitzler E, Laumanns M, Thiele L. SPEA2: improving the strength pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Zurich, Switzerland; 2001.; Zitzler E, Laumanns M, Thiele L. SPEA2: improving the strength pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Zurich, Switzerland; 2001.
[14] Knowles, J. D.; Corne, D. W., Approximating the nondominated front using the pareto archived evolution strategy, Evol Comput, 8, 2, 149-172 (2000)
[15] Zitzler, E.; Künzli, S., Indicator-based selection in multiobjective search, (Parallel problem solving from nature VIII (2004), Springer: Springer Berlin, Germany), 832-842
[16] Zitzler, E.; Thiele, L., Multiobjective optimization using evolutionary algorithms—a comparative case study, (Proceedings of fifth international conference on parallel problem solving from nature (1998), Springer-Verlag: Springer-Verlag London, UK), 292-304
[17] Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms: empirical results, Evol Comput, 8, 2, 173-195 (2000)
[18] Deb, K.; Jain, S., Running performance metrics for evolutionary multi-objective optimization, (Wang, L.; Tan, K. C.; Furuhashi, T.; Kim, J.-H.; Yao, X., Proceedings of fourth asia-pacific conference on simulated evolution and learning (2002), Nanyang Technical University: Nanyang Technical University Singapore), 13-20
[19] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; da Fonseca, V. G., Performance assesment of multiobjective optimizers: an analysis and review, IEEE Trans Evol Comput, 7, 2, 117-132 (2003)
[20] Knowles J, Thiele L, Zitzler E. A tutorial on the performance assessment of stochastic multiobjective optimizers. TIK Report 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich; 2006.; Knowles J, Thiele L, Zitzler E. A tutorial on the performance assessment of stochastic multiobjective optimizers. TIK Report 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich; 2006.
[21] Rahoual, M.; Kitoun, B.; Hakim Mabed, M.; Bachelet, V.; Benameur, F., Multicriteria genetic algorithms for the vehicle routing problem with time windows, (Proceedings of fourth metaheuristics international conference (2001)), 527-532
[22] Srinivas, N.; Deb, K., Multiobjective optimization using nondominated sorting in genetic algorithms, Evol Comput, 2, 3, 221-248 (1994)
[23] Jung, S.; Moon, B. R., A hybrid genetic algorithm for the vehicle routing problem with time windows, (Proceedings of 2002 genetic and evolutionary computation conference (2002), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 1309-1316
[24] Zhu, K. Q., A diversity-controlling adaptive genetic algorithm for the vehicle routing problem with time windows, (Proceedings of 15th IEEE international conference on tools with artificial intelligence (2003), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA, USA), 176-183
[25] Jozefowiez, N.; Semet, F.; Talbi, E.-G., Enhancements of NSGA II and its application to the vehicle routing problem with route balancing, (Artificial evolution (2005)), 131-142
[26] Murata, T.; Itai, R., Multi-objective vehicle routing problems using two-fold EMO algorithms to enhance solution similarity on non-dominated solutions, (Coello Coello, C. A.; Hernandez, A.; Zitzler, E., Proceedings of third international conference on evolutionary multi-criteria optimization, Lecture Notes in Computer Science, vol. 3410 (2005), Springer: Springer Guanajuato, Mexico), 885-896 · Zbl 1109.90304
[27] Le Bouthillier, A.; Crainic, T. G., A cooperative parallel metaheuristic for vehicle routing with time windows, Comput Oper Res, 32, 1685-1708 (2005) · Zbl 1074.90006
[28] Glover, F. W.; Laguna, M., Tabu search (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA, USA · Zbl 0954.90069
[29] Homberger, J.; Gehring, H., A two-phase hybrid metaheuristic for the vehicle routing problem with time windows, Eur J Oper Res, 162, 220-238 (2005) · Zbl 1132.90378
[30] Beyer, H.-G.; Schwefel, H.-P., Evolution strategies—a comprehensive introduction, Nat Comput, 1, 1, 3-52 (2002) · Zbl 1014.68134
[31] Tan, K. C.; Chew, Y. H.; Lee, L. H., A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows, Comput Optim Appl, 34, 1, 115-151 (2006) · Zbl 1111.90022
[32] Ombuki, B.; Ross, B. J.; Hanshar, F., Multi-objective genetic algorithms for vehicle routing problem with time windows, Appl Intell, 24, 1, 17-30 (2006)
[33] Zitzler, E.; Laumanns, M.; Thiele, L., SPEA 2: improving the strength pareto evolutionary algorithm for multiobjective optimization, (Giannakoglou, K.; Tsahalis, D.; Periaux, J.; Papailiou, K.; Fogarty, T., Evolutionary methods for design optimisation and control (2002), Barcelona, Spain: Barcelona, Spain CIMNE), 19-26
[34] Garcia-Najera A, Bullinaria JA. A multi-objective density restricted genetic algorithm for the vehicle routing problem with time windows, in: Proceedings of 2008 UK workshop on computational intelligence, 2008.; Garcia-Najera A, Bullinaria JA. A multi-objective density restricted genetic algorithm for the vehicle routing problem with time windows, in: Proceedings of 2008 UK workshop on computational intelligence, 2008.
[35] Garcia-Najera, A.; Bullinaria, J. A., Bi-objective optimization for the vehicle routing problem with time windows: using route similarity to enhance performance, (Ehrgott, M.; Fonseca, C.; Gandibleux, X.; Hao, J. K.; Sevaux, M., Proceedings of fifth international conference on evolutionary multi-criterion optimization, Lecture Notes in Computer Science, vol. 5467 (2009), Springer-Verlag: Springer-Verlag Berlin, Germany), 275-289
[36] Garcia-Najera A. Preserving population diversity for the multi-objective vehicle routing problem with time windows. In: GECCO 2009 graduate student workshop, ACM; 2009. p. 2689-92.; Garcia-Najera A. Preserving population diversity for the multi-objective vehicle routing problem with time windows. In: GECCO 2009 graduate student workshop, ACM; 2009. p. 2689-92.
[37] Sörensen, K., Distance measures based on the edit distance for permutation-type representations, J Heuristics, 13, 1, 35-47 (2007)
[38] Garcia-Najera, A.; Bullinaria, J. A., Comparison of similarity measures for the multi-objective vehicle routing problem with time windows, (Proceedings of 2009 genetic and evolutionary computation conference (2009), ACM: ACM New York, NY, USA), 579-586
[39] Eiben, A. E.; Smith, J. E., Introduction to evolutionary computing (2003), Springer · Zbl 1028.68022
[40] Goldberg DE, Deb K. A comparative analysis of selection schemes used in genetic algorithms. In: Foundations of genetic algorithms. Morgan Kaufmann; 1991. p. 69-93.; Goldberg DE, Deb K. A comparative analysis of selection schemes used in genetic algorithms. In: Foundations of genetic algorithms. Morgan Kaufmann; 1991. p. 69-93.
[41] Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper Res, 35, 2, 254-265 (1987) · Zbl 0625.90047
[42] Pisinger, D.; Ropke, S., A general heuristic for vehicle routing problems, Comput Oper Res, 34, 8, 2403-2435 (2007) · Zbl 1144.90318
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.