TS算法视域下物流配送车辆优化调度问题研究，本文主要内容关键词为：视域论文,算法论文,物流配送论文,车辆论文,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)。
3.2 邻域构造
3.3 禁忌表和禁忌长度
禁忌表采用数组Tb来记录在迭代过程中已经计算出来的局部最优解，如最优解0－3－5－2－4－1－0，则Tb[i＋1]＝“0－3－5－2－4－1－0”，i表示当前数组中最后一个元素，每增加一个新的禁忌解都作为最后一个元素置入数组。
禁忌长度的取值，可以设置为迭代次数的线性函数，在寻优初期，为了使得算法尽快收敛寻求最优解，则设置为较小的值；在寻优后期，为了使得算法免于陷入局部最优解而导致“早熟”，设置较大的禁忌长度。
3.4 时间窗和候选解
采用数组Path来表示所有候选解，如Path[i]＝“0－3－5－2－4－1－0”，表示候选集中的第i个候选解。
3.5 终止规则和结果输出
当迭代次数达到最大值，或连续寻优得到不变解的次数超过某个最大值时候，禁忌算法停止寻优，并将当前解作为最优解进行输出。
4 仿真实验
为了验证算法的性能，设有10个客户点分布在边长为100km的正方形区域内，配送中心位于正方形中心，坐标点为(0，0)，车辆的载重量为10t，客户点的详细信息见表1。
采用C－W首先求的初始解，再采用文中改进的禁忌算法进行寻优，经过300次迭代后，可以得到所需要的车辆为3，配送路径总距离为502.4，对应的3条优化路径为：
路径1：0－8－4－2－0；
路径2：0－7－10－0；
路径3：0－3－9－5－6－1－0；
实验结果如图1所示。
图1 优化路径图
采用经典TS算法和与文中的方法分别对实例进行仿真，得到的对比结果图如图2所示。
图2 文中算法和经典TS算法比较
从图2可以看出，经典的TS算法和文中改进的TS算法在迭代300次时都收敛并得到最优解，但文中所得的路径总长度为502.4，而经典TS算法为710.5，显然文中方法由于经过了C－W方法求解初始值，所以使得全局寻优能力更强，所得结果更符合真实值。
5 结语
带时间窗的车辆调度问题是一个经典的NP难题，通常采用启发式搜索的方法对其进行解决，本文在对带时间窗的车辆调度问题进行深入分析的基础上，提出了一种改进的禁忌算法，实现了对带时间窗的车辆调度问题的求解。通过实例仿真证明该算法能改善经典TS的缺陷，能够更精确地寻求最优解。