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

Krzysztof Podlaski; Grzegorz Wiatrowski

doi:10.7494/csci.2017.18.3.1809

Authors

Krzysztof Podlaski Uniwersytet Łódzki, Wydział Fizyki i Informatyki Stosowanej
Grzegorz Wiatrowski Uniwersytet Łódzki, Wydział Fizyki i Informatyki Stosowanej

DOI:

https://doi.org/10.7494/csci.2017.18.3.1809

Keywords:

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

Abstract

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.

Downloads

Download data is not yet available.

References

Battarra M.: Exact and heuristic algorithms for routing problems. In: 4OR, vol. 9(4), pp. 421–424, 2011. ISSN 1619-4500. URL http://dx.doi.org/10. 1007/s10288-010-0141-9. June 17, 2017 str. 16/19

Berger J., Barkaoui M.: A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. In: Computers & Operations Research, vol. 31(12), pp. 2037–2053, 2004.

Braysy O., Gendreau M.: Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. In: Transportation Science, vol. 39(1), pp. 104–118, 2005. URL http://dx.doi.org/10.1287/trsc.1030. 0056.

Braysy O., Gendreau M.: Vehicle Routing Problem with Time Windows, Part II: Metaheuristics. In: Transportation Science, vol. 39(1), pp. 119–139, 2005. URL http://dx.doi.org/10.1287/trsc.1030.0057.

Cordeau J.F., Laporte G., Mercier A., et al.: A unified tabu search heuristic for vehicle routing problems with time windows. In: Journal of the Operational research society, vol. 52(8), pp. 928–936, 2001.

Dantzig G.B., Ramser J.H.: The Truck Dispatching Problem. In: Management Science, vol. 6(1), pp. 80–91, 1959.

Eiben A.E., Schippers C.A.: On Evolutionary Exploration and Exploitation. In: Fundam. Inf., vol. 35(1-4), pp. 35–50, 1998. ISSN 0169-2968. URL http://dl. acm.org/citation.cfm?id=297119.297124.

Fisher M.L.: Optimal Solution of Vehicle Routing Problems Using Minimum KTrees. In: Operations Research, vol. 42(4), pp. 626–642, 1994. URL http://dx. doi.org/10.1287/opre.42.4.626.

Geetha S., Poonthalir G., Vanathi P.T.: A Hybrid Particle Swarm Optimization with Genetic Operator for Vehicle Routing Problem. In: Journal of Advances in Information Technology, vol. 1(4), 2010.

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.

Kallehauge B., Larsen J., Madsen O.B.: Lagrangian duality applied to the vehicle routing problem with time windows. In: Computers & Operations Research, vol. 33(5), pp. 1464–1487, 2006.

Kohl N.: Exact methods for time constrained routing and related scheduling problems. Ph.D. thesis, Technical University of Denmark, 1995.

Kohl N., Desrosiers J., Madsen O.B., Solomon M.M., Soumis F.: 2-path cuts for the vehicle routing problem with time windows. In: Transportation Science, vol. 33(1), pp. 101–116, 1999.

Laporte G., Gendreau M., Potvin J.Y., Semet F.: Classical and modern heuristics for the vehicle routing problem. In: International Transactions in Operational Research, vol. 7(4-5), pp. 285–300, 2000. ISSN 1475-3995. URL http: //dx.doi.org/10.1111/j.1475-3995.2000.tb00200.x.

Larsen J.: Parallelization of the vehicle routing problem with time windows. Ph.D. thesis, Technical University of DenmarkDanmarks Tekniske Universitet, Department of Informatics and Mathematical ModelingInstitut for Informatik og June 17, 2017 str. 17/19 Matematisk Modellering, 1999.

Lenstra J.K., Kan A.: Complexity of vehicle routing and scheduling problems. In: Networks, vol. 11(2), pp. 221–227, 1981.

Liu B., Wang L., Jin Y.H.: An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers. In: Computers & Operations Research, vol. 35(9), pp. 2791–2806, 2008.

Mann H.B., Whitney D.R.: On a Test of Whether one of Two Random Variables is Stochastically Larger than the Other. In: Ann. Math. Statist., vol. 18(1), pp. 50–60, 1947. URL http://dx.doi.org/10.1214/aoms/1177730491.

Minocha B., Tripathi S.: Two Phase Algorithm for Solving VRPTW Problem. In: International Journal of Artificial Inteligence and Expert Systems, vol. 4, 2013.

Moccia L., Cordeau J.F., Laporte G.: An incremental tabu search heuristic for the generalized vehicle routing problem with time windows. In: Journal of the Operational Research Society, vol. 63(2), pp. 232–244, 2012.

Ombuki B., Ross B.J., Hanshar F.: Multi-objective Genetic Algorithms for Vehicle Routing Problem with Time Windows. In: Applied Intelligence, vol. 24, p. 2006, 2006.

Puljić K., Manger R.: Comparison of eight evolutionary crossover operators for the vehicle routing problem. In: Mathematical Communications, vol. 18(2), pp. 359–375, 2013.

Reimann M., Doerner K., Hartl R.F.: D-ants: Savings based ants divide and conquer the vehicle routing problem. In: Computers & Operations Research, vol. 31(4), pp. 563–591, 2004.

Rochat Y., Taillard É.D.: Probabilistic diversification and intensification in local search for vehicle routing. In: Journal of heuristics, vol. 1(1), pp. 147–167, 1995.

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.

SINTEF: top VRPTW web page. URL https://www.sintef.no/projectweb/top/vrptw/.

Solomon M.: Solomon’s VRPTW Benchmark Problems, 1999. URL http: //http://w.cba.neu.edu/~msolomon/problems.htm.

Taillard É., Badeau P., Gendreau M., Guertin F., Potvin J.Y.: A tabu search heuristic for the vehicle routing problem with soft time windows. In: Transportation science, vol. 31(2), pp. 170–186, 1997.

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. URL http://dx. doi.org/10.1109/CAIA.1991.120888.

Toth P., Vigo D., eds.: The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2001. ISBN 0-89871-498-2.

Zhang Z., Qin H., Lim A., Guo S.: Branch and Bound Algorithm for a Single June 17, 2017 str. 18/19 Vehicle Routing Problem with Toll-by-Weight Scheme. In: N. García-Pedrajas, F. Herrera, C. Fyfe, J. Benítez, M. Ali, eds., Trends in Applied Intelligent Systems, Lecture Notes in Computer Science, vol. 6098, pp. 179–188. Springer Berlin Hei- delberg, 2010. ISBN 978-3-642-13032-8. URL http://dx.doi.org/10.1007/978-3-642-13033-5_19.