实时城市配送具有点对点、小批量、多频次的特点，故对物流配送的及时响应和灵活性皆均有较高的技术要求. 实时城市配送决策高度依赖于动态环境，须及时处理配送系统中由各种动态事件带来的实时变化，因此出现了带时间窗的动态取送货问题（dynamic pick-up and delivery problem with time windows，DPDP-TW）. 近年来，对于DPDP-TW的研究备受关注，实时城市配送的发展也极为迅速. 针对该问题，在传统的DPDP-TW基础上，考虑4种实时信息，即新请求出现、旧请求的改变或取消、交通拥堵和车辆抛锚，称为考虑真实场景多项动态事件的动态取送货问题（dynamic pick-up and delivery problem considering multiple dynamic events in a real-world environment，DPDP-MDE），尝试揭示动态事件对真实场景取送货问题的影响规律，提高实时动态决策能力和快速响应能力.

针对DPDP-TW以及DPDP-MDE建模问题，大多数研究者为了简化问题，考虑单项动态事件的影响. 较少有文献如Francesco等^[1]同时响应和有效处理新请求到达、交通拥堵和车辆扰动3种动态事件，提出实时控制方法以实现制定路径规划与执行运输服务（需求）同步控制，并采用禁忌搜索算法进行规划调整. 针对新请求出现的单项动态事件，Fabri等^[2]采用新请求插入方法，在新请求出现后算法会更新目前路径计划，将新请求分配给每一辆车，转化为单车路径规划问题. Mitrovic´-Minic´等^[3]采用最小值插入算法等待策略插入新增请求，比较研究多种请求增加时的等待策略. Branke等^[4-7]采用缓冲策略，在请求出现后将该请求搁置一段时间或者令车辆移动到未来请求较容易到达的节点. Pureza等^[8]证明在无容量限制的动态取送货问题中采用等待策略和缓冲策略整合新请求的优势. 针对交通拥堵单项动态事件，Kok等^[9]采用选择替代路线、更改客户访问顺序和更改车辆分配等措施，提出反映交通拥堵高峰时段车辆速度模型，消除路径规划中87%的交通拥堵. Sun等^[10]从运输服务商通过选择运输请求来取得最大化利润和利用交通状况的周期性两方面优化DPDP-TW的运输服务，在交通流较少时段对车辆进行路径规划. 针对车辆抛锚单项动态事件，Mamasis等^[11]针对城市单一产品配送过程中车辆抛锚问题，在团队定向问题模型的基础上考虑最大时间约束、最大距离约束和车辆容量约束，重构路径规划模型，采用快速标记算法几乎可以实时得到有效解.

关于时变条件下的DPDP-TW问题，Bruce等^[12]围绕行驶时间建模、应用和求解，系统进行时变条件下路径规划问题文献解析. Sun等^[10]研究一系列时变条件下的DPDP-TW问题，采用分支定界的算法求解，通过数值算例对改进算法框架的有效性和加速技巧的影响进行评估. Kritzinger等^[13]评价时变条件下车辆路径规划问题的算法，采用可变邻域搜索算法显著改善解的质量. Gerardo等^[14]总结时变条件下DPDP-TW的2种优化方法，即时法和滚动时域法. Michel等^[15]在解决DPDP-TW时采用即时法，即每出现一个新信息（新的请求或请求取消），就进行全局重新优化，这样会造成计算时间过长不适合实时情景. 滚动时域法相继由Mitrovic´-Minic´等^{[3, 16]}提出，该方法将调度时域分解为更小的时间间隔，在调度时域开始时按照静态问题的算法求出初始解，之后当信息到来时采用插入法或删除法这类启发式算法更新初始解. Pisinger等^[17]采用滚动时域的框架和分割调度时域，解决动态车辆路径规化问题. 可见，滚动时域法与静态问题的算法深度结合在求解真实场景DPDP-MDE问题时具有独特优势，在其动态算法框架中，静态问题求解算法及其优化对于实时场景问题快速求解具有重要作用. 本研究在完善动态算法框架的同时，通过禁忌搜索算法（TS）和自适应大规模邻域搜索算法（ALNS）改善初始可行解质量，并运用动态插入法解决未固定请求和新请求同步处理问题.

