Self-Organizing Maps in Evolutionary Approachmeant for Dimensioning Routes to the Demand

Authors: J.-C. Créput, A. Koukam, A. Hajjam

Abstract:

We present a non standard Euclidean vehicle routing problem adding a level of clustering, and we revisit the use of self-organizing maps as a tool which naturally handles such problems. We present how they can be used as a main operator into an evolutionary algorithm to address two conflicting objectives of route length and distance from customers to bus stops minimization and to deal with capacity constraints. We apply the approach to a real-life case of combined clustering and vehicle routing for the transportation of the 780 employees of an enterprise. Basing upon a geographic information system we discuss the influence of road infrastructures on the solutions generated.

Keywords: Evolutionary algorithm, self-organizing map, clustering and vehicle routing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1077465

References:

[1] Angéniol, B., G. de La Croix Vaubois, and J.Y. Le Texier. (1988). "Self-Organizing feature Maps and the Travelling Salesman Problem". Neural Network, vol. 1, pp. 289-293.
[2] Aras, N., B.J. Oommen, and I.K. Altinel. (1999). "The Kohonen network Incorporating Explicit Statistics and its Appplication to the Travelling Salesman Problem". Neural Networks, vol. 12, no 9, pp. 1273-1284.
[3] Arora, Sanjeev. (1998b). "Polynomial Time Approximation Schemes for Euclidean k-medians and related problems". In ACM STOC'98.
[4] Balas, E. (1989). "The prize collecting traveling salesman problem" Networks, 19, 621-636.
[5] J. L. Bentley, B. W. Weide, and A. C. Yao, "Optimal Expected Time Algorithms for Closest Point Problems," ACM Transactions on Mathematical Software, vol. 6, no. 4, pp. 563-580, December 1980.
[6] Bishop, C.M. (1985). "Neural Networks for Pattern Recognition". Oxford University Press, ISBN-0-19-853849-9.
[7] Christofides, N., A. Mingozzi, and P. Toth. (1979). "The vehicle routing problem". In Christofides N. et al. (eds), Combinatorial Optimization, Wiley, 315-338.
[8] E. M. Cochrane and J. E. Beasley, "The co-adaptive neural network approach to the Euclidean Travelling Salesman Problem," Neural Networks, vol. 16, pp.1499-1525, 2003.
[9] Créput, J.C., A. Koukam, T. Lissajoux, and A. Caminada. (2005). "Automatic Mesh Generation for Mobile Network Dimensioning using Evolutionary Approach". IEEE Transactions on Evolutionary Computation, vol. 9, no. 1, pp. 18-30.
[10] Darden, L. and J. A. Cain. (1989). "Selection type Theories". Philosophy of Science, Vol. LVI.
[11] Durbin, R. and D.J. Willshaw. (1987). "An Analogue Approach to the Traveling Salesman problem using an Elastic Net Method". Nature 326, pp 689-691.
[12] Erwin, E., K. Obermayer and K. Schulten. (1992). "Self-organizing maps: Ordering, convergence properties and energy functions". Biological Cybernetics, vol. 67, pp. 47-55.
[13] Ghaziri, H. (1996). "Supervision in the Self-Organizing Feature Map: Application to the Vehicle Routing Problem". In Meta-Heuristics: Theory & Applications, I.H. Osman and J.P. Kelly (eds), Kluwer, Boston, 651-660.
[14] Goldberg, David E. (1991). "Genetic Algorithms". Addison-Wesley USA.
[15] Graepel, T., M. Burger and K. Obermayer. (1998). "Self-organizing maps: Generalisations and new optimisation techniques". Neurocomputing, vol. 20, pp. 173-190, 1998.
[16] Kariv, O. and S.L. Hakimi. (1979). "An algorithmic approach to network location problems; part 2. The p-median". SIAM Journal on Applied Mathematics 37, 539-560.
[17] Kohonen, T. (2001). "Self-Organization Maps and associative memory". Springer Verlag, Berlin, 3rd edition.
[18] Kohonen, T. (1982). "Clustering, Taxonomy, and Topological Maps of Patterns". Proceedings of the 6th International Conference on Pattern Recognition.
[19] Kushner, H.J. and D.S. Clark. (1978). "Stochastic Approximation Methods for Constrained and Unconstrained Systems". New York, Berlin: Springer-Verlag.
[20] Labbé M. and G. Laporte. (1986). "Maximizing user convenience and postal service efficiency in post box location". Belgian Journal of Operations Research, Statistics and Computer Science, 26, 21-35, 1986.
[21] Labbé, M., G. Laporte and I. Rodr├¡guez Mart├¡n. (1998). "Path, tree and cycle location". In Fleet Management and Logistics, T. Crainic and G. Laporte (edts), Kluwer, Boston, 187-204.
[22] Labbé, M., I. Rodr├¡guez Mart├¡n, and J.J. Salazar Gonz├ílez. (2005). "Locating Median Cycles in Networks". European Journal of Operational Research, 160:457-470.
[23] Labbé, M., G. Laporte, I. Rodr├¡guez Mart├¡n, and J.J. Salazar Gonz├ílez. (2004). "The Ring Star Problem: Polyhedral Analysis and Exact Algorithm". Networks, vol. 43, pp. 177-189.
[24] Laporte, G. and U. Palekar. (2000). "Some Applications of the Clustered Traveling Salesman Problem". Les Cahiers du GERAD, http://www.gerad.ca.
[25] Leung, K.S., H.D. Jin, and Z.B. Xu. (2004). "An expanding selforganizing neural network for the travelling salesman problem". Neurocomputing, 62, 267-292.
[26] Manderick, B. (1992). "Selectionist Systems as Cognitive Systems". Proceedings of the First European Conference on Artificial Life, ECAL'91, MIT Press, Cambridge, MA.
[27] Megiddo N. and K.J. Supowit. (1984). "On the complexity of Some Common Geometric Location Problems". SIAM Journal on Computing 13, 182-196.
[28] Merz, P. and B. Freisleben. (2002). "Fitness Landscape and Memetic Algorithm Design", in F. Glover und G. Kochenberger (Herausgeber), Handbook of Metaheuristics, pages 321-353, Kluwer Academic Publishers, Norwell, MA.
[29] Min, H., V. Jayaraman, and R. Srivastava. (1998). "Combined location-routing problems: A synthesis and future research directions". European Journal of Operational Research 108:1-15.
[30] Modares, A., S. Somhom, and T. Enkawa. (1999). "A self-organizing neural network approach for multiple traveling salesman and vehicle routing problems". International Transactions in Operational Research, 6:591-606.
[31] Moscato, P. (1999). "Memetic Algorithms: A Short Introduction". In New Ideas in Optimization, D. Corne, M. Dorigo, and F. Glover, eds., McGraw Hill.
[32] M├╝hlenbein, H. (1991). "Evolution in Time and Space - The Parallel Genetic Algorithm". In G. Rawlins (Ed.), Foundations of Genetic Algorithms, Morgan Kaufmann, Los Altos, CA.
[33] Muhlenbein, H, M. Georges-Schleuter, and O. Kramer. (1988). "Evolution algorithms in combinatorial optimization". Parallel Computation 7, 65-85.
[34] Mulier, F. and V. Cherkassky. (1995). "Self-Organization as an iterative kernel smoothing process", Neural Computation, 7:1165- 1177.
[35] Ritter, H. and K. Schulten. (1986). "On the stationary state of Kohonen's self-organizing sensory mapping". Biological Cybernetics, vol. 54, pp. 99-106.
[36] Simic, P.D. (1990). "Statistical mechanics as the underlying theory of 'elastic' and 'neural' optimizations". Network 1:89-103.
[37] Smith, K. (1996). "An Argument for Abandoning the Traveling Salesman Problem as a Neural Network Benchmark". IEEE Transactions on Neural Networks, Vol. 7, No. 6.
[38] Vieira, F.C., A.D. Doria Neto, and J.A. Ferreira Costa. (2003). "An efficient approach to the travelling salesman problem using selforganizing maps". International Journal of Neural Systems, vol. 2, pp. 59-66.
[39] Volgenant, T. and R. Jonker. (1987). "On some generalizations of the traveling salesman problem". Journal of the Operational Research Society, 38, 1073-1079.