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.