Bi-Objective Vehicle Routing for Muck Transportation in Urban Road Networks

Abstract

As a consequence of expedited urban construction, large quantities of wastes are shipped every day. Because of the excessive pursuit of economic benefits by muck truck drivers and unreasonable transportation route choices, the accident rates of these drivers continue to increase. It is very important to optimize the safe transportation routing of muck trucks. In this paper, a safe transportation routing model was established to minimizes path safety risks and single driving time as the bi-objective, and two different situations for the optimal path of the model were analyzed. For the situation in which there are several short paths in the network, one of which is the path with the least safety risks, an exact algorithm, A*, was designed, and time complexity was analyzed. For the situation in which there is a single path or several shortest paths in the network but the path with the minimal path safety risks is not included in the set of shortest paths, an approximation algorithm, GA*, was designed, and time complexity and the approximation ratio were analyzed. Our experimental results demonstrated the validity of our developed model and approaches. Moreover, a case study is carried out on a real-case application related to the network in the Xi'an International Port District.

Keywords

• Muck trucks
• safety transportation
• vehicle routing
• bi-objective programming
• approximation algorithm