A Branch-and-Price Algorithm for the Location-Routing Problem with District-Delimited Demand
- 29 November 2025
- journal article
- Published by SAGE Publications in Transportation Research Record: Journal of the Transportation Research Board
- Vol. 2680 (8) , 121-138
Abstract
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.Keywords
This publication has 44 references indexed in Scilit:
- A survey of the standard location-routing problemAnnals of Operations Research, 2017
- Multi-objective, multi-period location-routing model to distribute relief after earthquake by considering emergency roadway repairNeural Computing and Applications, 2016
- A Metaheuristic for a Two Echelon Location-Routing Problem2010
- A Branch-and-Price Algorithm for Combined Location and Routing Problems Under Capacity Restrictions2009
- Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking4OR, 2006
- An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problemsNetworks, 2004
- Split delivery routingNaval Research Logistics (NRL), 1990
- An exact algorithm for solving a capacitated location-routing problemAnnals of Operations Research, 1986
- An exact algorithm for minimizing routing and operating costs in depot locationEuropean Journal of Operational Research, 1981
- A comparative study of heuristics for a two-level routing-location problemEuropean Journal of Operational Research, 1980