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

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.

Authors:

• J.-C. Créput
• A. Koukam
• A. Hajjam

Keywords:

• Evolutionary algorithm
• self-organizing map
• clustering and vehicle routing.

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.