The single vehicle routing problem with toll-by-weight scheme : A branch-and-bound approach

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

23 Scopus Citations
View graph of relations

Author(s)

  • Zizhen Zhang
  • Hu Qin
  • Wenbin Zhu
  • Andrew Lim

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)295-304
Journal / PublicationEuropean Journal of Operational Research
Volume220
Issue number2
Publication statusPublished - 16 Jul 2012

Abstract

Expressways in China make use of the toll-by-weight scheme, in which expressway tolls are collected based on the weight and traveling distance of the vehicle. Most vehicle routing models assume that the cost of traversing each edge is equivalent to edge length or some constant; as a result, such models cannot be practically applied to the Chinese expressway transportation system. This study addresses a new single vehicle routing problem that takes the vehicle's (laden and unladen) weight into account. To solve this problem exactly, we provide a branch-and-bound algorithm with a provably valid lower bound measure, along with five dominance checkers for additional pruning. We analyze our algorithm using instances generated from standard TSP test cases, as well as two new sets of test cases based on real expressway information from the Gansu and Jiangxi provinces in China. The algorithm can be applied to any toll scheme in which the toll per unit distance monotonically increases with weight, even if the toll function is non-linear. © 2012 Elsevier B.V. All rights reserved.

Research Area(s)

  • Branch and bound, Toll-by-weight, Vehicle routing problem

Citation Format(s)

The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach. / Zhang, Zizhen; Qin, Hu; Zhu, Wenbin et al.
In: European Journal of Operational Research, Vol. 220, No. 2, 16.07.2012, p. 295-304.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review