本研究综合考虑新请求出现、旧请求改变或取消、交通堵塞和配送车辆抛锚4种真实场景动态事件的影响重构规划模型；将滚动时域法与禁忌搜索算法和自适应大规模邻域搜索算法相结合，完善动态算法框架.

本研究提出的DPDP-MDE数学规划模型如下：假定所有相应的服务请求由车场调度车辆去完成，每一辆车在调度期开始时从车场出发，在调度期结束之前必须返回车场. 每辆车必须先访问请求的取货点然后运送至相应的送货点完成一个完整的请求. 每一个请求对取货点和送货点都有时间窗要求，而且在整个模型中动态出现. 假定每个间隔为 $\tau $，调度时域T被分为p个间隔 $({t_1},{t_2},\cdots,{t_p})$， $p = T/\tau $.

在规划路径时，考虑传统模型以外的4种因素，即请求改变、新请求出现、交通拥堵和车辆抛锚. 在调度时域 $T$内不断更新路径规划方案与调度计划，以调度时域 $T$内的车辆配送总成本最小为目标函数，车辆配送总成本包括车辆总行驶费用、晚于时间窗的惩罚费用和使用的车辆的固定使用成本费用三部分，从而得到车辆路径规划的最优解.

DPDP-MDE数学规划模型中常量定义如下： $K$为车辆的数量； $C$为调度时域的最大长度； $V$为地理上分布的所有节点的集合， $V = \left\{ {{v_0},{v_1},\cdots,{v_n}} \right\}$， ${v_0}$为车场， $n$为偶数； $Q$为每辆车的最大容量； $D$为车辆的最大行驶距离； $t$为规划时域内任意一个间隔进行路径优化的时刻； $N(t)$为 $t$时刻尚未接受服务的客户请求、新增加的动态请求和修改请求的地点集合， $N(t) = V/{v_0}$，可以分成大小相同的2个子集. ${N^ + }$为取货点的集合； ${N^ - }$为送货点的集合； ${N^ + } \cup {N^ - } = N(t)$， ${N^ + } \cap {N^ - } = \varnothing $； $\left| {{N^ + }} \right|$、 $\left| {{N^{\rm{ - }}}} \right|$为请求的数量， $\left| {{N^ + }} \right|{\rm{ = }}\left| {{N^ - }} \right|$. $k$为第 $k$辆车， $k = 1,2,\cdots,K$； ${d_{ij}}$为每一对节点 $({v_i},{v_j})(0 \leqslant i \ne j \leqslant n)$都存在的非负距离； ${s_k}(t)$为 $t$时刻车辆 $k$在所处交通状况的速度； $t_{ij}^k(t)$为 $t$时刻车辆 $k$从节点 ${v_i}$到节点 ${v_j}$须运行的时间， $t_{ij}^k(t) = {d_{ij}}/{s_k}(t)$； ${D_k}(t)$为 $t$时刻车辆 $k$从车场出发后的累积行驶距离； ${Q_k}(t)$为 $t$时刻车辆 $k$的剩余容量；W_p(t)为t时刻网络中不同情形下所有车辆所在地、请求和车场的集合，p=1, 2, 3, 4； ${W_1}(t)$为 $t$时刻网络中所有车辆所在地的集合； ${W_2}(t)$为 $t$时刻网络中所有车辆所在地和车场的集合； ${W_3}(t)$为 $t$时刻车辆路径中尚未接受服务的客户请求、新增加的动态请求和修改请求以及车场的集合； ${W_4}(t)$为 $t$时刻所有车辆所在地、尚未接受服务的客户请求、新增加的动态请求和修改请求以及车场的集合.

${{\rm{ss}}_i}$为节点 ${v_i}$的作业时间， ${v_i} \in N$； ${q_i}$为节点 ${v_i}$的需求量， ${v_i} \in N$，对于所有的取货点 ${v_i} \in {N^ + }$，需求量 ${q_i} > 0$，对于所的送货点 ${v_i} \in {N^ - }$，需求量 ${q_i} < 0$； $[{e_i},{l_i}]$为节点 ${v_i}$的服务时间窗， ${e_i}$为在节点 ${v_i}$处开始服务的最早时间，l_i为在节点 ${v_i}$处开始服务的最晚时间，在车场 ${v_i}$处， ${q_0} = 0$， ${{\rm{ss}}_0} = 0$， ${e_0} = 0$， ${l_0} = C$； $\alpha $为晚于时间窗的惩罚费用； $\beta $为每台车辆的固定使用成本（包括车辆的折旧费、维修费等）； $c$为单位路径成本.

