车辆路径问题优化算法

1、车辆路径问题优化算法美国物流管理学会（Council of Logistics Management , CLM）对物流所作的定 义为： “为符合顾客的需要，对原料、制造过程中的存货与制成品以及相关信息， 从其起运点至最终消费点之间，做出的追求效率与成本效果的计划、执行与控制 过程。”而有关资料显示，物流配送过程 （包含仓储、分拣、运输等 ）的成本构成中，运输 成本占到 52% 之多。因此，如何在满足客户适当满意度的前提下，将配送的运 输成本合理地降低，成为一个紧迫而重要的研究课题，车辆路径问题正是基于这 一需求而产生的。2.1 车辆路径问题的定义 车辆路径问题可以描述为：给定一组有容量限制的

2、车辆的集合、一个物流中心（或 供货地）、若干有供货需求的客户，组织适当的行车路线，使车辆有序地通过所 有的客户，在满足一定的约束条件（如需求量、服务时间限制、车辆容量限制、 行驶里程限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、 使用车辆数尽量少等）。 4 因此研究车辆的路径问题，就是要研究如何安排运输车辆的行驶路线， 使运输车 辆依照最短的行驶路径或最短的时间费用， 依次服务于每个客户后返回起点，总 的运输成本实现最小。车辆路径问题已被证明是 NP-Hard 问题，因此求解比较困难。然而，由于其在 现实生活中应用非常广泛，使得它无论在理论上还是在实践上都有极大的研究价 值。P

3、enousal Machado 等人5 指出车辆路径问题 （vehicle routing problem ，简称 VRP）是一个复杂的组合优化问题，是古老的旅行商问题和背包问题的综合。实 际上，车辆路径问题通常可被分解或转化成一个或几个已经研究过的基本问题， 再采用相应比较成熟的基本理论和方法，以得到最优解或满意解。这些与车辆路径问题相关的常用基本问题有； 旅行商问题、运输问题、背包问题、 最短路问题、最小费用最大流问题、中国邮路问题、指派问题等。旅行商问题可被描述为：一个推销员欲到 n 个城市推销商品，每 2 个城市之间的 距离是已知的。如何选择一条路径使推销员依次又不重复地走遍每个城市后

4、， 回 到起点且所走的路径最短。运输问题关心的是（确实的或是比喻的）以最低的总配送成本把供应中心（称为 出发地，sources）的任何产品运送到每一个接受中心（称为目的地， destinations ）。运输问题需要的数据仅仅是供应量、需求量和单位成本。 背包问题是指有一只固定容量的背包和若干体积、 重量不等的物品，背包的容量 不允许装下这所有的物品，那么如何选择适当的物品装入背包，使得背包的装载 量（所装物品的重量之和）最大。最短路径问题解决的是在一个网络中， 如何寻找两点之间的最短路径。这两点之 间通常没有直接的通路可达，但可经由若干中间结点相通。最小费用流问题主要解决如何以最小成本在一个

5、配送网络中运输货物。 最小费用 流问题又称为网络配送问题。最大流问题和最小费用流问题一样，也与网络中的流有关。但是它们的目标不同， 最大流问题不是使得流的成本最小化， 而是寻找一个流的方案，使得通过网络的 中国邮路问题是由我国管梅谷同志在 1962 年首先提出的，它可描述为：一个邮 递员负责某一个地区的信件投递。 每天要从邮局出发， 走遍该地区所有的街道再 返回邮局，问应该怎样安排送信路线可以使所走的路程最短。指派问题解决将 n 件工作安排给 m 个人完成的问题。已知不同人完成不同工作 的效率(或成本)不同，指派问题要求以最高的效率(或最小的人工成本)完成 工作的安排。2.2 车辆路径问题的分

6、类 车辆路径问题当不考虑时间要求， 仅根据空间位置安排路线时称为车辆路线安排 问题(Vehicle Routing Problem 简记VRP)；当考虑时间要求安排路线时称为车辆 调度问题(Vehicle Scheduling Problem 简记VSP);当同时考虑空间位置和时间要 求时称为路线和调度混合问题 6 。车辆调度冋题即有时间要求的车辆路径冋题(VSP)又被称为带时间窗的车辆路 径问题(Vehicle Routing Problem with Time Windows ,简记为 VRPTW)。VRPTW 是在VRP的基础上增加了客户要求访问的时间窗口，是一般车辆路径问题的扩 展。其

