• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学 ›› 2020, Vol. 42 ›› Issue (11): 2096-2102.

• • 上一篇    

基于改进遗传算法的连锁便利店配送路径优化

李丹莲,曹倩,徐菲   

  1. (北京工商大学电商与物流学院,北京 100048)
  • 收稿日期:2019-12-12 修回日期:2020-03-18 接受日期:2020-11-25 出版日期:2020-11-25 发布日期:2020-11-30
  • 基金资助:
    国家自然科学基金(61702018);北京市属高校高水平教师队伍建设支持计划青年拔尖人才培育计划项目(CIT&TCD201804029);北京工商大学教育教学改革研究项目(JG205224);北京工商大学研究生教育教学改革研究项目(2020YJG35)

Delivery route optimization of chain convenience  stores based on improved genetic algorithm

LI Danlian,CAO Qian,XU Fei   

  1. (School of Ebusiness and Logistics,Beijing Technology and Business University,Beijing 100048,China)
  • Received:2019-12-12 Revised:2020-03-18 Accepted:2020-11-25 Online:2020-11-25 Published:2020-11-30

摘要: 提出一种针对软时间窗下连锁便利店配送路径规划的带时间窗口的多染色体遗传算法。为解决单车场多车型带密集半软时间窗问题,讨论解决方案预防其陷入局部最优解。对于上述配送路径问题,提出多染色体改进遗传算法在减少车辆运输成本、惩罚成本的目标下进行最优路径求解,并为连锁便利店的路径规划案例提出车辆与路径选择的优化方案,最后将该算法与传统遗传算法进行实验对比分析。实验结果表明,本文算法在密集半软时间窗下,相比传统遗传算法明显减少了总配送成本,从而验证了本文算法的有效性。

关键词: 软时间窗, 车辆路径优化, 遗传算法, 多车型, 多染色体

Abstract: Based on the delivery route planning of chain convenience stores under soft time windows, a multichromosome genetic algorithm with time windows for such scenarios is proposed to solve the problem of single distribution center with multiple types of vehicles under dense semisoft time windows, and its feasible solution of preventing falling into local optimal solution is discussed. For the abovementioned delivery route planning problem, the proposed multichromosome genetic algorithm solves the optimal route under the goal of reducing vehicle transportation cost and penalty cost, and proposes an optimization plan for vehicle and route selection for the chain convenience store's route planning case. Finally, the algorithm is compared with the traditional genetic algorithm. The experimental results show that this algorithm significantly reduces the total delivery cost in comparison to the traditional genetic algorithm under the dense semisoft time window, thus verifying the effectiveness of the algorithm.


Key words: soft time window, vehicle routing optimization, genetic algorithm, heterogeneous fleet, multiple chromosomes