Skip to main content
SpringerLink
Log in

A Genetic Algorithm Based Approach to Optimal Toll Level and Location Problems

  • Published:
Networks and Spatial Economics Aims and scope Submit manuscript

Abstract

The derivative based approach to solve the optimal toll problem is demonstrated in this paper for a medium scale network. It is shown that although the method works for most small problems with only a few links tolled, it fails to “converge” for larger scale problems. This failure led to the development of an alternative genetic algorithm (GA) based approach for finding optimal toll levels for a given set of chargeable links. A variation on the GA based approach is used to identify the best toll locations making use of “location indices” suggested by Verhoef (2002).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Abdulaal, M. and L.J. LeBlanc. (1979). “Continuous Equilibrium Network Design Models.” Transportation Research 13B, 19–32.

    Google Scholar 

  • Allsop, R.E. (1974). “Some Possibilities for Suing Traffic Control to Influence Trip Distribution and Route Choice.” In D.J. Buckley (ed.), Proc. of the 6th International Symposium on Transportation and Traffic Theory. New York: Elsevier, pp. 345–373.

    Google Scholar 

  • Arnott, R.J., A. de Palma, and R. Lindsey. (1990). “Departure Time and Route Choice for the Morning Commuter.” Transportation Research 42B, 209–228.

    Google Scholar 

  • Ben-Ayed, O. and C. Blair. (1990). “Computational Difficulties of Bilevel Programming.” Operations Research 38, 556–560.

    Google Scholar 

  • Ben-Ayed, O., D.E. Boyce, and C.E. Blair III. (1988). “A General Bilevel Linear Programming Formulation of the Network Design Problem.” Transportation Research 22B, 311–318.

    Google Scholar 

  • Bergendorff, P., D.W. Hearn, and M.V. Ramana. (1997). “Congestion Toll Pricing of Traffic Networks.” In P.M. Pardalos, D.W. Hearn, and W.W. Hager (eds.), Lecture Notes in Economics and Mathematical Systems, Vol. 450. Springer-Verlag.

  • Boyce D.E., L.J. LeBlanc, and G.R.M. Jansen. (1991). “Optimal Toll Stations in a Road Pricing System: An Investigation into the Feasibility of Optimisation Methods.” Report INRO (unpublished).

  • Cree, N.D., M.J. Maher, and B. Paechter. (1998). “The Continuous Equilibrium Optimal Network Design Problem: A Genetic Approach.” In M.G.H. Bell (ed.), Transportation Networks: Recent Methodological Advances. Pergamon, Amsterdam, pp. 163–174.

    Google Scholar 

  • Davis, L. and M. Steenstrup. (1987). “Genetic Algorithms and Simulates Annealing: An Overview.” In L. Davis (ed.), Genetic Algorithms and Simulated Annealing. Los Altos, CA: Morgan Kaufmann Publishers, pp. 1–11.

    Google Scholar 

  • Friesz, T.L., H.J. Cho, N.J. Mehta, R.L. Tobin, and G. Anadalingam. (1992). “A Simulated Annealing Approach to the Network Design Problem with Variational Inequality Constraints.” Transportation Science 26, 18–26.

    Google Scholar 

  • Friesz, T.L., R.L. Tobin, H.-J. Cho, and N.J. Metha. (1990). “Sensitivity Analysis Based Heuristic Algorithms for Mathematical Programs with Variational Inequality Constraints.” Mathematical Programming 48, 265–284.

    Google Scholar 

  • Glazer, A. and E. Niskanen. (1992). “Parking Fees and Congestion.” Regional Science and Urban Economics 22, 123–132.

    Google Scholar 

  • Hearn, D.W. and M.V. Ramana. (1998). “Solving Congestion Toll Pricing Models.” In P. Marcotte and S. Nguyen (eds.), Equilibrium and Advances Transportation Modelling. Netherlands: Kulwer Academic Publishers, pp. 109–124.

    Google Scholar 

  • Hearn, D.W. and M.B. Yildirim. (2002). “A Toll Pricing Framework for Traffic Assignment Problems with Elastic Demand.” In M. Gendreau and P. Marcotte (eds.), Transportation and Network Analysis: Current Trends. Netherlands: Kluwer Academic Publishers.

    Google Scholar 

  • Knight, F.H. (1924). “Some Fallacies in the Interpretation of Social Cost.” Quaterly Journal of Economics 38, 582–606.

    Google Scholar 

  • LeBlanc, L.J. and D.E. Boyce. (1986). “A Bilevel Programming Algorithm for Exact Solution of the Network Design Problem with User-Optimal Flows.” Transportation Research 20B, 259–265.

    Google Scholar 

  • Levy-Lambert, H. (1968). “Tarification des Services a Qualite Variable: Application Aux Peages de Circulation.” Econometrica 36(3/4), 564–574.

    Google Scholar 

  • Liu, L.N. and J.F. McDonald. (1999). “Economic Efficiency of Second-Best Congestion Pricing Schemes in Urban Highway Systems.” Transportation Research 33B(3), 157–188.

    Google Scholar 

  • Marchand, M. (1968). “A Note on Optimal Tolls in an Imperfect Environment.” Econometrica 36, 575–581.

    Google Scholar 

  • Marcotte, P. (1983). “Network Optimization with Continuous Control Parameters.” Transportation Science 17, 181–197.

    Google Scholar 

  • Marcotte, P. (1986). “Network Design Problem with Congestion Effects: A Case of Bilevel Programming.” Mathematical Programming 34, 140–162.

    Google Scholar 

  • May, A.D., R. Liu, S.P. Shepherd, and A. Sumalee. (2002). “The Impact of Cordon Design on the Performance of Road Pricing Schemes.” Transport Policy 9, 209–220.

    Google Scholar 

  • Meng, Q., H. Yang, and M.G.H. Bell. (2001). “An Equivalent Continuous Differentiable Model and Locally Convergent Algorithm for the Continuous Network Design Problem.” Transportation Research 35B, 83–105.

    Google Scholar 

  • Michalewicz, Z. (1992). Genetic Algorithms + Data Structures = Evolution Programs. New York: Springer-Verlag.

    Google Scholar 

  • Oscar Faber Consultancy. (2001). “Road User Charging Study-West Midlands.” Final Report Prepared for Birmingham City Council (unpublished).

  • Pigou, A.C. (1920). Wealth and Welfare. London: Macmillan.

    Google Scholar 

  • Sharp, C.H. (1966). “Congestion and Welfare, an Examination of the Case for Congestion Tax.” Economic Journal 76, 806–817.

    Google Scholar 

  • Shepherd, S.P., A.D. May, and D.S. Milne. (2001a). “The Design of Optimal Road Pricing Cordons.” In Proc. of the Ninth World Conference on Transport Research. Seoul, Korea.

  • Shepherd S.P., A.D. May, D.S. Milne, and A. Sumalee. (2001b). “Practical Algorithms for Finding the Optimal Road Pricing Location and Charges.” In Proc. of European Transport Conference, Cambridge. UK. Sept. 2001.

  • Small, K.A. and J. Yan. (2001). “The Value of “Value Pricing” of Roads: Second-Best Pricing and Product Differentiation.” Journal of Urban Economics 49, 310–336.

    Google Scholar 

  • Smith, M.J. (1979). “The Existence, Uniqueness and Stability of Traffic Equilibrium.” Transportation Research 13B, 295–304.

    Google Scholar 

  • Steenbrink, P.A. (1974). Optimization of Transport Network. London: John Wiley & Sons.

    Google Scholar 

  • Suwansirikul, C., T.L. Friez, and R.L. Tobin. (1987). “Equilibrium Decomposed Optimisation: A Heuristic for the Continuous Network Equilibrium Design Problem.” Transportation Science 21, 254–263.

    Google Scholar 

  • Tobin, R.L. and T.L. Friesz. (1983). “Sensitivity Analysis for Equilibrium Network Flow.” Transportation Science 22(4), 242–250.

    Google Scholar 

  • Van Vliet, D. (1982). “SATURN—A Modern Assignment Model.” Traffic Engineering and Control 23(12).

  • Verhoef, E.T. (2002). “Second-Best Congestion Pricing in General Networks: Heuristic Algorithms for Finding Second-Best Optimal Toll Levels and Toll Points.” Transportation Research 36B, 707–729.

    Google Scholar 

  • Vickrey, W.S. (1969). “Congestion Theory and Transport Investment.” American Economics Review 59, 251–260.

    Google Scholar 

  • Walters, A.A. (1961). “The Theory and Measurement of Private and Social Cost of Highway Congestion.” Econometrica 29(4), 676–697.

    Google Scholar 

  • Wardrop, J. (1952). “Some Theoretical Aspects of Road Traffic Research.” Proc. of the Institute of Civil Engineers 1(2).

  • Wilson, J.D. (1983). “Optimal Road Capacity in the Presence of Unpriced Congestion.” Journal of Urban Economics 13, 337–357.

    Google Scholar 

  • Whitley, D. (1989). “The GENITOR Algorithm and Selection Pressure: Why Rank Based Allocation of Reproductive Trial is Best.” In J. Schaffer (ed.), Proceeding of the 3rd International Conference on Genetic Algorithms. CA, USA: Morgan Kaufmann, Publishers.

    Google Scholar 

  • Yang, H., X. Zhang, and H.-J. Huang. (2002). “Determination of Optimal Toll Level and Toll Locations of Alternative Congestion Pricing Schemes.” In M.A.P. Taylor (ed.), Transportation and Traffic Theory in the 21st Century: Proceeding of the 15th International Symposium on Transportation and Traffic Theory. Adelaide, Australia, New York: Elsevier Science.

    Google Scholar 

  • Yang, H. (1997). “Sensitivity Analysis for the Elastic-Demand Network Equilibrium Problem with Applications.” Transportation Research 31B, 55–70.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Leeds, Institute for Transport Studies, LS2 9JT, UK

    Simon Shepherd & Agachai Sumalee

Authors
  1. Simon Shepherd
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Agachai Sumalee
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Agachai Sumalee.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Shepherd, S., Sumalee, A. A Genetic Algorithm Based Approach to Optimal Toll Level and Location Problems. Networks and Spatial Economics 4, 161–179 (2004). https://doi.org/10.1023/B:NETS.0000027771.13826.3a

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/B:NETS.0000027771.13826.3a

Search

Navigation