An adaptive large neighborhood search for a vehicle routing problem with multiple routes

An adaptive large neighborhood search for a vehicle routing problem with multiple routes

0.00 Avg rating0 Votes
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: , ,
Keywords: combinatorial optimization, heuristics: local search
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.