Abstract
Most of previous studies on vehicle routing problems assume that traversal cost of each edge is simply equivalent to a constant number. Unfortunately, the models of this kind can not be applied in China because toll per kilometer of Chinese expressways varies with vehicle’s weight. Motivated by rapidly increasing market of expressway transportation in China, we address a new and special vehicle routing problem that takes a single vehicle and its weight into account. To solve this problem practically, we provide a branch-and-bound algorithm with a well-designed lower bound. This algorithm can deal with any toll scheme in which toll per unit distance monotonically increases with weight. Computational results show that test instances with up to 42 vertices can be solved in reasonable computing time.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Toth, P., Vigo, D. (eds.): The vehicle routing problem. SIAM, Philadelphia (2002)
Gutin, G., Punnen, A. (eds.): The Traveling Salesman Problem and Its Variations. Kluwer Academic Publishers, Dordrecht (2002)
Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M.: The minimum latency problem. In: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing (STOC 1994), Montreal, Quebec, Canada, pp. 163–171 (1994)
Goemans, M., Kleinberg, J.: An improved approximation ratio for the minimum latency problem. Mathematical Programming 82(1-2), 111–124 (1998)
Arora, S., Karakostas, G.: Approximation schemes for minimum latency problems. SIAM Journal on Computing 32(5), 1317–1337 (2003)
Wu, B., Huang, Z., Zhan, F.: Exact algorithms for the minimum latency problem. Information Processing Letter 92(6), 303–309 (2004)
Archer, A., Levin, A., Williamson, D.: A faster, better approximation algorithm for the minimum latency problem. SIAM Journal on Computing 37(5), 1472–1498 (2008)
García, A., Jodrá, P., Tejel, J.: A note on the traveling repairman problem. Networks 40(1), 27–31 (2002)
Salehipour, A., Sörensen, K., Goos, P., Bräysy, O.: An efficient grasp+vnd metaheuristic for the traveling repairman problem. Working papers, University of Antwerp, Faculty of Applied Economics (2008)
Minieka, E.: The delivery man problem on a tree network. Annals of Operations Research 18(1-4), 261–266 (1989)
Fischetti, M., Laporte, G., Martello, S.: The delivery man problem and cumulative matroids. Operations Research 41(6), 1055–1064 (1993)
Méndez-Díaz, I., Zabala, P., Lucena, A.: A new formulation for the traveling deliveryman problem. Discrete Applied Mathematics 156(17), 3223–3237 (2008)
Bianco, L., Mingozzi, A., Ricciardelli, S.: The traveling salesman problem with cumulative costs. Networks 23(2), 81–91 (1993)
Chen, X., Li, J., Fan, Y., Wu, Y., Ding, L.: Design and implementation of vehicle routing optimization system based on toll-by-weight. Manufacture Information Engineering of China 17, 69–72 (2007)
Shen, C., Qin, H., Lim, A.: A capacitated vehicle routing problem with toll-by-weight rule. In: Chien, B., Hong, T. (eds.) Opportunities and Challenges for Next-Generation Applied Intelligence. Studies in Computational Intelligence, vol. 214, pp. 311–316. Springer, Heidelberg (2009)
Hardy, G., Littlewood, J., Pólya, G.: Inequalities. Cambridge University Press, Cambridge (1988)
Hall, P.: On representatives of subsets. Journal of London Mathematical Society 10, 26–30 (1935)
Gross, J., Yellen, J. (eds.): Graph Theorey and Its Applications. Chapman and Hall/CRC (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhang, Z., Qin, H., Lim, A., Guo, S. (2010). Branch and Bound Algorithm for a Single Vehicle Routing Problem with Toll-by-Weight Scheme. In: García-Pedrajas, N., Herrera, F., Fyfe, C., Benítez, J.M., Ali, M. (eds) Trends in Applied Intelligent Systems. IEA/AIE 2010. Lecture Notes in Computer Science(), vol 6098. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13033-5_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-13033-5_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13032-8
Online ISBN: 978-3-642-13033-5
eBook Packages: Computer ScienceComputer Science (R0)