7、简单的描述如下： 用于服务的若干车辆从站点出发， 为处在不同地理位置、 具有不同货物需求和不同服务时间窗要求的所有顾客提供服务，然后返回站点， 其中为每个顾客仅提供一次服务。 其目标是在时间窗内为顾客提供服务时， 使车 辆的行驶时间和等待时间之和最短。根据时间约束的严格与否， 带时间窗的车辆路径问题被分为两类： 软时间窗车辆 路径问题和硬时间窗车辆路径问题。 软时间窗车辆路径问题要求配送车辆尽可能 在时间窗内到达访问，否则将给予一定的惩罚。该惩罚包括两部分：(1)车辆在要求的最早到达时间之前到达，必须在任务点处等待而损失的成本；(2)车辆在要求的最迟到达时间之后到达， 必须付给客户预先约定的罚

8、金。 而硬时间窗车辆 路径问题则要求必须在时间窗内到达访问，否则服务被拒绝。Koskosidis 等人( 1992) 7 指出，软时间窗模式比硬时间窗更具优势是因为： 第一、软时窗模式较传统硬时窗模式更为一般化， 且软时窗的求解演算法较具弹 性(因限制式较少)。而且若要提高准点服务频率，只需适当的提高惩罚成本即 可；第二、在现实世界中，时窗限制大多属于软时窗限制。配送服务商没有在约 定的时间内送达顾客端， 并非一定不可服务， 而是可以服务但必须付出双方约定 的惩罚成本。 有较高准点送达要求的顾客的惩罚成本大， 不准时但是在可以忍受 的时间内送达的顾客的惩罚成本相对小些； 第三、软时窗模式可以有

9、效的反应配 送商在车队营运成本、 规模和服务水准两者之间的关系； 第四、软时窗模式可以 发现硬时窗模式无法找到的可行解。 特别是在小规模车队服务多数顾客以及严苛 的时间限制条件状况下。 在上述的情形得到软时窗限制下的可行解后， 可再调整 时间窗让违反时间窗的情况得到改善。车辆路径问题还有确定性 (Deterministic) 模式和随机性 (Stochastic) 模式之分8 。 确定性模式假设：其一、客户的数目在配送开始前是已知且固定的；其二、客户 的需求量在配送开始前是已知且固定的； 其三、两点之间的旅行时间仅取决于这 两点之间的距离。 而随机性模式不要求以上一个或多个假设。 随机性模式又

10、称为 随机需求车辆路径问题。如果考虑装卸工人的调配问题， 则车辆路径问题就称为带装卸工调配的车辆路径 问题。带装卸工调配的车辆路径问题描述如下 9:设配送中心有n辆货车都要 向b个客户装卸货物。配送中心可以安排 位装卸工跟着车辆，也可以安排位装 卸工固定在客户 处。已知在客户 处需要的装卸工人数是 ，配送中心应该考虑 如何调配装卸工，使总的装卸工人数最少。除了以上分类， 车辆路径问题还可以按任务特征分为装货问题、 卸货问题及装卸 混合问题； 按任务性质分为对弧服务问题 （如中国邮递员问题） 和对点服务问题 （如旅行商问题）以及混合服务问题（如校车路线安排问题）；按车辆载货状况 分为满载问题和非

11、满载问题； 按车场数目分为单车场问题和多车场问题； 按车辆 类型数分为单车型问题和多车型问题； 按车辆对车场的所属关系分为车辆开放问 题（车辆可不返回车场）和车辆封闭问题（车辆必须返回车场）；按优化目标可 分为单目标问题和多目标问题，等等。针对上述不同的分类方法，车辆路径问题的模型构造及求解算法有很大差别。2.3 车辆路径问题的构成要素 物流配送车辆路径问题的构成因素主要包括货物、车辆、配送中心、客户、运输 网络、约束条件和目标函数等要素 10 。2.3.1 货物 货物是配送的对象。可将每个客户需求（或供应）的货物看成一批货物。每批货 物包括品名、包装、重量、体积、要求送到（或取走）的时间和地

