Local improvement in planar facility location using vehicle routing. (English) Zbl 1163.90613
Summary: In physical distribution the location of depots and vehicle routes are interdependent problems, but they are usually treated independently. Location-routing is the study of solving locational problems such that routing considerations are taken into account. We present an iterative heuristic for the location-routing problem on the plane. For each depot the Weber problem is solved using the end-points of the routes found previously as input nodes to the Weiszfeld procedure. Although the improvements found are usually small they show that it pays not to ignore the routing aspects when solving continuous location problems. Possible research avenues in continuous location-routing will also be suggested.
MSC:
| 90B80 | Discrete location and assignment |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
VRPReferences:
| [1] | Brimberg, J., & Salhi, S. (2005). A continuous location-allocation problem with zone-dependent fixed costs. Annals of Operations Research, 136, 99–115. · Zbl 1114.90054 · doi:10.1007/s10479-005-2041-5 |
| [2] | Burness, R. C., & White, J. A. (1976). The traveling salesman location problem. Transportation Science, 10, 348–360. · doi:10.1287/trsc.10.4.348 |
| [3] | Christofides, N., Mingozzi, A., & Toth, P. (1979). The vehicle routing problem. In N. Christofides, A. Mingozzi, P. Toth & C. Sandi (Eds.), Combinatorial optimization. Chichester: Wiley. · Zbl 0413.90075 |
| [4] | Drezner, Z., Klamroth, K., Schöbel, A., & Wesolowsky, G. (2001). The Weber problem. In Z. Drezner & H. W. Hamacher (Eds.), Facility location: applications and theory. Berlin: Springer. · Zbl 1041.90023 |
| [5] | Eilon, S., Watson-Gandy, C. D. T., & Christofides, N. (1971). Distribution management: mathematical modelling and practical analysis. London: Griffin. |
| [6] | Laporte, G. (1988). Location-routing problems. In B. L. Golden & A. A. Assad (Eds.), Vehicle routing: methods and studies. Amsterdam: Elsevier. · Zbl 0644.90030 |
| [7] | Laporte, G., Gendreau, M., Potvin, J.-Y., & Semet, F. (2000). Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, 7, 285–300. · doi:10.1111/j.1475-3995.2000.tb00200.x |
| [8] | Mladenović, N., Brimberg, J., Hansen, P., & Perez, M. (2007). The p-median problem: a survey of metaheuristic approaches. European Journal of Operational Research, 179, 927–939. · Zbl 1163.90610 · doi:10.1016/j.ejor.2005.05.034 |
| [9] | Nagy, G., & Salhi, S. (1996). A nested location-routing heuristic using route length estimation. Studies in Locational Analysis, 10, 109–127. · Zbl 0885.90071 |
| [10] | Nagy, G., & Salhi, S. (2007). Location-routing: issues, models and methods. European Journal of Operational Research, 177, 649–672. · Zbl 1109.90056 · doi:10.1016/j.ejor.2006.04.004 |
| [11] | Perl, J., & Daskin, M. S. (1985). A warehouse location-routing problem. Transportation Research, 19B, 381–396. |
| [12] | Pfeiffer, B., & Klamroth, K. (2006, to appear). A unified model for Weber problems with continuous and network distances. Computers and Operations Research. · Zbl 1141.90024 |
| [13] | Plastria, F. (1995). Continuous location problems. In Z. Drezner (Ed.), Facility location: a survey of applications and methods. New York: Springer. |
| [14] | Rand, G. K. (1976). Methodological choices in depot location studies. Operational Research Quarterly, 27, 241–249. · doi:10.1057/jors.1976.39 |
| [15] | Salhi, S. (1987). The integration of routing into the location-allocation and vehicle fleet composition problems (PhD dissertation). Lancaster: Lancaster University. |
| [16] | Salhi, S. (1997). A perturbation heuristic for a class of location problems. Journal of the Operational Research Society, 48, 1233–1240. · Zbl 0895.90132 |
| [17] | Salhi, S., & Fraser, M. (1996). An integrated heuristic approach for the combined location vehicle fleet mix problem. Studies in Locational Analysis, 8, 3–21. · Zbl 1176.90362 |
| [18] | Salhi, S., & Nagy, G. (1999). Consistency and robustness in location-routing. Studies in Locational Analysis, 13, 3–19. · Zbl 0981.90043 |
| [19] | Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European Journal of Operational Research, 39, 150–156. · Zbl 0658.90050 · doi:10.1016/0377-2217(89)90188-4 |
| [20] | Salhi, S., & Sari, M. (1997). Models for the multi-depot vehicle fleet mix problem. European Journal of Operational Research, 103, 95–112. · Zbl 0922.90061 · doi:10.1016/S0377-2217(96)00253-6 |
| [21] | Schwardt, M., & Dethloff, J. (2005). Solving a continuous location-routing problem by use of a self-organising map. International Journal of Physical Distribution & Logistics Management, 35, 390–408. · doi:10.1108/09600030510611639 |
| [22] | Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics, 123, 487–512. · Zbl 1060.90065 · doi:10.1016/S0166-218X(01)00351-1 |
| [23] | Wassan, N. A. (2006). A reactive tabu search for the vehicle routing problem. Journal of the Operational Research Society, 57, 111–116. · Zbl 1121.90131 · doi:10.1057/palgrave.jors.2601957 |
| [24] | Weiszfeld (Vázsonyi), E. (1937). Sur le point pour lequel la somme des distances de n points donnés est minimum. Tôhoku Mathematical Journal, 43, 355–386. · JFM 63.0583.01 |
| [25] | Zainuddin, Z. M., & Salhi, S. (2007). A perturbation-based heuristic for the capacitated multisource Weber problem. European Journal of Operational Research, 179, 1194–1207. · Zbl 1127.90048 · doi:10.1016/j.ejor.2005.09.050 |
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.
