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 vehicles 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.