Solution methods for two-echelon vehicle routing problems

This project deals with solution methods for the two-echelon vehicle routing problem with time windows (2E- VRPTW). The problem is motivated by a real world application in the context of city logistics. In urban areas space is limited, especially in the city center, and has to be shared between public and private passenger transport and parking facilities. Freight transportation produces congestions, emissions and noise. Moreover, the presence of large and heavy vehicles in the city should be avoided, since they are an uncomforting factor to the citizens. City logistics are initiatives taken to coordinate and consolidate freight in a city in order to minimize the flow of products, while still guaranteeing that every demand is met. In a city, demand is made up by products required by shops, supermarkets, restaurants, office buildings and private households. These flows of products entering a city have to be managed carefully. In a two-tiered city-logistics system loads arrive from major terminals outside the city. Then they are shipped to intermediate satellite facilities, where they are loaded in smaller vehicles and transported to the customers. The problem related to this policy is called two-echelon vehicle routing problem (2E-VRP). We will consider the case where time windows apply at customer nodes. The 2E-VRP consists of two levels. The first level considers the transportation from the depot to the satellites and the second level is composed of the delivery from the satellite facilities to the customers. The second level problem is a multi-depot VRP with time windows. The linkage between first and second level is the assignment of demand to satellite facilities. We will first start by considering the basic case and then a number of extensions to it. As solution methods we will develop an exact method, based on branch-and-price and a metaheuristic solution method. The Metaheuristic will also be extended to deal with three real life extensions. First we will allow split deliveries at the satellite facilities. This means that in the first level routes the satellites can be visited more than once as long as the total demand is satisfied. The next extension deals with synchronizing the visits of first level and second level vehicles. We assume that no inventory can be kept at the satellite facilities and therefore loading and unloading operations have to be performed immediately. Small waiting times may be used. Finally as a third extension we deal with time dependent travel times. Those extensions are considered because they correspond to a real life setting faced within a city logistics context.