An Adaptive Guidance Approach for the Heuristic Solution of a Multi-Trip Vehicle Routing Problem

Maria Battarra, Michele Monaci, Daniele Vigo

Research output: Contribution to journalArticlepeer-review

83 Citations (SciVal)


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.

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.
Original languageEnglish
Pages (from-to)3041-3050
JournalComputers and Operations Research
Issue number11
Early online date25 Feb 2009
Publication statusPublished - 2009


Dive into the research topics of 'An Adaptive Guidance Approach for the Heuristic Solution of a Multi-Trip Vehicle Routing Problem'. Together they form a unique fingerprint.

Cite this