Article ID: | iaor20141082 |
Volume: | 41 |
Issue: | 6 |
Start Page Number: | 167 |
End Page Number: | 173 |
Publication Date: | Jan 2014 |
Journal: | Computers and Operations Research |
Authors: | Potvin Jean-Yves, Gendreau Michel, Azi Nabila |
Keywords: | combinatorial optimization, heuristics: local search |
The vehicle routing problem with multiple routes consists in determining the routing of a fleet of vehicles when each vehicle can perform multiple routes during its operations day. This problem is relevant in applications where the duration of each route is limited, for example when perishable goods are transported. In this work, we assume that a fixed‐size fleet of vehicles is available and that it might not be possible to serve all customer requests, due to time constraints. Accordingly, the objective is first to maximize the number of served customers and then, to minimize the total distance traveled by the vehicles. An adaptive large neighborhood search, exploiting the ruin‐and‐recreate principle, is proposed for solving this problem. The various destruction and reconstruction operators take advantage of the hierarchical nature of the problem by working either at the customer, route or workday level. Computational results on Euclidean instances, derived from well‐known benchmark instances, demonstrate the benefits of this multi‐level approach.