A heuristic algorithm for solving bi-level programming problems with application to large-scale location-arc routing in urban traffic lights maintenance

Subject Areas : Transportation Analysis

Amir Abbas Shojaie ¹ , Alireza Rashidi Komijan ² , Mohammad Amirabadi ³

1 - Department of Industrial Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran
2 - Department of Industrial Engineering, Firoozkooh Branch, Islamic Azad University, Firoozkooh, Iran
3 - School of Industrial Engineering, Islamic Azad University, South Tehran Branch, Tehran, Iran

Received: 2023-11-12 Accepted : 2024-05-28 Published : 2024-06-10

Keywords: Bi-level programming, heuristic, support center location, location arc routing, urban services,

Abstract :

The present study developed a bi-level mathematical model to determine optimal routes for repair teams in charge of inspecting urban traffic lights. In this model, the municipality as the leader locates the construction sites of urban spare parts warehouses and repair centers to minimize the costs of constructing the facilities. At the follower level, the contractor determines the optimal routes for the repair teams. Bi-level models are strongly NP-hard in type. A heuristic algorithm is therefore developed to solve numerical examples, in which the leader first determines different decision-making strategies for the follower through generating a set of justified solutions. In response to the leader’s set of strategies, the follower presents a set of corresponding solutions. The individual solutions of the follower are then entered into the leader model and the corresponding values of the objective function are calculated. A solution with the optimal numerical value for the leader is ultimately selected as the Stackelberg equilibrium. The efficiency of the proposed model and algorithm was evaluated by presenting the computational results obtained from solving several random numerical examples of small, medium and large dimensions through generating the Stackelberg equilibrium and establishing a relationship between the leader and follower levels. The present findings are recommended to be used as a management tool by policymakers in the urban management sector.

References:

