Kohonen maps for solving a class of location-allocation problems.

*(English)*Zbl 0943.90007Summary: Location-allocation problems occur whenever more than one facility need to be located to serve a set of demand centers and it is not known or fixed a priori their allocation to the supply centers. This paper deals with a continuous space problem in which demand centers are independently served from a given number of independent, uncapacitated supply centers. Installation costs are assumed not to depend on neither the actual location nor the actual throughput of the supply centers. Transportation costs are considered to be proportional to the square Euclidean distance travelled and a minimum criterion is adopted. The problem is recognized as identical to certain cluster analysis and vector quantization problems. Such a relationship leads to applying Kohonen maps, which are artificial neural networks capable of extracting the main features, i.e. the structure, of the input data through a self-organizing process based on local adaptation rules. This approach has previously been applied to other combinatorial problems such as the travelling salesperson problem.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90B80 | Discrete location and assignment |

68T05 | Learning and adaptive systems in artificial intelligence |

PDF
BibTeX
XML
Cite

\textit{S. Lozano} et al., Eur. J. Oper. Res. 108, No. 1, 106--117 (1998; Zbl 0943.90007)

Full Text:
DOI

##### References:

[1] | Angéniol, B.; de la Croix Vaubois, G.; le Texier, J.Y., Self-organizing feature maps and the traveling salesman problem, Neural networks, 1, 289-293, (1988) |

[2] | Baxter, J., Local optima avoidance in depot location, Journal of the operational research society, 32, 815-819, (1981) |

[3] | Baxter, J., Depot location: A technique for the avoidance of local optima, European journal of operational research, 18, 208-214, (1984) |

[4] | Burke, L.I.; Damany, P., The guilty net for the traveling salesman problem, Computers and operations research, 19, 255-265, (1992) · Zbl 0757.90081 |

[5] | Burke, L.I., Neural methods for the traveling salesman problem: insights from operations research, Neural networks, 7, 681-690, (1994) · Zbl 0820.90111 |

[6] | Cavalier, T.M.; Sherali, H.D., Euclidean distance location-allocation problems with uniform demands over convex polygons, Transportation science, 20, 107-116, (1986) · Zbl 0646.90030 |

[7] | Cooper, L., Location-allocation problems, Operations research, 11, 331-343, (1963) · Zbl 0113.14201 |

[8] | Cooper, L., Heuristic methods for location-allocation problems, SIAM review, 6, 37-53, (1964) · Zbl 0956.90014 |

[9] | Crainic, T.G.; Gendreau, M.; Soriano, P.; Toulouse, M., A tabu search procedure for multicommodity location/allocation with balancing requirements, () · Zbl 0775.90289 |

[10] | Drezner, Z., The planar two-center and two-Median problems, Transportation science, 18, 351-361, (1984) |

[11] | El Ghaziri, H., Solving routing problems by a selforganizing map, (), 829-834 |

[12] | Favata, F.; Walker, R., A study of the application of Kohonen-type neural networks to the travelling salesman problem, Biological cybernetics, 64, 463-468, (1991) · Zbl 0722.92002 |

[13] | Fort, J.C., Solving a combinatorial problem via selforganizing process: an application of the Kohonen algorithm to the TSP, Biological cybernetics, 59, 33-40, (1988) · Zbl 0641.92020 |

[14] | Francis, R.L.; White, J.A., Facility layout and location: an analytical approach, (1974), Prentice-Hall Englewood Cliffs |

[15] | Fritzke, B., Let it grow — self-organizing feature maps with problem dependent cell structure, (), 403-408 |

[16] | Gosh, A.; Harche, F., Location-allocation models in the private sector: progress, problems and prospects, Location science, 1, 57-79, (1993) |

[17] | Gosh, A.; Rushton, G., Spatial analysis and location-allocation models, (1987), Van Nostrand Reinhold New York |

[18] | Grabec, I., Self-organization of neurons described by the maximum-entropy principle, Biological cybernetics, 63, 403-409, (1990) · Zbl 0704.92004 |

[19] | Gray, R.M., Vector quantization, IEEE ASSP magazine, 4-29, (1984), april |

[20] | Jacobsen, S.K.; Madsen, O.B.G., A comparative study of heuristics for a two-level routing location problem, European journal of operational research, 5, 378-387, (1980) · Zbl 0441.90028 |