12、点、能否分批 配送等属性。货物的品名和包装， 是选用配送车辆的类型以及决定该批货物能否 与其他货物装在同一车辆内的依据。 例如，一些货物因性质特殊需要使用专用车 辆装运；而一些货物虽然性质特殊， 但由于包装条件很好， 故也能与其它货物装 在同一车辆内。 另外， 货物的重量和体积也是进行车辆装载决策的重要依据。 当 某个客户的需求量 （供应量） 的货物的重量或体积超过车辆的最大装载量或体积 时，则对该客户需要采用多台车辆进行配送。2.3.2 车辆 车辆是货物的运载工具，其主要包括 : 车辆的类型、装载量、一次配送的最大行 驶距离、配送前以及完成任务后车辆的停放位置等。 其一、车辆的类型有通用车辆

13、和专用车辆之分， 通用车辆适于运载大多数普通货 物，专用车辆适于载运一些性质特殊的货物。 其二、车辆的装载量是指车辆的最大装载重量和最大装载容积， 是进行车辆装载 决策的依据。在某个配送系统中，车辆的装载量可以相同也可以不同。 其三、对每台车辆一次配送的行驶距离的要求可以分为以下几种情况 : 第一、无 距离限制 ; 第二、有距离限制 ; 第三、有距离限制，但可以不遵守。 其四、车辆在配送前可以是停放在某个停车场、 配送中心或者是客户所在地。 完 成任务后，其停放位置一般可以分为以下几种情形 : 一是必须返回出发点 ; 二是 必须某个停车场或配送中心 ; 三是可返回任意停车场 ; 四是可停放在任

14、何地点。2.3.3 配送中心 配送中心是从事货物配备 （集货、加工、拣选、配货 ） 和组织对客户的送货，以提 高水平实现销售或供应的现代流通设施。 在某个配送系统中， 配送中心的个数可 以是一个也可以是多个， 这涉及到配送网络问题， 如在某些配送网点多而且配送 范围广的情形下， 往往采用多级配送中心进行配送， 通过一级配送中心配送到下 一级配送中心再配送， 在多个二级配送中心下， 究竟由哪个配送中心配送， 这涉 及到配送的优化问题。其配送示意图见图 2-1:图 2-1 分级配送示意图2.3.4 客户 也称为用户，包括各盆景展览馆、陈列中心、公司、家庭用户等。单个客户一次 所需的盆景数量可能大于

15、盆景配送车某车辆的最大装载量， 也可能小于该车辆的 最大装载量。 而该系统全部客户的货物需求 （或供应）总量可能超过全部车辆的 总装载量。在以上情形下，当货物一次性需求（或供应）总量超过运输能力时， 需要多次（多辆）分批配送；当货物一次性需求（或供应）量小于某车辆的最大 装载量时，在可能的情况下，应进行货物配载。客户的需求（或供应）盆景的时间，是指要求盆景送达（或取走）的时间，对配 送时间的要求可分为以下几种情况 : 第一、无时间限制；第二、要求在指定的时 间区间（也称为时间窗）内完成运输任务；第三、有时间限制，但可以不遵守， 只是不遵守时要给予一定的惩罚。2.3.5 运输网络 运输网络是由顶

16、点（指配送中心、客户、停车场等）、无向边和有向弧组成 的，边、弧的属性包括方向、权值和交通流量限制等。运输网络中边或弧的权值 可以表示距离、 时间或费用。边或弧的权值变化可分为以下几种情况 : 一是固定， 即不随时间和车辆的不同而变化；二是随时间而变化；三是随车辆不同而变化； 四是既随时间不同而变化，又随车辆不同而变化。对运输网络权值间的关系可以要求其满足三角不等式，即两边之和大于第三边。 也可以不加限制。运输网络见示意图 2-2.图 2-2 运输网络示意图 对运输网络中顶点、边或弧的交通流量要求分为以下几种 : 其一、交通流量随时 间不同而变化 ; 其二、边、弧限制，即每条边、 弧上同时行驶

