首页 | 本学科首页   官方微博 | 高级检索  
     检索      


The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach
Authors:Zizhen Zhang  Hu Qin  Wenbin Zhu  Andrew Lim
Institution:1. Department of Management Sciences, City University of Hong Kong, Tat Chee Ave, Kowloon Tong, Kowloon, Hong Kong;2. School of Management, Huazhong University of Science and Technology, No. 1037, Luoyu Road, Wuhan, China;3. Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong
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.
Keywords:Branch and bound  Vehicle routing problem  Toll-by-weight
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号