An Improved Branch and Bound Algorithm for Location-Routing Problems

An important limitation of the fixed charge location model, is the assumption that full truckload quantities are shipped from a facility to a customer. In many contexts, shipments are made in less-than-truckload (LTL) quantities from a facility to customers along a multiple-stop route. The different location decision is made from the different cost of delivery. In this paper we are concerned with a particular type of facility location problem in which there exist two echelons of facilities. To make the location decision, the delivery cost of a multiple-stop route are calculated. We note that this is an NP-hard problem and use a Lagrangian relaxation-based branch and bound algorithm to solve this location-routing problem. We present numerical results for various size test problems. Results indicates the method is efficient.