17、的车辆数有限制 ; 其 三、顶点限制，即每个顶点上同时装、卸的车辆数有限；其四、边、弧、顶点都 有限制。2.3.6 约束条件 通常说来， 物流配送车辆路径问题应满足的约束条件主要包括： 第一，满足所有 客户对货物品种、规格、数量的要求；第二，满足客户对货物发到的时间范围的 要求；第三，在允许通行时间进行配送（如有时规定白天不能通行货车等）；第 四，车辆在配送过程中的实际载货量不得超过车辆的最大允许装载量； 第五，在 配送中心现有的运力范围内。2.3.7 目标函数对物流配送车辆路径问题， 可以只选用一个目标， 也可以是多个目标。 经常 选用的目标函数主要有 : 第一，配送总里程最短。 配送里程与

18、配送车辆的耗油量、 磨损程度以及司机疲劳程度等直接相关， 它直接决定运输的成本， 对配送业务的 经济效益有很大影响。 由于配送里程计算简便， 它是确定配送路线时用得最多的 指标。第二， 配送车辆的吨位公里数最少。 该目标将配送距离与车辆的载重量结 合起来考虑， 即以所有配送车辆的吨位数 （最大载重吨） 与其行驶距离的乘积的 总和最少为目标。 第三，综合费用最低。 降低综合费用是实现配送业务经济效益 的基本要求。在物流配送中，与取送有关的费用包括 : 车辆维护和行驶费用、路 桥费用、车队管理费用、货物装卸费用、有关人员工资费用等。第四，准时性最 高。由于客户对交货时间有较严格的要求， 为提高配送

19、服务质量， 有时需要将准 时性最高作为确定配送路线目标。 第五，运力利用最合理。 该目标要求使用的较 少的车辆完成配送任务，并使车辆的满载率最高，以充分利用车辆的装卸能力。 第六，劳动消耗最低。即以司机人数最少、司机工资时间最短为目标。2.4 车辆路径问题的求解方法 车辆路径问题通常被构造成整数规划模型、图论或其它模型，这些模型之间 存在着某种联系。 但从建立模型时的出发点考虑， 大多数模型都可看成是下面三 种模型的变形与组合： 第一，以车流为基础的模型； 第二，以物流为基础的模型； 第三，集覆盖模型。求解方法上，常用的基本理论和方法有：分枝定界法、割平面法、线性规划法、 动态规划法、匹配理论

20、、对偶理论、组台理论、线搜索技术、列生成技术、拉格 朗日松弛技术、状态空间松弛技术、 Benders 分解技术、扶梯度 （sub gradient） 优化技术、概率分析、统计分析、最差情况分析、经验分折等常用算法基本上可分为优化算法和启发式算法两大类。 优化算法求解时间长， 算 法效率低且不适合求解规模较大的问题， 因此在实际应用中受到限制； 启发式算 法效率较高且能逼近最优解， 为此专家们主要把精力花在构造高质量的启发式算 法上。目前已提出的启发式算法相当多，大体上可分为传统启发式算法 （ Heuristic ）和巨集启发式算法（ Meta-Heuristic ）两大类 11 。 传统启发式

21、算法具有求解速度快、 求得的解较为固定的特点。 已被证明会陷入局 部优化解中 11 。巨集启发式算法则尝试以不同的方式跳出局部解，在可接受的 时间内，求得近似最优解，甚至是全局最优解。所以在近年来的研究中，多用巨 集启发式算法来求解车辆路径问题， 或者混合使用传统启发式算法和巨集启发式 算法。2.4.1 传统启发式算法根据 Bodin 等人12 的研究，用于求解车辆路径问题的传统启发式算法可 分为： 第一，先分组后安排路线的方法（ Cluster-First Route-Second ）：这种方法先把 节点（或弧）的需求进行分组或划群，然后对每一组设计一条经济的路线。如 Gillett 和 M

22、iller 于 1974 年提出的扫描（ sweep ）算法13,14,15 。方法是先以极 坐标的方式表示各个客户点的区域位置， 再任取一个客户点作为起点以顺时针方 向，以车辆容量为限制条件（或再加入其它限制条件）对区域进行分割，使不超 过车辆容量 （或满足其它限制条件） 的需求点组成一个区域， 一个区域就是一个 组。当形成一系列这样的组后， 再对每一组中的各点安排线路。 这种算法一般仅 适用于装货（或卸货）问题，且车辆是封闭的。 第二，先安排路线后分组的方法（ Route-First Cluster-Second ）：在不考虑约束 条件的前提下进行路线的构建， 然后再根据约束条件对路线进行

