Article
A COMPARATIVE ANALYSIS OF METAHEURISTIC APPROACHES FOR SENSORS DEPLOYMENT PROBLEM ON TRANSPORT NETWORKS
DOI: 10.7708/ijtte.2021.11(2).10
11 / 2 / 310-322 Pages
Author(s)
Ivana Jovanović - University of Belgrade, Faculty of Transport and Traffic Engineering, Vojvode Stepe 305, 11000 Belgrade, Serbia -
Abstract
The need for traffic flow data is essential for proper traffic management and control. Travel time estimation and early response to possible traffic incidents can be achieved with deployment of appropriate number of detectors, and placing them on optimal locations on traffic network. With more detectors located the level of accuracy of the data obtained increases, while at the same time requires more investment and maintenance costs. The detectors should be deployed in such a way to appropriately sample traffic conditions, and also provide travel time estimation with the lowest possible error. On the other hand, traffic authorities have a tendency to reduce the number of detectors located on the network in order to achieve investment savings. The proposed model provides the most suitable detector locations on a road section, while minimizing travel time estimation error with limited available funds which are considered in the model constraints. The Bee Colony Optimization metaheuristic was used to solve the sensor deployment problem, and its variant based on solution improvement, BCOi. The results obtained using BCOi metaheuristics were compared with the results obtained using the Simulated Annealing (SA) metaheuristics. In terms of the CPU time, BCOi outperformed the SA algorithm, while in comparable operating time the BCOi algorithm achieved better solutions to larger scale problems. The applications of both algorithms were tested on real case study data on a section of the E-763 road in the Republic of Serbia.
Number of downloads: 412
Acknowledgements:
This research was partially supported by the Ministry of Education, Science and Technological Development, Government of the Republic of Serbia, through the project TR36002 for the period 2011-2020.
References:
Bianco, L.; Confessore, G.; Gentili, M. 2006. Combinatorial aspects of the sensor location problem, Annals of Operations Research 144: 201–234.
Černý, V. 1985. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, Journal of Optimization Theory and Applications 45: 41–51.
Davidović, T.; Ramljak, D.; Šelmić, M.; Teodorović, D. 2011. Bee colony optimization for the p-center problem, Computers and Operations Research 38(10): 1367–1376.
Edara, P.; Guo, J.; Smith, B. L.; Mc Ghee, C. 2008. Optimal placement of point detectors on Virginia’s highways: case studies of northern Virginia and Richmond. Report VTRC08-CR3. Virginia Transportation Research Council, Richmond, VА.
Edara, P.; Smith, B.; Guo, J.; Babiceanu, S.; McGhee, C. 2011. Methodology to identify optimal placement of point detectors for travel time estimation, Journal of Transportation Engineering 137(3): 155–173.
Eglese, R.W. 1990. Simulated Annealing: A tool for Operational Research, European Journal of Operational Research 46(3): 271–281.
Jovanović, A. 2017. Choice of signal timing for traffic control by bee colony optimization. Doctoral disertation, Faculty of Transport and Traffic Engineering, University of Belgrade, Belgrade. 131p. (in Serbian).
Jovanović, I. 2020. Sensors selection and deployment on transport networks using operations research methods. Doctoral disertation, Faculty of Transport and Traffic Engineering, University of Belgrade, Belgrade. 169p. (in Serbian).
Jovanović, A.; Nikolić, M.; Teodorović, D. 2017. Area-wide urban traffic control: a bee colony optimization approach, Transportation Research Part C: Emerging Technologies 77: 329–350.
Jovanović, I.; Šelmić, M.; Nikolić, M. 2019. Metaheuristic approach to optimize placement of detectors in transport networks – case study of Serbia, Canadian Journal of Civil Engineering 46(3): 176–187.
Kim, J.; Park, B.; Lee, J.; Won, J. 2011. Determining optimal sensor locations in freeway using genetic algorithm-based optimization, Engineering Applications of Artificial Intelligence 24: 318–324.
Kirkpatrick, S.; Gelatt Jr., C.D.; Vecchi, M.P. 1983. Optimization by Simulated Annealing, Science 220(4598): 671–680.
Liu, H.; Danczyk, A. 2009. Optimal sensor locations for freeway bottleneck identification, Computer-Aided Civil and Infrastructure Engineering 24 (8): 535–550.
Metropolis, N.; Rosenbluth, A.; Rosenbluth, M.; Teller, A. 1953. Equation of state calculations by fast computing machines, Journal of Chemical Physics 21: 1087–1092.
Nikolić, M.; Teodorović, D. 2013. Transit network design by bee colony optimization, Expert Systems with Applications 40(15): 5945–5955.
Nikolić, M.; Teodorović, D. 2014. A simultaneous transit network design and frequency setting: Computing with bees, Expert Systems with Applications, 41 (16): 7200–7209.
Nikolić, M.; Teodorović, D. 2015. Vehicle rerouting in the case of unexpectedly high demand in distribution systems, Transportation Research Part C: Emerging Technologies 55: 535–545.
Nikolić, M.; Teodorović, D. 2019. Mitigation of disruptions in public transit by Bee Colony Optimization, Transportation Planning and Technology 42(6): 573–586.
Nikolić, M.; Teodorović, D.; Vukadinović, K. 2015. Disruption management in public transit: the bee colony optimization approach, Transportation Planning and Technology 38(2): 162–180.
Nikolić, М. 2015. Disruption management in transportation by the Bee Colony Optimization metaheuristic. Doctoral disertation, Faculty of Transport and Traffic Engineering, University of Belgrade, Belgrade. 159p. (in Serbian).
Teodorović, D. 2007. Transportation networks. Faculty of Transport and Traffic Engineering, University of Belgrade, Belgrade. 429 p. (in Serbian).
Teodorović, D.; Šelmić, M.; Praveen, E. 2010. Bee colony optimization approach to optimize placement of traffic sensors on highways. In Proceedings of the 13th International Conference on Traffic Science, 27.-28. May 2010, Portorož, Slovenia.
Teodorović, D.; Šelmić, M.; Nikolić, M.; Jovanović, I.; Vidas, M. 2017. Metaheuristic approach for detector locations in transport networks. In Proceedings of SYM-OP-IS 2017: XLIV Symposium on Operational Research, Zlatibor, 723–728. (in Serbian).
Todorović, N.; Petrović, S. 2013. Bee colony optimization algorithm for nurse rostering, IEEE Transactions on Systems, Man, and Cybernetics: Systems 43(2): 467–473.
Vidas, M. 2017. Impact of access control on capacity and level of service of two-lane highways. Doctoral disertation, Faculty of Transport and Traffic Engineering, University of Belgrade, Belgrade. 203p. (in Serbian).
Quoted IJTTE Works
There is no quoted studies.
Related Keywords