基于遗传算法的应急物资复杂配送问题的优化研究.pdf

硕士研究生学位论文摘要

摘要

累积容量受限的车辆路径问题（CumulativeCapacitatedVehicleRoutingProblem,

CCVRP）是一种广泛应用于物流运输、调度优化等领域的组合优化问题，其目标是最

小化到达服务点的总时间，而不是最小化路径总成本。该问题在突发性自然灾害降临

时的救灾抢险、应急物资配送过程中具有重要作用。本文围绕CCVRP在灾后应急物资

配送问题中的应用展开两方面研究：

首先，在灾后应急物资配送问题的背景下，考虑到因突发性自然灾害后受灾区域

路况存在不确定性，导致车辆行驶在受损路径上的行驶速度与理想状况存在偏差，产

生延误时间。因此建立一种以最小化到达客户时间为目标的应急物资配送模型解决该

问题，其中通过使用二项分布与正态分布建立一种考虑路径破坏情况的预测模型。依

Predicted

据问题特点，设计了一种考虑预测路径受损情况的带预测的增强遗传算法（

EnhancedGeneticAlgorithm,PEGA）求解该问题模型。在上述模型下，PEGA与蚁群算

AntColonyOptimization,ACO30

法（）和其他经典算法对比，通过在标准算例上独立

次的独立运行，实验结果表明PEGA更优。

其次，对多中心累积容量受限的车辆路径问题（MultiDepotCumulative

CapacitatedVehicleRoutingProblem,MDCCVRP）进行了探索，该部分实验同样考虑灾

害对配送路径造成的影响，使用第一部分实验中的路径预测模型预测灾后路径的受损

情况。在多中心车辆路径问题中，考虑路径受损导致配送时间大于理想情况的同时，

还需考虑每个配送中心的车辆调度以及最大车辆使用数的约束条件。因此，本文使用

K-means聚类算法根据预测结果选择合适的配送中心，并设计带预测步骤的变邻域算

法（PredictiveVariableNeighborhoodSearch,PVNS）求解该问题模型。在标准测试集p

与pr上进行了性能验证，对比经典遗传算法（GeneticAlgorithm，GA），自适应大邻

域算法（AdaptiveLargeNeighborhoodSearch，ALNS）以及不带预测步骤的变邻域搜

索算法（VariableNeighborhoodSearch,VNS），实验结果表明PVNS对应实验结果均优

于其他算法，且有着更快的收敛速度。

关键词：车辆路径规划；CCVRP；路径预测模型；邻域有哪些信誉好的足球投注网站算法；多中心

I

硕士研究生学位论文Abstract

Abstract

TheCumulativeCapacitatedVehicleRoutingProblem（CCVRP）isacombinatorial

optimizationproblemwidelyusedinlogisticsandtransportation,schedulingoptimizationand

otherfields,anditsgoalistominimizethetotaltimetoreachtheservicepoint,ratherthan

minimizethetotalcostoftheroute.Inparticular,