The capacitated arc routing problem for on-road anti-dust operations

Motivated by anti-dust operations in traffic networks, where time-of-service and service types can lead to significant differences in the effectiveness of dust suppression, this paper introduces a new variant of the capacitated arc routing problem (CARP) called CARP with heterogeneous services and time-dependent profits (CARP-HSTP). A nonlinear 0-1 programming model is formulated, and a two-stage metaheuristic with variable neighborhood search (VNS) and hybrid genetic algorithm (HGA) is developed to solve it. The dust suppression effects of various services are tested through a set of atmospheric lab experiments. Evaluated via numerical experiments and field data from the Pidu network in Chengdu, China, the proposed approach-particularly VNS-outperforms current practices by 197.8%. In addition to the practical merits in anti-dust operations, the proposed method may also shed light on other CARPs with heterogeneous service and time-dependent profits or costs.