Towards Faster Vehicle Routing by Transferring Knowledge from Customer Representation

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

1 Scopus Citations
View graph of relations

Author(s)

  • Liang Feng
  • Yuxiao Huang
  • Ivor W. Tsang
  • Abhishek Gupta
  • Ke Tang
  • Yew-Soon Ong

Detail(s)

Original languageEnglish
Pages (from-to)952-965
Journal / PublicationIEEE Transactions on Intelligent Transportation Systems
Volume23
Issue number2
Online published10 Sep 2020
Publication statusPublished - Feb 2022

Abstract

The Vehicle Routing Problem (VRP) is a well-known NP-hard combinatorial optimization problem, which has wide spread applications in real world, such as logistics, bus route planning, and urban path planning. To solve VRP, traditional optimization methods usually start the search from scratch and ignore the VRPs solved in the past, which could lead to repeated explorations of the search space of related problems, and thus results in slow optimization process involving unnecessary computational cost. Keeping this in mind, to speed up the optimization for vehicle routing, this article presents a new study towards faster vehicle routing by transferring knowledge from customer representations which are learned from past solved VRPs. In particular, we propose to capture the useful traits buried in previous optimized routing solutions by learning a new customer representation, which can be transferred across VRPs, serving as the prior knowledge, to bias the optimization in the target VRP. In contrast to existing approaches, the proposed knowledge transfer is consist of a learning of new customer representation based on the optimized routing solution, which is general to VRPs possessing different structural properties, and a weightedlnorm-regularized formulation for building sparse mapping across VRPs, that is easy to solve. Further, the proposed knowledge transfer across VRPs occurs along the whole optimization search process, and is thus able to guide the routing optimization process consistently. To verify the efficacy of the proposed method, by using population-based optimization method as the VRP solver, comprehensive empirical studies on both commonly used VRP benchmarks and real world vehicle routing application are presented.

Research Area(s)

  • knowledge transfer, population-based search, transfer optimization, Vehicle routing

Citation Format(s)

Towards Faster Vehicle Routing by Transferring Knowledge from Customer Representation. / Feng, Liang; Huang, Yuxiao; Tsang, Ivor W.; Gupta, Abhishek; Tang, Ke; Tan, Kay Chen; Ong, Yew-Soon.

In: IEEE Transactions on Intelligent Transportation Systems, Vol. 23, No. 2, 02.2022, p. 952-965.

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