Application of Particle Swarm Optimization and Genetic Algorithm Techniques to Solve Bi-level Congestion Pricing Problems

Document Type : Research Paper

Authors

1 MSc. Grad., Department of Civil Engineering Department, Yazd University, Yazd, Iran

2 Assistant Professor, Department of Civil Engineering, Yazd University, Yazd, Iran

3 Assistant Professor, Industrial Engineering Division, Yazd University, Iran

Abstract

The solutions used to solve bi-level congestion pricing problems are usually based on heuristic network optimization methods which may not be able to find the best solution for these type of problems. The application of meta-heuristic methods can be seen as viable alternative solutions but so far, it has not received enough attention by researchers in this field. Therefore, the objective of this research was to compare the performance of two meta-heuristic algorithms namely, Genetic Algorithm (GA) and Particle Swarm Optimization (PSO), with each other and also with a conventional heuristic method in terms of degree of optimization, computation time and the level of imposed tolls. Hence, a bi-level congestion pricing problem formulation, for simultaneous optimization of toll locations and toll levels on a road network, using these two meta-heuristic methods, was developed. In the upper level of this bi-level problem, the objective was to maximize the variation in the Net Social Surplus (NSS) and in the lower level, the Frank-Wolfe user equilibrium method was used to assign traffic flow to the road network. PSO and GA techniques were used separately to determine the optimal toll locations and levels for a Sioux Falls network. The numerical results obtained for this network showed that GA and PSO demonstrated an almost similar performance in terms of variation in the NSS. However, the PSO technique showed 45% shorter run time and 24% lower mean toll level and consequently, a better overall performance than GA technique. Nevertheless, the number and location of toll links determined by these two methods were identical. Both algorithms also demonstrated a much better overall performance in comparison with a conventional heuristic algorithm. The results indicates the capability and superiority of these methods as viable solutions for application in congestion pricing problems. 

Keywords

References

- Cree, N. D., Maher, M. J and Paechter, B. (1998) “The continuous equilibrium optimal network design problem: a genetic approach”, Transportation Networks: Recent Methodological Advances. Pergamon, Amsterdam, pp. 163–174.
- Ekstrom, J. (2008) “Designing urban road congestion charging systems-models and heuristic solution approaches”, M.Sc. thesis, Department of Science and Technology, Linkoping University, Sweden.
- Ekstrom, J. (2014) “Finding second-best toll locations and levels by relaxing the set of first-best feasible toll vectors”, European Journal of Transport and Infrastructure Research, Vol. 14, No. 1, pp. 7-29.
- Fan, W. (2016) “Optimal congestion pricing toll design under multiclass transportation network schemes: Genetic algorithm approaches”, Journal of Case Studies on Transport Policy, Vol. 2, No. 4, pp. 78-87.
- Frank, M. and Wolfe, P. (1956) “An algorithm for quadratic programming”, Journal of Naval Research Logistics Quarterly, Vol. 3, pp. 95–110.
- Kuoa, R. J. and Huang, C. C. (2009) “Application of particle swarm optimization algorithm for solving bi-level linear programming problem”, Journal of Computers and Mathematics with Applications, Vol. 58, No. 4, pp. 678–685.
- LeBlanc, L. J. (1975) “An algorithm for the discrete network design problem”, Journal of Transportation Science, Vol. 9, No. 3, pp. 183-199.
- Li, Z. and Hensher, D. A (2012) “Congestion charging and car use: A review of stated preference and opinion studies and market monitoring evidence”, Journal of Transport Policy, Vol. 20, pp. 47-61.
- Lindsey, R. and Verhoef, E.T. (2001) “Traffic congestion and congestion pricing”, In: D.A. Hensher and K.J. Button (Eds.) (2001) Handbook of Transport Systems and Traffic Control, Handbooks in Transport, Vol. 3, Elsevier /Pergamon, Amsterdam, pp.77–105.
- Liu, L. N. and McDonald, G. (1999) “Economic efficiency of second-best congestion pricing schemes in urban highway systems”, Journal of Transportation Research Part B, Vol. 33, pp. 157–188.
- Ma, W. and Wang, M. (2013) “Particle Swarm Optimization-based algorithm for bi-level joint pricing and lot-sizing decisions in a supply chain”, International Journal of Applied Artificial Intelligence, Vol. 27, No. 6, pp. 441-460.
- Marchand, M. (1968) “A note on optimal tolls in an imperfect environment”, Journal of Econometrica, Vol. 36, pp. 575–581.
- Mirbaha, B., Saffarzadeh, M., Seyed Abrishami, S. E. and Prdovani, A. (2014) “Evaluating the Willingness to pay for urban congestion priced zones (case study of Tehran)”, International Journal of Transportation Engineering, Vol. 1, No. 3, pp. 199-210.
- Sheffi, Y. (1984) “Urban transportation networks: Equilibrium analysis with mathematical programming methods”, Prentice-Hall, New Jersey.
- Shepherd, S. and Sumalee, A. (2004) “A genetic algorithm based approach to optimal toll level and locations problems”, Journal of Network Spatial Economics, Vol. 2, No. 4, pp. 161–179.
- Sumalee, A. (2004) “Optimal road user charging cordon design: A heuristic optimization approach”, Journal of Computer-Aided Civil and Infrastructure Engineering Vol. 19, No. 5, pp. 377–392.- -       Verhoef, E.T., Nijkamp, P. and Ritveld, P. (1996) “Second-best congestion pricing: the case of an un-tolled alternative”, Journal of Urban Economics, Vol. 40, No. 3, pp. 279–302.
- Verhoef, E.T. (2002) “Second-best congestion pricing in general static transportation networks with elastic demands”, Journal of Regional Science and Urban Economics, Vol. 32, No. 3, pp. 281-310.
- Yang, H. and Lam, W.H.K. (1996) “Optimal road tolls under conditions of queuing and congestion”, Journal of Transportation Research Part A, Vol. 30, No. 5, pp. 319–332.
- Yang, H. and Zhang, X. (2003) “Optimal toll design in second-best link-based congestion pricing”, Journal of Transportation Research Record, No. 1857, pp. 85–92.
- Yang, H. and Huang H. J. (2005) “Mathematical and economic theory of road pricing”, Elsevier Science Inc, New York.
- Zaman, F., Elsayed, S. M., Ray, T. and Sarker, R. A. (2017) “Co-evolutionary approach for strategic bidding in competitive electricity markets”, Journal of Applied Soft Computing, Vol.  51, pp. 1-22.
- Zhao, Z. and Gu, X. (2006) “Particle swarm optimization based algorithm for bilevel programming problems”, Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications, Vol. 02, pp. 951-956.
- Zhong, F. Yuan, B. and Li, B. (2016) “A hybrid evolutionary algorithm for multiobjective variation tolerant logic mapping on nanoscale crossbar architectures”, Journal of Applied Soft Computing, Vol. 38, pp. 955-966.
International Journal of Transportation Engineering
Volume 5, Issue 3 - Serial Number 19
January 2018
Pages 261-273

Files

Share

How to cite

Statistics