×

zbMATH — the first resource for mathematics

Location-routing: issues, models and methods. (English) Zbl 1109.90056
Summary: This paper is a survey of location-routing: a relatively new branch of locational analysis that takes into account vehicle routing aspects. We propose a classification scheme and look at a number of problem variants. Both exact and heuristic algorithms are investigated. Finally, some suggestions for future research are presented.

MSC:
90B80 Discrete location and assignment
90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
VRP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albareda-Sambola, M., 2003. Models and Algorithms for Location-Routing and Related Problems. PhD dissertation, Catalonia Polytechnic University.
[2] Albareda-Sambola, M.; Díaz, J.A.; Fernández, E., A compact model and tight bounds for a combined location-routing problem, Computers and operations research, 32, 407-428, (2005) · Zbl 1061.90016
[3] Albareda-Sambola, M., Fernández, E., Laporte, G., in press. Heuristic and lower bound for a stochastic location-routing problem. European Journal of Operational Research, doi:10.1016/j.ejor.2005.04.051. · Zbl 1163.90582
[4] Ambrosino, D.; Scutellà, M.G., Distribution network design: new problems and related models, European journal of operational research, 165, 610-624, (2005) · Zbl 1062.90008
[5] Averbakh, I.; Berman, O., Routing and location-routing p-delivery men problems on a path, Transportation science, 28, 184-197, (1994)
[6] Averbakh, I.; Berman, O., Probabilistic sales-delivery man and sales-delivery facility location problems on a tree, Transportation science, 29, 184-197, (1995) · Zbl 0860.90058
[7] Averbakh, I.; Berman, O., A simple heuristic for m-machine flow-shop and its applications in routing-scheduling problems, Operations research, 47, 165-170, (1999) · Zbl 1046.90027
[8] Averbakh, I.; Berman, O., Minmax p-traveling salesmen location problems on a tree, Annals of operations research, 110, 55-62, (2002) · Zbl 1013.90103
[9] Averbakh, I.; Berman, O.; Simchi-Levi, D., Probabilistic a priori routing-location problems, Naval research logistics, 41, 973-989, (1994) · Zbl 0830.90086
[10] Aykin, T., The hub location and routing problem, European journal of operational research, 83, 200-219, (1995) · Zbl 0903.90110
[11] Baita, F.; Ukovich, W.; Pesenti, R.; Favaretto, D., Dynamic routing-and-inventory problem: A review, Transportation research A, 32, 585-598, (1998)
[12] Balakrishnan, A.; Ward, J.E.; Wong, R.T., Integrated facility location and vehicle routing models: recent work and future prospects, American journal of mathematical and management sciences, 7, 35-61, (1987)
[13] Barreto, S.S., 2004, Análise e Modelização de Problemas de Localização-Distribuição. PhD Dissertation, Aveiro University.
[14] Barreto, S.S., 2003. http://sweet.ua.pt/ iscf143/.
[15] Barreto, S., Ferreira, C., Paixão, J., Sousa Santos, B., in press. Using clustering analysis in a capacitated location-routing problem. European Journal of Operational Research, doi:10.1016/j.ejor.2005.06.074. · Zbl 1163.90589
[16] Beasley, J.; Nascimento, E.M., The vehicle routing-allocation problem: A unifying framework, Top, 4, 65-86, (1996) · Zbl 0856.90042
[17] Bednar, L.; Strohmeier, E., Lagerstandortoptimierung und fuhrparkeinsatzplanung in der konzumgüter-industrie, Zeitschrift für operations research, 23, B89-B104, (1979) · Zbl 0404.90044
[18] Berger, R., 1997. Location-routing models for distribution system design, PhD dissertation, Northwestern University.
[19] Berman, O.; Krass, D., Facility location problems with stochastic demands and congestion, (), 329-371 · Zbl 1061.90068
[20] Berman, O.; Jaillet, P.; Simchi-Levi, D., Location-routing problems with uncertainty, (), 427-452
[21] Berman, O.; Simchi-Levi, D., Minisum location of a traveling salesman, Networks, 16, 239-254, (1986) · Zbl 0644.90031
[22] Berman, O.; Simchi-Levi, D., Finding the optimal a priori tour and location of a traveling salesman with nonhomogenous customers, Transportation science, 22, 148-154, (1988) · Zbl 0653.90082
[23] Bertsimas, D.J., Traveling salesman facility location problems, Transportation science, 23, 184-191, (1989) · Zbl 0682.90039
[24] Billionnet, A.; Elloumi, S.; Grouz-Djerbi, L., Designing radio-mobile access networks based on synchronous digital hierarchy rings, Computers and operations research, 32, 379-394, (2005) · Zbl 1073.90522
[25] Boffey, B.; Karkazis, J., Models and methods for location and routing decision relating to hazardous materials, Studies in locational analysis, 5, 149-166, (1993)
[26] Boffey, B.; Karkazis, J., Location, routing and the environment, (), 453-466
[27] Boffey, B., Galvão, R., Espejo, L., in review. Capacity effects in the location of facilities with immobile servers. European Journal of Operational Research.
[28] Bookbinder, J.H.; Reece, K.E., Vehicle routing considerations in distribution system design, European journal of operational research, 37, 204-213, (1988) · Zbl 0652.90036
[29] Branco, I.M.; Coelho, J.D., The Hamiltonian p-Median problem, European journal of operational research, 47, 86-95, (1990) · Zbl 0706.90039
[30] Bruns, A.D., 1998. Zweistufige Standortplanung unter Berücksichtigung von Tourenplanungsaspekten - Primale Heuristiken und Lokale Suchverfahren, PhD Dissertation, Sankt Gallen University.
[31] Bruns, A.; Klose, A.; Stähly, P., Restructuring of swiss parcel delivery services, OR spektrum, 22, 285-302, (2000) · Zbl 0970.90044
[32] Burness, R.C.; White, J.A., The traveling salesman location problem, Transportation science, 10, 348-360, (1976)
[33] Cappanera, P.; Gallo, G.; Maffioli, F., Discrete facility location and routing of obnoxious activities, Discrete applied mathematics, 133, 3-28, (2004) · Zbl 1053.90077
[34] Çetiner, S., 2003. An Iterative Hub Location and Routing Problem for Postal Delivery Systems. MSc dissertation, Middle East Technical University.
[35] Chan, A.W.; Francis, R.L., A round-trip location problem on a tree graph, Transportation science, 10, 35-51, (1976)
[36] Chan, A.W.; Hearn, D.W., A rectilinear distance round-trip location problem, Transportation science, 11, 107-123, (1977)
[37] Chan, Y.; Carter, W.B.; Burnes, M.D., A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands, Computers and operations research, 28, 803-826, (2001) · Zbl 1027.90034
[38] Chao, I.-M., A tabu search method for the truck and trailer routing problem, Computers and operations research, 29, 33-51, (2002) · Zbl 1026.90102
[39] Chien, T.W., Heuristic procedures for practical-sized uncapacitated location-capacitated routing problems, Decision sciences, 24, 995-1021, (1993)
[40] Christofides, N.; Eilon, S., Expected distances in distribution problems, Operational research quarterly, 20, 437-443, (1969)
[41] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (), 315-338
[42] Cooper, L., The transportation-location problem, Operations research, 20, 94-108, (1972) · Zbl 0237.90036
[43] Daganzo, C.F., Logistics systems analysis, (2005), Springer Heidelberg
[44] Daskin, M.S.; Coullard, C.R.; Shen, Z.-J.M., An inventory-location problem: formulation, solution algorithm and computational results, Annals of operations research, 110, 83-106, (2002) · Zbl 1013.90001
[45] Díaz-Báñez, J.M.; Mesa, J.A.; Schöbel, A., Continuous location of dimensional structures, European journal of operational research, 152, 22-44, (2004) · Zbl 1040.90021
[46] Drezner, Z., Fast algorithms for the round trip location problem, IEE transactions, 14, 243-248, (1982)
[47] Drezner, Z.; Scott, C.; Song, J.-S., The central warehouse location problem revisited, IMA journal of management mathematics, 14, 321-336, (2003) · Zbl 1093.90021
[48] Drezner, Z.; Wesolowsky, G.O., A trajectory approach for the round-trip location problem, Transportation science, 16, 56-66, (1982)
[49] Erkut, E.; Verter, V., Hazardous material logistics, (), 467-506
[50] EWGLA, 2003. http://www.vub.ac.be/EWGLA/literature.html.
[51] Ferrer, L., Nagy, G., Wassan, N.A., in review. The vehicle routing problem with packing considerations.
[52] Gerdessen, J.C., Vehicle routing problem with trailers, European journal of operational research, 93, 135-147, (1996) · Zbl 0912.90117
[53] Ghiani, G.; Laporte, G., Eulerian location problems, Networks, 34, 291-302, (1999) · Zbl 0948.90085
[54] Giannikos, I., A multiobjective programming model for locating treatment sites and routing hazardous wastes, European journal of operational research, 104, 333-342, (1998) · Zbl 0955.90120
[55] Gunnarsson, H., Rönnqvist, M., Carlsson, D., in press. A combined terminal location and ship routing problem. Journal of the Operational Research Society.
[56] Hansen, P.H.; Hegedahl, B.; Hjortkjær, S.; Obel, B., A heuristic solution to the warehouse location-routing problem, European journal of operational research, 76, 111-127, (1994) · Zbl 0925.90245
[57] Hennes, H., Hamacher, H.W., in press. Integrated scheduling and location models: Single machine makespan problems. Studies in Locational Analysis. · Zbl 1167.90511
[58] Hindi, K.S.; Basta, T., Computationally efficient solution of a multiproduct, two-stage distribution-location problem, Journal of the operational research society, 45, 1316-1323, (1994) · Zbl 0812.90092
[59] 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
[60] Jamil, M.; Batta, R.; Malon, D.M., The traveling repairperson home base location problem, Transportation science, 28, 150-161, (1994) · Zbl 0820.90046
[61] Klose, A., 2005. http://www.wiwi.uni-wuppertal.de/TSCFLRP.1321.0.html.
[62] Kolen, A., The round-trip p-center and covering problem on a tree, Transportation science, 19, 222-234, (1985) · Zbl 0606.90041
[63] Kulcar, T., Optimizing solid waste collection in Brussels, European journal of operational research, 90, 26-44, (1996) · Zbl 0914.90186
[64] Labbé, M.; Laporte, G., Maximizing user convenience and postal service efficiency in post box location, Belgian journal of operational research, statistics and computer science, 26, 21-35, (1986)
[65] Labbé, M.; Laporte, G.; Rodríguez-Martín, I., Path, tree and cycle location, (), 187-204 · Zbl 0978.90064
[66] Labbé, M.; Laporte, G.; Rodríguez-Martín, I.; Salazar-González, J.J., Locating Median cycles in networks, European journal of operational research, 160, 457-470, (2005) · Zbl 1067.90109
[67] Labbé, M.; Rodríguez-Martín, I.; Salazar-Gonzalez, J.J., A branch-and-cut algorithm for the plant-cycle location problem, Journal of the operational research society, 55, 513-520, (2004) · Zbl 1060.90053
[68] Laporte, G., Location-routing problems, (), 163-198
[69] Laporte, G., A survey of algorithms for location-routing problems, Investigación operativa, 1, 93-123, (1989)
[70] Laporte, G.; Dejax, P.J., Dynamic location-routing problems, Journal of the operational research society, 40, 471-482, (1989) · Zbl 0665.90028
[71] Laporte, G.; Gendreau, M.; Potvin, J.-Y.; Semet, F., Classical and modern heuristics for the vehicle routing problem, International transactions in operational research, 7, 285-300, (2000)
[72] Laporte, G.; Louveaux, F.; Mercure, H., Models and exact solutions for a class of stochastic location-routing problems, European journal of operational research, 39, 71-78, (1989) · Zbl 0676.90019
[73] Laporte, G.; Nobert, Y., An exact algorithm for minimizing routing and operating costs in depot location, European journal of operational research, 6, 224-226, (1981) · Zbl 0451.90047
[74] Laporte, G.; Nobert, Y.; Arpin, D., An exact algorithm for solving a capacitated location-routing problem, Annals of operations research, 6, 293-310, (1986)
[75] Laporte, G.; Nobert, Y.; Pelletier, P., Hamiltonian location problems, European journal of operational research, 12, 82-89, (1983) · Zbl 0502.90021
[76] Laporte, G.; Nobert, Y.; Taillefer, S., Solving a family of multi-depot vehicle routing and location-routing problems, Transportation science, 22, 161-172, (1988) · Zbl 0662.90039
[77] Lee, Y.; Kim, S.-i.; Lee, S.; Kang, K., A location-routing problem in designing optical Internet access with WDM systems, Photonic network communications, 6, 151-160, (2003)
[78] Levy, L.; Bodin, L., The arc oriented location routing problem, Infor, 27, 74-94, (1989)
[79] Lin, C.K.Y.; Chow, C.K.; Chen, A., A location-routing-loading problem for bill delivery services, Computers and industrial engineering, 43, 5-25, (2002)
[80] Lischak, C., 2001, Standortplanung für einem Privaten Paketdienstleister, PhD dissertation, Technical University of Rhineland-Westphalia Aachen.
[81] Lischak, C., Triesch, E., in review. Location planning for a parcel delivery service.
[82] List, G.F.; Mirchandani, P.B., An integrated network/planar multiobjective model for routing and siting for hazardous materials and wastes, Transportation science, 25, 146-156, (1991)
[83] List, G.F.; Mirchandani, P.B.; Turnquist, M.A.; Zografos, K.G., Modeling and analysis for hazardous materials transportation: risk analysis, routing/scheduling and facility location, Transportation science, 25, 100-114, (1991)
[84] Liu, S.C.; Lee, S.B., A two-phase heuristic method for the multi-depot location routing problem taking inventory control decisions into considerations, International journal of advanced manufacturing technology, 22, 941-950, (2003)
[85] Madsen, O.B.G., Methods for solving combined two level location-routing problems of realistic dimensions, European journal of operational research, 12, 295-301, (1983)
[86] Maranzana, F.E., On the location of supply points to minimise transport costs, Operational research quarterly, 15, 261-270, (1964)
[87] Maze, T.H.; Khasnabis, S., Bus garage location planning with dynamic vehicle assignments: A methodology, Transportation research B, 19, 1-13, (1985)
[88] McDiarmid, C., Probability modelling optimal location of a travelling salesman, Journal of the operational research society, 43, 533-538, (1992) · Zbl 0756.90057
[89] Melechovský, J.; Prins, C.; Wolfler Calvo, R., A metaheuristic to solve a location-routing problem with non-linear costs, Journal of heuristics, 11, 375-391, (2005) · Zbl 1122.90382
[90] Melkote, S., 1996. Integrated Models of Facility Location and Network Design, PhD dissertation, Northwestern University.
[91] Melkote, S.; Daskin, M.S., An integrated model of facility location and transportation network design, Transportation research A, 35, 515-538, (2001)
[92] Mesa, J.A.; Boffey, T.B., A review of extensive facility location in networks, European journal of operational research, 95, 592-603, (1996) · Zbl 0926.90057
[93] Metters, R.D., Interdependent transportation and production activity at the united states postal service, Journal of the operational research society, 47, 27-37, (1996)
[94] Min, H., Consolidation terminal location-allocation and consolidated routing problems, Journal of business logistics, 17, 235-263, (1996)
[95] Min, H.; Jayaraman, V.; Srivastava, R., Combined location-routing problems: A synthesis and future research directions, European journal of operational research, 108, 1-15, (1998) · Zbl 0943.90008
[96] Moin, N.H., Salhi, S., in press. Inventory routing problems: A logistical overview. Journal of the Operational Research Society. · Zbl 1192.90012
[97] Mosheiov, G., The pickup delivery location problem on networks, Networks, 26, 243-251, (1995) · Zbl 0856.90066
[98] Murty, K.G.; Djang, P.A., The U.S. army national guard’s mobile training simulators location and routing problem, Operations research, 47, 175-182, (1999) · Zbl 0995.90581
[99] Nagy, G., 1996. Heuristic Methods for the Many-to-Many Location-Routing Problem, PhD dissertation, University of Birmingham.
[100] Nagy, G.; Salhi, S., Nested heuristic methods for the location-routing problem, Journal of the operational research society, 47, 1166-1174, (1996) · Zbl 0869.90019
[101] Nagy, G.; Salhi, S., A nested location-routing heuristic using route length estimation, Studies in locational analysis, 10, 109-127, (1996) · Zbl 0885.90071
[102] Nagy, G.; Salhi, S., The many-to-many location-routing problem, Top, 6, 261-275, (1998) · Zbl 0916.90182
[103] Nambiar, J.M.; Gelders, L.F.; Van Wassenhove, L.N., A large scale location-allocation problem in the natural rubber industry, European journal of operational research, 6, 183-189, (1981) · Zbl 0451.90044
[104] Nambiar, J.M.; Gelders, L.F.; Van Wassenhove, L.N., Plant location and vehicle routing in the Malaysian rubber smallholder sector: A case study, European journal of operational research, 38, 14-26, (1989)
[105] Ogryczak, W.; Studziński, K.; Zorychta, K., A solver for the multiobjective transshipment problem with facility location, European journal of operational research, 43, 53-64, (1989) · Zbl 0681.90035
[106] Ogryczak, W.; Studziński, K.; Zorychta, K., DINAS: A computer-assisted analysis system for multiobjective transshipment problems with facility location, Computers and operations research, 19, 637-647, (1992)
[107] Or, I.; Pierskalla, W.P., A transportation location-allocation model for regional blood banking, AIIE transactions, 11, 86-94, (1979)
[108] Perl, J., 1983. A Unified Warehouse Location-Routing Analysis, PhD dissertation, Northwestern University.
[109] Perl, J.; Daskin, M.S., A unified warehouse location-routing methodology, Journal of business logistics, 5, 92-111, (1984)
[110] Perl, J.; Daskin, M.S., A warehouse location-routing problem, Transportation research B, 19, 381-396, (1985)
[111] Rand, G.K., Methodological choices in depot location studies, Operational research quarterly, 27, 241-249, (1976)
[112] Reece, K., 1985. Vehicle Routing Considerations in Distribution System Design, M.A.Sc. thesis, University of Waterloo. · Zbl 0652.90036
[113] ReVelle, C.; Cohon, J.; Shobrys, D., Simultaneous siting and routing in the disposal of hazardous wastes, Transportation science, 25, 138-145, (1991)
[114] Rodríguez-Martín, I., 2000. Cycle Location Problems, PhD dissertation, University of La Laguna.
[115] Salhi, S., 1987. The Integration of Routing into the Location-Allocation and Vehicle Fleet Composition Problems, PhD dissertation, Lancaster University.
[116] Salhi, S.; Fraser, M., An integrated heuristic approach for the combined location vehicle fleet mix problem, Studies in locational analysis, 8, 3-21, (1996) · Zbl 1176.90362
[117] Salhi, S.; Nagy, G., Consistency and robustness in location-routing, Studies in locational analysis, 13, 3-19, (1999) · Zbl 0981.90043
[118] Salhi, S., Nagy, G., in review. Local improvement in planar facility location using vehicle routing. Annals of Operations Research. · Zbl 1163.90613
[119] Salhi, S.; Rand, G.K., The effect of ignoring routes when locating depots, European journal of operational research, 39, 150-156, (1989) · Zbl 0658.90050
[120] Schwardt, M.; Dethloff, J., Solving a continuous location-routing problem by use of a self-organising map, International journal of physical distribution and logistics management, 35, 390-408, (2005)
[121] Semet, F., A two-phase algorithm for partial accessibility constrained vehicle routing problem, Annals of operations research, 61, 45-65, (1995) · Zbl 0845.90045
[122] Semet, F.; Taillard, E., Solving real-life vehicle routing problems efficiently using tabu search, Annals of operations research, 41, 469-488, (1993) · Zbl 0775.90156
[123] Souid, M., 2003. Résolution Approchée d’un Problèm de Tournées de Véhicule avec Contraintes d’Accessibilité. PhD thesis, University of Valenciennes.
[124] Souid, M., Hanafi, S., Semet, F., in review. Variable neighborhood search for the vehicle routing problem with accessibility constraints. European Journal of Operational Research.
[125] Shen, Z.-J.M.; Coullard, C.; Daskin, M.S., A joint location-inventory model, Transportation science, 37, 40-55, (2003)
[126] Simchi-Levi, D., 1987, The Multistop Location Problems, PhD dissertation, University of Tel-Aviv.
[127] Simchi-Levi, D., The capacitated traveling salesman location problem, Transportation science, 25, 9-18, (1991) · Zbl 0725.90050
[128] Simchi-Levi, D.; Berman, O., Heuristics and bounds for the travelling salesman location problem on the plane, Operations research letters, 6, 243-248, (1987) · Zbl 0637.90032
[129] Simchi-Levi, D.; Berman, O., A heuristic algorithm for the traveling salesman location problem on networks, Operations research, 36, 478-484, (1988) · Zbl 0647.90097
[130] Srivastava, R., 1986. Algorithms for Solving the Location-Routing Problem, PhD dissertation, Ohio State University.
[131] Srivastava, R., Alternate solution procedures for the location-routing problem, Omega, 21, 497-506, (1993)
[132] Srivastava, R.; Benton, W.C., The location-routing problem: considerations in physical distribution system design, Computers in operations research, 17, 427-435, (1990)
[133] Stowers, C.L.; Palekar, U.S., Location models with routing considerations for a single obnoxious facility, Transportation science, 27, 350-362, (1993) · Zbl 0800.90630
[134] Tham, W.C., 2005. Depot location-routing models based on a real supply chain network. PhD dissertation, Lancaster University.
[135] Toth, P., Vigo, D., 2002a. The Vehicle Routing Problem. SIAM, Philadelphia. · Zbl 0979.00026
[136] Toth, P.; Vigo, D., Models, relaxations and exact approaches for the capacitated vehicle routing problem, Discrete applied mathematics, 123, 487-512, (2002) · Zbl 1060.90065
[137] Türkay, A., Emel, E., in review. Vehicle routing problem with packing constraints.
[138] Tuzun, D.; Burke, L.I., A two-phase tabu search approach to the location routing problem, European journal of operational research, 116, 87-89, (1999) · Zbl 1009.90056
[139] Verter, V.; Dincer, M.C., Facility location and capacity acquisition: an integrated approach, Naval research logistics, 42, 1141-1160, (1995) · Zbl 0836.90110
[140] Wasner, M.; Zäpfel, G., An integrated multi-depot hub-location vehicle routing model for network planning of parcel service, International journal of production economics, 90, 403-419, (2004)
[141] Watson-Gandy, C.D.T.; Dohrn, P.J., Depot location with Van salesmen – a practical approach, Omega, 1, 321-329, (1973)
[142] Wu, T.-H.; Low, C.; Bai, J.-W., Heuristic solutions to multi-depot location-routing problems, Computers and operations research, 29, 1393-1415, (2002) · Zbl 0994.90019
[143] Webb, M.H.J., Cost functions in the location of depots for multiple-delivery journeys, Operational research quarterly, 19, 311-320, (1968)
[144] Zografos, K.G.; Samara, S., A combined location-routing model for hazardous waste transportation and disposal, Transportation research record, 1245, 52-59, (1989)
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.