Hybridization of NSGA-II and MILP for optimization of the location of electric-scooters sharing-stations
Keywords:
Multi-Objective Mixed-Integer Linear Programming, Meta-heuristics, Math-heuristics, E-Scooters, Sustainable TransportationAbstract
TA crucial aspect of the proper functioning of bikes and electric scooters’ sharing systems is the correct location
and dimensioning of the sharing stations. The resolution of the previous problem is carried out based on the maximization of coverage or the minimization of costs, but the two objectives are not usually treated at the same time.
In this work, we propose a method based on the hybridization of the popular Elitist Non-Dominated Sorting Genetic Algorithm (NSGA- II) with a Mixed-Integer Linear Programming (MILP) model to approximate the Pareto Frontier of the problem. This allows the decision-maker a greater understanding of the range of possible options. The NSGA-II plays the role of an outer block that deals with the selection and sizing of each of sharing stations. The MILP model is an inner block that calculates the associated coverage of that solution. The schema was compared with an adaptative-weighting algorithm, reaching the hybridization of NSGA-II and MILP a better coverage of the Pareto Frontier.
Downloads
References
C. Hardt and K. Bogenberger, “Usage of e-scooters in urban environments,” Transportation Research Procedia, vol. 37, pp. 155–162, 2019, 21st EURO Working Group on Transportation Meeting, EWGT 2018, 17th – 19th September 2018, Braunschweig, Germany. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S2352146518305933
Łukasz Nawaro, “E-scooters: competition with shared bicycles and relationship to public transport,” International Journal of Urban Sustainable Development, vol. 13, no. 3, pp. 614–630, 2021. [Online]. Available: https://doi.org/10.1080/19463138.2021.1981336
A. Bozzi and A. Aguilera, “Shared e-scooters: A review of uses, health and environmental impacts, and policy implications of a new micro-mobility service,” Sustainability (Switzerland), vol. 13, 08 2021.
I. Frade and A. Ribeiro, “Bike-sharing stations: A maximal covering location approach,” Transportation Research Part A General, vol. 82, p.216–227, 12 2015.
T. Casey. (2021, Mar.) Where to dock charge them all? Web article. CleanTechnica. https://cleantechnica.com/2021/03/05/so-many-e-scooters-so-where-to-dock-charge-them-all/.
C. Shui and W. Szeto, “A review of bicycle-sharing service planning problems,” Transportation Research Part C: Emerging Technologies, vol. 117, p. 102648, 2020. [Online]. Available:https://www.sciencedirect.com/science/article/pii/S0968090X20305635
J. Zhou, Y. Guo, J. Sun, E. Yu, and R. Wang, “Review of bike-sharing system studies using bibliometrics method,” Journal of Traffic and Transportation Engineering (English Edition), 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S2095756422000174
J. C. García-Palomares, J. Gutiérrez, and M. Latorre, “Optimizing the location of stations in bike-sharing programs: A gis approach,” Applied Geography, vol. 35, no. 1, pp. 235–246, 2012. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0143622812000744
E. Croci and D. Rossi, “Optimizing the position of bike sharing stations. The Milan case.” SSRN Electronic Journal, 01 2014.
J. Liu, Q. Li, M. Qu, W. Chen, J. Yang, H. Xiong, H. Zhong, and Y. Fu, “Station site optimization in bike sharing systems,” in 2015 IEEE International Conference on Data Mining, 2015, pp. 883–888.
C. Park and S. Sohn, “An optimization approach for the placement of bicycle-sharing stations to reduce short car trips: An application to the city of seoul,” Transportation Research Part A: Policy and Practice, vol. 105, pp. 154–166, 11 2017.
C. Cintrano, F. Chicano, and E. Alba, “Using metaheuristics for the location of bicycle stations,” Expert Systems with Applications, vol. 161, p. 113684, 2020. [Online]. Available: https://www.sciencedirect. com/science/article/pii/S095741742030508X
K. E. Rosing, C. S. Revelle, and H. Rosing-Vogelaar, “The p-median and its linear programming relaxation: An approach to large problems,” The Journal of the Operational Research Society, vol. 30, no. 9, pp. 815–823, 1979. [Online]. Available: http://www.jstor.org/stable/3009503
E. Alba and E. Domínguez, “Comparative analysis of modern optimization tools for the p-median problem,” Statistics and Computing, vol. 16, pp. 251–260, 09 2006.
T. Drezner and Z. Drezner, “The gravity p-median model,” European Journal of Operational Research, vol. 179, pp. 1239–1251, 02 2007.
W. Mu and D. Tong, “On solving large p-median problems,” Environment and Planning B: Urban Analytics and City Science, vol. 47, no. 6, pp. 981–996, 2020. [Online]. Available: https://doi.org/10.1177/2399808319892598
R. Church and C. ReVelle, “The maximal covering location problem,” Papers of the Regional Science Association, vol. 32, no. 1, pp. 101–118, 1974. [Online]. Available: https://doi.org/10.1007/BF01942293
N. Megiddo, E. Zemel, and S. L. Hakimi, “The maximum coverage location problem,” Siam Journal on Algebraic and Discrete Methods, vol. 4, pp. 253–261, 1983.
M. Fazel Zarandi, S. Davari, and S. Haddad Sisakht, “The large scale maximal covering location problem,” Scientia Iranica, vol. 18, no. 6, pp. 1564–1570, 2011. [Online]. Available: https: //www.sciencedirect.com/science/article/pii/S1026309811002100
V. C. Guzmán, D. A. Pelta, and J. L. Verdegay, “An approach for solving maximal covering location problems with fuzzy constraints,” International Journal of Computational Intelligence Systems, vol. 9, pp. 734–744, 2016. [Online]. Available: https://doi.org/10.1080/18756891. 2016.1204121
M. Bansal, “Planar maximum coverage location problem with partial coverage and general spatial representation of demand and service zones,” 09 2017.
R. Alizadeh, T. Nishi, J. Bagherinejad, and M. Bashiri, “Multi-period maximal covering location problem with capacitated facilities and modules for natural disaster relief services,” Applied Sciences, vol. 11, no. 1, 2021. [Online]. Available: https://www.mdpi.com/2076-3417/11/1/397
D. Ma, T. Guo, J. Yang, L. He, and K. Tang, “Layout optimization of campus bike-sharing parking spots,” Journal of Advanced Transportation, vol. 2020, p. 8894119, 2020. [Online]. Available: https://doi.org/10.1155/2020/8894119
J. Yu, Y. Ji, C. Yi, C. Kuai, and D. I. Samal, “Optimization model for the supply volume of bike-sharing: Case study in nanjing, china,” Information, vol. 12, no. 5, 2021. [Online]. Available: https://www.mdpi.com/2078-2489/12/5/182
Z. Tian, W. Hou, X. Gu, F. Gu, and B. Yao, “The location optimization of electric vehicle charging stations considering charging behavior,” SIMULATION, vol. 94, no. 7, pp. 625–636, 2018. [Online]. Available: https://doi.org/10.1177/0037549717743807
S. Yan, C.-K. Lin, and Z.-Q. Kuo, “Optimally locating electric scooter battery swapping stations and battery deployment,” Engineering Optimization, vol. 53, no. 5, pp. 754–769, 2021. [Online]. Available: https://doi.org/10.1080/0305215X.2020.1751148
S. Deb, X.-Z. Gao, K. Tammi, K. Kalita, and P. Mahanta, “Nature-inspired optimization algorithms applied for solving charging station placement problem: Overview and comparison,” Archives of Computational Methods in Engineering, vol. 28, pp. 91–106, 2019.
Y.-W. Chen, C.-Y. Cheng, S.-F. Li, and C.-H. Yu, “Location optimization for multiple types of charging stations for electric scooters,” Applied Soft Computing, vol. 67, pp. 519–528, 2018. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1568494618300978
M. J. Alves and J. Clímaco, “A review of interactive methods for multiobjective integer and mixed-integer programming,” European Journal of Operational Research, vol. 180, no. 1, pp. 99–115, 2007. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0377221706002384
M. A. Boschetti, V. Maniezzo, M. Roffilli, and A. Bolufé Röhler, “Matheuristics: Optimization, simulation and control,” in Hybrid Metaheuristics, M. J. Blesa, C. Blum, L. Di Gaspero, A. Roli, M. Sampels, and A. Schaerf, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 171–177.
M. Ball, “Heuristics based on mathematical programming,” Surveys in Operations Research and Management Science, vol. 16, pp. 21–38, 01 2011.
I. Herszterg, “Efficient algorithms for solving multi-objective optimization and large-scale transportation problems,” Ph.D. dissertation, Georgia Institute of Technology, Aug. 2020.
M. Á. Domínguez-Ríos, F. Chicano, and E. Alba, “Improving search efficiency and diversity of solutions in multiobjective binary optimization by using metaheuristics plus integer linear programming,” in Applications of Evolutionary Computation, P. A. Castillo and J. L. Jiménez Laredo, Eds. Cham: Springer International Publishing, 2021, pp. 242–257.
H. Xu, W. Fan, T. Wei, and L. Yu, “An or-opt nsga-ii algorithm for multi-objective vehicle routing problem with time windows,” in 2008 IEEE International Conference on Automation Science and Engineering, 2008, pp. 309–314.
J. J. Durillo, J. Garcia-Nieto, A. J. Nebro, C. A. C. Coello, F. Luna, and E. Alba, “Multi-objective particle swarm optimizers: An experimental comparison,” in EMO 2009, 2009.
M. Elarbi, S. Bechikh, L. B. Said, and R. Datta, Recent Advances in Evolutionary Multi-objective Optimization. Springer, 2017, ch. Multi-objective Optimization: Classical and Evolutionary Approaches, pp. 1–30.
Q. Liu, X. Li, H. Liu, and Z. Guo, “Multi-objective metaheuristics for discrete optimization problems: A review of the state-of-the-art,” Applied Soft Computing, vol. 93, p. 106382, 2020. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1568494620303227
E. Mezura-Montes and C. A. Coello Coello, “Constraint-handling in nature-inspired numerical optimization: Past, present and future,” Swarm and Evolutionary Computation, vol. 1, no. 4, pp. 173–194, 2011. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S2210650211000538
S. Luke. (2013) Essentials of metaheuristics. [Online]. Available: http://cs.gmu.edu/sean/book/metaheuristics/
T. Saber, A. Ventresque, J. Marques-Silva, J. Thorburn, and L. Murphy, “Milp for the multi-objective vm reassignment problem,” 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 41–48, 2015.
M. Fischetti and M. Fischetti, Matheuristics. Cham: Springer International Publishing, 2016, pp. 1–33. [Online]. Available: https://doi.org/10.1007/978-3-319-07153-4_14-1
K. Deb, Multi-Objective Optimization using Evolutionary Algorithms. John Wiley and Sons, 2001. O. L. de Weck, “Multiobjective optimization : History and promise,” 2004.
N. Jozefowiez, F. Semet, and E.-G. Talbi, “Enhancements of nsga ii and its application to the vehicle routing problem with route balancing,” 102005, pp. 131–142.
K. Bestuzheva, M. Besançon, W.-K. Chen, A. Chmiela, T. Donkiewicz, J. van Doornmalen, L. Eifler, O. Gaul, G. Gamrath, A. Gleixner, L. Gottwald, C. Graczyk, K. Halbig, A. Hoen, C. Hojny, R. van der Hulst, T. Koch, M. Lübbecke, S. J. Maher, F. Matter, E. Mühmer, B. Müller, M. E. Pfetsch, D. Rehfeldt, S. Schlein, F. Schlösser, F. Serrano, Y. Shinano, B. Sofranac, M. Turner, S. Vigerske, F. Wegscheider, P. Wellner, D. Weninger, and J. Witzig, “The SCIP Optimization Suite 8.0,” Optimization Online, Technical Report, December 2021. [Online]. Available: http://www.optimization-online.org/DB_HTML/2021/12/8728.html
L. Kim and O. D. Weck, “Adaptive weighted sum method for multi-objective optimization: a new method for pareto front generation,” Structural and Multidisciplinary Optimization, vol. 2, no. 31, pp. 105–116, 2006.
J. Ryu, S. Kim, and H. Wan, “Pareto front approximation with adaptive weighted sum method in multiobjective simulation optimization,” in Proceedings of the 2009 Winter Simulation Conference (WSC), Dec 2009, pp. 623–633.
E. Zitzler and L. Thiele, “Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach,” IEEE Transactions on Evolutionary Computation, vol. 3, no. 4, pp. 257–271, Nov 1999.
E. Zitzler, D. Brockhoff, and L. Thiele, “The hypervolume indicator revisited: On the design of pareto-compliant indicators via weighted integration,” in Evolutionary Multi-Criterion Optimization, S. Obayashi.
K. Deb, C. Poloni, T. Hiroyasu, and T. Murata, Eds. Berlin, Heidelberg: Springer, 2007, pp. 862–876.
