Modified NSGA-II for solving Bi-objective support unit location problem to assist roadside traffic survey with multi-stages

• Published in: Expert systems with applications 2024-09, Vol.249, p.123448, Article 123448
• Main Authors: Camara, Marcus Vinicius Oliveira, Ferrari, Thayse, Ribeiro, Glaydston Mattos
• Format: Article
• Language: English
• Subjects: Bi-objective optimization; Facility location; Modified NSGA-II; Roadside traffic survey
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2024.123448

Monitoring highways and obtaining traffic data are relevant for planning and programming new investments. This data often comes from automatic counting stations or roadside traffic surveys that can also obtain socioeconomic and trip origin and destination information. This paper presents novel contributions to address the Bi-objective Support Unit Location Problem to Assist Roadside Traffic Survey with Multi-Stages (BSULP). The objective of this research is to propose an approach to optimize two conflicting objectives simultaneously: minimizing travel costs from support units to survey stations and minimizing the number of selected support units. To achieve this, we propose three modified versions of the NSGA-II algorithm, with tailored strategies for constraints handling of the BSULP. These strategies involve a significantly reduced structure for the chromosomes, and initial population, crossover and mutation algorithms that maintain the feasibility of the solutions. For a benchmark of instances, we implemented an exact ϵ-Constraint method, and the results were compared with different versions of modified NSGA-II using Hypervolume (HV) and Generational Distance (GD) metrics. The best results were obtained with the M3NSGA-II version, which on average represented more than 94% (HV) and less than 17% (runtime) of the exact method. In addition, it was possible to obtain solutions for large instances which was not possible with the exact method. •Modified NSGA proposal with relevant results in reduced computational time.•Chromosome encoding with significant size reduction and increased efficiency.•A new strategy for population reduction after the first generation.•Average of 94% for the Hypervolume with less than 17% of the exact method runtime.•Greater gains on medium and large instances.