| 基于Voronoi划分的同城即时配送优化策略研究 |
| |
| 引用本文： | 徐贤浩,沈夏婵,任欣欣. 基于Voronoi划分的同城即时配送优化策略研究[J]. 运筹与管理, 2022, 31(10): 6-11. DOI: 10.12005/orms.2022.0312 |
| |
| 作者姓名： | 徐贤浩 沈夏婵 任欣欣 |
| |
| 作者单位： | 华中科技大学 管理学院,湖北 武汉 430074 |
| |
| 基金项目： | 国家自然科学基金资助项目(71971095,71821001,71620107002) |
| |
| 摘 要： | 近年来经济社会发展及新零售业强势崛起使得平台或商家对大规模即时配送需求日益增加,在求解大规模车辆路径问题时仅使用启发式算法或其融合算法已无法满足实际需求。本文针对基于分众级的同城即时配送模式及现阶段存在的问题,确定了基于Voronoi划分算法的即时配送分区方法和对基础蚁群算法的三个改进策略;并以全程配送产生的总成本最少为目标函数,构建了带用户需求软时间窗的车辆路径问题数学模型;最后选取客户、车辆以及门店共计一百二十个真实地理位置数据,验证了本文提出的求解策略的有效性,并分析最终结果。结果显示,①使用Voronoi分区-改进蚁群算法的两阶段方法求解大规模车辆路径问题能显著减少配送总成本,同时提升客户满意度;②在多门店的条件假设下,采用改进蚁群算法求解得到的超时时间比基础蚁群算法少36%,配送总成本低17%。
|
| 关 键 词： | 路径规划 即时配送 蚁群算法 Voronoi划分 |
| 收稿时间： | 2020-06-29 |
Research on Optimization Strategy of Same City Instant Delivery Based on Voronoi Division |
| |
| XU Xian-hao,SHEN Xia-chan,REN Xin-xin. Research on Optimization Strategy of Same City Instant Delivery Based on Voronoi Division[J]. Operations Research and Management Science, 2022, 31(10): 6-11. DOI: 10.12005/orms.2022.0312 |
| |
| Authors: | XU Xian-hao SHEN Xia-chan REN Xin-xin |
| |
| Affiliation: | School of Management, Huazhong University of Science and Technology, Wuhan 430074, China |
| |
| 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%. |
| |
| Keywords: | path planning instant delivery ant colony algorithm voronoi partition |
|
| 点击此处可从《运筹与管理》浏览原始摘要信息 |
|
点击此处可从《运筹与管理》下载免费的PDF全文 |
|