23、切割。 这种方法 首先构造一条或几条很长的路线 （通常不可行 ），它包括了所有需求对象，然后再 把这些很长的路线划分成一些短而可行的路线。 具体进行时， 一般是先解一个经 过所有点的旅行商问题，形成一条路线，然后根据一定的约束 （ 如车辆容量等 ）对 它进行分划。典型的有由 Rosenkrantz 等人16于 1977 年提出的最临近点法。 思路是以车场为起点， 寻找离车场距离成本最小且没有加入路线的节点为起始路 线，重复以上步骤直至找不到可以满足车辆限制条件的节点时， 回到车场重新出 发，另外构建一条新的路径。第三，节约插入算法（ Saving or Insertion ）：根据节约值的大小

24、来构建路线， 直至无法改善或达到停止条件为止。 该算法的每一步， 把当前的线路构形 （很可 能是不可行的）跟另外的构形（也可能是不可行的）进行比较，后者或是根据某 个判别函数（例如总费用） 会产生最大程度的节约的构形， 或是以最小代价把一 个不在当前构形上的需求对象插人进来的掏形，最后得到一个较好的可行构形。 节约算法最早是由 Clark 和 Wright 于 1964 年提出的 11 。根据三角形两边之和 大于第三边的性质， 以一部车服务一个客户作为初始解， 一部车服务一个客户然 后就返回车场为其起始状况， 计算路径间的合并节约值。 将算出的节约值按照降 幂排序并依次合并路径。 若找不到满足

25、限制条件的节点， 便回到车场， 重新构建 新的路径，直到没有大于零的节约值为止。节约算法是利用节约值的大小和是否满足限制条件来决定两节点是否相连的。 节 约值的计算如下：设0表示示车场，i和j为两个任务点，定义点对i和j的节约 值为 其含义为点i和点j在同一条线路上的距离成本与点i和点j各在不同线路上的距 离成本相比得到的距离成本的节约值。这种算法与 Sweep 算法的适用范围差不 多。2.4.2 巨集启发式算法 巨集启发式算法主要基于改进或交换( Improvement or Exchange )的思路，即 先构建一个初始解，再用贪婪算法( Greedy)17 ，进行路线的优化，直至无法 改

26、进或达到停止条件为止。 该算法在始终保持解可行的情况下， 力图向最优目标 靠近，每一步都产生另一个可行解以代替原来的解， 使目标函数值得以改进， 一 直继续到不能再改进目标函数值为止。 经典的遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法都属于这一类方法。 遗传算法( Genetic Algorithm, GA) 最早由 Holland 18 于 1975 年提出，是根据 达尔文进化论中 “物竞天择，适者生存 ”的自然进化法则发展而来。其基本精神是 进化与选择，利用复制( reproduction )、交配( crossover )、突变( mutat ion ) 三个基本运算元重复运作， 以

27、达到淘汰较差解的目的。 其做法是： 先由数个可行 解个体产生一母体集合，其中的元素即为基因(gene )。再通过计算第一代母 体中个体目标值的方式，选出较优秀的个体，以交配、突变等方式产生下一代。 最后依据停止条件结束演算。 遗传算法具有多点平行搜寻可行解的特性， 已逐渐 被运用于高度空间搜寻的组合最佳化问题上。模拟退火算法(Simulated Ann eali ng ，SA)，其最初的思想由 Metropolis在 1953 年提出， Kirkpatrick 等人19 在 1983 年成功地将其应用在组合最优化问题 中。模拟退火算法来源于固体退火原理： 将固体加温至充分高， 再让其徐徐冷却，

28、 加温时， 固体内部粒子随温升变为无序状， 内能增大， 而徐徐冷却时粒子渐趋有 序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。用固体 退火模拟组合优化问题，将内能 E模拟为目标函数值f，温度T演化成控制参数 t，由初始解i和控制参数t的初值开始，对当前解重复 产生新解计算目标函 数差一接受或舍弃”的迭代，逐步衰减t值，并设定终止条件，即得到解组合优 化问题的模拟退火算法。 算法终止时的当前解即为所得近似最优解， 这是基于蒙 特卡罗迭代求解法的一种启发式随机搜索过程。模拟退火算法具有能往目标值较差处移动的机会， 这种随机过程产生的机会使得 该算法有能力避免陷入局部优化，而得到全

