Dual-Based Heuristic for Optimal Cordon Pricing Design
Publication: Journal of Transportation Engineering
Volume 139, Issue 11
Abstract
This paper formulates the cordon pricing design problem with elastic demand as a mathematical program with complementarity constraints (MPCC) to simultaneously optimize the cordon locations and cordon-specific toll levels, thus maximizing total social welfare. The formulation is flexible so that various charging requirements, such as those on cordon numbers, cordon size, and cordon types, can be easily satisfied by slightly modifying the formulation. A dual-based heuristic algorithm is proposed to handle the problem by sequentially solving a relaxed cordon pricing design problem and an updating problem. To avoid directly dealing with the complementarity constraints contained in the two problems, the paper adopts alternative approaches by solving a series of subproblems. These subproblems can be easily handled by using available commercial solvers. Numerical tests are performed to generate different cordon designs for one single-layered cordon, multilayered cordons, and multicentered cordons. The results demonstrate that the proposed model and solution algorithm are able to efficiently produce optimal cordon pricing schemes on real-sized transportation networks.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The authors thank three anonymous reviewers for their helpful comments. This research was supported in part by the Humanities and Social Science Research Project, Ministry of Education (11YJCZH242) and the Fundamental Research Funds for the Central Universities [DUT10RC(3)90]. The second author was also supported by the National Natural Science Foundation of China (71101109).
References
Ahuja, R., Magnanti, T., and Orlin, J. (1993). Network flows: Theory, algorithms, and applications, Prentice Hall, Saddle River, NJ.
Ban, X., and Liu, H. X. (2009). “A link-node discrete-time dynamic second-best toll pricing model with a relaxation solution algorithm.” Netw. Spat. Econ., 9(2), 243–267.
Brooke, A., Kendirck, D., and Meeraus, A. (1992). GAMS: A user’s guide, Scientific Press, San Francisco.
CPLEX [Computer software]. ILOG, Sunnyvale, CA.
De Palma, A., Kilani, M., and de Lara, M. (2009). “Cordon pricing in the monocentric city model: Theory and application to Ile-de-France.” Proc., TRB 88th Annual Meeting, Transportation Research Board, National Research Council, Washington, DC.
De Palma, A., and Lindsey, R. (2011). “Traffic congestion pricing methodologies and technologies.” Transp. Res. Part C, 19(6), 1377–1399.
Dimitriou, L., and Tsekeris, T. (2009). “Elastic multi-user stochastic equilibrium toll design with direct search meta-heuristics.” Metaheuristics in the Service Industry, K. Sörensen, M. Sevaux, W. Habenicht, and M. J. Geiger, eds., Springer-Verlag, Berlin Heidelberg, Germany, 45–61.
Drud, A. (1994). “CONOPT—A large scale GRG code.” INFORMS J. Comput., 6(2), 207–216.
Ekström, J., Engelson, L., and Rydergren, C. (2008). “Decision support for finding locations and toll levels within a congestion pricing scheme.” Proc., TRB 86th Annual Meeting, Transportation Research Board, National Research Council, Washington, DC.
Ekström, J., Sumalee, A., and Lo, H. K. (2012). “Optimizing toll locations and levels using a mixed integer linear approximation approach.” Transp. Res. Part B, 46(7), 834–854.
Farvaresh, H., and Sepehri, M. M. (2011). “A single-level mixed integer linear formulation for a bi-level discrete network design problem.” Transp. Res. Part E, 47(5), 623–640.
Geroliminis, N., and Levinson, D. M. (2009). “Cordon pricing on congested networks.” Proc., TRB 88th Annual Meeting, Transportation Research Board, National Research Council, Washington, DC.
Han, D., Yang, H., and Wang, X. L. (2010). “Efficiency of the plate-number-based traffic rationing in general networks.” Transp. Res. Part E, 46(6), 1095–1110.
Ho, H. W., Wong, S. C., Yang, H., and Loo, B. P. Y. (2005). “Cordon-based congestion pricing in a continuum traffic equilibrium system.” Transp. Res. Part A, 39(7–9), 813–834.
Joksimovic, D., Bliemer, M. C. J., and Bovy, P. H. L. (2005). “Optimal toll design problem in dynamic traffic networks with joint route and departure time choice.” Transportation Research Record 1923, Transportation Research Board, Washington, DC, 61–72.
Kocis, G. R., and Grossmann, I. E. (1989). “Computational experience with DICOPT solving MINLP problems in process systems engineering.” Comput. Chem. Eng., 13(3), 307–315.
Lawphongpanich, S., and Hearn, D. W. (2004). “An MPEC approach to second-best toll pricing.” Math. Program. Ser. B, 101(1), 33–55.
LeBlanc, L. J. (1975). “An algorithm for the discrete network design problem.” Transport. Sci., 9(3), 183–199.
Lin, D. Y., Unnikrishnan, A., and Waller, S. T. (2011). “A dual variable approximation based heuristic for dynamic congestion pricing.” Netw. Spat. Econ., 11(2), 271–293.
Long, J., Gao, Z., Zhang, H., and Szeto, W. Y. (2010). “A turning restriction design problem in urban road networks.” Eur. J. Oper. Res., 206(3), 569–578.
Luathep, P., Sumalee, A., Lam, W. H. K., Li, Z. C., and Lo, H. K. (2011). “Global optimization method for mixed transportation network design problem: A mixed-integer linear programming approach.” Transp. Res. Part B, 45(5), 808–827.
Marchand, M. (1968). “A note on optimal tolls in an imperfect environment.” Econometrica, 36(3–4), 575–581.
May, A., Liu, R., Shepherd, S., and Sumalee, A. (2002). “The impact of cordon design on the performance of road pricing schemes.” Transp. Pol., 9(3), 209–220.
May, A., Shepherd, S., Sumalee, A., and Koh, A. (2007). “Design tools for road pricing cordons.” Road congestion pricing in Europe: Implications for the United States, H. Richardson and C. Bae, eds., Edward Elgar, Cheltenham, UK, 138–155.
Meng, Q., and Liu, Z. (2011). “Trial-and-error method for congestion pricing scheme under side-constrained probit-based stochastic user equilibrium conditions.” Transportation, 38(5), 819–843.
Meng, Q., and Liu, Z. (2012). “Impact analysis of cordon-based congestion pricing scheme on mode-split of bimodal transportation network.” Transp. Res. Part C, 21(1), 134–147.
Meng, Q., Liu, Z., and Wang, S. (2012). “Optimal distance tolls under congestion pricing and continuously distributed value of time.” Transp. Res. Part E, 48(5), 937–957.
Mun, S., Konishi, K., and Yoshikawa, K. (2003). “Optimal cordon pricing.” J. Urban Econ., 54(1), 21–38.
Mun, S., Konishi, K., and Yoshikawa, K. (2005). “Optimal cordon pricing in a non-monocentric city.” Transp. Res. Part A, 39(7–9), 723–736.
Scheel, H., and Scholtes, S. (2000). “Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity.” Math. Oper. Res., 25(1), 1–22.
Small, K. A., and Verhoef, E. T. (2007). The economics of urban transportation, Routledge, London.
Strotz, R. H. (1965). “Urban transportation parables.” The public economy of urban communities, J. Margolis, ed., Resources for the Future, Washington, DC, 127–169.
Sumalee, A. (2004). “Optimal road user charging cordon design: A heuristic optimization approach.” Comput. Aided Civ. Infrastruct. Eng., 19(5), 377–392.
Sumalee, A., Shepherd, S., and May, A. (2009). “Road user charging design: Dealing with multi-objectives and constraints.” Transportation, 36(2), 167–186.
Sun, D. J., Chang, Y., and Zhang, L. (2012). “An ant colony optimization based model for traffic counting location problem.” Transport, 165(3), 175–185.
Verhoef, E. T. (2002). “Second-best congestion pricing in general networks: Heuristic algorithms for finding second-best optimal toll levels and toll points.” Transp. Res. Part B, 36(8), 707–729.
Vickrey, W. S. (1963). “Pricing in urban and suburban transport.” Am. Econ. Rev., 53(2), 452–465.
Walters, A. A. (1961). “The theory and measurement of private and social cost of highway congestion.” Econometrica, 29(4), 676–699.
Wang, D. Z. W., and Lo, H. K. (2010). “Global optimum of the linearized network design problem with equilibrium flows.” Transp. Res. Part B, 44(4), 482–492.
Wang, S., Meng, Q., and Yang, H. (2013). “Global optimization methods for the discrete network design problem.” Transp. Res. Part B, 50, 42–60.
Yang, H., and Bell, M. G. H. (1997). “Traffic restraint, road pricing and network equilibrium.” Transp. Res. Part B, 31(4), 303–314.
Yang, H., and Lam, W. H. K. (1996). “Optimal road tolls under conditions of queuing and congestion.” Transp. Res. Part A, 30(5), 319–332.
Yang, H., and Zhang, X. (2003). “Optimal toll design in second-best link-based congestion pricing.” Transportation Research Record 1857, Transportation Research Board, Washington, DC, 85–92.
Yang, H., Zhang, X., and Huang, H. J. (2002). “Determination of optimal toll level and toll locations of alternative congestion pricing schemes.” Proc., 15th Int. Symp. on Transportation and Traffic Theory, Elsevier, Adelaide, Australia, 519–540.
Zhang, H. M., and Ge, Y. E. (2004). “Modeling variable demand equilibrium under second best road pricing.” Transp. Res. Part B, 38(8), 733–749.
Zhang, L., Lawphongpanich, S., and Yin, Y. (2009). “Reformulating and solving discrete network design problem via an active set technique.” Proc., 18th Int. Symp. on Transportation and Traffic Theory, Springer, Hong Kong, China, 283–300.
Zhang, X., and Yang, H. (2004). “Optimal cordon-based network congestion pricing problem.” Transp. Res. Part B, 38(6), 517–537.
Zheng, N., Waraich, R. A., Axhausen, K. W., and Geroliminis, N. (2012). “A dynamic cordon pricing scheme combining the Macroscopic Fundamental Diagram and an agent-based traffic model.” Transp. Res. Part A, 46(8), 1291–1303.
Zuo, Z., Liu, K., and Morikawa, T. (2011). “A swarm intelligence method for second-best road pricing problem.” Proc., 11th Int. Conf. of Chinese Transportation Professionals, ASCE, Nanjing, China, 255–266.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 139 • Issue 11 • November 2013
Pages: 1105 - 1116
Copyright
© 2013 American Society of Civil Engineers.
History
Received: Dec 15, 2012
Accepted: Jun 11, 2013
Published online: Jun 13, 2013
Published in print: Nov 1, 2013
Discussion open until: Nov 13, 2013
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.