Solving Generalized Vehicle Routing Problem With Occasional Drivers via Evolutionary Multitasking

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

4 Scopus Citations
View graph of relations

Author(s)

  • Liang Feng
  • Lei Zhou
  • Abhishek Gupta
  • Jinghui Zhong
  • Zexuan Zhu
  • Kai Qin

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number8938734
Pages (from-to)3171-3184
Journal / PublicationIEEE Transactions on Cybernetics
Volume51
Issue number6
Online published23 Dec 2019
Publication statusPublished - Jun 2021

Abstract

With the emergence of crowdshipping and sharing economy, vehicle routing problem with occasional drivers (VRPOD) has been recently proposed to involve occasional drivers with private vehicles for the delivery of goods. In this article, we present a generalized variant of VRPOD, namely, the vehicle routing problem with heterogeneous capacity, time window, and occasional driver (VRPHTO), by taking the capacity heterogeneity and time window of vehicles into consideration. Furthermore, to meet the requirement in today's cloud computing service, wherein multiple optimization tasks may need to be solved at the same time, we propose a novel evolutionary multitasking algorithm (EMA) to optimize multiple VRPHTOs simultaneously with a single population. Finally, 56 new VRPHTO instances are generated based on the existing common vehicle routing benchmarks. Comprehensive empirical studies are conducted to illustrate the benefits of the new VRPHTOs and to verify the efficacy of the proposed EMA for multitasking against a state-of-art single task evolutionary solver. The obtained results showed that the employment of occasional drivers could significantly reduce the routing cost, and the proposed EMA is not only able to solve multiple VRPHTOs simultaneously but also can achieve enhanced optimization performance via the knowledge transfer between tasks along the evolutionary search process.

Research Area(s)

  • Evolutionary multitasking, occasional driver, time window, vehicle routing problem (VRP)

Citation Format(s)

Solving Generalized Vehicle Routing Problem With Occasional Drivers via Evolutionary Multitasking. / Feng, Liang; Zhou, Lei; Gupta, Abhishek; Zhong, Jinghui; Zhu, Zexuan; Tan, Kay-Chen; Qin, Kai.

In: IEEE Transactions on Cybernetics, Vol. 51, No. 6, 8938734, 06.2021, p. 3171-3184.

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