29、局最优解。禁忌搜索法( Tabu Search, TS )，是由 Glover20 于 1977 年提出的， Willard 21 于 1989 年将其用于车辆路径问题上。其求解的过程是先求得一初始解，然后在 邻域中搜索较佳解或是移动到较差的区域搜索该区域最佳解， 并且记录曾经搜寻 的路径，作为下次搜索的依据， 以避免陷入局部最优解中。 禁忌搜索算法主要包 含移步(Move)、候选列表(Can didate List)、禁忌列表(Tabu List)、渴望 准则( Aspiration Level )及搜寻停止准则( Stopping Criterion )等五种要素。 蚁群算法( Ant S

30、ystem, AS )最早由 Macro Dorigo22 于 1992 年提出，其灵感 来自蚂蚁觅食时可以在食物和巢穴间找到最短路径的能力。 蚂蚁觅食时会在走过 的路线上留下一种称为费洛蒙 ( pheromone )的化学物质， 费洛蒙的浓度与遗留 时间成反比，与走过该路线的蚂蚁的数量成正比。 当一只蚂蚁面临路线的选择时， 它会优先选取费洛蒙浓度高的路线。 就是说， 费洛蒙残留的浓度越高， 则吸引蚂 蚁前来的能力越强，越多的蚂蚁经过某条路线时，该路线的费洛蒙浓度就越高， 从而吸引更多的蚂蚁前来。 通过这种方式， 蚂蚁就可找出食物与巢穴间的最短路 径。2.4.3 混合启发式算法 一是、基于数学

31、规划的算法( Mathematical-Programming Based ) 6 是把问题 直接描述成一个数学规划问题， 根据其模型的特殊构形， 应用一定的技术 (如分 解)进行分划，进而求解已被广泛研究过的子问题。典型的有 Fisher 和 Jaikumar 提出的算法。该算法把车辆路线问题构造为一个广 义分派问题， 并提出下述启发式算法： 首先把问题描述为一个数学规划问题， 再 将问题分解成一个旅行商问题和一个分派问题。 对每一辆车将顾客进行分派， 这 通过解一般分派问题来得到。 每辆车为它的顾客服务， 以一个近似等于旅行商线 路的费用为目标， 分派一旦做出， 通过应用一些旅行商问题的启

32、发式算法或优化 算法来得到每辆车的行车路线。二是、交互式优化法 6 。即把人的因素结合到问题的求解过程中，其思想是； 有经验的决策者应具有确定和修改参数的能力， 并且根据知识经验， 把主观的估 计加到优化模型中去。这通常会增加模型最终实现并被采用的可能性。 如 Cuilew， Jarvis 和 Ratfiff 提出的两段法： 第一阶段： 由有经验的调度员或是根据自动生成 规则选定一些 “组”点，目标函数定义为线性近似 ( )，其中 定义为需求点 i 和“组 点”之间的欧氏距离，根据确定的 组”点坐标求解得出的分派问题，由求出的结 果再求解得出的定点问题，即重新确定每个 “组”点的位置，以使分派

33、给它的各需 求点离它的总距离最小。 交替求解分派问题和定点问题， 直到目标没有进一步的 改进。第二阶段：用列生成技术生成新解，直到不能进一步改进为止。 这几种启发式算法常不是绝对划分的，有的方法同属于好几类。4.1.1 算法描述 模拟退火算法是一种用于求解大规模优化问题的随机搜索算法， 它以优化问题求 解过程与物理系统退火过程之间的相似性为基础； 优化的目标函数相当于金属的 内能；优化问题的自变量组合状态空间相当于金属的内能状态空间； 问题的求解 过程就是找一个组合状态， 使目标函数值最小。 大量的研究证明， 模拟退火算法 可在多项式时间内求解全局优化问题的目标。模拟退火算法来源于固体退火原理

