Paper Info
Title
The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach.
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.
Year
DOI
Venue
2012
10.1016/j.ejor.2012.01.035
European Journal of Operational Research
Keywords
Field
DocType
Branch and bound,Vehicle routing problem,Toll-by-weight
Monotonic function,Mathematical optimization,Branch and bound,Vehicle routing problem,Upper and lower bounds,Toll,Destination-Sequenced Distance Vector routing,Test case,Mathematics,Traverse
Journal
Volume
Issue
ISSN
220
2
0377-2217
Citations 
PageRank 
References 
10
0.50
14
Authors
4
Name
Order
Citations
PageRank
Zizhen Zhang110017.27
Hu Qin220116.49
Wenbin Zhu321415.34
Andrew Lim493789.78