A memetic algorithm for the multiperiod vehicle routing problem with profit

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

34 Scopus Citations
View graph of relations

Author(s)

  • Zizhen Zhang
  • Oscar Che
  • Brenda Cheang
  • Andrew Lim
  • Hu Qin

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)573-584
Journal / PublicationEuropean Journal of Operational Research
Volume229
Issue number3
Publication statusPublished - 16 Sep 2013

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. © 2013 Elsevier B.V. All rights reserved.

Research Area(s)

  • Giant-tour, Memetic algorithm, Metaheuristics, Multiperiod, Periodic vehicle routing

Citation Format(s)

A memetic algorithm for the multiperiod vehicle routing problem with profit. / Zhang, Zizhen; Che, Oscar; Cheang, Brenda; Lim, Andrew; Qin, Hu.

In: European Journal of Operational Research, Vol. 229, No. 3, 16.09.2013, p. 573-584.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal