A Branch-and-Price Algorithm for the Location-Routing Problem with District-Delimited Demand

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.