在线动态订单需求车辆路径规划

摘要

针对客户满意度和时间窗时域单一的问题，提出一种多时域分级方式衡量车辆配送进度，该设计细化普通时间窗时域，分成多个时域衡量车辆行进位置，算法方面，遗传算法(genetic algorithm, GA)与变邻域下降搜索算法(variable neighborhood descent, VND)的组合优化形式得到静态预优化路径最优车辆行进线路。动态调度周期中，现有贪婪订单插入算法(greedy order insertion algorithm, GOIA)搜索效率不高，提出一种改进后的贪婪订单插入算法(improved new greedy insertion algorithm, IGOIA),摒弃了GOIA随机插入路径的方式，最有原则的将订单插入到配送路径中去，将其与变邻域下降搜索算法组合优化(Genetic algorithm-Variable Neighborhood Descent, GAVND),对未服务的客户点进行局部优化。通过数学模型优化和求解算法改进，在统一平台上与IGOIA-GAVND、GOIA-GAVND与GOIA-GA2-opt的遗传算法改进形式进行对比试验，改进后的动态订单插入算法在不同规模的Solomon算例下，平均目标值降低了11%,算法平均计算时间降低了2.74 s,实例分析中，成本解分别节约了23%、31%、21%,研究结果证明了原则订单插入算法在滚动周期策略作用下可以获得较高质量的解。

关键词

多域分级时间窗 / 遗传算法 / 变邻域下降搜索算法 / 原则订单插入算法 / 滚动周期