A biased random-key genetic algorithm for road congestion minimization. (English) Zbl 1202.90025
Summary: One of the main goals in transportation planning is to achieve solutions for two classical problems, the traffic assignment problem and the toll pricing problem. 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.
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.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90B10 | Deterministic network models in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
transportation networks; system optimal; user equilibrium; genetic algorithms; dynamic shortest pathsSoftware:
CVXOPTReferences:
| [1] | Ahuja R.K., Magnanti T.L., Orlin J.B.: Network Flows–Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993) · Zbl 1201.90001 |
| [2] | Arnott R., Small K.: The economics of traffic congestion. Am. Sci. 82, 446–455 (1994) |
| [3] | Bai, L.: Computational methods for toll pricing models. Ph.D. thesis, University of Florida, Gainesville, Florida (2004) |
| [4] | 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) · Zbl 1117.90029 |
| [5] | Bar-Gera, H.: Transportation networks test problems (2007). http://www.bgu.ac.il/\(\sim\)bargera/tntp |
| [6] | Bean J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 6, 154–160 (1994) · Zbl 0807.90060 |
| [7] | Bureau of Public Roads: Traffic Assignment Manual. Tech. rep., US Dept. of Commerce, Urban Planning Division, Washington, DC (1964) |
| [8] | 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 · Zbl 1243.90221 · doi:10.1287/ijoc.1070.0231 |
| [9] | 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) · Zbl 1202.90025 |
| [10] | 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) · Zbl 1072.90528 · doi:10.1002/net.20070 |
| [11] | Dahl, J., Landenberghe, L.: CVXOPT (2005). http://abel.ee.ucla.edu/cvxopt |
| [12] | Dial R.B.: Minimal-revenue congestion pricing part I: a fast algorithm for the single origin case. Transp. Res. B 33, 189–202 (1999) · doi:10.1016/S0191-2615(98)00026-5 |
| [13] | Dial R.B.: Minimal-revenue congestion pricing part II: an efficient algorithm for the general case. Transp. Res. B 34, 645–665 (1999) · doi:10.1016/S0191-2615(99)00046-6 |
| [14] | 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) · Zbl 1068.90092 · doi:10.1023/A:1014852026591 |
| [15] | 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) · Zbl 0864.90042 |
| [16] | 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/\(\sim\)mgcr/doc/srkga.pdf ). To appear in J. Heuristics |
| [17] | Hearn, D.W., Ramana, M.: Solving Congestion Toll Pricing Models. Equilibrium and Advances in Transportation Modeling. North-Holland, New York (1988) |
| [18] | 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) |
| [19] | 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) · Zbl 0947.90017 · doi:10.1016/S0167-6377(99)00004-8 |
| [20] | Lawphongpanich S., Hearn D.W.: An MPEC approach to second-best toll pricing. Math. Program. Ser. B 101, 33–55 (2004) · Zbl 1076.90009 · doi:10.1007/s10107-004-0536-5 |
| [21] | 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) · doi:10.1016/0041-1647(75)90030-1 |
| [22] | 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) · Zbl 1219.90035 |
| [23] | Shepherd S., Sumalee S.: A genetic algorithm based approach to optimal toll level and location problems. Netw. Spatial Econ. 4(2), 161–179 (2004) · Zbl 1079.90082 · doi:10.1023/B:NETS.0000027771.13826.3a |
| [24] | 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) |
| [25] | Tsekeris T., Voß S.: Design and evaluation of road pricing: state-of-the-art and methodological advances. Netnomics 10, 5–52 (2009) · doi:10.1007/s11066-008-9024-z |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
