Multi-Trip Vehicle Routing Problem with Time Windows and Heterogeneous Fleet

Abstract

Distribution logistics comprises all activities related to the provision of finished products and merchandise to customers. Defining strategies for optimising the distribution procedure becomes a crucial issue for logistics enterprises. Normally, finding optimal strategies for a given logistic distribution problem is not straightforward since the complexity and time execution exponentially increases as the number of components of the problem increases. An efficient way that overcomes the complexity of finding optimal strategies within a reasonable time concerns the use of approximation algorithms and metaheuristics aiming to find good solutions in terms of quality and execution time. This article introduces a metaheuristic approach to solve a variation of a logistic problem named Vehicle Routing Problem (VRP). Concretely, we present a solution for the Multi-Trip VRP with Time Windows and Heterogeneous Fleet. We add constraints to the original VRP concerning the time and the customer supply. Time constraints concerns the time windows on each customer and time horizon within which customers must be satisfied. In respect of the customer supply, we consider a heterogeneous fleet where vehicles are allowed to do multiple trips. We propose a solution for the problem using a Local Search and the Simulated Annealing technique. A set of benchmark scenarios widely used for the VRP is used in order to evaluate the performance of our approach.