关键词: 路径规划, 即时配送, 蚁群算法, Voronoi划分

Abstract: In recent years, the economic and social development and the strong rise of the new retail industry have made the demand for large-scale real-time distribution of platforms or businesses increasing. When solving large-scale vehicle routing problems, only heuristic algorithms or their fusion algorithms can not meet the actual needs. Aiming at the real-time distribution mode in the same city based on crowd level and the existing problems at the present stage, this paper determines the real-time distribution partition method based on Voronoi partition algorithm and three improvement strategies for the basic ant colony algorithm. Taking the total cost of the whole process distribution as the objective function, the mathematical model of vehicle routing problem with soft time window of user demand is constructed. Finally, a total of 120 real geographical location data of customers, vehicles and stores are selected to verify the effectiveness of the solution strategy proposed in this paper, and the final results are analyzed. The results show that ①the two-stage method of Voronoi partition improved ant colony algorithm can significantly reduce the total cost of distribution and improve customer satisfaction; ②under the assumption of multiple stores, the timeout time obtained by the improved ant colony algorithm is 36% less than the basic ant colony algorithm, and the total cost of distribution is 17%.

Key words: path planning, instant delivery, ant colony algorithm, voronoi partition