Algorithms for the time window assignment vehicle routing problem

Abstract

We study the Time Window Assignment Vehicle Routing Problem (TWAVRP), which appears in real contexts where we can see, for example, unknown demand, fluctuations per delivery, and multi-periods. We consider two problems, that share as the main characteristics of capacitated vehicles, and exogeneous time windows for each client. The first problem is a stochastic approach, we deal with a set of scenarios, and a multi-period variant. Our goal is to minimize transportation costs and to assign endogeneous time windows overall scenarios, for variant 1, and for all periods, for variant 2. We propose a hybrid algorithm for both problems, that generates a set of routes by requesting an Iterated Local Search (ILS) metaheuristic and then chooses the most appropriate routes through a set-covering based auxiliary formulation. The contributions described here are threefold. First, we improve the best-known solutions reported to the stochastic TWAVRP, proposed in the literature. Then we test an approach for the multi-period TWAVRP by adding heterogeneous vehicles and driver stopping periods assumptions. This variant appears in the pharmaceutical industry. With a database provided by the Coopservice company, TWAVRP has been adjusted to handle real instances. Finally, we test our approach with such an instance. Computational results indicate that the proposed algorithm is accurate in practice, obtained good solutions for both artificial and real instances. For instances that have more than 45 customers, our method outperforms the results found in the literature. In the end, we were able to answers our research question: "What are the algorithms that can optimize costs and respect all constraints of TWAVRP and its variant concerning the Coopservice routing planning?"