带硬时间窗车辆路线问题的模拟退火算法研究.doc

带硬时间窗车辆路线问题的模拟退火算法研究 徐丽蕊 1 赵姣 林晖钢 胡大伟 (长安大学 汽车学院，陕西 西安 710064) 摘要：本文在对硬带时间窗车辆路线问题进行描述的基础上，建立了该问题的数学模型。针对该 模型的 NP－hard 属性，设计了相应的模拟退火算法；即利用改进节约法构造初始可行解，提高了求解 速度；路线内和路线间同时进行邻域搜索，避免了算法陷入局部最优；通过恰当地选择技术参数，实现 了快速有效地求得问题的满意解。实例仿真测算表明本文提出的算法求得的解质量较高，从而说明了模 拟退火算法解决带硬时间窗的车辆路线问题具有一定的有效性和实用价值。 关键词：车辆路线问题； 硬时间窗； 改进节约法； 模拟退火算法 Study on vehicle routing problem with hard windows by simulated annealing algorithm Xu Lirui Zhao Jiao Lin Huigang Hu Dawei (College of automobile, chang’an university , xi’an, 710064, China) Abstract: This paper describes the vehicle routing problem with hard time window, and sets up the mathematical model of this problem. In view of this model’s NP - hard attribute, the paper designes a kind of simulation annealing algorithm to solve this problem, ie. the initial feasible solution is made up by improved saving algorithm. Neighbour searching between two routes and in two routes are used at the same time so the local optimum solution is avoided. By choosing proper technology parameter, it can obtain satisfied solution quickly and effectively. It is indicated that the results of this paper is better by calculating the simulation example, and the simulation annealing algorithm has certain effective and practical value when solving this kind of problems. Keywords: vehicle routing problem; hard time-windows; simulated annealing algorithm; improved saving algorithm; 1. 引言 车辆路线问题（Vehicle Routing Problem，简称 VRP）最早由 Dantzig 于 1959 年提出[1]。所谓 VRP 是指对一系列特定位置和需求量的客户点，调用一定数量的车辆，从中心仓库出发，选择最优的行车路 线，使车辆有序地访问各客户点，在满足特定的约束条件（如客户的需求量，车辆载重限制等）下，使 得货物尽快达到客户点并且运输总费用最低。 带时间窗的车辆路线问题（Vehicle Routing Problem with Time Windows，简称VRPTW）是在VRP 的基础上增加了时间窗约束的一种变化形式，是运筹学和物流管理学科的研究热点问题之一。VRPTW 给定了各客户点的需求量和允许服务的时间范围，求车辆从站点出发并回到站点的一组行车路线，满足 各车辆不超载，并使总费用最少。VRPTW在实际的物流配送决策中经常遇到，是典型的组合优化问题。 Saveslbergh（1985）已经证明 VRPTW 是一个 NP 难题[2]。在规模较小时，用精确解法可以求得问 题的最优解；在求解大规模 VRPTW 时，无法避开指数爆炸问题，而启发式算法总可以在有限时间里，找 到满意的次优解或可行解，这是精确算法难以做到的。 求解 VRPTW 的启发式算法主要可以分为三类：①路线生成算法，包括节约算法和插入算法；②路 线改进算法，有 2－Swap、2－opt、2－opt*、or－opt 等；③现代优化算法，包括禁忌搜索、遗传算 法、模拟退火算法和蚁群算法等。本文设计了一种改进模拟退火算法，它首先应用路线生成方法产生初 始解，然后结合 2－opt*、2－Swap 和 or－opt 改进策略用模拟退火算法对初始解进行优化，从而求得 VRPTW 的优化解；最后用文献[3]的数据对此算法进行验证，说明此算法的有效性。 2. 数学模型 项目来源：中国物流学会 2006 年课题研究计划项目（2006024） 1 徐丽蕊，女，1980 年生，长安大学硕士研究生。主要研究方向：物流系统。Email:xu_lirui@163.com 1 VRPTW 可简单的描述如下：用于服务的若干车辆从站点出发，为处在不同地理位置、具有不同货 物需求和不同服务时间窗要求的所有顾客提供服务，然后返回站点。其目标是在时间窗内为顾客提供服 务时，使车辆的行驶距离最短。 首先，对数学模型中的决策变量和参数定义如下： I 表示站点和客户的集合，即 I ={0,1,2,L , n}，0 表示站点；J 表示客户集合，即 J  {1,2, , n}；K 表示车辆集合，即 K  {1,2, , m}；C 表示车辆的最大容量； cij 表示从客户 i 到客 户 j 的运输成本； dj 表示客户 j 的需求量； xijk 为决策变量，车辆 k 从 i 到 j 时取 1，否则取 0； yjk 取 1 表示客户 j 由车辆 k 提供服务，否则取 0； ai 表示客户 i 接受服务的最早时间，i＝0 时表示车辆从站点 出发时间； bi 表示客户 i 接受服务的最迟时间； wik 表示车辆 k 服务客户 i 的开始时间，要求落在区间 [ai ,bi ] 内； si 表示完成 i 点任务所需时间； tij 表示车辆从客户 i 行驶到客户 j 的行驶时间；根据问题描 述，建立带时间窗车辆路线问题的数学模型如下[4]： Min å å å cij xijk （2-1） kÎ K iÎ I jÎ I xijk =1 å å k K j I Î i  J （2-2）  k K （2-3） Î x jk  1  j J 0  xijk - å xjik =0 å i I i I Î  k  K , j  J （2-4） Î xi k =1  k  K å i I （2-5） ,0, Î xijk (wik +si +tij - wjk ) £ 0 " k Î K ,i Î I , j Î I （2-6） dj yjk £ C å j J  k K （2-7） ai £ wik £ bi " i Î J ,kÎ K （2-8） xijk  {0,1} " k Î K ,i Î I , j Î I （2-9） yjk Î {0,1} " kÎ K , j Î I （2-10） Î 式（2-1）为目标函数，表示总配送距离最小；式（2-2）表示一个客户只能由一个车辆提供服务； （2-3） 、 （2-4）和（2-5）表示车辆从站点 0 出发，服务完所有客户后，最后回到站点；式（2-6）表示 若车辆正在从客户 i 到客户 j 途中，它不能先于时间 wik  tij  si 到达客户 j ；式（2-7）保证满足每辆 车的容量限制；式（2-8）表示满足客户的时间窗要求；式（2-9）和（2-10）为 0、1 约束。 3. 模拟退火算法求解 3.1 模拟退火算法的原理[5] 模拟退火算法（simulated annealing）是局部搜索算法的扩展。它不同于局部搜索算法之处是以 一定的概率选择邻域中费用值大的状态。理论上讲，它是一个全局最优算法。模拟退火算法最早的思想 由Metropolis在1953年提出，Kirkpatrick在1983年成功地应用到组合优化问题中。 退火是一种物理过程，一种金属物体在加热至一定的温度后，它的所有分子在其状态空间中自由运 动。随着温度的下降，这些分子逐渐停留在不同的状态。在温度最低时，分子重新以一定的结构排列。 统计力学的研究表明，在同一个温度，分子停留在能量小状态的概率比停留在能量大状态的概率要大。 2 当温度相当高时，每个状态的概率基本相同，都接近平均值。当温度趋向0时，分子停留在最低能量状 态的概率趋向于1。 模拟退火算法是一种基于上述退火原理建立的随机搜索算法。组合优化问题与金属物体的退火过程 可进行如下类比：组合优化问题的解类似于金属物体的状态，组合优化问题的最优解类似于金属物体的 能量最低状态，组合优化问题的费用函数类似于金属物体的能量。 模拟退火算法的直观理解是：在一个给定的温度，搜索从一个状态随机地变化到另一个状态，每一 个状态到达的次数服从一个概率分布，当温度很低时，以概率1停留在最优解。 为了克服局部搜索算法极易陷入局部最优解的缺点，模拟退火算法使用基于概率的双方向随机搜索 技术:当基于邻域的一次操作使当前解的质量提高时，模拟退火算法接受这个被改进的解作为新的当前 解；在相反的情况下，算法以一定的概率 exp(- Dc / T ) 接受相对于当前解来说质量较差的解作为新的当 前解，其中△c为邻域操作前后解的评价值之差，T为退火过程的控制参数(即温度)。模拟退火算法已在 理论上被证明是一种以概率1收敛于全局最优解的全局优化算法。 3.2 VRPTW 模拟退火算法设计 （1）解的表示[6] 启发式算法求解车辆路线问题时常用的解的表示方法有三种。①客户与虚拟物流中心共同排列；② 车辆和客户对应排列；③客户直接排列。客户直接排列的表示方法占用的计算机存储量较少，表示直观， 而且容易产生可行解，因此本文解的表示采用客户直接排列的方法。 这种表示方法是直接产生L个1—L间互不重复的自然数的排列，该客户排列就构成一个解，并对应 一种配送路线方案。按照带时间窗车辆路线问题的约束条件，可依次将解的元素（客户）划入各台车辆 的配送路线中。例如，对于一个用3台车辆向9个客户送货的带时间窗车辆路线问题，设某解中的客户排 列为412876935，可用如下方法得到其对应的配送路线方案:首先将客户4(解中的第1个客户)作为第1台 配送车辆服务的第1个客户，然后判断能否满足问题的约束条件，即客户4的需求量是否超过第1台车辆 的最大载重量，且客户4的服务时间窗能否被满足，设能够满足，这时可将客户1(解中的第2个客户)作 为第1台配送车辆服务的第2个客户，然后判断能否满足问题的约束条件，依此类推。当不能满足问题的 约束条件时，这说明客户2不能由第1台配送车辆服务，由此可得第1台车辆的配送路线:0-4-1-0；然后， 将客户2作为第2台配送车辆服务的第1个客户，仍按上述方法可将解中的其它客户也依次加入到其它车 辆的配送路线中。若某个解中的排在最后的若干个客户不能纳入到车辆的配送路线中，则说明该解为一 个不可行解。 （2）解的评价 用上述表示方法所确定的配送路线方案，能够满足每条配送路线上各客户需求量之和不超过配送车 辆的最大载重量，并且满足每个客户的时间窗约束，但不能保证所有的客户全部都能得到配送服务。对 于某个解，若全部客户均能纳入到车辆的配送路线中，则该配送路线方案为一个可行解，计算该配送路 线方案的目标函数值，即为该解的评价值。 （3）初始解的生成 本文采用改进节约法[7]构造初始解，其详细步骤如下： 1）初始化，N 个需求点构造 N 条路线，每条路线只包含一个需求点； 2）计算任意两点间的节约值 S(i, j ) ，令 M ={S(i, j ) | S(i, j ) >0}，并在 M 内将 S(i, j ) 按大小顺 序排列；其中 S(i, j ) =ci 0 +c0 j - dij 。 3）若 M 为空集，则算法终止，否则考查对应的（i，j），若满足下列条件之一： ①点 i 和点 j 均不在已构成的线路上； ②点 i 或点 j 在已构成的线路上，但不是线路的内点； ③点 i 和点 j 在已构成的线路上，但均不是内点，且一个是起点，一个是终点。 则转步骤 4）；否则转步骤 6）； 3 4）检查点 i 和点 j 连接后路线上的客户总需求量 Q ，若 Q £ C ，则转步骤 5） ；否则转步骤 6）； 5）计算点 j 及其之后的点的时间窗约束，若满足则连接点 i、j，转步骤 6） ；否则直接转步骤 6）； 6）令 M =M - S(i, j ) ，转步骤 3） 。 （4）邻域解的构造 1）路线间 将当前路线中的k条边用另外k条边代替， 这种变换称为k-opt[8],最为常见的是2-opt，即将边(i,i+1)、 (j,j+1)用(i,j)、(i+1,j+1)代替。然而这种交换使得原来路线中边(i+1,j)的方向发生变化，由于VRPTW 问题中有时间窗约束，这种方向的改变很可能导致所得路线不可行。因而在求解VRPTW问题时，使用2－ opt*[9]比2－opt更有效。2－opt*变换是用边(i,j+1)、(j,i+1)代替边(i,i+1)、(j,j+1),即将两条路线 中顾客i、j后的所有顾客整体交换，如图1所示。可以看到，这种交换保持了原来路线中顾客的先后次 序，所以变换后路线的可行性得到了保证。因而适用于带时间窗的车辆路线问题的路线间优化。 i i j+1 j+1 i+1 i+1 j j 代表选中 DC， 图1 代表客户， 和 * 2－opt 交换法示意图 代表路线 2）路线内 ①Or-opt法 Or-opt法是考虑一条路线中任意一个点（或多个点）插入到其他弧中的方法。在本文中任意选择路 线中的一个点，考虑其插入到其他弧中的目标函数值，如果满足时间窗同时得到更小的目标函数值则更 新当前路线。这种交换只改变了所要交换的点的优先顺序，并不改变其他点的顺序，也能满足带时间窗 路线问题的要求。Or－opt的插入过程如图2所示（需求点3插入到弧1－2中）。 2 1 2 3 1 4 代表选中 DC， 图2 3 代表客户， 和 Or-opt交换示意图 4 代表路线 ②2－Swap 2-Swap 指任意选择一条路线，从中任意选择两个不同的客户，交换它们的位置。2－Swap 交换过程 的示意图如图 3 所示。 （5）温度参数的控制 1）初始温度的选取 4 初始温度值的设置是影响模拟退火算法全局搜索性能的重要因素之一。初始温度高，则算法搜索到 全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可 能受到影响。实际应用过程中，需要依据实验结果进行若干次调整。从理论上说，初始温度t0应保证平 稳分布中每一状态的概率相等，即满足 exp(Dfij / t0 ) » 1，据此可以很容易地得到初始温度的一个估计 值，即， t0 =Kd ，K为充分大的正数，实际计算中可取K=10, 20, 100,⋯ 等实验值。 2 1 1 2 3 4 3 4 代表选中DC， 代表客户， 和 图3 2-Swap法示意图 代表路线 d =max{f ( j ) | j Î D}- min{f ( j ) j Î D}，实际计算中，对 d 的值可以简单地加以估计。 2)温度下降规则 本文采用下式实现模拟退火算法的温度下降过程， Ti +1 =h×Ti ，式中 Ti 是迭代 i 次时的当前温度， h 一个小的时间常数。 3）每一温度的迭代步长 采用上述温度下降规则，用以下退火策略： ①若在温度 Ti 时，随机进行 U 次循环，就认为在该温度下，每个分子都已经有足够的机会达到最 佳位置。因而可以将温度下降到 Ti +1 =h×Ti 。 ②若在温度 Ti 时，成功地对解改进 L 次。这相当于退火过程中，已有足够的分子达到了最佳位置。 在这时，也将温度下降到 Ti +1 =h×Ti 。 （6）停止规则 算法停止规则是当温度降至终止温度 Tf 时，表示已经达到最低温度，算法停止。 3.3 模拟退火算法的实现步骤 模拟退火算法的详细步骤如下，程序框图见图 4。 Step1：设置控制参数。包括初始温度 T0 、温度衰减系数 h 、终止温度 Tf ，当前温度迭代次数 u =0 ，当前成功迭代次数 l =0； Step2：初始解的产生。用改进节约法产生 f0 ； fi = f0 ； Step3：构造邻域解。按照上述方法进行路线内和路线间调整得到一个邻域解 f j ，且 u =u +1； Step4：判断时间窗约束。若不满足时间窗约束，转 Step3； Step5：比较。如果 f j ³ fi ，则转 Step6；否则 fi = f j ，记录当前解为最优解， l =l +1，转 Step7； Step6 ： Metropolis 准 则 检 验 。 计 算 Dfij = f j - fi ， 若 exp(- Dfij / Ti ) >random(0,1) 时 ， 则 fi = f j ， l =l +1；否则不接受；转 Step7； Step7：温度下降规则。若 u ³ U 或 l ³ L 时， Ti +1 =h×Ti ， u =0 ， l =0，转 Step8；否则返回 Step3； Step8：算法终止规则。若当前温度 Ti +1