[21] | Jeffries, C.; Niznik, T., Easing the conscience of the guilty net, Computers and operations research, 21, 961-968, (1994) · Zbl 0815.90132 |

[22] | Jockusch, S.; Ritter, H., Self-organizing maps: local competition and evolutionary optimization, Neural networks, 7, 1229-1239, (1994) |

[23] | Johnson, M.E., Multivariate statistical simulation, (1987), Wiley Chichester · Zbl 0604.62056 |

[24] | Kleijnen, J.P.C.; van Groenendaal, W., Simulation. A statistical perspective, (1992), Wiley Chichester · Zbl 0797.90001 |

[25] | Kohonen, T., Self-organized formation of topologically correct feature maps, Biological cybernetics, 43, 59-69, (1982) · Zbl 0466.92002 |

[26] | Kohonen, T., Self-organization and associative memory, (1989), Springer-Verlag New York · Zbl 0528.68062 |

[27] | Kohonen, T., Self-organizing maps: optimization approaches, (), 981-990 |

[28] | Krarup, J.; Pruzan, P.M., Ingredients of locational analysis, (), 1-54 · Zbl 0728.90053 |

[29] | Kuenne, R.E.; Soland, R.M., Exact and approximate solutions to the multisource Weber problem, Mathematical programming, 3, 193-209, (1972) · Zbl 0245.90021 |

[30] | Laporte, G., Location-routing problems, (), 163-197 |

[31] | Linde, Y.; Buzo, A.; Gray, R., An algorithm for vector quantizer design, IEEE transactions on communications, 28, 84-95, (1980) |

[32] | Lithwhiler, D.; Aly, A.A., Large region location problems, Computers and operations research, 6, 1-12, (1979) |

[33] | Liu, C.-M.; Kao, R.-L.; Wang, A.-H., Solving location-allocation problems with rectilinear distances by simulated annealing, Journal of the operational research society, 45, 1304-1315, (1994) · Zbl 0812.90095 |

[34] | Loukas, S.; Kemp, C.D., On computer sampling from trivariate and multivariate discrete distributions, Journal of statistical computation and simulation, 17, 113-123, (1983) · Zbl 0506.65003 |

[35] | Love, R.F.; Juel, H., Properties and solutions methods for large location-allocation problems, Journal of the operational research society, 33, 443-452, (1982) · Zbl 0478.90017 |

[36] | Mangiameli, P.; Chen, S.K.; West, D., A comparison of SOM neural network and hierarchical clustering methods, European journal of operational research, 93, 402-417, (1996) · Zbl 0912.90209 |

[37] | Martinetz, T.; Schulten, K., A ‘neural-gas’ network learns topologies, (), 397-402 |

[38] | Marucheck, A.S.; Aly, A.A., An efficient algorithm for the location-allocation problem with rectangular regions, Naval research logistics quarterly, 28, 309-323, (1981) · Zbl 0462.90029 |

[39] | Michelot, C., Properties of a class of location-allocation problems, Cahiers CERO, 29, 105-114, (1987) · Zbl 0642.90033 |

[40] | Moreno, J.; Rodriguez, C.; Jiménez, N., Heuristic cluster algorithm for multiple facility location-allocation problem, Recherche opirationnelle, 25, 97-107, (1991) · Zbl 0726.90043 |

[41] | Mulvey, J.M.; Crowder, H., Cluster analysis: an application of Lagrangean relaxation, Management science, 25, 329-340, (1979) · Zbl 0415.90085 |

[42] | Okabe, A.; Boots, B.; Sugihara, K., Spatial tessellations: concepts and applications of Voronoi diagrams, (1992), Wiley Chichester · Zbl 0877.52010 |

[43] | ReVelle, C.; Marks, D.; Liebman, J.C., An analysis of private and public sector location models, Management science, 16, 692-707, (1970) · Zbl 0195.21901 |

[44] | Ritter, H., Learning with the self-organizing map, (), 379-384 |

[45] | Ritter, H.; Martinetz, T.; Schulten, K., Neural computation and self-organizing maps, (1992), Addison-Wesley Reading · Zbl 0752.68068 |

[46] | Rosing, K.E., A background paper on aspects of the multi-Weber problem, (), 88/3 · Zbl 0760.90064 |

[47] | Wang, S., A self-organizing approach to managerial nonlinear discriminant analysis: A hybrid method of linear discriminant analysis and neural networks, INFORMS journal on computing, 8, 118-124, (1996) · Zbl 0864.62042 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.