带软时间窗约束的多车场车辆路径问题及其禁忌搜索算法研究

何小年

（湖南涉外经济学院信息与机电工程学院 湖南 长沙 410205）

0 引言

车辆路径优化是物流配送中的核心问题，对提高配送活动的效率和效益至关重要。自DANTAIG等[1]于1959年首次提出车辆路径问题（vehicle routing problem，VRP）以来，对该问题的研究不仅成果丰硕，而且热度一直不减，究其原因，一是该问题的NP-难性质足以吸引科研人员，二是该问题及其更复杂的各类延伸问题的广泛应用性。多车场问题即属于这一类极为复杂的延伸问题。本文研究一种VRP的复杂的延伸问题——带软时间窗约束的多车场车辆路径问题（multi-depot VRP with soft time windows, MDVRPSTW）。MDVRPSTW研究的是有多个车场可以同时对若干个有一定货物需求量的客户进行服务，要求在满足各客户货物需求和时间约束的前提下，对各车场车辆和行驶路线进行适当安排，使总配送费用最低。我国城市规模人口和面积一般都较大，交通拥挤，单车场很难实现配送的及时性并且可能会导致配送成本增大，多车场能有效解决此问题，现实中也有许多物流企业采用多车场调度方案。

对于多车场车辆调度问题的求解，从现有研究文献来看，有的采用多车场整体优化法还有的采用通用启发式算法优化算法。整体优化法是设定一个虚拟车场，将所有车场假设成一个整体来求解路径问题，LI等[2]采用整体法法把各个车场都考虑进来进行整体优化，得到最小的费用。但这种方法把多个发车点统一到一个发车点，对于不同发车点的车辆数限制、发货量限制、时间限制都比较难处理。徐东洋等[3]、胡蓉等[4]、周鲜成等[5]、王新玉等[6]在其著作中采用通用启发式优化算法的研究重点集中在如何合理地缩小搜索空间和简化求解步骤上，本文采用现代启发式算法把多车场车辆路径问题看作一个复杂的组合优化问题进行研究。

1 MDVRPSTW问题描述与数学模型

MDVRPSTW可以描述为：有M个车场（编号分别为N+1,N+2,...,N+M），每个车场拥有容量为Q的车辆Km台（m∈﹛N+1，N+2，…，N+M﹜），负责对N（客户编号为1,2...,N）个客户配送货物，假设客户点i的货物需求量为di（i∈﹛1，2，…，N﹜）且di≤Q，每个客户由任意一个车场的车辆服务但只能由一辆车服务一次。车辆早于客户规定的时间窗到达则在此等待，需要支付一定的等待费用，车辆晚于客户规定的时间窗到达则需支付一定的惩罚费用。完成任务后，各车辆直接返回各自原属车场。为构造数学模型，定义变量如下：

根据各客户的需求量和车辆载重量可估计出所需车辆数的下限：

其中，[*]表示向下取整。

符号说明：K—需要的车辆数；L—车辆最大行驶距离；Q—车辆最大载重量；i,j—待服务的客户点和车场；dij—从客户点i到客户点j的直接的距离，距离矩阵视为对称，即dij=dji；di—客户点i的货物需求量；l—每辆车每公里的配送费用；c—车辆固定费用；ai—客户点i的最早服务时间；bi—客户点i的最晚服务时间；ti—车辆到达客户点i的时间；tij—从客户点i到客户点j所需要的时间；p1—早于ai到达客户点i等待时每分钟的损失费用；v—平均车速；p2—晚于bi到达客户点i并服务的延迟惩罚费用。客户点i和客户点j在同一路线且客户点j恰好在客户点i之后服务，则车辆到达客户点j的时间为：tj=ti+tij。

因此，MDVRPSTW数学模型可以描述为：

满足：

模型中，式（2）表示第一个优化目标，最小化所需车辆数；式（3）表示第二个优化目标，最小化总的配送费用（包括车辆行驶费用，车辆固定使用费用以及时间窗偏离惩罚费用；式（4）表示每条路线的行驶距离限制；式（5）表示车辆受到载重量的限制；式（6）表示每个客户点只能由一辆车服务且所有客户点都要得到服务；式（7）表示K条路线都从车场出发，最后又回到原车场；式（8）表示不能从车场到车场；式（9）表示车场m的车辆k是否从客户点i到客户点j；式（10）表示客户点i的货物运输任务是否由车场m的车辆k来完成的。

2 求解MDVRPSTW问题的禁忌搜索算法

