It has been proven that a simultaneous determination of facility locations and vehicle routes can effectively reduce the overall investment and operational costs of a distribution-inventory logistics system. While most previous studies on location-routing problems (LRPs) treat possible demand concentrated only at a given set of places, some real-life scenarios observe that demand is diversely distributed in a district and the district demand can be jointly serviced by multiple facilities within the district. In such cases, supply allocation among facilities becomes another dimension of optimization, alongside facility location and vehicle routing decisions. This study addresses such a new two-echelon LRP with district-delimited demand, aiming at minimizing the total cost of facility construction, vehicle routing and service provision while meeting the aggregate demand of each district. Utilizing the Dantzig-Wolfe decomposition, we decompose the LRP into a master problem and a set of subproblems and develop a tailored branch-and-price algorithm to solve it. Through several synthetic and real-world test instances, we demonstrate the superior solution accuracy and computational efficiency of the algorithm. In addition, we perform a set of critical sensitivity analyses on facility number and vehicle capacity to assess their impact on solutions.
SalhiS.RandG. K.The Effect of Ignoring Routes When Locating Depots. European Journal of Operational Research, Vol. 39, 1989, pp. 150–156.
2.
LopesR. B.FerreiraC.SantosB. S.BarretoS.A Taxonomical Analysis, Current Methods and Objectives on Location-Routing Problems. International Transactions in Operational Research, Vol. 20, 2013, pp. 795–822.
3.
MaraS. T. W.KuoR.AsihA. M. S.Location-Routing Problem: A Classification of Recent Research. International Transactions in Operational Research, Vol. 28, 2021, pp. 2941–2983.
4.
NagyG.SalhiS.Location-Routing: Issues, Models and Methods. European Journal of Operational Research, Vol. 177, 2007, pp. 649–672.
5.
ProdhonC.PrinsC.A Survey of Recent Research on Location-Routing Problems. European Journal of Operational Research, Vol. 238, 2014, pp. 1–17.
6.
SchneiderM.DrexlM.A Survey of the Standard Location-Routing Problem. Annals of Operations Research, Vol. 259, 2017, pp. 389–414.
7.
UkkusuriS. V.YushimitoW. F.Location Routing Approach for the Humanitarian Prepositioning Problem. Transportation Research Record: Journal of the Transportation Research Board, 2008. 2089: 18–25.
8.
WangS.TaoF.ShiY.Optimization of Location–Routing Problem for Cold Chain Logistics Considering Carbon Footprint. International Journal of Environmental Research and Public Health, Vol. 15, 2018, p. 86.
9.
TangJ.QiC.WangH.Integrated Optimization of Order Splitting and Distribution Routing for the Front Warehouse Mode E-Retailing. International Journal of Production Research, Vol. 62, 2024, pp. 1715–1736.
10.
ChenJ.LiaoW.YuC.Route Optimization for Cold Chain Logistics of Front Warehouses Based on Traffic Congestion and Carbon Emission. Computers & Industrial Engineering, Vol. 161, 2021, p. 107663.
11.
SecomandiN.Comparing Neuro-Dynamic Programming Algorithms for the Vehicle Routing Problem with Stochastic Demands. Computers & Operations Research, Vol. 27, 2000, pp. 1201–1225.
12.
ZhengC.ChangZ.LiuF.GengM.ChenH.JiangJ.ZhouS., et al. Interpretation of the Protocol for Prevention and Control of COVID-19 in China. China CDC Weekly, Vol. 2, 2020, p. 902.
13.
LuY.LuQ.FuL.HeT.LiY.CaiR.LuL.HuG.Measures for the Activation and Renovation of Large-Scale Centralized Medical Isolation and Observation Points for Urban COVID-19 Epidemics. Chinese Journal of Disinfection, Vol. 39, 2022, pp. 786–788.
14.
DrexlM.SchneiderM.A Survey of Variants and Extensions of the Location-Routing Problem. European Journal of Operational Research, Vol. 241, 2015, pp. 283–308.
15.
CudaR.GuastarobaG.SperanzaM. G.A Survey on Two-Echelon Routing Problems. Computers & Operations Research, Vol. 55, 2015, pp. 185–199.
16.
LaporteG.NobertY.An Exact Algorithm for Minimizing Routing and Operating Costs in Depot Location. European Journal of Operational Research, Vol. 6, 1981, pp. 224–226.
17.
LaporteG.NobertY.PelletierP.Hamiltonian Location Problems. European Journal of Operational Research, Vol. 12, 1983, pp. 82–89.
18.
LaporteG.NobertY.ArpinD.An Exact Algorithm for Solving a Capacitated Location-Routing Problem. Annals of Operations Research, Vol. 6, 1986, pp. 291–310.
19.
BergerR. T.CoullardC. R.DaskinM. S.Location-Routing Problems with Distance Constraints. Transportation Science, Vol. 41, 2007, pp. 29–43.
20.
AkcaZ.BergerR.RalphsT.A Branch-and-Price Algorithm for Combined Location and Routing Problems Under Capacity Restrictions. In Operations Research and Cyber-Infrastructure (ChinneckJ. W.KristjanssonB.SaltzmanM. J., eds.), Charleston, SC, Springer, Boston, MA, 2009, pp. 309–330.
21.
BelenguerJ.-M.BenaventE.PrinsC.ProdhonC.CalvoR. W.A Branch-and-Cut Method for the Capacitated Location-Routing Problem. Computers & Operations Research, Vol. 38, 2011, pp. 931–941.
22.
BaldacciR.MingozziA.Wolfler CalvoR.An Exact Method for the Capacitated Location-Routing Problem. Operations Research, Vol. 59, 2011, pp. 1284–1296.
23.
ContardoC.CordeauJ.-F.GendronB.An Exact Algorithm Based on Cut-and-Column Generation for the Capacitated Location-Routing Problem. INFORMS Journal on Computing, Vol. 26, 2014, pp. 88–102.
24.
PrinsC.ProdhonC.RuizA.SorianoP.Wolfler CalvoR.Solving the Capacitated Location-Routing Problem by a Cooperative Lagrangean Relaxation-Granular Tabu Search Heuristic. Transportation Science, Vol. 41, 2007, pp. 470–483.
25.
VincentF. Y.LinS.-W.LeeW.TingC.-J.A Simulated Annealing Heuristic for the Capacitated Location Routing Problem. Computers & Industrial Engineering, Vol. 58, 2010, pp. 288–299.
26.
DerbelH.JarbouiB.HanafiS.ChabchoubH.Genetic Algorithm with Iterated Local Search for Solving a Location-Routing Problem. Expert Systems with Applications, Vol. 39, 2012, pp. 2865–2871.
27.
ArchettiC.SperanzaM. G.Vehicle Routing Problems with Split Deliveries. International Transactions in Operational Research, Vol. 19, 2012, pp. 3–22.
28.
WangH.DuL.MaS.Multi-Objective Open Location-Routing Model with Split Delivery for Optimized Relief Distribution in Post-Earthquake. Transportation Research Part E: Logistics and Transportation Review, Vol. 69, 2014, pp. 160–179.
29.
VahdaniB.VeysmoradiD.ShekariN.MousaviS. M.Multi-Objective, Multi-Period Location-Routing Model to Distribute Relief After Earthquake by Considering Emergency Roadway Repair. Neural Computing and Applications, Vol. 30, 2018, pp. 835–854.
30.
SunZ.YanN.SunY.LiH.Location-Routing Optimization with Split Demand for Customer Self-Pickup via Data Analysis and Heuristics Search. Asia-Pacific Journal of Operational Research, Vol. 36, 2019, p. 1940013.
31.
JacobsenS. K.MadsenO. B.A Comparative Study of Heuristics for a Two-Level Routing-Location Problem. European Journal of Operational Research, Vol. 5, 1980, pp. 378–387.
32.
NguyenV.-P.PrinsC.ProdhonC.A Multi-Start Iterated Local Search with Tabu List and Path Relinking for the Two-Echelon Location-Routing Problem. Engineering Applications of Artificial Intelligence, Vol. 25, 2012, pp. 56–71.
33.
NguyenV.-P.PrinsC.ProdhonC.Solving the Two-Echelon Location Routing Problem by a GRASP Reinforced by a Learning Process and Path Relinking. European Journal of Operational Research, Vol. 216, 2012, pp. 113–126.
34.
AmbrosinoD.SciomachenA.ScutellàM. G.A Heuristic Based on Multi-Exchange Techniques for a Regional Fleet Assignment Location-Routing Problem. Computers & Operations Research, Vol. 36, 2009, pp. 442–460.
35.
ContardoC.HemmelmayrV.CrainicT. G.Lower and Upper Bounds for the Two-Echelon Capacitated Location-Routing Problem. Computers & Operations Research, Vol. 39, 2012, pp. 3185–3199.
36.
BocciaM.CrainicT. G.SforzaA.SterleC.A Metaheuristic for a Two-Echelon Location-Routing Problem. Proc., Experimental Algorithms: 9th International Symposium, Ischia Island, Naples, Italy, Springer, Berlin, Heidelberg, 2010, pp. 288–301.
37.
WinkenbachM.KleindorferP. R.SpinlerS.Enabling Urban Logistics Services at La Poste Through Multi-Echelon Location-Routing. Transportation Science, Vol. 50, 2016, pp. 520–540.
38.
DantzigG. B.WolfeP.Decomposition Principle for Linear Programs. Operations Research, Vol. 8, 1960, pp. 101–111.
39.
DesaulniersG.Branch-and-Price-and-Cut for the Split-Delivery Vehicle Routing Problem with Time Windows. Operations Research, Vol. 58, 2010, pp. 179–192.
40.
LuoZ.QinH.ZhuW.LimA.Branch and Price and Cut for the Split-Delivery Vehicle Routing Problem with Time Windows and Linear Weight-Related Cost. Transportation Science, Vol. 51, 2017, pp. 668–687.
41.
DrorM.TrudeauP.Savings by Split Delivery Routing. Transportation Science, Vol. 23, 1989, pp. 141–145.
42.
DrorM.TrudeauP.Split Delivery Routing. Naval Research Logistics, Vol. 37, 1990, pp. 383–402.
43.
FeilletD.DejaxP.GendreauM.GueguenC.An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints: Application to Some Vehicle Routing Problems. Networks, Vol. 44, 2004, pp. 216–229.
44.
IrnichS.DesaulniersG.Shortest Path Problems with Resource Constraints. In Column Generation (DesaulniersG.DesrosiersJ.SolomonM. M., eds.), Springer, Boston, MA, 2006, pp. 33–65.
45.
PonboonS.QureshiA. G.TaniguchiE.Branch-and-Price Algorithm for the Location-Routing Problem with Time Windows. Transportation Research Part E: Logistics and Transportation Review, Vol. 86, 2016, pp. 1–19.
46.
PrinsC.ProdhonC.CalvoR. W.Solving the Capacitated Location-Routing Problem by a GRASP Complemented by a Learning Process and a Path Relinking. 4OR, Vol. 4, 2006, pp. 221–238.
