A memetic algorithm for the multiperiod vehicle routing problem with profit

A memetic algorithm for the multiperiod vehicle routing problem with profit

0.00 Avg rating0 Votes
Article ID: iaor20133097
Volume: 229
Issue: 3
Start Page Number: 573
End Page Number: 584
Publication Date: Sep 2013
Journal: European Journal of Operational Research
Authors: , , , ,
Keywords: memetic algorithm
Abstract:

In this paper, we extend upon current research in the vehicle routing problem whereby labour regulations affect planning horizons, and therefore, profitability. We call this extension the multiperiod vehicle routing problem with profit (mVRPP). The goal is to determine routes for a set of vehicles that maximizes profitability from visited locations, based on the conditions that vehicles can only travel during stipulated working hours within each period in a given planning horizon and that the vehicles are only required to return to the depot at the end of the last period. We propose an effective memetic algorithm with a giant‐tour representation to solve the mVRPP. To efficiently evaluate a chromosome, we develop a greedy procedure to partition a given giant‐tour into individual routes, and prove that the resultant partition is optimal. We evaluate the effectiveness of our memetic algorithm with extensive experiments based on a set of modified benchmark instances. The results indicate that our approach generates high‐quality solutions that are reasonably close to the best known solutions or proven optima, and significantly better than the solutions obtained using heuristics employed by professional schedulers.

Reviews

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