Neighborhood Search Algorithms for Multi-Trip Vehicle Routing

Think about the lines of trucks we overtake on highways. Each of these trucks is performing a journey that may include several delivery or pickup operations before getting to a depot. And each of these journeys is generally determined through a large-scale planning process that concerns a fleet of vehicles. While establishing such a plan, transport operators organize vehicle journeys with an underlying objective such as the minimization of the transportation cost or the maximization of the service level. During the planning process, at least the following decisions have to be made: which customers are going to be visited by each vehicle and in which order. This is a difficult problem to solve even for as few as several tens of customers. In the literature, it is referred to as the vehicle routing problem, which has been extensively studied for nearly six decades.
When solving a vehicle routing problem in a practical context, industry or company-specific constraints have to be taken into account, constantly providing the scientific community with new challenges. One of these calls for deciding how many times and when each vehicle should come back to a depot for loading purposes, besides determining the attribution of customers to vehicles and the related visit sequences. The underlying problem is called the multi-trip vehicle routing problem since each vehicle may perform more than one trip during the planning period, trips being separated by loading operations. Such problems are especially relevant in the field of city logistics. In this thesis, we propose a tailored heuristic approach to solve the multi-trip routing problem and compare it to a more classical solution scheme. We extend both solution methods and compare them on a variant of the problem that takes into account time windows and driver shifts. We configure our methods using an automatic algorithm configuration software and obtain numerical results that show that our tailored approach is very effective, especially in the presence of time windows. Moreover, we provide insights about the behavior of several algorithmic components. Also, we question algorithmic development methodologies and benchmark instances commonly used, and we propose related methodological contributions.