A two-stage scheduling algorithm for dynamic interval multi-objective vehicle routing problem in medical waste collection

Proper scheduling of medical waste collection vehicles can reduce the cost of large-scale epidemic prevention and control, and improve the collecting efficiency. In this work, a multi-objective, multi-trip and multi-intermediate depot vehicle routing model for collecting medical wastes is developed, accounting for the uncertainty of vehicle speed and dynamic changes in customer requirements, as well as the differences in disposal capacity of various disposal sites. The cost and infection risk are minimized through the determination of the optimal collecting route and disposal site for each vehicle, while considering the constraints of vehicle capacity and number of vehicles. To solve the model, a novel two-stage scheduling method is proposed. In the stage of static optimization, a knowledge-guided interval multi-objective shuffled frog leaping algorithm is designed to obtain the initial collecting routes. The possibility degree of interval number is introduced to perform individual encoding and decoding for speed intervals, and also implement the interval non-dominated sorting. In the stage of dynamic optimization, a problem-specific neighborhood search method is adopted to provide a quick response to the dynamic collecting requirements. Systematic experimental studies are implemented on a real-world medical waste collection scenario and eight synthetic instances. Comparison results with state-of-the-art algorithms suggest that the proposed algorithm generates a set of interval non-dominated schedules with lower cost and infection risk. • Constructing a dynamic and uncertain multi-trip model for medical waste collection. • Proposing a two-stage scheduling algorithm to solve the formulated model. • Designing a knowledge-guided interval optimization method to handle uncertainty. • Developing neighborhood search-based dynamic scheduling to react to changes. • Presenting a convertible encoding for individuals to realize the diversified search.