Multi-objective optimization of vehicle routing problem using evolutionary algorithm with memory

• Autorzy: Podlaski K. , Wiatrowski G.

Identyfikatory

DOI

10.7494/csci.2017.18.3.1809

• Języki publikacji: EN

Abstrakty

EN

The idea of a new evolutionary algorithm with memory aspect included is proposed to find multiobjective optimized solution of vehicle routing problem with time windows. This algorithm uses population of agents that individually search for optimal solutions. The agent memory incorporates the process of learning from the experience of each individual agent as well as from the experience of the population. This algorithm uses crossover operation to define agents evolution. In the paper we choose as a base the Best Cost Route Crossover (BCRC) operator. This operator is well suited for VPRTW problems. However it does not treat both of parent symmetrically what is not natural for general evolutionary processes. The part of the paper is devoted to find an extension of the BCRC operator in order to improve inheritance of chromosomes from both of parents. Thus, the proposed evolutionary algorithm is implemented with use of two crossover operators: BCRC and its extended-modified version. We analyze the results obtained from both versions applied to Solomon’s and Gehring & Homberger instances. We conclude that the proposed method with modified version of BCRC operator gives statistically better results than those obtained using original BCRC. It seems that evolutionary algorithm with memory and modification of Best Cost Route Crossover Operator lead to very promising results when compared to the ones presented in the literature.

Słowa kluczowe

EN

vehicle routing problem; time windows; evolutionary algorithms; multi-objective optimization

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2017
• Tom: Vol. 18 (3)
• Strony: 269--286
• Opis fizyczny: Bibliogr. 31 poz., rys., wykr., tab.

Twórcy

autor

Podlaski K.

• University of Lodz, Faculty of Physics and Applied Informatics, Łodz, Poland

autor

Wiatrowski G.

• University of Lodz, Faculty of Physics and Applied Informatics, Łodz, Poland

Bibliografia