DPDP-MDE数学规划模型中变量定义如下： $y_i^k$为车辆 $k$服务完节点 ${v_i}$的负载； $a_i^k$为车辆 $k$到达节点 ${v_i}$的时间； $w_i^k$为车辆 $k$在节点 ${v_i}$的等待时间， $w_i^k{\rm{ = }}\max\; \left\{ {0,{e_i} - a_i^k} \right\}$，即如果车辆 $k$到达节点 ${v_i}$的时间早于 ${e_i}$，那么车辆须等待直到 ${e_i}$，服务才可以开始； $t_{1i}^k$为车辆 $k$ 离开节点 ${v_i}$的时间， $t_{1i}^k{\rm{ = }}a_i^k + w_i^k + {\rm{ss}}_i^{}$； ${t_2}_i^k$为车辆 $k$到达节点 ${v_i}$晚于时间窗的时间， $t_{2i}^k =\max \;\left\{ {0,{t_{1i}^k - {l_i}}} \right\}$； $d_i^k$为车辆 $k$服务完节点 ${v_i}$的已行驶距离， $d_0^k = 0$； ${u_k}$为车辆k是否被使用的选择变量，被使用为1，否则为0； ${n_t}$为 $t$时刻规划使用的车辆数， ${n_t} = \displaystyle\sum\nolimits_{k = 1}^K {{u_k}}$； ${z_{ij}}$为节点 ${v_i}$和 ${v_j}$是否对应同一个请求的判断变量，若是则为1，否则为0， $0 \leqslant i \ne j \leqslant n$.

DPDP-MDE数学规划模型中决策变量定义为

