Abstract
One of the main goals in transportation planning is to achieve solutions for two classical problems, the traffic assignment and toll pricing problems. The traffic assignment problem aims to minimize total travel delay among all travelers. Based on data derived from the first problem, the toll pricing problem determines the set of tolls and corresponding tariffs that would collectively benefit all travelers and would lead to a user equilibrium solution. Obtaining high-quality solutions for this framework is a challenge for large networks. In this paper, we propose an approach to solve the two problems jointly, making use of a biased random-key genetic algorithm for the optimization of transportation network performance by strategically allocating tolls on some of the links of the road network. Since a transportation network may have thousands of intersections and hundreds of road segments, our algorithm takes advantage of mechanisms for speeding up shortest-path algorithms.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Ahuja R.K., Magnanti T.L., Orlin J.B.: Network Flows—Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993)
Arnott R., Small K.: The economics of traffic congestion. Am. Sci. 82, 446–455 (1994)
Bai, L.: Computational methods for toll pricing models. Ph.D. thesis, University of Florida, Gainesville, Florida (2004)
Bai L., Hearn D.W., Lawphongpanich S.: Relaxed toll sets for congestion pricing problems. In: Hearn, D., Lawphongpanich, S., Smith, M. (eds) Mathematical and Computational Models for Congestion Charging, Springer, Berlin (2006)
Bar-Gera, H.: Transportation networks test problems (2007). http://www.bgu.ac.il/~bargera/tntp
Bean J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 6, 154–160 (1994)
Bureau of Public Roads: Traffic Assignment Manual. Tech. rep., US Dept. of Commerce, Urban Planning Division, Washington, DC (1964)
Buriol L., Resende M., Thorup M.: Speeding up dynamic shortest-path algorithms. INFORMS J. Comput. 20, 191–204 (2008). doi:10.1287/ijoc.1070.0231
Buriol, L.S., Hirsch, M.J., Pardalos, P., Querido, T., Resende, M.G., Ritt, M.: A hybrid genetic algorithm for road congestion minimization. In: Proceedings of the XLI Simpósio Brasileiro de Pesquisa Operacional, pp. 2515–2526 (2009)
Buriol L.S., Resende M.G.C., Ribiero C.C., Thorup M.: A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Networks 46, 36–56 (2005)
Dahl, J., Landenberghe, L.: CVXOPT (2005). http://abel.ee.ucla.edu/cvxopt
Dial R.B.: Minimal-revenue congestion pricing part I: a fast algorithm for the single origin case. Transp. Res. B 33, 189–202 (1999)
Dial R.B.: Minimal-revenue congestion pricing part II: an efficient algorithm for the general case. Transp. Res. B 34, 645–665 (1999)
Ericsson M., Resende M.G.C., Pardalos P.M.: A genetic algorithm for the weight setting problem in OSPF routing. J. Combin. Optim. 6, 299–333 (2002)
Florian M., Hearn D. et al.: Network equilibrium models and algorithms. In: Ball, M.O. (eds) Network Routing, pp. 485–550. Elsevier Science, Amsterdam (1995)
Gonçalves, J., Resende, M.: Biased random-key genetic algorithms for combinatorial optimization. Tech. rep., AT&T Labs Research, Florham Park, NJ (2010). (http://www.research.att.com/~mgcr/doc/srkga.pdf). To appear in J. Heuristics
Hearn, D.W., Ramana, M.: Solving Congestion Toll Pricing Models. Equilibrium and Advances in Transportation Modeling. North-Holland, New York (1988)
Hearn, D.W., Ribera, J.: Bounded flow equilibrium by penalty methods. In: Proceedings of the IEEE International Conference on Circuits and Computers, pp. 162–164 (1980)
Kim D., Pardalos P.: A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure. Oper. Res. Lett. 24, 195–203 (1999)
Lawphongpanich S., Hearn D.W.: An MPEC approach to second-best toll pricing. Math. Program. Ser. B 101, 33–55 (2004)
LeBlanc L.J., Morlok E.K., Pierskalla W.P.: An efficient approach to solving the road network equilibrium traffic assignment problem. Transp. Res. 9, 309–318 (1975)
Reis, R., Ritt M., Buriol, L.S., Resende, M.G.C.: A biased random-key genetic algorithm for OSPF and DEFT routing to minimize network congestion. Int. Trans. Oper. Res. (2010, in press)
Shepherd S., Sumalee S.: A genetic algorithm based approach to optimal toll level and location problems. Netw. Spatial Econ. 4(2), 161–179 (2004)
Spears, W., DeJong, K.: On the virtues of parameterized uniform crossover. In: Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 230–236 (1991)
Tsekeris T., Voß S.: Design and evaluation of road pricing: state-of-the-art and methodological advances. Netnomics 10, 5–52 (2009)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Buriol, L.S., Hirsch, M.J., Pardalos, P.M. et al. A biased random-key genetic algorithm for road congestion minimization. Optim Lett 4, 619–633 (2010). https://doi.org/10.1007/s11590-010-0226-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-010-0226-6