TS算法视域下物流配送车辆优化调度问题研究

       1 引言

       物流配送车辆优化调度问题(Vehicle scheduling problem)由Dantzing和Ramser于1959年首次提出，可以描述为对于一系列的客户配送需求，从配送中心派出若干车辆，通过组织合理的行车路线，使车辆能有序经过它们，满足客户的配送需要，并满足一定的约束条件，这些约束条件通常包括车辆容量限制、客户时间窗限制、路程最短和费用最少等[1]。

       带时间窗车辆调度问题(Vehicle scheduling problem with time window,VSPTW)是在VSP的基础上加入客户时间窗约束，更符合物流企业车辆调度的现实情况。目前已有的解决物流车辆调度问题的方法通常包含精确算法和启发式搜索算法，精确算法包含分支界定算法和拉格朗日分解法等[2]，启发式方法主要包含遗传算法[3]、禁忌算法[4]和模拟退火算法[5]等。

       对于解决高度优化问题，有许多求解方法。基于禁忌搜索的动态车辆路径问题，通过将动态规划转化为静态子问题从而使用禁忌算法进行求解[6]；将遗传算法和禁忌算法结合来解决一体化集货和配送车辆路径问题[7]；采用蚁群优化算法来解决带时间窗的车辆路径问题文献[8]；通过构造动态禁忌表来提高全局寻优能力[9]。

       上述求解方法，对高度优化具有一定意义，但也存在不足。由于没有对初始解进行优化，求解过程也是考虑局部优化条件，所以导致了全局解求取的精度不高和算法的收敛速度慢等问题。TS算法是一种新兴的现代启发式寻优技术，适合于求解组合优化问题，并能以很大的概率跳出局部最优解。

       为了解决带时间窗的车辆调度问题，本文在对车辆调度问题进行深入分析的基础上，根据TS算法理论，首先提出了车辆调度问题的数据模型，通过C－W算法来获得车辆调度的初始解，并通过禁忌算法来进行全局寻优，从而解决了带时间窗的车辆调度问题。

       2 带时间窗的车辆调度数学模型

      

       带时间窗的车辆调度问题的数学模型可以表示为公式(1)：

      

       其中式(1)表示配送路径的总代价，式(2)表示车所配送的所有货物总量不能超过其容量，式(3)表示任何客户点仅由一辆车来进行派送，式(4)和(5)表示到达某一个客户点的车辆有且仅有一辆，式(6)表示车辆到达客户点i的时间必须满足时间窗约束。

       3 改进的禁忌算法

       禁忌算法由Glover在1986年首次提出，是一种通过记忆功能，实现对局部领域的扩展，进而实现全部寻优的算法，但其全局寻优能力受限于初始解的好坏。

       3.1 C－W算法求初始解

       为了解决禁忌算法的最终解依赖于初始解的优劣，采用C－W算法进行初始路径求解，同样采用表示从客户点i到客户点j的运输费用。

       (1)首先计算任意两点的表示将客户点i和客户点j连接在一起时，比各自单独连接时费用的节约值，其值可以根据式(7)进行计算：

      

       (3)判断W是否为空，如为空，则算法终止；如不为空，抽取出W中第一个元素，即的最大值，开始对路径ij进行判断下面三个条件之一是否符合，如果符合则转步骤(4)：

       a.客户点i和点j不在已有路径上；

       b.客户点i和点j在已有路径上，但不和配送中心相连；

       c.客户点i和点j在已有的路径上，但一个是起点另一个是终点。

       (4)判断加入路径ij后的总货运量是否满足容量Q约束，如不满足进入步骤(7)，否则进入步骤(5)；

       (5)判断加入路径ij是否满足i和j的时间窗约束，如果不满足进入步骤(7)，否则进入步骤(6)；

       (6)连接客户点i和点j；

       (7)W＝W－并转步骤(3)。