34、， 将固体加温至充分高， 再让其徐徐冷却， 加 温时，固体内部粒子随温升变为无序状， 内能增大，而徐徐冷却时粒子渐趋有序， 在每个温度都达到平衡态， 最后在常温时达到基态， 内能减为最小。 用固体退火 模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t， 即得到解组合优化问题的模拟退火算法：由初始解 i和控制参数初值t开始，对 当前解重复 产生新解一计算目标函数差一接受或舍弃”的迭代，并逐步衰减t值, 算法终止时的当前解即为所得近似最优解， 这是基于蒙特卡罗迭代求解法的一种 启发式随机搜索过程。模拟退火算法需要一个构建好的初始解作为算法的输入参数， 在进入迭代后， 每 一次迭

35、代都需要构建新解。 本文用最临近点法来构建初始解， 用区域搜索法来求 得每一次迭代的新解 28 。分别论述如下：1）最临近点法构建初始解：从盆景养护基地出发，寻找距离它最近的客户，生 成一条线路；再从该客户出发，寻找他的最临近客户，加入该线路。重复该过程 直到满足车辆的最大装载容量限制 （同时考虑时间窗限制和车辆的最大行驶距离 限制），即完成一条线路的构建。返回盆景养护基地，重复以上步骤继续构建线 路，直到所有的客户都被加入线路中，则初始解的构建就完成了。2）区域搜索法产生新解：区域搜索法是通过不断改善路经来求得更佳的解，并 以贪婪法则决定是否接受新的改善解。 改善的方法是在同一条线路中随机交

36、换节 点，或在相邻线路中随机交换节点。有2-opt交换法、3-opt交换法以及Cross-opt 交换法，本文采用 2-opt 交换法。4.1.2 算法步骤 模拟退火算法的主要步骤如下 29 ：1）初始化：初始温度 （充分大 ），初始解状态 （是算法迭代的起点 ）， 每个 值的 迭代次数 ；2）对 重复以下第 （3）至第（6）步；3）产生新解 ；4）计算增量 ，其中 为评价函数；5）若 则接受 作为新的当前解，否则以概率 接受 作为新的当前解；6）如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为 连续若干个新解都没有被接受时终止算法。否则执行下面第 （7） 步；7）逐渐衰减（

37、趋于零），然后转第 （2） 步。4.1.3 重点抽样与 Metroplis 准则模拟退火的主要思想是： 在搜索区间（二维平面中） 随机游走（即随机选择点） ， 再以 Metropolis 准则抽样，使随机游走逐渐收敛于局部最优解。Metropolis 抽样准则是一种有效的重点抽样法。其思想为：系统从一种状态变到 另一种状态时，相应的能量从 变化到 ，如果 ，系统接收此状态，否则，以 的 概率接收或丢弃此状态。经过一定次数的迭代，系统会逐渐趋于稳定状态。 重点抽样时，新状态如果向下则接受（局部最优），若向上（全局搜索），以一 定概率接受。 模拟退火方法从某个初始解出发， 经过大量解的变换后， 可

38、以求得 给定控制参数值时组合优化问题的相对最优解。然后减小控制参数 的值，重复 执行 Metropolis 算法，就可以在控制参数 T 趋于零时，最终求得组合优化问题 的整体最优解。控制参数的值必须缓慢衰减。温度是 Metropolis 算法的重要控制参数。开始时温度高 （ 值大 ），算法可能接受 较差的恶化解；随着 值的减小，只能接受较好的恶化解；最后当 趋于 0 时，就 不再接受任何恶化解了。当 值足够大时（即无限高温），系统立即均匀分布，接受所有提出的变换。 衰 减得越小， 到达终点的时间就越长， 但可使马可夫链缩短， 使到达准平衡分布的 时间缩短。4.1.4 算法重点和难点 模拟退火算法的重点是新解的产生和接受。主要有以下四个步骤： 其一、由一个产生函数从当前解产生下一个位于解空间的新解。 为便于后续的计 算和接受， 减少算法耗时， 通常选择由当前新解经过简单地变换即可产生新解的 方法，如对构成新解的全部或部分元素进行置换、 互换等。 产生新解的变换方法 决定了当前解的邻域结构，因而对冷却进度表的选取有一定的影响。其二、计算与新解所对应的目标函数差。 因为目标函数差仅由变