Modeling and Optimization of Multi-Model Waste Vehicle Routing Problem Based on the Time Window

Introduction

With the continuous development of China’s economy and the explosive increase in the population, the production of municipal waste has also entered an exponential growth stage. Lie (Yang and Chen et al., 2013) found that in the past fifteen years, the production of municipal waste in China has increased significantly compared with that in the United States. In the face of massive urban waste production, how to recycle and dispose of waste has become the most concerning issue of municipal and other related departments. This paper converts the waste collection problem into a classic Vehicle Routing Problem (VRP) and further expands it to the Municipal Waste Collection Vehicle Routing Problem (Han and Ponce Cueto, 2015) (MWCVRP), which aims to study how to minimize the total cost of transporting waste.

This problem has been identified as an NP-hard problem since it was proposed (Kim and Ong et al., 2015) (Yousefikhoshbakht and Didehvar et al., 2014); that is, it is difficult to solve with an exact algorithm, so people have proposed two less accurate but very effective solutions to this problem (Beliën and De Boeck et al., 2014), namely, the classical heuristics algorithm and the meta-heuristics algorithm. Gevorg (Guloyan and Aydin, 2020) used the genetic greedy hybrid algorithm to find a route with the lowest total transportation cost in the case of municipal solid waste recycling in Yerevan. Sobhan (Darmian and Moazzeni, et al., 2020) used a heuristic-based multi-objective local search algorithm to determine the collection center and the route with the lowest total cost as the recycling route. Emre (Eren and Tuzkaya, 2021) converted the vehicle routing problem into the traveling salesman problem (TSP) and solved a safe recycling route when recycling COVID-19 medical waste. Meiling (He and Wei et al., 2021) adopted an adaptive variable neighborhood. The search ant colony algorithm solves the vehicle routing problem with time windows. Luis (Flores-Luyo and Agra et al., 2020) brought the traditional vehicle routing problem into the wireless network environment and used greedy combined with a heuristic algorithm to improve the loading rate of vehicles. They (Zhang and Yang et al., 2020) used a multi-objective evolutionary algorithm to reduce the vehicle waiting time in the path planning problem with time windows. Combining (Dong and Zhou et al., 2018) the discrete firefly evolution mechanism with the variable neighborhood evolution mechanism, and its design scheme was efficient in dealing with multi-objective path planning problems. Based on the Solomon dataset, they (Nasri and Hafidi et al., 2020) adopted a parallel adaptive large neighborhood search metaheuristic algorithm to obtain the best robust solution under different scenarios in the dataset.

The above studies have good results in their respective application scenarios, but there are few studies on multi-model routing problems with time windows and capacity constraints (Mojtahedi and Fathollahi-Fard et al., 2021). For this reason, this paper is closer to reality (Ticha and Absi et al., 2017)(Fallah and Tavakkoli-Moghaddam et al., 2019), studies the routing problem based on multi-model waste transport vehicles, considers the difference in the mileage fee and station service fee of different types of transport vehicles, introduces a cost calculation criterion that combines the total mileage and the number of service stations, establishes a multi-model waste transport vehicle path optimization model, and then like Chenxin (Sun and Huang et al., 2022) designs a simple and effective heuristic-based task dynamic assignment algorithm to solve the problem. Different from the genetic algorithm (Ombuki and Ross et al., 2006) (Yusuf and Baba et al.,2014) that requires multiple iterations, the algorithm used in this paper focuses more on a timely assignment strategy, and we believe that this can better combine the real-life urban waste transportation problem with the theoretical multi-model routing problem with time windows. At the same time, the Solomon dataset (Solomon, 1987) is used to verify the feasibility and effectiveness of the proposed model and algorithm through experiments, which provides methodological guidance for decision support for urban waste transportation.