The single vehicle routing problem with toll-by-weight scheme : A branch-and-bound approach
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 295-304 |
Journal / Publication | European Journal of Operational Research |
Volume | 220 |
Issue number | 2 |
Publication status | Published - 16 Jul 2012 |
Link(s)
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.
In: European Journal of Operational Research, Vol. 220, No. 2, 16.07.2012, p. 295-304.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review