The cooperative inspection routing problem for urban environmental management

Urban environmental management against air pollution is of critical importance to public health. Despite the proliferation of ubiquitous air quality sensors and advancement of information systems, an integral part of urban environmental management in China involves routine inspections of pollution hotspots in the number of thousands distributed in the city. Departing from this particular scenario, this work proposes a routing problem termed the Cooperative Inspection Routing Problem (CIRP) that systematically integrates subset selection with mixed mandatory and elective nodes, priority heterogeneity across inspection targets, soft time windows through time-sensitive scoring with decay functions, and synchronized visits for mandatory nodes for the first time. This complex problem is formulated as a Mixed Integer Programming model and solved using a customized Adaptive Large Neighborhood Search (ALNS) algorithm in a timely fashion to accommodate real-time routing in response to pollution hazards. Based on the real Chengdu pollution source database, 112 test instances were established to examine the performance of the ALNS algorithm. On small-scale instances, the ALNS algorithm achieved solutions close to or even equivalent to those obtained by CPLEX. On large-scale instances, CPLEX can no longer obtain feasible solutions within the 1-hour time limit, while the proposed algorithm can still obtain satisfactory solutions within 10 to 100 s.