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

详细信息	查看全文 | 推荐本文 |

• 作者：Zizhen Zhang^a ; ^{zizzhang@cityu.edu.hk} ; Hu Qin^b ; ^{tigerqin1980@gmail.com} ; Wenbin Zhu^c ; ^i@zhuwb.com ; Andrew Lim^a ; ^{lim.andrew@cityu.edu.hk}
• 关键词：Branch and bound ; Vehicle routing problem ; Toll-by-weight
• 刊名：European Journal of Operational Research
• 出版年：2012
• 期刊代码：58_03772217
• 类别：et
• 出版时间：16 July, 2012
• 卷：220
• 期：2
• 页码：295-304
• 文件大小：469 K

摘要

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鈥檚 (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.