• [1] Battarra M.: Exact and heuristic algorithms for routing problems, 4OR, vol. 9(4), pp. 421–424, 2011. http://dx.doi.org/10.1007/s10288-010-0141-9.
• [2] Berger J., Barkaoui M.: A parallel hybrid genetic algorithm for the vehicle routing problem with time windows, Computers & Operations Research, vol. 31(12), pp. 2037–2053, 2004.
• [3] Braysy O., Gendreau M.: Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms, Transportation Science, vol. 39(1), pp. 104–118, 2005. http://dx.doi.org/10.1287/trsc.1030.0056.
• [4] Braysy O., Gendreau M.: Vehicle Routing Problem with Time Windows, Part II: Metaheuristics, Transportation Science, vol. 39(1), pp. 119–139, 2005. http://dx.doi.org/10.1287/trsc.1030.0057.
• [5] Cordeau J.F., Laporte G., Mercier A.: A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society, vol. 52(8), pp. 928–936, 2001.
• [6] Dantzig G.B., Ramser J.H.: The Truck Dispatching Problem, Management Science, vol. 6(1), pp. 80–91, 1959.
• [7] Eiben A.E., Schippers C.A.: On Evolutionary Exploration and Exploitation, Fundamenta Informaticae, vol. 35(1–4), pp. 35–50, 1998. http://dl.acm.org/ citation.cfm?id=297119.297124.
• [8] Fisher M.L.: Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees, Operations Research, vol. 42(4), pp. 626–642, 1994. http://dx.doi. org/10.1287/opre.42.4.626.
• [9] Geetha S., Poonthalir G., Vanathi P.T.: A Hybrid Particle Swarm Optimization with Genetic Operator for Vehicle Routing Problem, Journal of Advances in Information Technology, vol. 1(4), 2010.
• [10] Gehring H., Homberger J.: A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In: Proceedings of EUROGEN99, vol. 2, pp. 57–64, Springer, Berlin, 1999.
• [11] Kallehauge B., Larsen J., Madsen O.B.: Lagrangian duality applied to the vehicle routing problem with time windows, Computers & Operations Research, vol. 33(5), pp. 1464–1487, 2006.
• [12] Kohl N.: Exact methods for time constrained routing and related scheduling problems. Ph.D. thesis, Technical University of Denmark, 1995.
• [13] Kohl N., Desrosiers J., Madsen O.B., Solomon M.M., Soumis F.: 2-path cuts for the vehicle routing problem with time windows, Transportation Science, vol. 33(1), pp. 101–116, 1999.
• [14] Laporte G., Gendreau M., Potvin J.Y., Semet F.: Classical and modern heuristics for the vehicle routing problem, International Transactions in Operational Research, vol. 7(4-5), pp. 285–300, 2000. http://dx.doi.org/10.1111/j. 1475-3995.2000.tb00200.x.
• [15] Larsen J.: Parallelization of the vehicle routing problem with time windows. Ph.D. thesis, Technical University of Denmark, Danmarks Tekniske Universitet, Department of Informatics and Mathematical Modeling, Institut for Informatik og Matematisk Modellering, 1999.
• [16] Lenstra J.K., Kan A.: Complexity of vehicle routing and scheduling problems, Networks, vol. 11(2), pp. 221–227, 1981.
• [17] Liu B., Wang L., Jin Y.H.: An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers, Computers & Operations Research, vol. 35(9), pp. 2791–2806, 2008.
• [18] Mann H.B., Whitney D.R.: On a Test of Whether one of Two Random Variables is Stochastically Larger than the Other, The Annals of Mathematical Statistics, vol. 18(1), pp. 50–60, 1947. http://dx.doi.org/10.1214/aoms/1177730491.
• [19] Minocha B., Tripathi S.: Two Phase Algorithm for Solving VRPTW Problem, International Journal of Artificial Inteligence and Expert Systems, vol. 4, 2013.
• [20] Moccia L., Cordeau J.F., Laporte G.: An incremental tabu search heuristic for the generalized vehicle routing problem with time windows, Journal of the Operational Research Society, vol. 63(2), pp. 232–244, 2012.
• [21] Ombuki B., Ross B.J., Hanshar F.: Multi-objective Genetic Algorithms for Vehicle Routing Problem with Time Windows, Applied Intelligence, vol. 24(1), pp. 17–30, 2006.
• [22] Puljic K., Manger R.: Comparison of eight evolutionary crossover operators for the vehicle routing problem, Mathematical Communications, vol. 18(2), pp. 359–375, 2013.
• [23] Reimann M., Doerner K., Hartl R.F.: D-ants: Savings based ants divide and conquer the vehicle routing problem, Computers & Operations Research, vol. 31(4), pp. 563–591, 2004.
• [24] Rochat Y., Taillard É.D.: Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, vol. 1(1), pp. 147–167, 1995.
• [25] Shaw P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Principles and Practice of Constraint Programming – CP98, pp. 417–431. Springer, 1998.
• [26] SINTEF: top VRPTW web page. https://www.sintef.no/projectweb/top/ vrptw/.
• [27] Solomon M.: Solomon’s VRPTW Benchmark Problems, 1999. http://w.cba. neu.edu/~msolomon/problems.htm.
• [28] Taillard É., Badeau P., Gendreau M., Guertin F., Potvin J.Y.: A tabu search heuristic for the vehicle routing problem with soft time windows, Transportation Science, vol. 31(2), pp. 170–186, 1997.
• [29] Thangiah S.R., Nygard K.E., Juell P.L.: GIDEON: a genetic algorithm system for vehicle routing with time windows. In: Proceedings. The Seventh IEEE Conference on Artificial Intelligence Application, vol. i, pp. 322–328, 1991. http://dx.doi.org/10.1109/CAIA.1991.120888.
• [30] Toth P., Vigo D. (eds.): The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2001.
• [31] Zhang Z., Qin H., Lim A., Guo S.: Branch and Bound Algorithm for a Single Vehicle Routing Problem with Toll-by-Weight Scheme. In: García-Pedrajas N., Herrera F., Fyfe C., Benítez J., Ali M. (eds.), Trends in Applied Intelligent Systems, Lecture Notes in Computer Science, vol. 6098, pp. 179–188, Springer, Berlin–Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-13033-5_19.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).