[1] Arakaki, R. K., & Usberti, F. L. (2019). An efficiency-based path-scanning heuristic for the capacitated arc routing problem. Computers & Operations Research, 103, 288-295. https://doi.org/10.1016/j.cor.2018.11.018
[2] Behura, N. (2007). A survey of maintenance practices of light-emitting diode traffic signals and some recommended guidelines. Institute of Transportation Engineers, 77(4), 18-22. http://worldcat.org/oclc/614107147
[3] Çetinkaya, C., Gökçen, H., & Karaoğlan, İ. (2018). The location routing problem with arc time windows for terror regions: a mixed integer formulation. Journal of Industrial and Production Engineering, 35(5), 309-318. https://doi.org/10.1080/21681015.2018.1479894
[4] Chen, L., Hà, M. H., Langevin, A., & Gendreau, M. (2014). Optimizing road network daily maintenance operations with stochastic service and travel times. Transportation Research Part E: Logistics and Transportation Review, 64, 88-102. DOI: 10.1016/j.tre.2014.02.002
[5] Chen, Y., Bouferguene, A., Shen, Y., Yin, X., & Al-Hussein, M. (2020). Bilevel Decision-Support Model for Bus-Route Optimization and Accessibility Improvement for Seniors. Journal of Computing in Civil Engineering.04019057, (2)34 DOI:10.1061/(ASCE)CP.1943-5487.0000875.
[6] Cruciol, L. L., Weigang, L., Clarke, J.-P., & Li, L. (2015). Air traffic flow management data mining and analysis for in-flight cost optimization Engineering and Applied Sciences Optimization (pp. 73-86): Springer. DOI: 10.1007/978-3-319-18320-6_5
[7] Cvokic, D.D., Stanimirovic, Z. (2020). A Single Allocation Hub Location and Pricing Problem. Computational and Applied Mathematics, 39, 40. DOI: 10.1007/s40314-019-1025-z
[8] Doulabi, S. H. H., & Seifi, A. (2013). Lower and upper bounds for location-arc routing problems with vehicle capacity constraints. European journal of operational research, 224(1), 189-208. DOI: 10.1016/j.ejor.2012.06.015
[9] Eiselt, H. A., & Marianov, V. (2015). Location modeling for municipal solid waste facilities. Computers & Operations Research, 62, 305-315. DOI: 10.1016/j.cor.2014.05.003
[10] El Hatri, C., & Boumhidi, J. (2017). Traffic management model for vehicle re-routing and traffic light control based on Multi-Objective Particle Swarm Optimization. Intelligent Decision Technologies, 11(2).199-208. DOI: 10.3233/IDT-170288
[11] Fernández, E., Laporte, G., & Rodríguez-Pereira, J. (2019). Exact Solution of Several Families of Location-Arc Routing Problems. Transportation Science, 53(5), 1313-1333. DOI: 10.1287/trsc.2018.0881
[12] Gao, H., & Zhang, X. (2013). A Markov‐Based Road Maintenance Optimization Model Considering User Costs. Computer‐Aided Civil and Infrastructure Engineering, 28(6), 451-464. DOI: 10.1111/mice.12009
[13] Göttlich, S., Herty, M., & Ziegler, U. (2015). Modeling and optimizing traffic light settings in road networks. Computers & Operations Research.55, 36-51. . DOI: 10.1016/j.cor.2014.10.001
[14] Han, G., Wang, H., Jiang, J., Zhang, W., & Chan, S. (2018). CASLP: A confused arc-based source location privacy protection scheme in WSNs for IoT. IEEE Communications Magazine, 56(9), 42-47. DOI: 10.1109/MCOM.2018.1701062
[15] Hiassat, A., Diabat, A., & Rahwan, I. (2017). A genetic algorithm approach for location-inventory-routing problem with perishable products. Journal of Manufacturing Systems, 42, 93-103. DOI: 10.1016/j.jmsy.2016.10.004
[16] Huber, S. (2016). Strategic decision support for the bi-objective location-arc routing problem. Paper presented at the 2016 49th Hawaii International Conference on System Sciences (HICSS). DOI: 10.1016/j.jmsy.2016.10.004
[17] Jayaswal, S., Vidyarthi, N. (2023). Multiple Allocation Hub Location with Service Level Constraints for Two Shipment Classes. European Journal of Operational Research, 309(2), 634-655. DOI: 10.1016/j.ejor.2023.01.066
[18] Khan, M. U., Mesbah, M., Ferreira, L., & Williams, D. J. (2017). Development of a post-flood road maintenance strategy: Case study Queensland, Australia. International Journal of Pavement Engineering, 18(8), 702-713. DOI: 10.1080/10298436.2015.1121781
[19] Miao, T.T., Qin, T.B. (2023). A Bi-Objective Mixed Capacitated Arc Routing Problem Based on Epsilon Constraint Algorithm. 3rd International Conference on Artificial Intelligence, Automation, and High-Performance Computing (AIAHPC 2023); 127172E. DOI: 10.1080/10298436.2015.1121781
[20] Moretti, L., Cantisani, G., & Di Mascio, P. (2016). Management of road tunnels: Construction, maintenance and lighting costs. Tunnelling and Underground Space Technology, 51, 84-89. DOI: 10.1016/j.tust.2015.10.027
[21] Norouzi, N., Sadegh-Amalnick, M., & Tavakkoli-Moghaddam, R. (2017). Modified particle swarm optimization in a time-dependent vehicle routing problem: minimizing fuel consumption. Optimization Letters, 11(1), 121-134. DOI: 10.1007/s11590-015-0996-y
[22] Ouma, Y. O., Opudo, J., & Nyambenya, S. (2015). Comparison of fuzzy AHP and fuzzy TOPSIS for road pavement maintenance prioritization: methodological exposition and case study. Advances in Civil Engineering, 2015. DOI: 10.1155/2015/140189
[23] Ozbek, M. E., de la Garza, J. M., & Triantis, K. (2010). Data and modeling issues faced during the efficiency measurement of road maintenance using data envelopment analysis. Journal of Infrastructure Systems, 16(1), 21-30. DOI: 10.1061/(ASCE)1076-0342(2010)16:1(21)
[24] Parvasi, S. P., Tavakkoli-Moghaddam, R., Taleizadeh, A. A., & Soveizy, M. (2019). A Bi-Level Bi-Objective Mathematical Model for Stop Location in a School Bus Routing Problem. IFAC-PapersOnLine, 52(13), 1120-1125. DOI: 10.1016/j.ifacol.2019.11.346
[25] Pérez-Ocón, F., Rubiño, M., Pozo, A., & Rabaza, O. (2013). Design of new traffic lights: Traffic safety and maintenance ease. Engineering Structures, 57, 388-392. DOI: 10.1016/j.engstruct.2013.09.047
[26] Rabbani, M., Heidari, R., Farrokhi-Asl, H., & Rahimi, N. (2018). Using metaheuristic algorithms to solve a multi-objective industrial hazardous waste location-routing problem considering incompatible waste types. Journal of cleaner production, 170, 227-241. DOI: 10.1016/j.jclepro.2017.09.029
[27] Rayat, F., Musavi, M., & Bozorgi-Amiri, A. (2017). Bi-objective reliable location-inventory-routing problem with partial backordering under disruption risks: A modified AMOSA approach. Applied Soft Computing, 59, 622-643. DOI: 10.1016/j.asoc.2017.06.036
[28] Skabardonis, A. (2020). Traffic management strategies for urban networks: smart city mobility technologies Transportation, Land Use, and Environmental Planning (pp. 207-216): Elsevier. DOI: 10.3390/drones8010007
[29] Soltani, A., Hewage, K., Reza, B., & Sadiq, R. (2015). Multiple stakeholders in multi-criteria decision-making in the context of municipal solid waste management: a review. Waste management, 35, 318-328. https://doi.org/10.1016/j.wasman.2014.09.010
[30] Stoilov, T., & Stoilova, K. (2016). A Self-Optimization Traffic Model by Multilevel Formalism Autonomic Road Transport Support Systems (pp. 87-111): Springer. DOI: 10.1007/978-3-319-25808-9_6
[31] Tohidi, H., & Jabbari, M. M. (2012) “CRM in organizational structure design,” Procedia Technology, 1, 579-582.‏ https://doi.org/10.1016/j.protcy.2012.02.126
[32] Tohidi, H., & Jabbari, M. M. (2012) “The necessity of using CRM,” Procedia Technology, 1, 514-516.‏ https://doi.org/10.1016/j.protcy.2012.02.110
[33] Tohidi, H., Namdari, A., Keyser, T. K., & Drzymalski, J. (2017) “Information sharing systems and teamwork between sub-teams: a mathematical modeling perspective,” Journal of Industrial Engineering International, 13, 513-520.‏ DOI 10.1007/s40092-017-0199-5
[34] Tavakkoli-Moghaddam, R., Amini, A., & Ebrahimnejad, S. (2018). A new mathematical model for a multi-product location-arc routing problem. Paper presented at the 2018 4th International Conference on Optimization and Applications (ICOA). DOI: 10.1109/ICOA.2018.8370551
[35] Tirkolaee, E. B., Alinaghian, M., Hosseinabadi, A. A. R., Sasi, M. B., & Sangaiah, A. K. (2019). An improved ant colony optimization for the multi-trip Capacitated Arc Routing Problem. Computers & Electrical Engineering, 77, 457-470. DOI: 10.1016/j.compeleceng.2018.01.040
[36] Tong, L., Nie, L., Guo, G.-c., Leng, N.-n., & Xu, R.-x. (2019). Layout scheme of high-speed railway transfer hubs: bi-level modeling and hybrid genetic algorithm approach. Cluster Computing, 22(5), 12551-12566. DOI: 10.1007/s10586-017-1682- x
[37] Wøhlk, S., & Laporte, G. (2018). A fast heuristic for large-scale capacitated arc routing problems. Journal of the Operational Research Society, 69(12), 1877-1887. https://doi.org/10.1080/01605682.2017.1415648
[38] Wøhlk, S., & Laporte, G. (2019). A districting-based heuristic for the coordinated capacitated arc routing problem. Computers & Operations Research, 111, 271-284. https://doi.org/10.1016/j.cor.2019.07.006
[39] Wu, Y., Qureshi, A.G., Yamada, T. (2022). Adaptive Large Neighborhood Decomposition Search Algorithm for Multi-Allocation Hub Location Routing Problem. European Journal of Operational Research, 302(3), 1113-1127. https://doi.org/10.1016/j.ejor.2022.02.002
[40] Yurtseven, C., & Gökçe, M. A. (2019). A Novel Arc-routing Problem of Electric Powered Street Sweepers with Time Windows and Intermediate Stops. IFAC-PapersOnLine, 52(13), 2308-2313. https://doi: 10.1016/j.ifacol.2019.11.550.