《车辆路径问题及遗传算法(共8页).docx》由会员分享，可在线阅读，更多相关《车辆路径问题及遗传算法(共8页).docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上车辆路径问题优化算法 美国物流管理学会(CouncilofLogisticsManagement，CLM)对物流所作的定义为：“为符合顾客的需要，对原料、制造过程中的存货与制成品以及相关信息，从其起运点至最终消费点之间，做出的追求效率与成本效果的计划、执行与控制过程。” 而有关资料显示，物流配送过程(包含仓储、分拣、运输等)的成本构成中，运输成本占到52%之多。因此，如何在满足客户适当满意度的前提下，将配送的运输成本合理地降低，成为一个紧迫而重要的研究课题，车辆路径问题正是基于这一需求而产生的。 2.1车辆路径问题的定义 车辆路径问题可以描述为：给定一组有容量限制的车
2、辆的集合、一个物流中心（或供货地）、若干有供货需求的客户，组织适当的行车路线，使车辆有序地通过所有的客户，在满足一定的约束条件（如需求量、服务时间限制、车辆容量限制、行驶里程限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。4 因此研究车辆的路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最短的行驶路径或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本实现最小。 车辆路径问题已被证明是NP-Hard问题，因此求解比较困难。然而，由于其在现实生活中应用非常广泛，使得它无论在理论上还是在实践上都有极大的研究价值。 PenousalMacha
3、do等人5指出车辆路径问题(vehicleroutingproblem，简称VRP)是一个复杂的组合优化问题，是古老的旅行商问题和背包问题的综合。实际上，车辆路径问题通常可被分解或转化成一个或几个已经研究过的基本问题，再采用相应比较成熟的基本理论和方法，以得到最优解或满意解。 这些与车辆路径问题相关的常用基本问题有；旅行商问题、运输问题、背包问题、最短路问题、最小费用最大流问题、中国邮路问题、指派问题等。 旅行商问题可被描述为：一个推销员欲到n个城市推销商品，每2个城市之间的距离是已知的。如何选择一条路径使推销员依次又不重复地走遍每个城市后，回到起点且所走的路径最短。 运输问题关心的是（确实的
4、或是比喻的）以最低的总配送成本把供应中心（称为出发地，sources）的任何产品运送到每一个接受中心（称为目的地，destinations）。运输问题需要的数据仅仅是供应量、需求量和单位成本。 背包问题是指有一只固定容量的背包和若干体积、重量不等的物品，背包的容量不允许装下这所有的物品，那么如何选择适当的物品装入背包，使得背包的装载量（所装物品的重量之和）最大。 最短路径问题解决的是在一个网络中，如何寻找两点之间的最短路径。这两点之间通常没有直接的通路可达，但可经由若干中间结点相通。 最小费用流问题主要解决如何以最小成本在一个配送网络中运输货物。最小费用流问题又称为网络配送问题。 最大流问题和
5、最小费用流问题一样，也与网络中的流有关。但是它们的目标不同，最大流问题不是使得流的成本最小化，而是寻找一个流的方案，使得通过网络的流量最大。 中国邮路问题是由我国管梅谷同志在1962年首先提出的，它可描述为：一个邮递员负责某一个地区的信件投递。每天要从邮局出发，走遍该地区所有的街道再返回邮局，问应该怎样安排送信路线可以使所走的路程最短。 指派问题解决将n件工作安排给m个人完成的问题。已知不同人完成不同工作的效率（或成本）不同，指派问题要求以最高的效率（或最小的人工成本）完成工作的安排。 2.2车辆路径问题的分类 车辆路径问题当不考虑时间要求，仅根据空间位置安排路线时称为车辆路线安排问题(Veh
6、icleRoutingProblem简记VRP)；当考虑时间要求安排路线时称为车辆调度问题(VehicleSchedulingProblem简记VSP)；当同时考虑空间位置和时间要求时称为路线和调度混合问题6。 车辆调度问题即有时间要求的车辆路径问题（VSP）又被称为带时间窗的车辆路径问题（VehicleRoutingProblemwithTimeWindows，简记为VRPTW)。VRPTW是在VRP的基础上增加了客户要求访问的时间窗口，是一般车辆路径问题的扩展。其简单的描述如下：用于服务的若干车辆从站点出发，为处在不同地理位置、具有不同货物需求和不同服务时间窗要求的所有顾客提供服务，然后返
7、回站点，其中为每个顾客仅提供一次服务。其目标是在时间窗内为顾客提供服务时，使车辆的行驶时间和等待时间之和最短。 根据时间约束的严格与否，带时间窗的车辆路径问题被分为两类：软时间窗车辆路径问题和硬时间窗车辆路径问题。软时间窗车辆路径问题要求配送车辆尽可能在时间窗内到达访问，否则将给予一定的惩罚。该惩罚包括两部分：(1)车辆在要求的最早到达时间之前到达，必须在任务点处等待而损失的成本；(2)车辆在要求的最迟到达时间之后到达，必须付给客户预先约定的罚金。而硬时间窗车辆路径问题则要求必须在时间窗内到达访问，否则服务被拒绝。 Koskosidis等人（1992）7指出，软时间窗模式比硬时间窗更具优势是因
8、为：第一、软时窗模式较传统硬时窗模式更为一般化，且软时窗的求解演算法较具弹性（因限制式较少）。而且若要提高准点服务频率，只需适当的提高惩罚成本即可；第二、在现实世界中，时窗限制大多属于软时窗限制。配送服务商没有在约定的时间内送达顾客端，并非一定不可服务，而是可以服务但必须付出双方约定的惩罚成本。有较高准点送达要求的顾客的惩罚成本大，不准时但是在可以忍受的时间内送达的顾客的惩罚成本相对小些；第三、软时窗模式可以有效的反应配送商在车队营运成本、规模和服务水准两者之间的关系；第四、软时窗模式可以发现硬时窗模式无法找到的可行解。特别是在小规模车队服务多数顾客以及严苛的时间限制条件状况下。在上述的情形得
9、到软时窗限制下的可行解后，可再调整时间窗让违反时间窗的情况得到改善。 车辆路径问题还有确定性(Deterministic)模式和随机性(Stochastic)模式之分8。确定性模式假设：其一、客户的数目在配送开始前是已知且固定的；其二、客户的需求量在配送开始前是已知且固定的；其三、两点之间的旅行时间仅取决于这两点之间的距离。而随机性模式不要求以上一个或多个假设。随机性模式又称为随机需求车辆路径问题。 如果考虑装卸工人的调配问题，则车辆路径问题就称为带装卸工调配的车辆路径问题。带装卸工调配的车辆路径问题描述如下9：设配送中心有n辆货车都要向b个客户装卸货物。配送中心可以安排位装卸工跟着车辆，也可
10、以安排位装卸工固定在客户处。已知在客户处需要的装卸工人数是，配送中心应该考虑如何调配装卸工，使总的装卸工人数最少。 除了以上分类，车辆路径问题还可以按任务特征分为装货问题、卸货问题及装卸混合问题；按任务性质分为对弧服务问题（如中国邮递员问题）和对点服务问题（如旅行商问题）以及混合服务问题（如校车路线安排问题）；按车辆载货状况分为满载问题和非满载问题；按车场数目分为单车场问题和多车场问题；按车辆类型数分为单车型问题和多车型问题；按车辆对车场的所属关系分为车辆开放问题（车辆可不返回车场）和车辆封闭问题（车辆必须返回车场）；按优化目标可分为单目标问题和多目标问题，等等。 针对上述不同的分类方法，车辆
11、路径问题的模型构造及求解算法有很大差别。 2.3车辆路径问题的构成要素 物流配送车辆路径问题的构成因素主要包括货物、车辆、配送中心、客户、运输网络、约束条件和目标函数等要素10。 2.3.1货物 货物是配送的对象。可将每个客户需求（或供应）的货物看成一批货物。每批货物包括品名、包装、重量、体积、要求送到（或取走）的时间和地点、能否分批配送等属性。货物的品名和包装，是选用配送车辆的类型以及决定该批货物能否与其他货物装在同一车辆内的依据。例如，一些货物因性质特殊需要使用专用车辆装运；而一些货物虽然性质特殊，但由于包装条件很好，故也能与其它货物装在同一车辆内。另外，货物的重量和体积也是进行车辆装载决
12、策的重要依据。当某个客户的需求量（供应量）的货物的重量或体积超过车辆的最大装载量或体积时，则对该客户需要采用多台车辆进行配送。 2.3.2车辆 车辆是货物的运载工具，其主要包括:车辆的类型、装载量、一次配送的最大行驶距离、配送前以及完成任务后车辆的停放位置等。 其一、车辆的类型有通用车辆和专用车辆之分，通用车辆适于运载大多数普通货物，专用车辆适于载运一些性质特殊的货物。 其二、车辆的装载量是指车辆的最大装载重量和最大装载容积，是进行车辆装载决策的依据。在某个配送系统中，车辆的装载量可以相同也可以不同。 其三、对每台车辆一次配送的行驶距离的要求可以分为以下几种情况:第一、无距离限制;第二、有距离
13、限制;第三、有距离限制，但可以不遵守。 其四、车辆在配送前可以是停放在某个停车场、配送中心或者是客户所在地。完成任务后，其停放位置一般可以分为以下几种情形:一是必须返回出发点;二是必须某个停车场或配送中心;三是可返回任意停车场;四是可停放在任何地点。 2.3.3配送中心 配送中心是从事货物配备(集货、加工、拣选、配货)和组织对客户的送货，以提高水平实现销售或供应的现代流通设施。在某个配送系统中，配送中心的个数可以是一个也可以是多个，这涉及到配送网络问题，如在某些配送网点多而且配送范围广的情形下，往往采用多级配送中心进行配送，通过一级配送中心配送到下一级配送中心再配送，在多个二级配送中心下，究竟
14、由哪个配送中心配送，这涉及到配送的优化问题。其配送示意图见图2-1: 图2-1分级配送示意图 2.3.4客户 也称为用户，包括各盆景展览馆、陈列中心、公司、家庭用户等。单个客户一次所需的盆景数量可能大于盆景配送车某车辆的最大装载量，也可能小于该车辆的最大装载量。而该系统全部客户的货物需求（或供应）总量可能超过全部车辆的总装载量。在以上情形下，当货物一次性需求（或供应）总量超过运输能力时，需要多次（多辆）分批配送；当货物一次性需求（或供应）量小于某车辆的最大装载量时，在可能的情况下，应进行货物配载。 客户的需求（或供应）盆景的时间，是指要求盆景送达（或取走）的时间，对配送时间的要求可分为以下几种
15、情况:第一、无时间限制；第二、要求在指定的时间区间（也称为时间窗）内完成运输任务；第三、有时间限制，但可以不遵守，只是不遵守时要给予一定的惩罚。 2.3.5运输网络 运输网络是由顶点（指配送中心、客户、停车场等）、无向边和有向弧组成的，边、弧的属性包括方向、权值和交通流量限制等。运输网络中边或弧的权值可以表示距离、时间或费用。边或弧的权值变化可分为以下几种情况:一是固定，即不随时间和车辆的不同而变化；二是随时间而变化；三是随车辆不同而变化；四是既随时间不同而变化，又随车辆不同而变化。 对运输网络权值间的关系可以要求其满足三角不等式，即两边之和大于第三边。也可以不加限制。运输网络见示意图2-2.
16、 图2-2运输网络示意图 对运输网络中顶点、边或弧的交通流量要求分为以下几种:其一、交通流量随时间不同而变化;其二、边、弧限制，即每条边、弧上同时行驶的车辆数有限制;其三、顶点限制，即每个顶点上同时装、卸的车辆数有限；其四、边、弧、顶点都有限制。 2.3.6约束条件 通常说来，物流配送车辆路径问题应满足的约束条件主要包括：第一，满足所有客户对货物品种、规格、数量的要求；第二，满足客户对货物发到的时间范围的要求；第三，在允许通行时间进行配送（如有时规定白天不能通行货车等）；第四，车辆在配送过程中的实际载货量不得超过车辆的最大允许装载量；第五，在配送中心现有的运力范围内。 2.3.7目标函数 对物
17、流配送车辆路径问题，可以只选用一个目标，也可以是多个目标。经常选用的目标函数主要有:第一，配送总里程最短。配送里程与配送车辆的耗油量、磨损程度以及司机疲劳程度等直接相关，它直接决定运输的成本，对配送业务的经济效益有很大影响。由于配送里程计算简便，它是确定配送路线时用得最多的指标。第二，配送车辆的吨位公里数最少。该目标将配送距离与车辆的载重量结合起来考虑，即以所有配送车辆的吨位数（最大载重吨）与其行驶距离的乘积的总和最少为目标。第三，综合费用最低。降低综合费用是实现配送业务经济效益的基本要求。在物流配送中，与取送有关的费用包括:车辆维护和行驶费用、路桥费用、车队管理费用、货物装卸费用、有关人员工
18、资费用等。第四，准时性最高。由于客户对交货时间有较严格的要求，为提高配送服务质量，有时需要将准时性最高作为确定配送路线目标。第五，运力利用最合理。该目标要求使用的较少的车辆完成配送任务，并使车辆的满载率最高，以充分利用车辆的装卸能力。第六，劳动消耗最低。即以司机人数最少、司机工资时间最短为目标。 2.4车辆路径问题的求解方法 车辆路径问题通常被构造成整数规划模型、图论或其它模型，这些模型之间存在着某种联系。但从建立模型时的出发点考虑，大多数模型都可看成是下面三种模型的变形与组合：第一，以车流为基础的模型；第二，以物流为基础的模型；第三，集覆盖模型。 求解方法上，常用的基本理论和方法有：分枝定界
19、法、割平面法、线性规划法、动态规划法、匹配理论、对偶理论、组台理论、线搜索技术、列生成技术、拉格朗日松弛技术、状态空间松弛技术、Benders分解技术、扶梯度(subgradient)优化技术、概率分析、统计分析、最差情况分析、经验分折等 常用算法基本上可分为优化算法和启发式算法两大类。优化算法求解时间长，算法效率低且不适合求解规模较大的问题，因此在实际应用中受到限制；启发式算法效率较高且能逼近最优解，为此专家们主要把精力花在构造高质量的启发式算法上。目前已提出的启发式算法相当多，大体上可分为传统启发式算法（Heuristic）和巨集启发式算法（Meta-Heuristic）两大类11。 传统
20、启发式算法具有求解速度快、求得的解较为固定的特点。已被证明会陷入局部优化解中11。巨集启发式算法则尝试以不同的方式跳出局部解，在可接受的时间内，求得近似最优解，甚至是全局最优解。所以在近年来的研究中，多用巨集启发式算法来求解车辆路径问题，或者混合使用传统启发式算法和巨集启发式算法。 2.4.1传统启发式算法 根据Bodin等人12的研究，用于求解车辆路径问题的传统启发式算法可分为： 第一，先分组后安排路线的方法（Cluster-FirstRoute-Second）：这种方法先把节点（或弧）的需求进行分组或划群，然后对每一组设计一条经济的路线。如Gillett和Miller于1974年提出的扫描
21、（sweep）算法13,14,15。方法是先以极坐标的方式表示各个客户点的区域位置，再任取一个客户点作为起点以顺时针方向，以车辆容量为限制条件（或再加入其它限制条件）对区域进行分割，使不超过车辆容量（或满足其它限制条件）的需求点组成一个区域，一个区域就是一个组。当形成一系列这样的组后，再对每一组中的各点安排线路。这种算法一般仅适用于装货（或卸货）问题，且车辆是封闭的。 第二，先安排路线后分组的方法（Route-FirstCluster-Second）：在不考虑约束条件的前提下进行路线的构建，然后再根据约束条件对路线进行切割。这种方法首先构造一条或几条很长的路线(通常不可行)，它包括了所有需求对
22、象，然后再把这些很长的路线划分成一些短而可行的路线。具体进行时，一般是先解一个经过所有点的旅行商问题，形成一条路线，然后根据一定的约束(如车辆容量等)对它进行分划。典型的有由Rosenkrantz等人16于1977年提出的最临近点法。思路是以车场为起点，寻找离车场距离成本最小且没有加入路线的节点为起始路线，重复以上步骤直至找不到可以满足车辆限制条件的节点时，回到车场重新出发，另外构建一条新的路径。 第三，节约插入算法（SavingorInsertion）：根据节约值的大小来构建路线，直至无法改善或达到停止条件为止。该算法的每一步，把当前的线路构形（很可能是不可行的）跟另外的构形（也可能是不可行
23、的）进行比较，后者或是根据某个判别函数（例如总费用）会产生最大程度的节约的构形，或是以最小代价把一个不在当前构形上的需求对象插人进来的掏形，最后得到一个较好的可行构形。 节约算法最早是由Clark和Wright于1964年提出的11。根据三角形两边之和大于第三边的性质，以一部车服务一个客户作为初始解，一部车服务一个客户然后就返回车场为其起始状况，计算路径间的合并节约值。将算出的节约值按照降幂排序并依次合并路径。若找不到满足限制条件的节点，便回到车场，重新构建新的路径，直到没有大于零的节约值为止。 节约算法是利用节约值的大小和是否满足限制条件来决定两节点是否相连的。节约值的计算如下：设0表示示车
24、场，i和j为两个任务点，定义点对i和j的节约值为 其含义为点i和点j在同一条线路上的距离成本与点i和点j各在不同线路上的距离成本相比得到的距离成本的节约值。这种算法与Sweep算法的适用范围差不多。 2.4.2巨集启发式算法 巨集启发式算法主要基于改进或交换（ImprovementorExchange）的思路，即先构建一个初始解，再用贪婪算法（Greedy）17，进行路线的优化，直至无法改进或达到停止条件为止。该算法在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止。 经典的遗传算法、模拟退火算法、禁忌
25、搜索算法、蚁群算法都属于这一类方法。 遗传算法（GeneticAlgorithm,GA)最早由Holland18于1975年提出，是根据达尔文进化论中“物竞天择，适者生存”的自然进化法则发展而来。其基本精神是进化与选择，利用复制（reproduction）、交配（crossover）、突变（mutation）三个基本运算元重复运作，以达到淘汰较差解的目的。其做法是：先由数个可行解个体产生一母体集合，其中的元素即为基因（gene）。再通过计算第一代母体中个体目标值的方式，选出较优秀的个体，以交配、突变等方式产生下一代。最后依据停止条件结束演算。遗传算法具有多点平行搜寻可行解的特性，已逐渐被运用于
26、高度空间搜寻的组合最佳化问题上。 (2)模拟退火算法（SimulatedAnnealing，SA），其最初的思想由Metropolis在1953年提出，Kirkpatrick等人19在1983年成功地将其应用在组合最优化问题中。模拟退火算法来源于固体退火原理：将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，由初始解i和控制参数t的初值开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，
27、逐步衰减t值，并设定终止条件，即得到解组合优化问题的模拟退火算法。算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。 模拟退火算法具有能往目标值较差处移动的机会，这种随机过程产生的机会使得该算法有能力避免陷入局部优化，而得到全局最优解。 禁忌搜索法（TabuSearch,TS），是由Glover20于1977年提出的，Willard21于1989年将其用于车辆路径问题上。其求解的过程是先求得一初始解，然后在邻域中搜索较佳解或是移动到较差的区域搜索该区域最佳解，并且记录曾经搜寻的路径，作为下次搜索的依据，以避免陷入局部最优解中。禁忌搜索算法主要包含移步（M
28、ove）、候选列表（CandidateList）、禁忌列表（TabuList）、渴望准则（AspirationLevel）及搜寻停止准则（StoppingCriterion）等五种要素。 蚁群算法（AntSystem,AS）最早由MacroDorigo22于1992年提出，其灵感来自蚂蚁觅食时可以在食物和巢穴间找到最短路径的能力。蚂蚁觅食时会在走过的路线上留下一种称为费洛蒙（pheromone）的化学物质，费洛蒙的浓度与遗留时间成反比，与走过该路线的蚂蚁的数量成正比。当一只蚂蚁面临路线的选择时，它会优先选取费洛蒙浓度高的路线。就是说，费洛蒙残留的浓度越高，则吸引蚂蚁前来的能力越强，越多的蚂蚁经
29、过某条路线时，该路线的费洛蒙浓度就越高，从而吸引更多的蚂蚁前来。通过这种方式，蚂蚁就可找出食物与巢穴间的最短路径。 2.4.3混合启发式算法 一是、基于数学规划的算法（Mathematical-ProgrammingBased）6是把问题直接描述成一个数学规划问题，根据其模型的特殊构形，应用一定的技术（如分解）进行分划，进而求解已被广泛研究过的子问题。 典型的有Fisher和Jaikumar提出的算法。该算法把车辆路线问题构造为一个广义分派问题，并提出下述启发式算法：首先把问题描述为一个数学规划问题，再将问题分解成一个旅行商问题和一个分派问题。对每一辆车将顾客进行分派，这通过解一般分派问题来得
30、到。每辆车为它的顾客服务，以一个近似等于旅行商线路的费用为目标，分派一旦做出，通过应用一些旅行商问题的启发式算法或优化算法来得到每辆车的行车路线。 二是、交互式优化法6。即把人的因素结合到问题的求解过程中，其思想是；有经验的决策者应具有确定和修改参数的能力，并且根据知识经验，把主观的估计加到优化模型中去。这通常会增加模型最终实现并被采用的可能性。如Cuilew，Jarvis和Ratfiff提出的两段法：第一阶段：由有经验的调度员或是根据自动生成规则选定一些“组”点，目标函数定义为线性近似（），其中定义为需求点i和“组点”v之间的欧氏距离，根据确定的“组”点坐标求解得出的分派问题，由求出的结果再
31、求解得出的定点问题，即重新确定每个“组”点的位置，以使分派给它的各需求点离它的总距离最小。交替求解分派问题和定点问题，直到目标没有进一步的改进。第二阶段：用列生成技术生成新解，直到不能进一步改进为止。 这几种启发式算法常不是绝对划分的，有的方法同属于好几类。 4.1.1算法描述 模拟退火算法是一种用于求解大规模优化问题的随机搜索算法，它以优化问题求解过程与物理系统退火过程之间的相似性为基础；优化的目标函数相当于金属的内能；优化问题的自变量组合状态空间相当于金属的内能状态空间；问题的求解过程就是找一个组合状态，使目标函数值最小。大量的研究证明，模拟退火算法可在多项式时间内求解全局优化问题的目标。
32、 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。 模拟退火算法需要一个构建好的初始解作为算法的输入参数，在进入迭代后，每一次迭代都需要
33、构建新解。本文用最临近点法来构建初始解，用区域搜索法来求得每一次迭代的新解28。分别论述如下： 1）最临近点法构建初始解：从盆景养护基地出发，寻找距离它最近的客户，生成一条线路；再从该客户出发，寻找他的最临近客户，加入该线路。重复该过程直到满足车辆的最大装载容量限制（同时考虑时间窗限制和车辆的最大行驶距离限制），即完成一条线路的构建。返回盆景养护基地，重复以上步骤继续构建线路，直到所有的客户都被加入线路中，则初始解的构建就完成了。 2）区域搜索法产生新解：区域搜索法是通过不断改善路经来求得更佳的解，并以贪婪法则决定是否接受新的改善解。改善的方法是在同一条线路中随机交换节点，或在相邻线路中随机交
34、换节点。有2-opt交换法、3-opt交换法以及Cross-opt交换法，本文采用2-opt交换法。 4.1.2算法步骤 模拟退火算法的主要步骤如下29： 1）初始化：初始温度(充分大)，初始解状态(是算法迭代的起点)，每个值的迭代次数； 2）对重复以下第(3)至第(6)步； 3）产生新解； 4）计算增量，其中为评价函数； 5）若则接受作为新的当前解，否则以概率接受作为新的当前解； 6）如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。否则执行下面第(7)步； 7）逐渐衰减（趋于零），然后转第(2)步。 4.1.3重点抽样与Metropli
35、s准则 模拟退火的主要思想是：在搜索区间（二维平面中）随机游走（即随机选择点），再以Metropolis准则抽样，使随机游走逐渐收敛于局部最优解。 Metropolis抽样准则是一种有效的重点抽样法。其思想为：系统从一种状态变到另一种状态时，相应的能量从变化到，如果，系统接收此状态，否则，以的概率接收或丢弃此状态。经过一定次数的迭代，系统会逐渐趋于稳定状态。 重点抽样时，新状态如果向下则接受（局部最优），若向上（全局搜索），以一定概率接受。模拟退火方法从某个初始解出发，经过大量解的变换后，可以求得给定控制参数值时组合优化问题的相对最优解。然后减小控制参数的值，重复执行Metropolis算法，
36、就可以在控制参数T趋于零时，最终求得组合优化问题的整体最优解。控制参数的值必须缓慢衰减。 温度是Metropolis算法的重要控制参数。开始时温度高(值大)，算法可能接受较差的恶化解；随着值的减小，只能接受较好的恶化解；最后当趋于0时，就不再接受任何恶化解了。 当值足够大时（即无限高温），系统立即均匀分布，接受所有提出的变换。衰减得越小，到达终点的时间就越长，但可使马可夫链缩短，使到达准平衡分布的时间缩短。 4.1.4算法重点和难点 模拟退火算法的重点是新解的产生和接受。主要有以下四个步骤： 其一、由一个产生函数从当前解产生下一个位于解空间的新解。为便于后续的计算和接受，减少算法耗时，通常选择
37、由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等。产生新解的变换方法决定了当前解的邻域结构，因而对冷却进度表的选取有一定的影响。 其二、计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。 其三、判断新解是否被接受，判断的依据是一个接受准则。最常用的接受准则是Metropo1is准则：若则接受作为新的当前解，否则以概率接受作为新的当前解。 其四、当新解被确定接受时，用新解代替当前解，同时更新目标函数值。此时，当前解实现了一次迭代。可在此基础上开始下一轮
38、试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。 模拟退火算法的难点是参数的控制，主要有以下三点问题： 一是、温度的初始值设置问题。温度的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一。初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。 二是、退火速度问题。模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索（退火）是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。
39、 三是、温度管理问题。温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：，式中为正的略小于1.00的常数，为降温的次数。 4.1.5算法参数选择 本文研究中所用模拟退火算法的参数选择如下： 第一、初始温度的选取：本文参照ymhui30在“模拟退火算法求解TSP问题”中建议的方法来确定初始温度。即，初始温度等于客户距离矩阵中的最大值和最小非零值之差乘以客户数目，再乘上一个可在实验中调整的初始温度系数。由于Metropolis的接收概率等于，足够大的初始值可保证Metropolis抽样的接收率在初始迭代阶段接近1。然而，
40、初始温度也不能一味地大，否则很难在可接受的计算时间内求得结果； 第二、衰减函数的选取：衰减函数用于控制温度的退火速度，本文采用模拟退火算法常用的衰减函数：，其中应是一个非常接近于1的常数，本文取0.95作为初始试验值，并用A公司实际配送数据进行验证，以求得适合A公司不同配送规模的值； 第三、退火速度的选取：退火速度指同一温度下的搜索（退火）次数，亦即马可夫链长度28，原则是在温度参数的衰减函数已选定的前提下，退火速度的取值应使得算法在的每一取值上都能恢复准平衡。本文参照ymhui在“模拟退火算法求解TSP问题”中建议的方法来确定该值，即取客户数目的3次幂作为该长度的初始试验值，然后通过试验最终确定A公司不同配送规模下的适合值； 第四、终止条件：有很多种终止条件的选择，各种不同的条件对算法的性能和解的质量有很大影响。本文采用常用的零度法终止条件，即当温度衰减到某个接近零的值时，终止算法。该值在本文中取0.01，终止条件为。 专心-专注-专业