Abstract
The paper presents an extension of the self- organizing map (SOM) by embedding it into an evolutionary algorithm to solve the Vehicle Routing Problem (VRP). We call it the memetic SOM. The approach is based on the standard SOM algorithm used as a main operator in a population based search. This operator is combined with other derived operators specifically dedicated for greedy insertion moves, a fitness evaluation and a selection operator. The main operators have a similar structure based on the closest point findings and local moves performed in the plane. They can be interpreted as performing parallels and massive insertions, simulating the behavior of agents which interact continuously, having localized and limited abilities. This self-organizing process is intended to allow adaptation to noisy data as well as to confer robustness according to demand fluctuation. Selection is intended to guide the population based search toward useful solution compromises. We show that the approach performs better, with respect to solution quality and/or computation time, than other neural network applications to the VRP presented in the literature. As well, it substantially reduces the gap to classical Operations Research heuristics, specifically on the large VRP instances with time duration constraint.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Arora S (1998). Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. J ACM 45(5): 753–782
Boese KD, Kahng AB and Muddu S (1994). Adaptive multi-start technique for combinatorial global optimization. J Oper Res Lett 16: 101–113
Buriol L, França PM and Moscato P (2004). A new memetic algorithm for the asymmetric traveling salesman problem. J Heuristics 10(5): 483–506
Bäck T, Hoffmeister F, Schwefel HP (1991) A survey of evolution strategies. In: 4th Int. Conf. on Genetic Algorithms, La Jolla, CA
Bentley JL, Weide BW and Yao AC (1980). Optimal expected time algorithms for closest point problems. ACM Trans Math Softw 6(4): 563–580
Christofides N, Mingozzi A and Toth P (1979). The vehicle routing problem. In: Christofides, N. (eds) Combinatorial optimization, pp 315–338. Wiley, New York
Clarke G and Wright JW (1964). Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12: 568–581
Cordeau JF, Laporte G and Mercier A (2001). A unified tabu search heuristic for vehicle routing problems with time windows. J Oper Res Soc 52: 928–936
Cordeau JF, Gendreau M, Hertz A, Laporte G and Sormany JS (2005). New heuristics for the vehicle routing problem. In: Langevin, A and Riopel, D (eds) Logistics systems: design and optimization, pp 279–297. Springer, New York
Créput JC, Lissajoux T, Koukam A (2000) A connexionnist approach to the hexagonal mesh generation. In: 16th IMACS World Congress, Lausanne
Créput JC, Koukam A, Lissajoux T and Caminada A (2005). Automatic mesh generation for mobile network dimensioning using evolutionary approach. IEEE Trans Evol Comput 9(1): 18–30
Créput JC and Koukam A (2006). Local search study of honeycomb clustering problem for cellular planning. Int J Mobile Network Des Innov 1(2): 153–160
Créput JC and Koukam A (2007). Interactive meshing for the design and optimization of bus transportation networks. J Transp Eng 133(9): 529–538
Créput JC and Koukam A (2007). Transport clustering and routing as a visual meshing process. J Inform Optim Sci 28(4): 573–601
Créput JC, Koukam A and Hajjam A (2007). Self-organizing maps in evolutionary approach for the vehicle routing problem with time windows. Int J Comput Sci Network Secur 7(1): 103–110
Cochrane EM and Beasley JE (2003). The co-adaptive neural network approach to the Euclidean travelling salesman problem. Neural Networks 16: 1499–1525
Dongarra JJ (2006) Performance of various computers using standard linear equations software. In: Technical Report CS-89-85, Department of Computer Science, University of Tennessee, USA, available at http://www.netlib.org/benchmark/performance.ps
Ergun Ö, Orlin JB, Steele-Feldman A (2003) Creating very large scale neighborhoods out of smaller ones by compounding moves: a study on the vehicle routing problem. MIT Sloan Working Paper No. 4393–02, USA
Gambardella LM, Taillard E and Agazzi G (1999). MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows. In: Corne, D, Dorigo, M, and Glover, F (eds) New ideas in optimization, pp 63–76. McGraw-Hill, UK
Gendreau M, Laporte G and Potvin J-Y (2002). Metaheuristics for the capacitated VRP. In: Toth, P and Vigo, D (eds) The vehicle routing problem, pp 129–154. SIAM, Philadelphia
Ghaziri H (1996). Supervision in the self-organizing feature map: application to the vehicle routing problem. In: Osman, IH and Kelly, JP (eds) Meta-heuristics: theory & applications, pp 651–660. Kluwer, Boston
Golden BL, Wasil EA, Kelly JP and Chao IM (1998). Metaheuristics in vehicle routing. In: Crainic, TG and Laporte, G (eds) Fleet management and logistics, pp 33–56. Kluwer, Boston
Gomes LCT, Von Zuben FJA (2002) Vehicle Routing Based on Self-Organization with and without Fuzzy Inference. In: Proc. of the IEEE International Conference on Fuzzy Systems, vol. 2, pp 1310–1315
Goldberg DE (1994). Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading, MA
Johnson DS and McGeoch LA (1997). The traveling salesman problem: a case study in local optimization. In: Aarts, EHL and Lenstra, JK (eds) Local search in combinatorial optimization, pp 215–310. Wiley, London,
Johnson DS, McGeoch LA (2002) Experimental analysis of heuristics for the STSP. In: Gutin G, Punnen A (eds) Traveling salesman problem and its variations. Kluwer, Dordrecht, pp 369–443
Kohonen T (2001). Self-organization maps and associative memory, 3rd edn. Springer, Berlin
Krasnogor N (2005). A tutorial for competent memetic algorithms: model, taxonomy and design issues. IEEE Trans Evol Comput 9(5): 474–488
Kytöjoki J, Nuortio T, Bräysy O and Gendreau M (2007). An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Comput Oper Res 34(9): 2743–2757
Laporte G, Gendreau M, Potvin JY and Semet F (2000). Classical and modern heuristics for the vehicle routing problem. Int Trans Oper Res 7: 285–300
Li F, Golden B and Wasil E (2005). Very large-scale vehicle routing: new test problems, algorithms, and results. Comput Oper Res 32: 1165–1179
Matsuyama Y (1991) Self-organization via competition, cooperation and categorization applied to extended vehicle routing problems. In: Proc. of the International Joint Conference on Neural Networks. Seatle, WA, pp 385–390
Merz P and Freisleben B (2001). Memetic algorithms for the traveling salesman problem. Complex Syst 13(4): 297–345
Merz P and Freisleben B (2002). Fitness landscape and memetic algorithm design. In: Glover, F and Kochenberger, G (eds) Handbook of metaheuristics, pp 321–353. Kluwer, Norwell, MA
Mester D and Bräysy O (2005). Active guided evolution strategies for large scale vehicle routing problems with time windows. Comput Oper Res 32: 1593–1614
Moscato P (1999) Memetic algorithms: a short introduction. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimization. McGraw-Hill, UK
Moscato P and Cotta C (2003). A gentle introduction to memetic algorithms. In: Glover, F and Kochenberger, G (eds) Handbook of metaheuristics, pp 105–144. Kluwer, Boston, MA
Modares A, Somhom S and Enkawa T (1999). A self-organizing neural network approach for multiple traveling salesman and vehicle routing problems. Int Trans Oper Res 6: 591–606
Mühlenbein H (1991) Evolution in time and space—the parallel genetic algorithm. In: Rawlins G (ed) Foundations of genetic algorithms. Morgan Kaufmann, Los Altos, CA
Nguyen HD, Yoshihara I, Yamamori K and Yasunaga M (2007). Implementation of an effective hybrid GA for large-scale traveling salesman problems. IEEE Trans Syst Man Cybern B 37(1): 92–99
Ong YS, Lim MH, Zhu N and Wong KW (2006). Classification of adaptive memetic algorithms: a comparative study. IEEE Trans Syst Man Cybern B 36(1): 141–152
Or I (1976) Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking. Ph.D. thesis, Northwestern University, Evanston, USA
Prins C (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res 31: 1985–2002
Preparata FP and Shamos MI (1985). Computational geometry: an introduction. Springer, New York
Rardin RL and Uzsoy R (2001). Experimental evaluation of heuristic optimization algorithms: a tutorial. J Heuristics 7: 261–304
Reimann M, Doerner K and Hartl RF (2004). D-ants: savings based ants divide and conquer the vehicle routing problem. Comput Oper Res 31: 563–591
Reinelt G (1991). TSPLIB-A traveling salesman problem library. ORSA J Comput 3: 376–384
Rochat Y and Taillard ED (1995). Probabilistic diversification and intensification in local search for vehicle routing. J Heuristics 1: 147–167
Schumann M, Retzko R (1995) Self-organizing maps for vehicle routing problems minimizing an explicit cost function. In: Proc. of the International Conference on Artificial Neural Networks, Paris, pp 401–406
Schwardt M and Dethloff J (2005). Solving a continuous location-routing problem by use of a self-organizing map. Int J Phys Distrib Logistics Manage 35(6): 390–408
Solomon MM (1987). Algorithms for the vehicle routing and scheduling problems with time window constrains. Oper Res 35: 254–264
Smith K (1996). An argument for abandoning the traveling salesman problem as a neural network benchmark. IEEE Trans Neural Networks 7(6): 1542–1544
Taillard ED, Gambardella ML, Gendreau M and Potvin JY (2001). Adaptive memory programming: a unified view of metaheuristics. Eur J Oper Res 135: 1–16
Toth P and Vigo D (2001). Branch-and-bound algorithms for the capacitated VRP. In: Toth, P and Vigo, D (eds) The vehicle routing problem, pp 29–52. SIAM, Philadelphia
Toth P and Vigo D (2003). The granular tabu search and its application to the vehicle routing problem. INFORMS J Comput 15: 333–348
Vakhutinsky AI, Golden BL (1994) Solving vehicle routing problems using elastic net. In: IEEE International Conference on Neural Network, pp 4535–4540
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Créput, JC., Koukam, A. The memetic self-organizing map approach to the vehicle routing problem. Soft Comput 12, 1125–1141 (2008). https://doi.org/10.1007/s00500-008-0281-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-008-0281-4