$ x_{ij}^k = \left\{ \begin{array}{l} 1,\quad{\text{车辆}}k{\text{访问节点}}{v_i}{\text{后达到节点}}{v_j};\\ 0,\quad{\text{其他}}. \end{array} \right. $

式中： $0 \leqslant i \ne j \leqslant n$， $k = 1, \cdots ,K$.

所提出的考虑4种实时信息的动态取送货问题单目标规划模型建立如下：

(1) $\begin{split} {\rm{min }}\;Z = & \mathop \sum \limits_{i \in {\rm{}}{W_4}(t)} \mathop \sum \limits_{j \in {W_3}(t)} \sum\limits_{k = 1}^K {c {d_{ij}} x_{ij}^k} +\\ & \mathop \sum \limits_{i \in {W_4}(t)} \sum\limits_{k = 1}^K {\alpha t_{2i}^k} {\rm{ + }} \beta {n_t}. \end{split}$

限制条件如下：

(2) $\sum\limits_{k = 1}^K {\sum\limits_{j \in N(t)} {x_{ij}^k} } = 1;\quad\forall i \in N(t),$

(3) $\sum\limits_{k = 1}^K {\sum\limits_{j \in N(t)} {x_{ij}^k} } = 1;\quad\forall i \in {W_2}(t),$

(4) $\sum\limits_{i \in N(t) \cup {W_1}(t)} {x_{i0}^k} = 1;\quad k = 1, \cdots ,K,$

(5) $\sum\limits_{i \in N(t)} {x_{ih}^k} - \sum\limits_{j \in N(t)} {x_{hj}^k} = 0;\;\;\forall h \in N(t),\;\; k = 1, \cdots ,K,$

(6) $\begin{split} &\displaystyle\sum\limits_{l \in N(t)} {x_{li}^k{z_{ij}}} - \displaystyle\sum\limits_{p \in N(t)} {x_{pj}^k{z_{ij}}} = 0;\quad\forall i,j \in N(t), \\ &\quad k = 1, \cdots ,K, \end{split} $

(7) $ y_j^k \leqslant Q;\;\forall j \in N(t),\;\; k = 1, \cdots ,K, $

(8) $ y_j^k = {Q_k}(t);\;\forall j \in {W_p}(t),\;\; k = 1, \cdots ,K, $

(9) $ x_{ij}^k(y_j^k - y_i^k - {q_j}) = 0;\;\;\forall i,j \in N(t),\;\; k = 1, \cdots ,K, $

(10) $ x_{ij}^k(t_{1i}^k + t_{ij}^k) \leqslant a_j^k;\;\;\forall i,j \in N(t),\;\; k = 1, \cdots ,K, $

(11) $t_{1i}^k = \max\; \{ a_j^k,{e_i}\} + {{\rm{ss}}_i};\;\;\forall i \in N(t),$

(12) ${z_{ij}}a_i^k \leqslant a_j^k;\;\;\forall i,j \in N(t),\;\;k = 1, \cdots ,K,$

(13) $x_{i0}^k(de_i^k + t_{i0}^k) \leqslant C;\;\;\forall i \in N(t),\;\; k = 1, \cdots ,K,$

(14) $d_j^k \leqslant D;\;\;\forall j \in N(t),\;\; k = 1, \cdots ,K,$

(15) $d_j^k = {D_k}(t);\;\;\forall j \in {W_p}(t),\;\; k = 1, \cdots ,K,$

(16) $x_{ij}^k(d_j^k - d_i^k - {d_{ij}}) = 0;\;\;\forall i,j \in N(t),\;\; k = 1, \cdots ,K,$

(17) $x_{i0}^k(d_i^k + d_{i0}^k) \leqslant D;\;\;\forall i \in N(t),\;\; k = 1, \cdots ,K.$

式（1）为目标函数，表示 $t$时刻动态调整后的车辆调度计划的总费用最少，总费用包括车辆总行驶费用、晚于时间窗的惩罚费用和使用的车辆的固定使用成本费用三部分.

式（2）~（17）为约束条件，详细说明如下：

1）车辆路径问题基本式. 式（2）确保每一个节点只被访问一次，动态问题中的节点是指在新增请求、修改请求和车辆抛锚这些动态事件发生后未固定请求的取送货节点；式（3）、（4）确保每一辆车从车场或时刻车辆位置出发，最后返回车场. 在动态问题建模中，车辆的位置除了车场位置和上一个间隔结束位置，还有无法进行生产活动的抛锚车辆在路径规划中被剔除的位置；式（5）为流平衡式，即确保一辆车访问了一个节点后就必须从这个节点离开.

2）取送货式. 式（6）为取送货问题特有的配对式，即确保一个请求的取货点和送货点只能由同一辆车访问；式（12）为取送货问题特有的优先式，即确保一个请求的取货点在送货点之前被访问.

3）时间窗式. 时间窗式由式（10）、（11）表示，式（10）表示车辆 $ k$离开节点 $ {v_i}$的时间与 $ t$时刻车辆从节点 $ {v_i}$到节点 $ {v_j}$需要运行的时间之和不大于车辆 $ k$到达节点 $ {v_j}$的时间；式（11）表示在时间的角度使车辆路径方案和调度保证服务质量，车辆执行路径计划的时间要满足顾客的时间窗要求；在动态问题中，实时变化车辆拥堵信息会改变车辆执行路径方案和调度. 在实时交通状况下车辆的速度定义为式（21）.

4）容量式. 式（7）~（9）共同为容量式，在考虑车辆的运载能力下满足顾客货运需求，从而设计路径方案；容量式表明在任何时刻车辆的负载不超过车辆的最大容量，须特别注意的是，在动态问题中，已经执行任务的车辆在重新规划时车辆是有负载的，这与静态问题不同.

5）调度时域式. 式（13）确保服务时间不超过动态问题的调度时域的最大长度.

6）距离式. 式（14）、（15）确保在任何时间车辆的总行驶距离不超过车辆的最大行驶距离；式（16）、（17）确保车辆在最大行驶距离内返回车场；须特别注意的是，在动态问题中，已经执行任务的车辆在重新规划时车辆已经行驶了一定距离，这与静态问题不同.

动态算法或在线算法本质上是动态环境中的算法框架. 本研究的动态算法的流程图如图1所示，即将问题分割成许多静态子问题，以方便利用构造型算法和改善型算法求得静态子问题的解.

在动态算法中，采用启发式算法求解调度时域子间隔. 其中求解分为2个阶段：第1阶段，采用构造型算法求出调度时域子间隔问题的初始解，详见2.1节；第2阶段，采用改善型算法，即禁忌搜索算法和自适应大规模邻域搜索算法这2种智能算法，改善第1阶段的初始解的质量，详见2.2节. 在构造和改善初始解之后，在2.3节中使用动态插入法重新规划路径.

作为经典车辆路径问题的衍变，基于实时信息的动态取送货问题要求：与1个请求相关的2个节点须满足同车服务，取货节点在送货节点前访问，这些复杂约束条件须采用构造型算法构造初始可行解.

从一条空路径开始，随机选择一个未安排的请求插入. 对于每一个请求而言，检查现存路径中所有可行的取货点和送货点插入位置. 这里的可行位置是指满足取货点在送货点之前的约束、取货点与相应送货点在同一条路径上的约束、容量约束和时间窗约束. 并且，初始化一条新的路径插入该请求. 比较所有可行位置，选择适应度函数（式（1））最小的插入位置，将所有未被安排的请求插入到路径中.

初始解通常具有较大的改善空间. 考虑到该问题是NP-hard问题，在第2阶段采用对求解效率和质量有着较好协调能力的智能算法改进初始解.

禁忌搜索算法是对人类思维过程的模拟，通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，以保证多样化的有效探索，从而实现全局搜索.

1）邻域移动. 采用邻域移动获得候选解. 如图2所示，从初始解的一条路径中随机移除一对取货点和送货点，再重新插入到初始解中的一条路径中，判断邻域解的可行性，并选择所有可插入位置中使得适应度函数最小的位置，得到的解就是候选解.

2）禁忌对象. 禁忌对象为边，如图2所示，转换后的红色虚线为禁忌对象. 边AB为间接取货边，边DE为间接送货边，边GH为直接取货边，边HE为直接送货边. 所有引起这些边发生变化的邻域移动都是禁忌的.

3）禁忌表长度和停止准则. 禁忌表长度和停止准则与静态子问题中须重新规划的请求数量成正比. 静态子问题中须规划的请求数量在求解过程中是动态的，须在每一次运行禁忌搜索算法前实时确定.

4）选择策略. 以候选解集为整个邻域，从中选择适应度函数为最小的解，作为下一次迭代的初始解.

5）渴望水平. 当邻域中存在一个解的适应度函数的值最小，且比此次迭代的初始解的适应度函数值小，则无论这个移动是否是禁忌的，都接受这个解.

自适应大规模邻域搜索算法的主要依据是根据破坏算子和修复算子扩大搜索范围. 通过给每个破坏算子和修复算子分配一个权重，再根据算子的表现调节权重，从而控制每个算子在搜索期间的使用频率，这样的自适应调节能够更快找到更优邻域.

1）动态选择算子. ALNS根据算子以前的表现选择破坏操作和修复操作的组合以产生邻域. 为了扩大邻域的搜索范围，表现较差的算子将以较低的概率继续生成邻域，本研究采用轮盘赌的方式生成选择各算子的概率. 假定有 $n$个算子，每个算子的权重为 ${\omega _i}$，该权重反映的是该算子之前的表现. 在当前解中每一个算子 $j$被选中的概率为 ${\omega _{{j}}}\Big/\displaystyle\sum\nolimits_{i = 1}^n {{\omega _{{i}}}}$.

在迭代开始时每一个算子 $i$的权重 ${\omega _i}$=1.0，在每次迭代时接受根据每个算子的分值更新每个算子的权重. 在每次迭代的开始，分值的权重都为0，在算子产生可行解后，更新算子的分值. 在实际中， ${Q_1}$为新解且改善了最优解， ${Q_2}$为新解且改善了初始解， ${Q_3}$为非新解但改善了初始解， ${Q_4}$为未改善初始解，但通过SA接受. 分值增量应设定为 ${Q_1} > {Q_2} > {Q_3} > {Q_4}$.

为了更新权重， ${\alpha _{{i}}}$为算子 $i$被引用的次数， ${\beta _{{i}}}$为算子 $i$的结果分值， $\eta \in [0,1.0]$表示权重 ${\omega _{{i}}}$对算子表现反应的快慢. 采用如下公式调节权重：

(18) ${\omega _{i,{\rm{seg + 1}}}} = \left\{ {\begin{array}{*{20}{l}} {{\omega _{i{\rm{,seg}}}},\quad{\beta _{i,{\rm{seg}}}} = 0;}\\ {(1 - \eta ){\omega _{i,{\rm{seg}}}} + \eta {\beta _{i,{\rm{seg}}}}/{\alpha _{i,{\rm{seg}}}},\quad{\text{其他}}.} \end{array}} \right.$

式中： ${\omega _{i,{\rm{seg + 1}}}} $为调节函数. $\eta $=1.0，表示在调节权重时完全忽略之前该算子的表现，只与上一次得到的分值有关. $\eta $=0表示在调节权重时完全忽略上一次得到的分值，只与之前算子的表现有关.

2）破坏算子.（a）最差请求去除（worst removal）. 先计算每一个请求去除后的成本减少量，再随机选择r%的请求去除. 这里被选择的概率随成本减少量的增加而增加.（b）随机去除（random removal）. 随机选择r%的请求从目前的解中去除.（c）相关节点去除（related removal）. 去除相关节点，2个请求的相关性与取货点和送货点的距离、服务时间的差和需求量的差有关. 为了适于本研究问题，设相关度为

(19) $\begin{split} R(i,j) =& \varphi ({d_{{{{P}}_i}{\rm{,}}{{{P}}_j}}} + {d_{{{{D}}_i},{{{D}}_j}}}) + \chi (\left| {{T_{{{{P}}_i}}} - {T_{{{{P}}_j}}}} \right| + \\& \left| {{T_{{{{D}}_i}}} - {T_{{{{D}}_i}}}} \right|){\rm{ + }} \psi (\left| {{q_i} - {q_j}} \right|). \end{split} $

式中： ${P_i}$、 ${D_i}$分别为请求 $i$的取货点和送货点， ${T_{{P_i}}}$为访问请求 $i$的取货点的时间， $\varphi $、 $\chi $、 $\psi $的取值范围为[0，1.0].

3）修复算子. 采用基于最佳插入和遗憾原则的2种插入法.（a）最佳插入法. 在每次迭代时，计算每一个移除请求的最佳插入成本，最低插入成本的请求放在最后的插入位置. 直到所有请求都被插入到路径中.（b）遗憾插入法. 基于后悔的算法， $\Delta f_i^j$为未规划的请求 $i$在第 $j$条最佳路径中的最佳位置时的插入成本. 在每一次迭代时，被选择插入到最佳位置的请求 ${i^ * } = {\arg\!\max\limits _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!i \in U}}\;\left(\displaystyle\sum\nolimits_{j = 2}^k {\Delta f_i^j} - \Delta f_i^1\right)$，直到所有的请求都已经插入.

4）接受和停止准则. 若新解的适应度函数值f(s′)小于当前解f(s)，则接受这个解；若新解的适应度函数值f(s′)大于当前解，根据模拟退火准则接受新解. 在每一次迭代时，模拟退火方法以 $\exp\;( - (f(s) - f(s'))/T)$的概率接受劣解，这个概率随着温度 $T$的降低而降低. 在每一次迭代后给温度 $T$乘以 $\theta $以降低温度，其中 $\theta \in [0,1.0]$. 借鉴模拟退火方法扩大邻域的搜索空间，避免陷入局部最优解.

5）自适应方面. 采用破坏和修复操作生成邻域，邻域 $i$与权重 ${\omega _i}$和分值 ${\phi _i}$相关. 采用轮盘赌的方法选择邻域. 第一次迭代，所有邻域的权重相同，邻域每引用一次，分值根据邻域的效果更新一次.

动态算法框架将整个调度时域分为多个间隔，在间隔之间，存在已经完成的路径、上一个间隔已经规划还未访问的请求和新请求. 须采用动态插入法重新规划路径，本研究采用未固定请求插入法. 如果在时间 $t$，一对取货点与送货点都未访问，那么这对取货点与送货点所对应的请求就是未固定的，否则这个请求就是固定请求.

未固定请求插入法是指，在间隔之间，先从原路径中移除所有未固定请求，再采用2.2节中的构造型算法将这些未固定请求和新请求重新插入到路径中. 如图3所示为未固定请求插入法重新插入动态新请求的例子. 图中，蓝色虚线为已经完成的路径，黑色实线为已规划但还未执行的路径，Depot代表车场，以p结尾的节点代表取货点，以d结尾的节点代表送货点，相同的数字代表同一个请求.

首先移除所有的未固定请求，即图3（a）中原路径中的请求3（请求1、2都是固定请求保持不变），移除后的路径如图3（b）所示. 然后将新请求4和原路径中的未固定请求3按照2.1节中构造型算法重新插入到路径中，结果如图3（c）所示.

以Li等^[7]在研究静态的PDPTW时所生成的数据为基础，数据来源为 https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/，增加请求出现时间、车辆速度矩阵和车辆抛锚事件，将静态数据改编为适合基于实时信息的动态取送货问题的动态数据.

本研究所有程序用MATLAB9.5编写，实验环境为Intel（R）Core（TM）i7-4790 CPU 3.60 GHz.

相比于普通的静态问题，动态问题中每一个请求都有一个出现时间. 本研究的请求出现时间表达式为

(20) $t_r^{{\rm{lat}}} = \min \left\{ {{l_i},{l_j} - {t_{ij}} - {s_i}} \right\} - {t_{{\rm{0}}i}} - \beta_{\rm r} .$

式中： $t_r^{{\rm{lat}}}$为请求 $r$最晚出现时间， ${v_i}$、 ${v_j}$分别为请求 $r$的取货点和送货点， ${s_i}$为每一个节点的服务时间， ${t_{ij}}$为取货点和送货点之间的运行时间， $\beta _{\rm r}$为收到请求的反应时间.

紧迫度 $\alpha $取值范围为[0.1，1.0]，步调为0.1. 每一个请求都有一个出现时刻：

(21) ${t_r} = \alpha t_r^{{\rm{lat}}}.$

本研究在解决动态问题时，将调度时域分割成许多间隔，进行多次路径与调度的规划. 在每次开始规划时，系统会根据此刻每一辆车所在的时段和位置，采用智能交通系统获取每一辆车的车速. 间隔时间越短车速越准确，规划方案越准确. 在本研究中，在时段T内，位于区域c的车速表达式为

(22) ${v_{{{c}}T}} = {a_{{{c}}T}} v.$

式中： $v$为车辆的正常速度，即Li等^[7]的静态数据中的车速； ${a_{{{c}}T}}$为车速调节因子，与车辆所在的位置和时段有关， ${a_{{{c}}T}} \in (0,2.0)$.

例如，当新请求出现时，通过式（21）中的参数 $\alpha $调节请求在时间维度上的分布，即当 $\alpha {\rm{ = }}1.0$时动态性最强， $\alpha {\rm{ = }}0.1$时动态性最弱，倾向于静态情况；当请求修改时，可以更改实时送货数量和时间；当交通拥堵时，通过调整式（22）中的车速调节因子 ${a_{cT}}$来更改车辆速度信息. 另外，鉴于一天内多辆车抛锚的事件发生概率较低，假定在调度时域内只有1辆车抛锚.

$f({s_{{\rm{old}}}})$为构造初始解的目标函数值， $f({s_{{\rm{new}}}})$为初始解改善解（即禁忌搜索算法和自适应大规模邻域搜索算法）的目标函数值，则解的改善程度表达式为

(23) $I = \frac{{f({s_{{\rm{old}}}}) - f({s_{{\rm{new}}}})}}{{f({s_{{\rm{old}}}})}} \times 100{\text%}. $

如图4所示为不同调度时域 $T$下的新请求总数 $N$. 可以看出，当 $T$∈（100，200）时，新请求出现的数量较多；当 $T$∈（300，400，500，600，700，800）时，新请求出现的数量适中；当 $T$∈（900，1 100）时，新请求出现的数量极少. 如图5所示为不同时域 $T$下禁忌搜索算法和大规模邻域搜索算法的改善初始解的程度.

对比图4、5，禁忌搜索算法和自适应大规模邻域搜索算法都使初始解得到改善，且自适应大规模搜索算法对解的改善程度优于禁忌搜索算法. 经过计算，禁忌搜索算法在不同间隔中平均改善3.11%，自适应大规模邻域算法改善9.98%.

在不同紧迫度 $\alpha (\alpha \in [0.1,1.0])$下，2种算法的解的改善程度对比如图6所示. 可以看出，在任何紧迫度下，自适应大规模邻域搜索算法对初始解的改善程度都优于禁忌搜索算法. 计算时间 ${{t}}$如图7所示. 可以看出，自适应大规模邻域搜索算法的计算时间长于禁忌搜索算法. 当紧迫度更高时，2种算法计算时间趋于接近. 紧迫度越高，请求越趋近于动态请求，2种算法的计算时间越接近. 当紧迫度较低时，没完成的请求占比较高，对自适应大规模邻域搜索算法的计算时间影响较大. 尤其当α<0.3时，自适应大规模邻域搜索算法的计算时间随着紧迫度的增加陡然降低.

相比自适应大规模邻域搜索算法，禁忌搜索算法的解的质量虽然不高，但计算时间较少且相对稳定；在紧迫度较高时，自适应大规模邻域搜索算法的计算时间与禁忌搜索算法相近，同时解的质量更高.

在不同请求规模下，2种改善算法的对比如表1所示. 采用第2节的算法求出请求规模分别为50、100、200、300（即节点数分别为100、200、400、600）的算例，其中自适应大规模邻域搜索算法的缺省处为计算时间过长（超过1 h），因此不再列出具体时间. 通过对比禁忌搜索算法和自适应大规模邻域搜索算法这2种智能算法对解的改善程度和计算时间，可以得出以下结论.

1）禁忌搜索算法在4种规模下都能够得到优化结果，其计算时间基本小于60 s；自适应大规模邻域搜索算法在请求规模达到300时，计算时间超过3600 s，对于求解动态问题无实际意义.

2）由表1可知，在改善程度中，自适应大规模邻域搜索算法一列的数据都大于禁忌搜索算法，即在自适应大规模邻域搜索算法可以应用的规模下（即请求规模小于200时），其对于初始解的改善程度比禁忌搜索算法要好.

3）当请求规模为50时，自适应大规模邻域搜索算法的计算时间小于100 s，当请求规模为100时，自适应大规模邻域搜索算法的计算时间为1026.40 s，当请求规模为200时，计算时间最多为12 203.84 s. 也就是说，自适应大规模邻域算法的计算时间随着请求规模的增加而骤然增加，验证了NP-hard问题的计算复杂度随着数据规模的增大而增大的既知事实.

本研究重新定义考虑真实场景多项动态事件的动态取送货问题，尝试揭示多项动态事件经典模型带时间窗取送货问题的不同影响，提高实时动态决策能力和快速响应能力. 构建考虑新请求出现、请求改变、交通拥堵和车辆抛锚4种动态事件的实时场景取送货动态车辆路径规划模型，即DPDP-MDE，该模型以调度时域 $T$内车辆调度计划的总费用最少为目标函数，围绕4种动态事件产生的影响，细化动态状态下车辆位置、时间窗、动态时域等约束条件，对于经典DPDP-TW问题进行有益的扩展性研究. 完善动态算法框架，运用动态插入法解决未固定请求和新请求同步处理问题，通过禁忌搜索算法和自适应大规模邻域搜索算法优化初始可行解质量. 数值实验表明，本研究提出的模型及设计的动态算法框架能有效解决DPDP-TW问题. 禁忌搜索算法和自适应大规模邻域搜索算法都能求解基于实时信息的动态取送货问题；相比于自适应大规模邻域搜索算法，禁忌搜索算法的求解效率高但求解质量差；自适应大规模邻域搜索算法在紧迫度较高、间隔数量更短时，其求解效率和求解质量更好.

本研究在考虑交通拥堵状况时，限于问题涵盖了真实场景的多项动态事件，较为复杂，因而未能细分车辆速度在不同的时段和区域有所不同的情景。在车辆规划路径时仅根据车辆所处的时段和区域类推车辆的速度，未来为了更符合实际情况，可以考虑车辆速度伴随线路拥堵情况呈某种递减规律的情况。同时，动态问题求解对算法的时效性要求较高，未来尝试采用并行思想设计新算法，以降低算法运行时间，提高决策快速响应能力。