论文部分内容阅读
容量受限车辆路径问题(Capacitated Vehicle Routing Problem,CVRP)模型在交通领域有着广泛应用,以应急救灾物资配送为例,在应急救灾场景下,对物资配送的及时性有着非常高的要求,既要顾全大局,保证灾区整体物资配送的快速及时,也不能牺牲少数受灾点和灾民的利益,以某一个安置点的严重延误换取其他安置点的及时配送。这就需要审慎地进行物资配送调度,尽最大可能减少任何延误的发生,且尽量减少物资总配送时间。为了更好地实现以上目标,引入安置点紧急度属性,建立考虑紧急程度的CVRP模型,分别对紧急度确定和紧急度不确定两种情况进行研究,并设计了结合问题特性的遗传算法进行求解。第一步研究了紧急度确定性的应急救灾CVRP问题,优化目标为降低救灾物资配送的延误时间和救灾车辆的总运输时间。建立了基于紧急度的救灾物资车辆路径问题模型,并设计了一种改进遗传算法对该模型进行求解。首先,提出了一种基于紧急度的任务再分配算法作为局部搜索算子,该算子依据紧急度,为延误安置点重新安排配送车辆或调整配送顺序,从而降低延误时间。对无延误的车辆优化其路线以降低总运输时间,以达到延误时间、总运输时间两个目标最优。其次,采用多种策略生成初始种群;在17个数据集上与先来先服务(First Come First Served,FCFS)算法、按紧急度排序(Sorted by Urgency,URGS)算法,遗传算法(Genetic Algorithm,GA)三种经典算法对比,结果表明,具有基于紧急度的任务再分配策略的遗传算法(Genetic Algorithm with Task Redistribution Strategy Based on Urgency Degree,TRUD-GA)相较于GA,平均延误时间减少25.0%,平均运输时间减少1.9%,与FCFS、URGS算法相比改进更加明显。第二步研究了紧急度不确定的应急救灾CVRP问题。以总延误时间和总运输时间为优化目标,建立紧急程度不确定的应急物流规划模型,以Beta分布模拟灾区紧急度变化情况,同时进行预测。在遗传算法的局部搜索阶段设计了一种紧急度依赖的路径调整算法,根据物资需求点的紧急度不同的特性,对存在延误的配送路径进行有针对性的优化。12组数据的测试结果表明,所提模型和求解算法(Genetic Algorithm with Urgency-Dependent Path Adjustment),简记为UDGA。有效降低了延误和运输时间,与一些经典算法相比改进明显,相较于URGS算法延误时间降低89.7%,运输时间降低38.0%。UDGA算法在实验的多组算例中效果稳定,表现出良好的鲁棒性。