禁忌搜索（tabu search，TS）算法是一种全局性邻域搜索算法，模拟人类具有记忆功能的逐步寻优特征。它通过局部邻域搜索机制和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效搜索，最终实现全局优化。

2.1 禁忌搜索算法初始解的产生

在算法中需要一个初始解开始搜索过程。本文采用自然数编码，以随机方式产生初始解序列。

2.2 邻域结构

禁忌搜索算法优化过程中一个很重要的组成部分就是邻域结构，其作用就是如何由一个解来产生一个新的解。本算法使用了四种邻域结构，即顶点重新指派、顶点交换“尾”交换和顶点2-Opt，以随机的方式选择其中一种领域结构应用于当前解。

2.3 算法的禁忌对象和禁忌长度

禁忌搜索算法的禁忌对象就是指禁忌表中被禁的那些局部最优解。本文将每次迭代得到的最好解，作为禁忌对象放人禁忌表中。算法的禁忌长度的长短决定解的选取，禁忌长度越短，获得优良解的可能性就相应增大，但是同时增加了迂回搜索，难以探索其他有效的搜索途径。本文的禁忌长度是在5到10之间随机选取。

2.4 特赦规则

本文采用基于适配值的藐视准则，即如果候选集中所有的解都为禁忌解，则解禁候选集中的最好解。

2.5 终止准则

本文采用事先限定算法的迭代次数为终止准则，该准则是指给定最大的迭代步数，使总的迭代步数不超过这个数，事先限定算法的迭代步数能有效控制算法的运行时间。

2.6 多车场的处理

本文将多配车场中心车辆调度问题看作一个复杂的组合优化问题来进行研究。假定每个车场可以派出车辆数所限制的前提下，本算法在带软时间窗约束的多车场车辆路径问题中多车场的处理方法是：从车场集合中随机地选取一个车场，配送车从被选中的车场出发，到各个客户点去完成配送任务，直到车辆足够满为止，在完成最后一个客户点的任务后，返回原车场的一条路线。如果所有的客户点还没有服务完，又从车场集合中随机选取一个车场，配送车从被选中车场出发，然后完成剩余的客户点的配送任务，直到车辆足够满为止，在完成最后一个客户点的任务后，返回原车场，一直循环，直到所有的客户点的配送任务都服务完毕。

3 MDVRPSTW案例测试

本算法已经在Pentium-Ⅳ2.67 GHZ微机上使用Delphi语言编程实现。为了测试算法的计算效果，本文使用两个案例进行计算，两个案例客户点坐标与载重量和时间窗数据见表1。两个案例数据都包含30个客户和4个车场，其中31、32、33、34为车场。假定车辆载重量为450，车速为1个单位，每一距离单位行驶费用为2.5，派车固定费用为100，车辆最大行驶距离为240，提前到达等待费用为0.2，延迟到达惩罚费用为2，忽略客户点的服务时间。本文按照两个案例数据分别进行计算，案例1的具体结果如表2所示、配送路径图如图1所示；案例2的具体结果如表3所示、配送路径图如图2所示。

表1 两个案例的客户点和各车场数据表

本文计算案例1的结果如表2所示，配送路径如图1所示：最优路径总长度551.1，行驶费用为1 377.78，程序运行时间0.05，时间窗内的客户点数29，等待与惩罚费用66.07，派车固定费用600，总费用为2 043.85。计算案例2的结果如表3所示，配送路径如图2所示：最优路径总长度628.34，行驶费用为1 570.85，程序运行时间0.05，时间窗内的客户点数28，等待与惩罚费用90.02，派车固定费用600，总费用为2 260.87。

表2 本文按照案例1的数据测试的结果

表3 本文按照案例2的数据测试的结果

图1 本文按案例1数据测试结果的车辆配送线路图

图2 本文按案例2数据测试结果的车辆配送线路图

4 结论

本文对带软时间窗约束的多车场车辆路径问题进行了研究，建立了相应的数学模型。通过随机选择车场，然后从被选中的车场里随机派车执行配送任务，车辆执行完配送任务后返回原车场，一直循环到所有的客户点都被服务完毕，将带软时间窗约束的多车场车辆路径问题的求解作为一个复杂的组合优化问题来研究，拓展了此类问题的求解算法。通过案例测试，得出了两个案例最少的车辆数和最优的路径优化解，能在较短的时间内得到满意的结果，等待与惩罚费用也在合理的范围内。这表明用本文设计的禁忌搜索算法能得到比较好的计算结果，计算效率也较高。