Solving continuous location-districting problems with Voronoi diagrams. (English) Zbl 1163.90621
Summary: Facility location problems are frequent in OR literature. In districting problems, on the other hand, the aim is to partition a territory into smaller units, called districts or zones, while an objective function is optimized and some constraints are satisfied, such as balance, contiguity, and compactness. Although many location and districting problems have been treated by assuming the region previously partitioned into a large number of elemental areas and further aggregating these units into districts with the aid of a mathematical programming model, continuous approximation, on the other hand, is based on the spatial density of demand, rather than on precise information on every elementary unit. Voronoi diagrams can be successfully used in association with continuous approximation models to solve location-districting problems, specially transportation and logistics applications. We discuss in the paper the context in which approximation algorithms can be used to solve this kind of problem.
MSC:
| 90B85 | Continuous location |
References:
| [1] | (Drezner, Z., Facility location: a survey of application and methods (1995), Springer: Springer Berlin) |
| [2] | (Drezner, Z.; Hamacher, H., Facility location: applications and theory (2002), Springer: Springer Berlin) · Zbl 0988.00044 |
| [3] | Hale, T. S.; Moberg, C. R., Location science research: a review, Annals of Operations Research, 123, 21-35 (2003) · Zbl 1137.90598 |
| [4] | Preparata, F. P.; Shamos, M. I., Computational geometry—an introduction (1985), Springer: Springer New York · Zbl 0759.68037 |
| [5] | Hojati, M., Optimal political districting, Computers & Operations Research, 23, 12, 1147-1161 (1996) · Zbl 0876.90062 |
| [6] | Mehrotra, A.; Johnson, E. L.; Nemhauser, G. L., An optimization based heuristic for political districting, Management Science, 44, 8, 1100-1114 (1998) · Zbl 0988.90542 |
| [7] | Boskaya, B.; Erkut, E.; Laporte, G., A tabu search heuristic and adaptive memory procedure for political districting, European Journal of Operational Research, 144, 12-26 (2003) · Zbl 1037.90535 |
| [8] | Williams, J. C., Political redistricting: a review, Papers in Regional Science, 74, 13-40 (1995) |
| [9] | Schoepfle, O. B.; Church, R. L., A new network representation of a “classic” school districting problem, Socio-Economic Planning Science, 25, 3, 189-197 (1991) |
| [10] | D’Amico, S. J.; Wang, S. J.; Batta, R.; Rump, C. M., A simulated annealing approach to police district design, Computers & Operations Research, 29, 6, 667-684 (2002) · Zbl 0995.90609 |
| [11] | Zoltners, A. A.; Sinha, P., Sales territory alignment: a review and model, Management Science, 29, 11, 1237-1256 (1983) · Zbl 0526.90055 |
| [12] | Boots, B.; South, R., Modeling retail trade areas using higher-order, multiplicatively weighted Voronoi diagrams, Journal of Retailing, 73, 4, 519-536 (1997) |
| [13] | Muyldermans, L.; Cattrysse, D.; Van Oudheusden, D.; Lotan, T., Districting for salt spreading operations, European Journal of Operational Research, 139, 3, 521-532 (2002) · Zbl 0995.90009 |
| [14] | Zhou, G.; Min, H.; Gen, M., The balanced allocation of customers to multiple distribution centers in the supply chain network: a genetic algorithm approach, Computers & Industrial Engineering, 43, 251-261 (2002) |
| [15] | Langevin, A.; Saint-Mleux, Y., A decision support system for physical distribution planning, Revue des Systèmes de Décisions, 1, 2-3, 273-286 (1992) |
| [16] | Novaes, A. G.; Graciolli, O. D., Designing multi-vehicle tours in a grid-cell format, European Journal of Operational Research, 119, 613-634 (1999) · Zbl 0938.90008 |
| [17] | Novaes, A. G.; Souza de Cursi, J. E.; Graciolli, O. D., A continuous approach to the design of physical distribution systems, Computers & Operations Research, 27, 9, 877-893 (2000) · Zbl 0972.90003 |
| [18] | Langevin, A.; Mbaraga, P.; Campbell, J. F., Continuous approximation models in freight distribution: an overview, Transportation Research B, 30, 3, 163-188 (1996) |
| [19] | Dasci, A.; Verter, V., A continuous model for production-distribution system design, European Journal of Operational Research, 129, 287-298 (2001) · Zbl 0980.90036 |
| [20] | Okabe, A.; Boots, B.; Sugihara, K., Spatial tessellations concepts and applications of Voronoi diagrams (2000), Wiley: Wiley Chichester · Zbl 0946.68144 |
| [21] | Suzuki, A.; Okabe, A., Using Voronoi diagrams, (Drezner, Z., Facilty location: a survey of applications and methods (1995), Springer: Springer New York), 103-118 |
| [22] | Galvão, L. C.; Novaes, A. G.; de Cursi, J. E.S.; Souza, J. C., A multiplicatively-weighted Voronoi diagram approach to logistics districting, Computers & Operations Research, 33, 93-114 (2006) · Zbl 1088.90004 |
| [23] | da Silva ACL. Districting strategies in logistics problems using Voronoi diagrams with obstacles. Doctoral Dissertation, Federal University of Santa Catarina, Brazil; 2004 [in Portuguese].; da Silva ACL. Districting strategies in logistics problems using Voronoi diagrams with obstacles. Doctoral Dissertation, Federal University of Santa Catarina, Brazil; 2004 [in Portuguese]. |
| [24] | Aurenhammer, F., Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys, 23, 3, 345-405 (1991) |
| [25] | Hoff III K, Culver T, Keyser J, Lin MC, Manocha D. Interactive motion planning using hardware-accelerated computation of generalized Voronoi diagrams. In: Proceedings of the 2000 IEEE international conference on robotics & automation. San Francisco, CA; 2000. p. 2931-2937.; Hoff III K, Culver T, Keyser J, Lin MC, Manocha D. Interactive motion planning using hardware-accelerated computation of generalized Voronoi diagrams. In: Proceedings of the 2000 IEEE international conference on robotics & automation. San Francisco, CA; 2000. p. 2931-2937. |
| [26] | Okabe, A.; Suzuki, A., Locational optimization problems solved through Voronoi diagrams, European Journal of Operational Research, 98, 445-456 (1997) · Zbl 0930.90059 |
| [27] | Fortune, S., A sweepline algorithm for Voronoi diagrams, Algorithmica, 2, 153-174 (1987) · Zbl 0642.68079 |
| [28] | Samet, H., Hierarchical data structures and algorithms for computer graphics, IEEE Computer Graphics & Applications, 48-68 (May 1988) |
| [29] | Klein, R., Concrete and abstract Voronoi diagrams (1989), Springer: Springer Berlin · Zbl 0699.68005 |
| [30] | Daganzo, C. F., The distance traveled to visit N points with a maximum of C stops per vehicle: an analytic model and an application, Transportation Science, 18, 331-350 (1984) |
| [31] | Newell, G. F.; Daganzo, C. F., Design of multiple-vehicle delivery tours—I. A ring-radial network, Transportation Research B, 20B, 5, 345-363 (1986) |
| [32] | Han, A. F.W.; Daganzo, C. F., Distributing nonstorable items without transhipments, Transportation Research Record, 1061, 32-41 (1986) |
| [33] | Daganzo, C. F., Logistics systems analysis (1996), Springer: Springer Berlin · Zbl 0912.90115 |
| [34] | Boor, C., A practical guide to splines (2001), Springer: Springer New York · Zbl 0987.65015 |
| [35] | Bathe, K., Finite element procedures in engineering analysis (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs |
| [36] | Hamacher, H. W.; Liebers, A.; Schöbel, A.; Wagner, D.; Wagner, F., Locating new stops in a railway network, Electronic Notes in Theoretical Computer Science, 50, 1 (2001), 11pp |
| [37] | Laporte, G.; Mesa, J. A.; Ortega, F. A., Locating stations on rapid transit lines, Computers & Operations Research, 29, 741-759 (2002) · Zbl 0995.90062 |
| [38] | Saka, A. A., Model for determining optimum bus-stop spacing in urban areas, Journal of Transportation Engineering, 195-199 (May-June 2001) |
| [39] | Sullivan S, Morrall J. Walking distances to and from light-rail transit stations. Transportation Research Record 1538, Washington, DC: Transportation Research Board; 1996.; Sullivan S, Morrall J. Walking distances to and from light-rail transit stations. Transportation Research Record 1538, Washington, DC: Transportation Research Board; 1996. |
| [40] | Hooke, R.; Jeeves, T. A., Direct search solution of numerical and statistical problems, Journal of the Association for Computing Machinery, 8, 212-229 (1962) · Zbl 0111.12501 |
| [41] | Pinter, J., Global optimization in action (1995), Kluwer Academic: Kluwer Academic Boston |
| [42] | Souza de Cursi JE. Minimisation stochastique de fonctionnelles non convexes en dimension infinie. Publications du service de Mathématiques de l’Ecole Centrale Nantes, France; 1992. Available at \(\langle;\) http://meca.insa-rouen.fr/\( \sim;\rangle;\); Souza de Cursi JE. Minimisation stochastique de fonctionnelles non convexes en dimension infinie. Publications du service de Mathématiques de l’Ecole Centrale Nantes, France; 1992. Available at \(\langle;\) http://meca.insa-rouen.fr/\( \sim;\rangle;\) |
| [43] | Pogu, M.; Souza de Cursi, J. E., Global optimization by random perturbation of the gradient method with a fixed parameter, Journal of Global Optimization, 5, 159-180 (1994) · Zbl 0827.90132 |
| [44] | Autrique, L.; Souza de Cursi, J. E., Une méthode mixte stochastique/déterministe pour l’identification en vulcanisation, APII(RAIRO), 28, 3, 263-282 (1994) |
| [45] | Autrique, L.; Souza de Cursi, J. E., On stochastic modification for global optimization problems: an efficient implementation for the control of the vulcanization process, International Journal of Control, 67, 1, 1-21 (1997) · Zbl 0879.93060 |
| [46] | Cortes, M. B.S.; Souza de Cursi, J. E., Approximate Gaussian distributions in optimization by random perturbation methods, Applied Numerical Mathematics, 30, 23-30 (1999) · Zbl 0961.90071 |
| [47] | Gonçalves, M. B.; Souza de Cursi, J. E., Parameter estimation in a trip model by random perturbation of a descent method, Transportation Research, part B, 35, 2, 137-161 (2001) |
| [48] | Bouhadi, M.; Ellaia, R.; Souza de Cursi, J. E., Stochastic perturbation methods for affine restrictions, (Pardalos, P.; Floudas, N., Advances in convex analysis and global optimisation (2001), Kluwer Academic: Kluwer Academic Boston), 489-500 · Zbl 1049.90047 |
| [49] | Bouhadi, M.; Ellaia, R.; Souza de Cursi, J. E., Global optimization under nonlinear restrictions by using stochastic perturbations of the projected gradient, (Pardalos, P.; Floudas, N., Advances in convex analysis and global optimization (2004), Kluwer Academic: Kluwer Academic Boston), 541-562 · Zbl 1176.90649 |
| [50] | Newell, G. F.; Daganzo, C. F., Design of multiple-vehicle delivery tours—II other metrics, Transportation Research B, 20B, 5, 365-376 (1986) |
| [51] | Larson, R. C.; Odoni, A. R., Urban operations research (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
