下载掌阅APP，畅读海量书库
立即打开
（1）问题描述及假设
CVRP是指：配送网络中有一系列客户点 j ∈{1，2，…， n }及相应需求量（ d j ），如何安排一个车队的运输路径访问这些客户点，在满足车辆最大装载量等约束条件下，使得总运输成本最小。CVRP示意图如图2.1所示。
图2.1 CVRP示意图
该问题研究一般考虑的假设如下：
①所有车辆同质，即具有相同的最大装载量、最大工作时间和车速。
②车辆从配送中心出发，完成任务后返回配送中心。
③每个客户有且仅被访问一次。
④在每个客户点的投货时间忽略不计。
（2）数学模型
模型中的变量及其含义如表2.1所示。
表2.1 模型中的变量及其含义
续表
式（2.1）表示目标函数，最小化运输成本。式（2.2）和式（2.3）表示派出车辆从配送中心出发，完成任务后返回配送中心。式（2.4）表示每个客户点有且仅被访问一次。式（2.5）表示车辆流平衡约束。式（2.6）表示车辆访问所有客户的装载量不能超过其最大允许装载量。式（2.7）表示子回路消除约束。式（2.8）表示0-1路径决策变量。式（2.9）表示客户访问次数决策变量。
（3）求解算法
饶卫振等（2014）提出了一种快速改进贪婪算法，基于贪婪算法思想设计了求解CVRP的贪婪算法，在此基础上进一步采用K-d Tree法和Held Karp模型改进算法的求解效率和求解质量。Bouzid等（2017）针对CVRP，以最小化路径成本为优化目标建立整数规划模型，并提出一种拉格朗日分解（Lagrangian Split，LS）与变邻域搜索（Variable Neighbourhood Search，VNS）相结合的混合算法进行求解。Altabeeb等（2019）提出了一种改进萤火虫算法，加入了两种改进局部搜索策略，加快了解的收敛与搜索到的解的质量。Yuliza等（2019）对石油气分销路线进行研究，建立CVRP模型并采用分支—定界算法进行求解。张景玲等（2020）提出一种基于强化学习的超启发算法，使用强化学习策略中的深度Q神经网络（Deep Q Network）算法提升初始解的质量，使用模拟退火的接受准则以获得高质量解。Altabeeb等（2019）提出了改进的混合萤火虫算法。Lin等（2019）提出了混合遗传算法。Kun等（2021）提出了一种自适应大邻域搜索（ALNS）算法用于求解装箱问题。夏小云等（2021）提出一种基于大邻域搜索的人工蜂群优化算法，采用算子区别应用机制、仔细侦察蜂机制、更新策略宽松机制优化算法，充分发挥了自适应大邻域搜索的局部搜索能力和人工蜂群算法的探索能力。马艳芳等（2021）提出两阶段启发式算法求解两级容量有限车辆路径优化模型：第一阶段设计改进的遗传—模拟退火算法增强全局搜索能力，采用轮盘赌选择机制结合精英保留策略保留优秀个体，部分匹配交叉算子结合自适应交叉率维持种群多样性，Metropolis准则以一定概率接受较差解。第二阶段是使用精确方法求解配送路径。Hao等（2022）提出了一种基于相关性矩阵的进化算法，利用相关性矩阵设计了一种基于关联矩阵的多样性保持策略，以提高算法效率和获得解的质量。季彬等（2022）研究带二维装箱约束的车辆路径问题，构建了混合整数线性规划模型，提出基于分支定价的方法，针对分支节点的松弛模型，基于列生成策略进行问题划分，并提出基于ng-route松弛策略的标签算法和基于禁忌搜索的装箱算法有效求解复杂子问题。在精确求解算法方面，Lysgaard等（2004）提出了分支—切割算法，Fukasawa等（2006）提出了分支定价切割算法，Ibrahim等（2020）提出了分支—切割和列生成算法。