Abstract
Most literature on min-cost network flow problems such as shortest path problem (SPP), traveling salesman problem (TSP), vehicle routing problem (VRP), assumes that the rate of any arc is constant. However, this assumption may not be true for some real applications occurring in China due to the toll-by-weight rule. Different from most toll rules, toll-by-weight allows the charging rates on some arcs to vary with vehicle’s total weight. Obviously, the min-cost path between two nodes may vary as the actual load of the vehicle changes when toll-by-weight rule is considered. In this work, we study a new variation of capacitated vehicle routing problem (CVRP) which considers the toll-by-weight rule, and the objective is to minimize the total transportation cost involved. To solve this problem, we implemented a simulated annealing (SA) algorithm and the results of extensive experiments showed the effectiveness of this algorithm.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Chen, X., Li, J.: Design and implementation of vehicle routing optimization system based on toll-by-weight. MIE of China 17, 69–72 (2007)
Toth, P., Vigo, D.: The Vehicle Routing Porblem. SIAM, Philadelphia (2001)
Osman, I.H.: Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research 41, 421–451 (1993)
China map data posted on webmap, http://sms.webmap.cn/xq.asp?dbid=127
Document of chinese communication ministry (Website, 2005), http://www.wzjt.gov.cn/dzzf/jtfg/jtgf/06092001203803223.htm
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Shen, C., Qin, H., Lim, A. (2009). A Capacitated Vehicle Routing Problem with Toll-by-Weight Rule. In: Chien, BC., Hong, TP. (eds) Opportunities and Challenges for Next-Generation Applied Intelligence. Studies in Computational Intelligence, vol 214. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92814-0_48
Download citation
DOI: https://doi.org/10.1007/978-3-540-92814-0_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92813-3
Online ISBN: 978-3-540-92814-0
eBook Packages: EngineeringEngineering (R0)