The location-or-routing problem

We introduce the location-or-routing problem (LoRP), which integrates the facility location and the vehicle routing problems by uncovering a new connection from the customer coverage perspective. In the LoRP, open facilities cover the customers in their neighborhood and the uncovered customers are transported to open facilities by capacitated vehicles. Each facility has a maximum coverage range and each vehicle route is constrained by a maximum length. In this setting, a customer can be covered either by 'location' or by 'routing', hence the problem name. We discuss several application areas of LoRP and present its relation to the location and routing problems. We develop a set covering model and a branch-and-price algorithm as an exact solution methodology. The results show that the facility coverage range is an important determinant of the number and location of open facilities. We find that the vehicle routes play a decreasing role on the total cost as facility range increases. Furthermore, trade-off analyses on random graphs show that the total cost decreases almost linearly by increasing facility coverage range. We investigate the reasons behind this observation using arguments from asymptotic analysis and find that it is a common property when the customers are uniformly distributed. (c) 2021 Elsevier Ltd. All rights reserved.

Automated summary

The study introduces the location-or-routing problem (LoRP), integrating facility location and vehicle routing problems from the perspective of customer coverage. It reveals that the facility coverage range is crucial in determining the number and location of open facilities, while the impact of vehicle routes on total cost decreases as facility range increases. Trade-off analyses on random graphs show that total cost decreases almost linearly with increasing facility coverage range.