基于Voronoi划分的同城即时配送优化策略研究

Research on Optimization Strategy of Same City Instant Delivery Based on Voronoi Division

近年来经济社会发展及新零售业强势崛起使得平台或商家对大规模即时配送需求日益增加,在求解大规模车辆路径问题时仅使用启发式算法或其融合算法已无法满足实际需求。本文针对基于分众级的同城即时配送模式及现阶段存在的问题,确定了基于Voronoi划分算法的即时配送分区方法和对基础蚁群算法的三个改进策略;并以全程配送产生的总成本最少为目标函数,构建了带用户需求软时间窗的车辆路径问题数学模型;最后选取客户、车辆以及门店共计一百二十个真实地理位置数据,验证了本文提出的求解策略的有效性,并分析最终结果。结果显示,(1)使用Voronoi分区-改进蚁群算法的两阶段方法求解大规模车辆路径问题能显著减少配送总成本,同时提升客户满意度;(2)在多门店的条件假设下,采用改进蚁群算法求解得到的超时时间比基础蚁群算法少36%,配送总成本低17%。

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(1)the two-stage method of Voronoi partition improved ant colony algorithm can significantly reduce the total cost of distribution and improve customer satisfaction;(2)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%.