An Adaptive Guidance Approach for the Heuristic Solution of a Minimum Multiple Trip Vehicle Routing Problem

One of the most important problems in combinatorial optimization is the well-known vehicle routing problem (VRP), which calls for the determination of the optimal routes to be performed by a fleet of vehi- cles to serve a given set of customers. Recently, there has been an increasing interest towards extensions of VRP arising from real-world applications. In this paper we consider a variant in which time windows for service at the customers are given, and vehicles may perform more than one route within a working shift. We call the resulting problem the minimum multiple trip VRP (MMTVRP), where a “multiple trip” is a sequence of routes corresponding to a working shift for a vehicle. The problem objective is to minimize the overall number of the multiple trips (hence the size of the required fleet), breaking ties in favor of the minimum routing cost. We propose an iterative solution approach based on the decomposition of the problem into simpler ones, each solved by specific heuristics that are suitably combined to produce feasible MMTVRP solutions. An adaptive guidance mechanism is used to guide the heuristics to possibly improve the current solution. Computational experiments have been performed on a set of real-world instances arising from a multi- regional scale distribution problem. The obtained results show that the proposed adaptive guidance mechanism is considerably effective, being able to reduce the overall number of required vehicles within a limited computing time.