Capacitated facility location problem on random input data

A. A. Kurochkin

Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 5, pp. 23-39.

Résumé

The Capacitated Facility Location Problem (CLFP) on random input data is considered. It is assumed that the transportation costs take random values according to discrete uniform distribution on the integer segment $[1,r]$. For CFLP with uniform capacity restrictions an algorithm with time complexity $O(n\log m)$ is constructed and conditions of asymptotical optimality are established (where $n$ is the number of consumers and $m$ is the number of facilities). For CFLP with various capacities an algorithm with time complexity $O(n^{2(1-\theta)}m)$ is given and the conditions of asymptotical optimality for some $\theta\frac12$ are established. Ill. 1, bibliogr. 17.

Détail

Keywords: facility location problem, probability, asymptotical optimality.
Mots-clés : polynomial algorithm

Bibliographie

[1] Ageev A. A., Gimadi E. Kh., Kurochkin A. A., “Polinomialnyi algoritm resheniya zadachi razmescheniya na tsepi s odinakovymi proizvodstvennymi moschnostyami predpriyatii”, Diskret. analiz i issled. operatsii, 16:5 (2009), 3–18 | MR | Zbl

[2] Voznyuk I. P., Gimadi E. Kh., Filatov M. Yu., “Asimptoticheski tochnyi algoritm dlya resheniya zadachi razmescheniya s ogranichennymi ob'ëmami proizvodstva”, Diskret. analiz i issled. operatsii. Ser. 2, 8:2 (2001), 3–16 | MR | Zbl

[3] Gimadi E. Kh., “Effektivnyi algoritm resheniya zadachi razmescheniya s oblastyami obsluzhivaniya, svyaznymi otnositelno atsiklicheskoi seti”, Upravlyaemye sistemy, 23, 1983, 12–23 | MR | Zbl

[4] Gimadi E. Kh., Matematicheskie modeli i metody issledovaniya operatsii, Uchebn. posobie, SibGUTI, Novosibirsk, 2009, 122 pp.

[5] Gimadi E. Kh., Kurochkin A. A., “Uniform capacitated facility location problem with random input data”, J. Math. Sci., 188:4 (2013), 359–377 | DOI | MR | Zbl | Zbl

[6] Gimadi E. Kh., Perepelitsa V. A., “Asimptoticheskii podkhod k resheniyu zadachi kommivoyazhera”, Upravlyaemye sistemy, 12, In-t matematiki SO AN SSSR, Novosibirsk, 1974, 35–45 | Zbl

[7] Golshtein E. G., Yudin D. B., Zadachi lineinogo programmirovaniya transportnogo tipa, Nauka, M., 1969, 494 pp. | Zbl

[8] Ageev A. A., “A polynomial-time algorithm for the facility location problem with uniform hard capacities on path graphs”, Proc 2nd Int. Workshop Discrete Optimization Methods in Production and Logistics, DOM'2004 (Omsk–Irkutsk, July 20–27, 2004), Nasledie, Dialog-Sibir, Omsk, 2004, 28–32

[9] Aikens C. H., “Facility location models for distribution planning”, Eur. J. Oper. Res., 22:3 (1985), 263–279 | DOI | MR | Zbl

[10] Akinc U., Khumawala B. M., “An efficient branch and bound algorithm for the capacitated warehouse location problem”, Manage. Sci., 23:6 (1977), 585–594 | DOI | MR | Zbl

[11] Angluin D., Valiant L. G., “Fast probabilistic algorithms for Hamiltonian circuits and matchings”, J. Comput. Syst. Sci., 18:2 (1979), 155–193 | DOI | MR | Zbl

[12] Chudak F., Williamson D., “Improved approximation algorithms for capacitated facility location problems”, Math. Program., 102:2 (2005), 207–222 | DOI | MR | Zbl

[13] Garey M. R., Johnson D. S., Computers and intractablity, Freeman, San Francisco, 1979, 340 pp. | MR | Zbl

[14] Karp R. M., “The probabilistic analysis of some combinatorial algorithms”, Algorithms and complexity: new directions and recent results, Acad. Press, New York, 1976, 1–19 | MR

[15] Korupolu M., Plaxton C., Rajaraman R., “Analysis of a local search heuristic for facility location problems”, J. Algorithms, 37:1 (2000), 146–188 | DOI | MR | Zbl

[16] Kuehn A. A., Hamburger M. J., “A heuristic program for locating warehouses”, Manage. Sci., 9:4 (1963), 643–666 | DOI

[17] Piersma N., “A probabilistic analysis of the capacitated facility location problem”, J. Comb. Optim., 3:1 (1999), 31–50 | DOI | MR | Zbl