An exact algorithm for solving a capacitated location-routing problem

In location-routing problems, the objective is to locate one or many depots within a set of sites (representing customer locations or cities) and to construct delivery routes from the selected depot or depots to the remaining sites at least system cost. The objective function is the sum of depot operating costs, vehicle acquisition costs and routing costs. This paper considers one such problem in which a weight is assigned to each site and where sites are to be visited by vehicles having a given capacity. The solution must be such that the sum of the weights of sites visited on any given route does not exceed the capacity of the visiting vehicle. The formulation of an integer linear program for this problem involves degree constraints, generalized subtour elimination constraints, and chain barring constraints. An exact algorithm, using initial relaxation of most of the problem constraints, is presented which is capable of solving problems with up to twenty sites within a reasonable number of iterations.