下载掌阅APP，畅读海量书库
立即打开
（1）问题描述及假设
带时间窗限制的车辆路径问题（VRPTW）是指：配送网络中有一系列客户点 j ∈{1，2，…， n }、需求量（ d j ）及相应送货时间窗[ e j ， l j ]。如何安排一个车队的运输路径访问这些客户点，在满足车辆最大装载容量和访问时间窗等约束条件下，使得总运输成本最小。VRPTW示意图如图2.2所示。
图2.2 VRPTW示意图
该问题研究一般考虑的假设如下：
①所有车辆同质，即具有相同的最大装载量、最大工作时间和车速。
②车辆从配送中心出发，完成任务后返回配送中心。
③每个客户有且仅被访问一次。
④在每个客户点的投货时间忽略不计。
（2）数学模型
模型中的参数和变量如表2.2所示。
表2.2 模型中的符号及解释
式（2.10）表示目标函数，最小化运输成本。式（2.11）和式（2.12）表示派出车辆从配送中心出发，完成任务后返回配送中心。式（2.13）表示每个客户点有且仅被访问一次。式（2.14）表示车辆流平衡约束。式（2.15）表示车辆访问所有客户的装载量不能超过其最大允许装载量。式（2.16）表示每个客户必须在其规定的时间窗内得到服务。式（2.17）表示客户 i 和客户 j 之间的服务时间关系。式（2.18）表示0～1路径决策变量。式（2.19）表示客户访问时间决策变量。
（3）求解算法
Ursani等（2011）基于交互式局部优化框架，设计了一种局部遗传算法。王征等（2013）以顾客时间窗偏离程度最小化和配送成本最小化为目标建立了数学规划模型，借助于多目标遗传算法进行测算，并给出算法的实时化处理方法，提高了干扰事件发生后的问题处理效率。孟祥虎等（2014）提出混合种群增量学习求解算法。Luo等（2015）提出混合蛙跳求解算法，该算法的优势是提出了一种基于改进和扩展的具有可选择移动算子的EO算法的邻域搜索方法。柴获等（2016）提出混合单变量边缘分布求解算法，改进了基本概率模型，提高了全局搜索能力。戚远航等（2018）提出了离散蝙蝠算法，引入了随机插入策略、最少客户车辆插入搜索、普通插入搜索、交换搜索、带时间窗的2-Opt搜索等策略来扩大搜索空间以提升算法的收敛速度。Gocken和Yaktubay（2019）提出了遗传算法。Zhang等（2020）提出了混合多目标进化算法。Bogue等（2020）以车辆数和总行驶距离最小化为优化目标，提出了基于可变邻域搜索的列生成算法和后优化启发式算法。李楠等（2021）以最小化总成本为优化目标，构建基于模糊可信性理论的模糊机会约束规划模型，并提出一种两阶段混合优化算法。张晓楠等（2021）设计了一种混合Memetic算法，基于客户时间窗升序排列的混合插入法构造初始种群，在单点交叉和简化变邻域搜索基础上引入邻域半径减少策略，提高搜索效率。在精确求解算法方面，Ticha和Absi（2017）提出了分支—定价算法，Sun等（2018）提出了一种基于分支—定价的精确求解方法，引入列生成算法及路径枚举方法。高远等（2022）在VRPTW模型的基础上建立了带有非线性潮汐时间窗约束的支线船舶路径规划模型，在分析问题特性的基础上将问题分解为主问题和子问题，并设计了列生成求解算法。