Optimization of a Two-Stage Distribution Network with Route Planning and Time Restrictions

Location and route planning are implemented independently in most distribution networks. In the majority of cases, low-quality solutions are obtained if sequential methods, e.g. Locate depots first and plan routes second, are used. In location-routing problems (LRPs), location and routing are solved simultaneously. The underlying basic problems are the well known facility location problem and the vehicle routing problem, which have been studied intensively over the last decades. This work extends a single-stage LRP to a two-stage distribution network, taking into account route planning and time restrictions, thus covering more realistic aspects, especially timing aspects, of many real-world problems. We present a tabu search approach for solving large-scale instances and compare its performance with a sequential approach.

1. Introduction

Europe's logistics market is one of the most important economic factors, with a market volume of billion in 2010 [14]. The largest part of the market volume is represented by transportation and warehousing, with a share of 42% and 26%, respectively. The increasing market competition and the service focus of customers force courier-express-parcel service providers to re-evaluate and to continuously improve their networks. Worldwide, the necessity to improve the service quality is rapidly growing. Especially time aspects, such as delivery to the destination within the next day, are key performance indicators for service quality. To reduce costs and increase service quality, facility location and route planning strategies are crucial choices. Both of the underlying basic problems - the facility location problem (FLP) and the vehicle routing problem (VRP) – have been studied and solved intensively over the last decades as individual models. To reduce the complexity of the combined problem, both problems are usually tackled independently and in a sequential manner (locate first and route second). In particular, aspects of future route plans are neglected during the strategical location planning level of most distribution systems, and only approximated. This approximation needs, however, a priori knowledge of transport services, and research has shown that this strategy often leads to suboptimal solutions, as shown by Salhi and Rand [24]. Exact methods for the capacitated location-routing problem include column generation [1] and branch-and-cut [3]. Although some instances with 100 customers remain unsolved, these methods are able to solve instances with up to 200 customers. However, real problems consist of large-size instances with up to 1000 customers and hundreds of potential depots. To handle this kind of instance, several metaheuristics have been proposed (e.g. [9], [18], [20], [21], [26], and [28]). In recent years, the attention has increased, and many of the published works deal with real problems. For example, military [17], the paper industry [22], and postal logistics (e.g. [5], [12], and [27]) to name just a few. An overview is provided by Nagy and Salhi [19].