A multi-objective optimization approach to package delivery by the crowd of occupied taxis

摘要

Taxi crowdsourcing has gained great interest from the logistics industry and academe due to its significant economic and environmental impact. However, existing approaches have several limitations and focus solely on single objective optimization problem. In this paper, we propose a three-stage framework, namely MOOP4PD to improve the existing approaches. Firstly, we propose a DesCloser* pruning algorithm with no limitation on taxi capacity and use A* algorithm to further optimize the delivery routes. Then, a novel multi-objective pruning algorithm, named MDesCloser*, is presented to find the non-dominated set, which contains waiting time window MaxWT and taxi capacity MaxC constraints. Finally, we develop a constraint solving approach to obtain the ideal solution (i.e., MaxWT equals 11 and MaxC equals 6). We evaluate the performance using the data set generated by Brinkhoff road network generator in the city of Luoyang, China. Results show that our approach improve the objectives of success rate, average number of participating taxis, average delivery distance and average delivery time. Especially, MDesCloser* have best performance on the success rate with more than 0.88 and minimize the total waiting time of all packages to 14916.6 time slices if failure in delivering and maximize the average transshipping rate of interchange stations.