论文资料-集装箱车辆调度问题的变邻域禁忌搜索算法研究修改稿.doc

螀膀蒆蒀袂莅莂葿羄膈芇蒈肇羁薆薇螆膇蒂薆衿罿莈薆羁膅芄薅螀羈芀薄袃芃蕿薃羅肆蒅薂肇芁莁薁螇肄芇蚀衿芀膃蚀羂肃蒁虿蚁芈莇蚈袄肁莃蚇羆莆艿蚆肈腿薈蚅螈羂蒄蚄袀膇莀螄羃羀芆螃蚂膆膂螂螅罿薀螁羇膄蒆螀聿肇莂蝿蝿节芈螈袁肅薇螈羃芁蒃袇肆肃荿袆螅艿芅蒂袈肂膁蒂肀芇薀蒁螀膀蒆蒀袂莅莂葿羄膈芇蒈肇羁薆薇螆膇蒂薆衿罿莈薆羁膅芄薅螀羈芀薄袃芃蕿薃羅肆蒅薂肇芁莁薁螇肄芇蚀衿芀膃蚀羂肃蒁虿蚁芈莇蚈袄肁莃蚇羆莆艿蚆肈腿薈蚅螈羂蒄蚄袀膇莀螄羃羀芆螃蚂膆膂螂螅罿薀螁羇膄蒆螀聿肇莂蝿蝿节芈螈袁肅薇螈羃芁蒃袇肆肃荿袆螅艿芅蒂袈肂膁蒂肀芇薀蒁螀膀蒆蒀袂莅莂葿羄膈芇蒈肇羁薆薇螆膇蒂薆衿罿莈薆羁膅芄薅螀羈芀薄袃芃蕿薃羅肆蒅薂肇芁莁薁螇肄芇蚀衿芀膃蚀羂肃蒁虿蚁芈莇蚈袄肁莃蚇羆莆艿蚆肈腿薈蚅螈羂蒄蚄袀膇莀螄羃羀芆螃蚂膆膂螂螅罿薀螁羇膄蒆螀聿肇莂蝿蝿节芈螈袁肅薇螈羃芁蒃袇肆肃荿袆螅艿芅蒂袈肂膁蒂肀芇薀蒁螀膀蒆蒀袂莅莂葿羄膈芇蒈肇羁薆薇螆膇蒂薆衿罿莈薆羁膅芄薅螀羈芀薄袃芃蕿薃羅肆蒅薂肇芁莁薁螇肄芇蚀衿芀膃蚀羂肃蒁虿蚁芈莇蚈袄肁莃蚇羆莆艿蚆肈腿薈蚅螈羂蒄蚄袀膇莀螄羃羀芆螃蚂膆膂螂螅罿薀螁羇膄蒆螀聿肇莂蝿蝿节芈螈袁肅薇螈羃芁蒃袇肆肃荿 集装箱车辆调度问题的变邻域禁忌搜索算法研究汪翼1，孙林岩12，李刚1(1.西安交通大学 管理学院 西安 710049；2.机械制造系统工程国家重点实验室 西安 710049)摘要：研究一类带工作时间约束的集装箱专用车辆调度问题的混合禁忌搜索算法。此问题可分解为车辆路线设定和车辆分配两个组合优化问题，但是两个问题的分开求解最优解的组合却并不一定是总问题的最优解。首先对问题给出数学描述，之后通过引入一个变邻域搜索策略，提出一个解决该问题的混合禁忌搜索算法。该算法使用两行向量进行编码，采用随机扩大禁忌步长，并设计三种邻域变换定义，采用变邻域策略来扩大搜索空间。最后通过对6个不同规模算例求解验证该算法在解决此类问题的有效性。关键词：禁忌搜索；变邻域策略；集装箱专用车辆调度问题；变禁忌步长中图分类号:U491 文献标识码: AAn Variable Neighborhood Tabu Search for Container Vehicle Routing ProblemWang Yi, Linyan Sun, Li Gang(School of Management, Xian Jiaotong University, Xian 710049,China)(State Key Laboratory for Mechanical Manufacturing Systems Engineering Xian ,710049)Abstract: A container vehicle routing problem with full container load is studied in this paper. This problem consists of two sub-problems: the classical assignment problem and the generalized assignment problem, but the composition of two optimal solutions of sub-problems may not be the optimal solution of primal problem. A mixed-integer nonlinear programming mode of this problem is firstly given and then a mixed tabu search algorithm based on variable neighborhood strategy is proposed. This tabu search employs a two-vector representation and variable expansible tabu length to detect and escape from a chaotic attractor basin. The heuristic procedure is compared to Lagrangian relaxation-based method and Lingo soft ware on six random created testing problems. The results demonstrate that the procedure developed here is efficiently in solving large scale problems.Key words: Tabu Search; Variable Neighborhood; Container Vehicle Routing Problem; Variable Tabu Length.1投稿日期：2007-12-10；修回日期：2008-04-09基金项目：国家自然科学基金重点资助项目（70433003）；国家自然科学基金项目（70701029）；作者简介：汪翼（1982），男，福建三明人，博士生。主要研究物流与供应链管理方向；0 引言货运车辆调度问题是一类在物流运输行业具有广泛应用背景的组合优化问题。选取适当的车辆运输路径，可以减少运输成本，缩短工作时间，提高服务质量，增强企业市场竞争力。因此研究货运车辆调度问题及相应算法具有重要的实际意义。实际经济生活中车辆调度问题有着不同调度形式或是不同约束条件，这使得实际问题难以用某一特定算法求解，或者是效率极低。本文针对一种特殊的带工作时间约束的集装箱专用车辆的调度问题提出一种有效的混合禁忌搜索算法。这种车辆调度问题经常出现在海港码头，某些公司使用集装箱专用车辆进行集装箱运输，需要将装满货物的集装箱从公司运输到某个卸货点，之后再前往某一装货点将另一集装箱运输回公司。同时，用于运输的车辆有自有车辆和租用车辆两种，两种车辆的费用不同，每日最大工作时间限制也不相同。此时存在一个车辆调度问题，即为不同的车辆（自有和租用车辆）确定各自的运输路线（装货卸货路线）。针对这一种特殊的车辆调度问题，本文提出一种变邻域禁忌搜索算法进行求解。1 问题描述和数学模型本文研究的带工作时间约束的集装箱专用车辆调度问题可以定义为：G = (V，A)。其中，V表示一些点的集合，这些点包括原点，卸货点，装货点。A表示的是一些有向的线路的集合。集装箱专用车辆的行驶路线包括两段不同的线路，一是装货的线路，另一段是卸货的线路。这两种类型的线路一般可以合并为一个线路：装卸线路（dp 集）。带工作时间约束的集装箱专用车辆调度问题有以下特点：（1）车辆分为自有车辆和租用车辆，自有车辆有工作时间的限制，而租用车辆没有工作时间限制，但是租用车辆的使用成本相对更高。出于成本的考虑，公司会尽可能使用自有车辆；当自有车辆不够时，才会使用租用的车辆。（2）所有装货卸货工作都必须完成，据此假设可租用的车辆数目是无限的。车辆每一天的工作不会仅限于完成一个装卸任务集，在工作时间可以接受的情况下，车辆可承担的装卸线路任务可以是多个。（3）自由车辆和租用车辆具有相同大小和载重，但是单位时间的运输成本及工作时间限制不同。本问题可以总结为：找到一个最优分配，把自由车辆和租用车辆分配到不同的装卸线路任务上，使得总物流成本最小。该问题又可以分解成为两个子问题：首先是要确定装卸线路任务（dp 集），其次要对每个装卸路线任务分配车辆。带工作时间约束的集装箱专用车辆调度问题是一个NP-hard问题1。图1表示一个典型的集装箱专用车辆调度问题的可行解，里面有10个装货点（点1-10），10个卸货点（点11-20）。首先，将装货点和卸货点分别组合成10个装卸线路任务（A、BJ），再将这些装卸线路任务分配到不同车辆上。图1 带工作时间约束的集装箱专用车辆调度问题的一个可行解求解该问题就是要找到令总成本最小的各个车辆的装卸线路任务。因此带工作时间约束集装箱专用车辆调度问题可表示为如下数学模型：其中，表示卡车k从仓库到卸货点i再到装货点j再返回仓库的总费用；表示卡车从仓库到卸货点i再到装货点j再返回仓库需要的时间；表示卡车的集合；表示装货点的集合；表示卸货点的集合；表示卡车k的最大工作时间；如果卡车k被分配到卸货点i再到装货点j的装卸集上，则=1，否则=0。其他约束条件表示的含义为：（2）表示每一装货点只能和一个卸货点组成装卸线路集，且只能被一个车辆服务；（3）表示每一卸货点只能和一个装货点组成装卸线路，且只能被一个车辆服务；（4）表示自有车辆工作时间要小于自身工作时间约束。2禁忌搜索算法及变邻域搜索算法描述禁忌搜索最早由Glover提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟2。TS一方面沿用局部邻域搜索的思想，用于实现邻域搜索；另一方面通过引入一个灵活的存储结构和相应的禁忌准则来设置禁忌表和禁忌对象，通过标记对应已搜索到的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而体现算法避免迂回搜索的特点，并保证对不同的有效搜索途径的探索；另外，通过设置藐视准则来奖励和赦免一些优良状态。禁忌搜索被大量的用于求解各种车辆调度问题中3，4，5。TS 的搜索速度快， 但对于初始解有较强的依赖性，且无法像GS那样进行对解集并行搜索。VNS（Variable Neighborhood Search）方法是Hansen7等提出的一种启发式算法，它是将局部搜索和变邻域结构策略相结合而产生的算法。区别于传统方法的单一邻域结构，VNS首先定义系列邻域结构，使用局部搜索办法，并在搜索过程中系统性地不断改变扩大邻域搜索范围，直到有新的更好的解产生。确定邻域结构及数量，及确定各邻域结构在搜索中的应用次序及改变策略，是VNS 要解决的基本问题。变邻域搜索运用变邻域策略，可以比较好的跳离局部最优。但是变邻域搜索算法在其爬山能力方面一向比较弱8。开发混合算法的目的是为了使原算法的优点被保持，弱点被克服或是削弱，提高算法的综合力度9。本文设计的混合算法将变邻域搜索的策略和禁忌搜索算法相结合，其主要思想是，当在某一邻域定义中的禁忌搜索在一定时间内无法搜索出更好的解时，则改变邻域结构，并以已经得到的最优解作为新搜索的初始解进行新的禁忌搜索，如此迭代，当最后满足终止条件时，输出最终解。3变邻域禁忌搜索算法 上文已经论证了带工作时间约束的集装箱专用车辆调度问题是两个组合优化问题的合成。第一个问题是装卸线路集的组合优化问题，此时的目标函数是总花费时间最少；第二个是针对得出最优的装卸路线集，求解车辆分配的组合优化问题，目标函数是总费用最少。但是两个问题的分开求解最优解的组合并不一定是总问题的最优解。本文采用的禁忌搜索求解这个问题的策略是在每一次求解第一个装卸集路线的优化问题的迭代中，进行若干次解决车辆分配问题的迭代。3.1 编码前面已经提到，带时间窗的集装箱专用车辆调度问题是两个组合问题的合成。一个可行解需要表示装卸集的组成，也要表示车辆的分配。本文将问题的解表达为一个序列（L1,L2）。其中，L1表示的是装货点和卸货点的配对集合，L2表示的是对每个装卸集的分配车辆的方案。本文采用Gen10等人的方法，使用两行向量来表示带时间窗的集装箱专用车辆调度问题的解。图2 一个可行解的序列表示图2中的解表示的正是图1中的装卸线路集和车辆分配结果。卸货点1和装货点15组成装卸线路集，这个线路集的任务由车辆1完成。依次的，卸货点2，装货点20组成装卸线路集，由车辆2完成。由于第一行装货点的顺序不变，取后面两行序列作为禁忌搜索中解的编码，图3表示的正是该解：图3 解的编码3.2 初始解由于禁忌搜索对于初始解的要求非常高，好的初始解将会使得搜索迅速而且高效，因此，我们采用贪心算法求解出一个比较好的解，在此基础上进行变邻域禁忌搜索。初始解生成算法具体步骤表述如下（k表示装货点数量）：（1）随机生成一个装卸线路集的排序；（2）for i=1: k-1:for j=i+1:k:（3）针对装卸路线集交换第i个和第j个装货点；（4）按照装卸路线集所需要的运输时间，从大到小分配分配给自有车辆，当达到最大自有车辆数后之分配给租用车辆；（5）输出此时的目标值和解，若小于目前最优解，则覆盖之；（6）回到（3）；（7）迭代次之后输出目前最优解。3.3 邻域变换定义与邻域变换策略为能够更好搜索到新的解空间，我们采用三个邻域变换定义：站点交换邻域变换（N1）、站点插入的邻域变换（N2）和车辆变换的邻域变换（N3）5。第一个邻域变换（N1）的定义为：新解的产生是通过选择两个站点并交换相互的位置产生的。第二个邻域变换（N2）的定义为：首先选择一个站点和一个位置，然后把这个站点插入到这个位置上，这样就产生一个新的解。第三个邻域变换（N3）的定义为：选定某个车辆，使其变化成为1到i+1中的任意一个车辆（该变换可能导致所需要的车辆数量增加），i表示当时的使用车辆总数。这三种邻域变换定义具体见图4：图4 三种邻域变换定义当在一定次数迭代过程后，最优解并没有产生变化的时候，变换邻域结构的定义进行进一步的搜索。这样交互变换邻域结构定义，直到满足最终迭代停止条件。每进行1次邻域变换（N1）或者是（N2）之后，我们都进行n/25次（N3）的邻域变换。3.4 禁忌步长随着禁忌搜索的进行，搜索到的解将逐渐的进入稳定状态，很大的可能是进入了某个局部搜索范围中，并无法逃离此局部范围，禁忌搜索晚期要使禁忌步长变长。此外，随机的禁忌步长可以避免死循环的出现。因此，为增加搜索的速度，减少不必要的迭代，采用基于迭代次数的随机的禁忌步长。第i次迭代中的禁忌步长表示为：其中，Tabulength (i)表示第i次迭代中的禁忌步长；intTL表示初始步长；rand表示一个随机生成的小于1的正数；k是一个根据具体问题的规模而设置的参数，用来保证禁忌步长的变化不能过大。3.5 终止策略在本算法中，使迭代终止的策略有两个：（1）当在若干次迭代后，最优解仍然没有变化；（2）在程序运行特定的足够长时间之后。满足以上任意一个条件，搜索过程就停止，并输出此时得到的最优解。3.5 算法步骤求解带工作时间约束的集装箱专用车辆调度问题的变邻域搜索算法，具体步骤为：（1）运用3.2章节所示算法生成初始解，并设为最优解，初始化参数，初始化两个邻域结构定义所对应的禁忌表；（2）for count=1:n:（3）采用（N1）或者（N2）邻域结构的定义，随机产生一些邻域集合T；（4）从T中选取可允许的最好变换或者是被特赦的sofarbest变换，做适当的交换，修改相应的禁忌表和其他变量，（5）采用（N3）邻域结构搜索，迭代n/30次；（6）如果选取解优于sofarbest，修改sofarbest信息；（7）如果在一定的迭代次数之内sofarbest依旧没有改变，则采用另一种邻域结构定义，并回到（3）；（8）如果某些信息达到停止准则，跳出循环，并输出最优解。4 测试实验和比较为检验算法的有效性，我们构造了6个不同规模的算例。用于实验的算例是按照不同规模随机生成的：我们在100100m2的面积内随机生成若干个装卸点，装卸点的坐标的生成函数为：。算例中假设发车点位于原点，装货点、卸货点和发车点之间的距离为直线距离。6个算例的集装箱车辆的详细信息见表1：表2 车辆信息表车辆类型自有车辆租用车辆每千米行驶费用30元60元每日工作时间约束8小时12小时时速50千米/时50千米/时为检验变邻域禁忌搜索在解决该问题上的有效性，我们分别使用变邻域禁忌搜索算法和Akio Imai文中所使用的拉格朗日算法1求解，两种算法所使用初始解相同（贪心算法求初始解）。在算例1中，经过3000次左右的迭代，拉格朗日算法收敛于目标值3528.8，而本算法在5000次左右迭代后收敛于目标值3285.0处。图5表示该算法和拉格朗日算法分别在求解算例1过程中的收敛过程：图5 两种算法的收敛速度比较图为了比较算法的有效性，本文还运用Lingo对各算例进行了求解。其他算例的基本信息及不同方法求解出的结果见表3：表3 6个算例的实验结果算例装卸点总数量自有车辆数量Lingo拉格朗日算法本算法目标值计算时间目标值计算时间目标值计算时间110010N/A-3528.8783 秒3285.04.9 小时210010N/A-3232.61059 秒3118.15.3小时3605N/A-2190.396 秒2017.5736 秒4605N/A-2206.6101 秒2096.0803 秒54031580.518.8 小时1580.511 秒1580.527 秒64031736.219.6 小时1736.212 秒1736.227 秒注：N/A 表示在可接受的时间内无法求出最优解。根据实验结果，可以看出在解决规模较大的问题时，变邻域禁忌搜索能取得比拉格朗日算法更优的解。在解决规模较小的问题时候，本算法和拉格朗日算法都求出了最优解。5 结束语本文研究一种特殊的带工作时间约束的集装箱专用车辆调度问题，给出该问题的数学描述，并提出一个求解该问题的包含变邻域策略的禁忌搜索算法。运用该算法针对随机生成的6个测试算例求解，并通过和现有文献所使用的拉格朗日算法的求解结果及Lingo软件求解结果进行比较，说明这种算法的有效性。参考文献：1A Imai, E Nishimura, J Current , A Lagrangian relaxation-based heuristic for the vehicle routing with full container loadJ，European Journal of Operational Research, 2007, 176(1):87105.2F Glover, M Laguna, Tabu searchM, Boston: Klower Academic Publishers,1997: 68-69.3符卓，带装载能力约束的开放式车辆路径问题及禁忌搜索算法研究J，系统工程理论与实践，2004, 24(3):124127.4钟石泉,，贺国光，有时间窗约束车辆调度优化的一种禁忌算法J，系统工程理论方法应用，2005, 14(6):5225265WP Nanry, J Wesley Barnes, Solving the pickup and delivery problem with time windows using reactive tabu search J, Transportation Research Part B, 2000, 107121.6 李大卫，王莉，王梦光，遗传算法与禁忌搜索算法的混合策略J，系统工程学报，1998, 13(3):2834.7P Hansen, N Mladenovic, An introduction to variable neighbour search M. In: Voss S, Martello S, Osman I, Roucairol C, editors. Metaheuristics: advances and trends in local search paradigms for optimization. Boston: Kluwer Academic Publishers, 1999: 433458.8JAM Perz, JM Moreno-Vega, IR Martn, Variable neighborhood tabu search and its application to the median cycle problemJ, European Journal of Operational Research, 2003, 151(2):365378.9唐芳，王凌