基本蚁群算法

摘 要许多实际工程问题可以抽象为相应的组合优化问题，TSP 问题是作为所有组合优化问题的范例而存在的，它已成为并将继续成为测试组合优化新算法的标准问题。从理论上讲，使用穷举法可以求解出 TSP 问题的最优解；但是对现有的计算机来说，让它在如此庞大的搜索空间中寻求最优解，几乎是不可能的。所以，各种求 TSP 问题近似解的算法应运而生了，本文所描述的蚁群算法（AC）也在其中。目前已出现了很多的启发式算法，而蚁群算法作为一种新型的启发式算法，已成功地应用于求解 TSP 问题。蚂蚁通过分泌信息素来加强较好路径上信息素的浓度，同时按照路径上的信息素浓度来选择下一步的路径：好的路径将会被越来越多的蚂蚁选择，因此更多的信息素将会覆盖较好的路径；最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反馈原理正是整个算法的关键所在。本文介绍了基本蚁群算法概念、原理及蚁群算法的特点，再根据蚁群算法的缺点做出了优化。采用轮盘赌选择代替了基本框架中通过启发式函数和信息素选择路径，改进蚁群算法的信息素传递参数，让整个算法更快速的找到最优解。其次，采用最大最小优化系统限制最大值和最小值，让整个系统更快收敛，得到最优解。关键字：蚁群算法，TSP 问题，启发式函数，轮盘算法，最大最小优化ABSTRACTMany practical engineering problems can be abstracted as corresponding combinatorial optimization problem, TSP problem is an example of all as a combinatorial optimization problem, it has become and will continue to be a new combinatorial optimization algorithm of standard test problems. In theory, using the exhaustion method can solve the TSP problem optimal solution; But for the existing computer, let it in such a large search space to seek the optimal solution, it is almost impossible. So, all kinds of algorithm arises at the historic moment, the approximate solution of the TSP problem described in this paper, ant colony algorithm (AC) is among them. Has appeared a lot of heuristic algorithm and ant colony algorithm as a kind of new heuristic algorithm, has been successfully used in solving TSP problems. Ant secretion by pheromones to strengthen the good path pheromone concentration, at the same time according to the path to choose the next path pheromone concentration: good paths will be more and more ants to choose, so that more information will cover good path; Eventually all the ants on a good path. This positive feedback based on the pheromone of ant principle is the key to the whole algorithm. This paper introduces the basic concept of ant colony algorithm, principle and characteristics of ant colony algorithm, according to the disadvantages of ant colony algorithm optimization. Adopting roulette selection instead of the basic framework by heuristic function and choose path pheromone, pheromone passing parameters of improved ant colony algorithm, make the whole algorithm find the optimal solution more quickly. Second, limiting the maximum and the minimum maximum minimum optimization system, make the whole system faster convergence and the optimal solution is obtained. Keywords: ant colony algorithm, the TSP problem, a heuristic function, roulette algorithm, maximum_minimum optimization目录摘 要 .2ABSTRACT .3第 1 章 绪论 .61.1 研究目的和意义 .61.2 国内外研究现状 .71.2.1 国外研究现状 .71.2.2 国内研究现状 .81.3 本文研究内容 .9（1） 基本蚁群算法 .9（2） 蚁群算法的优化 .9（3） 蚁群算法在 TSP 问题中的应用 .91.4 开发环境与工具 .91.5 论文的组织结构 .10第 2 章 蚁群算法 .102.1 蚁群算法简介 .102.2 蚁群算法的原理 .112.2.1 蚂蚁觅食规则 .122.2.2 蚂蚁移动规则 .122.2.3 蚂蚁避障规则 .122.2.4 蚂蚁撒信息素规则 .122.3 蚁群算法的特点及优缺点 .132.3.1 蚁群算法的特点 .132.3.2 蚁群算法的优点 .142.3.3 蚁群算法的缺点 .142.5 蚁群算法的核心函数 .15（1）初始化 .15（2）选择下一个城市，返回城市编号 .15（3）更新环境信息素 .17（4）检查终止条件 .18（5）输出最优值 .182.6 蚁群算法的参数分析 .192.6.1 蚂蚁数量 N_ANT_COUNT .192.6.2 启发因子 .192.6.3 期望启发因子 .202.6.4 信息素挥发度 .202.6.5 总信息量（DBQ） .21第 3 章 改进的蚁群算法 .213.1 轮盘赌选择 .223.1.1 轮盘赌选择基本思想 .223.1.2 轮盘赌选择工作过程 .223.2 MAX_MIN ACO .243.2.1 MAX_MIN 算法的框架结构 .243.2.2 MAX_MIN 算法流程图 .26第 4 章 蚁群算法在车辆路径问题中的应用 .284.1 车辆路径问题简介 .284.1.1 车辆路径问题定义 .284.1.2 车辆路径问题分类 .294.2 车辆路径问题的求解算法 .294.2.1 精确算法 .294.2.2 启发式算法 .304.3 蚁群算法解决车辆路径问题 .314.4 数值实验结果及分析 .334.4.1 轮盘赌选择优化前后数据对比 .334.4.2 MAX_MIN 算法改进前后数据对比 .34第 5 章 总结与展望 .36参考文献 .36第 1 章 绪论TSP 问题是一种特殊的车辆路径问题，是作为所有组合优化问题的范例而存在的，它已成为并将继续成为测试组合优化新算法的标准问题。传统解法对小搜索空间的 TSP 问题适用，而且有的算法获得精确解的性质也正是人们所期望的。于是，许多求 TSP 问题近似解的新算法应运而生，启发式算法便是其中之一。而蚁群算法（AC）是由意大利学者 Macro Dorigo 等人在 20 世纪 90 年代提出来的1，它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等之后的一种新型的启发式算法，已成功地应用于求解 TSP 问题。蚁群算法在解决 TSP 问题时具有许多优良性质，但也存在着两个主要的缺陷：收敛速度较慢，并且容易出现停滞。为此，不少研究者提出了一些优化策略及改进，如：蚁群系统算法 ACS（也称蚁群优化算法 ACO） 、最大最小蚁群系统算法 MMAS 等；这些改进在一定程度上提高了算法的有效性，但效果并不明显。如何进一步地对算法进行优化，即优化策略的研究，也正是当前蚁群算法研究的最大的热点。另外，人们也注意到：改进后的蚁群算法在解决大型的 TSP 问题时，关键参数的设置和信息素的更新将花费很长的时间。而由于蚁群算法中蚂蚁的个体行为具有内在的并行性，因此可以考虑将算法进行分布式并行处理来缩短算法的运行时间。如何进行并行处理，亦即并行策略的研究，是目前蚁群算法研究的又一个热点。1.1 研究目的和意义物流是供应链中最重要的组成部分，是商品从生产者经过各流通环节最终到达消费者手中的过程。物流业这是专门从事物流活动的行业，从企业销售成本和商品价格组成角度考察，物流业蕴藏着巨大的商机。物流业被誉为经济发展动脉的“加速器”和商业结果演变的“润滑剂” ，现代企业的“第三利润源泉”。通过提高物流管理水平和效率，降低物流成本，可以为企业及社会带来可观的经济效益，改善国民经济运行效率，提高国际竞争力。因此，国家和各地政府纷纷定制了各种有利于物流发展的政策和计划。在国家“十一五规划”中讲“大力发展现代物流”作为今后重点发展的领域，明确提出“十一五”结束即 2010 年，全社会物流成本要比 2004 年的计策上下降 23 个百分点。合理使用优化运输路线，降低企业物流成本，是物流管理的很重要内容。针对物流管理中对运输车辆路径优化调配的要求，1959 年由 Dantzig 和 Ramser首先提出了车辆路径问题的数学模型。车辆路径问题已经是近几十年来运筹学、应用数学、网络分析、计算机应用及交通运输等学科研究一个热点问题，并且在通讯、身长、国防、生物计算机应用等领域得到了广泛的应用。1.2 国内外研究现状车辆路径问题的研究有着现实的经济意义和学术意义。自从 VRP 被 Dantzig和 Ramser 于 1959 年提出之后，很快就引起了运筹学、应用数学、物流科学、计算机科学等各个学科专家学者与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿问题和研究热点。许多学者对该问题进行了大量的理论研究及实验分析，目前己经产生出多种成熟的算法，取得了令人瞩目的成果，为后人的继续研究提供了极高的参考价值。1.2.1 国外研究现状1962 年，Balinski 等人首先提出 VRP 的集分割，直接考虑可行解集合，在此基础上进行优化，建立了最简单的 VRP 模型。1971 年，Eilon 提出将动态规划法用于固定车辆数的 VRP，通过递归方法求解。1974 年，Wren Gillett 等人提出扫描算法，将该算法应用于车辆调度问题，并和当时其它算法进行了比较，证明该算法所求得的解较优于其它方法。1981 年，Christofides 等人提出了 k 度中心树和相关算法，对固定车辆数m 的 m-TSP 进行了进行 k 度中心树松弛。后来，M.L.Fishe 对这种方法做了进一步改进，可求解有 134 个客户的 VRP。1991 年，Gendreau 等人将禁忌搜索方法应用于 VRP，它是比较好的启发式算法，可以成功地应用于许多经典的 VRP。1996 年，J.Lawrence 将遗传算法用于 VRP 的研究，有效的求解出带时间窗限制的 VRP。1.2.2 国内研究现状在我国，有关车辆路径问题的研究是在 20 世纪 90 年代以后才逐渐兴起的，比国外相对落后。随着顾客需求的变化，运输车辆的调度显得日益重要。近年来，我国理论界逐渐开始关注车辆路径问题的研究，并已取得初步成果。蚁群算法、启发式算法以及一些混合算法被学者们广泛的利用，代表了较近的研究思想。启发式算法作为一种逐次逼近的算法，虽然不一定得到最优解，但是可以高效率地得到具有较高精度的解，而且也易于考虑各种实际问题，因此，现已成为解决 VRP 问题的重要方法。与传统的启发式算法相比，近年来所采用的一些新的启发式算法，通过对启发式规则和搜索方式的改进，在求解多节点、多约束的 VRP 问题上可以获得较快的收敛速度和较高质量的全局解。浙江大学蔡延光等人运用模拟退火算法和遗传算法求解多重车辆调度问题，并将其集成为智能算法库，作为设计智能运输调度系统的依据。鞍山钢铁学院李大卫和东北大学姜大力等分别针对有时间窗和无时间窗约束下的车辆路径问题用基因编码遗传算法求解，结果在较快速度下得到了近优解。崔雪丽、马良和范炳全等人基于近年来出现的新型智能优化思想：人工蚂蚁系统给出了一种可快速求解VRP 的蚂蚁搜索算法。通过定义基本的人工蚂蚁状态转移概，并结合局部搜索策略，用迭代次数控制算法的运行时间，从而使该方法具有使用意义和可操作性。经一系列数据测试和验证，与若干已有的经典算法相比较，获得了较好的结果。杨善林人等提出一种基于蚁群优化的混合算法来解决 VRP。首先提出一种 ACO 算子，然后加入局部搜索机制并使用基于问题的特定启发信息节约量来改进算法。尹小峰等针对了蚁群算法存在的过早收敛问题引入节省量以及车辆载重利用率两种启发式信息对蚁群算法加以改进，并加入 2.opt 方法对问题求解进行局部优化，计算机仿真结果表明，这种混合蚁群算法对求解车辆路径问题有较好的改进效果。1.3 本文研究内容本文的研究内容可以概括为三部分：蚁群算法的基础性理论、蚁群算法的优化以及蚁群算法在 TSP 问题中的应用：（1） 基本蚁群算法了解基本蚁群算法的概念、原理以及代码如何实现。（2） 蚁群算法的优化根据蚁群算法的基本原理做出优化，避免蚁群算法的缺点，在迭代次数尽量少，迭代结果尽量趋近最优解的情况下做出优化。本文主要讲解轮盘算法和max_min 算法在蚁群算法中的优化。（3） 蚁群算法在 TSP 问题中的应用利用蚁群算法的特点以及蚁群算法的优化应用到 TSP 问题中。1.4 开发环境与工具计算机：HP ProBook 4416S系统：Microft Windows XPProfessinal版本 2002Service Pack3内存：2G开发语言：C+运行环境：Microsoft Visual C+ 6.01.5 论文的组织结构第一章 绪论 主要是讲解本课题研究内容、目的和意义，国内外对蚁群算法的研究现状以及本系统开发环境的介绍；第二章 蚁群算法 主要是介绍什么是蚁群算法，蚁群算法的原理和思想以及蚁群算法的优缺点；第三章 改进的蚁群算法 主要是讲解在基本蚁群算法的基础上对蚁群算法做出优化（本文采用了轮盘选择和 MAX-MIN 两种优化方式）第四章 蚁群算法在车辆路径问题中的应用第五章 总结与展望第 2 章 蚁群算法2.1 蚁群算法简介蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由 Marco Dorigo 于 1992 年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对 PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。蚁群算法（Ant Clony Optimization， ACO）是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。蚁群算法是一种仿生学算法，是由自然界中蚂蚁觅食的行为而启发的。在自然界中，蚂蚁觅食过程中，蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。图（1）显示了这样一个觅食的过程。图（1）蚂蚁觅食在图 1（a）中，有一群蚂蚁，假如 A 是蚁巢，E 是食物源（反之亦然） 。这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶。假如在 A 和 E 之间突然出现了一个障 碍物（图 1（b） ） ，那么，在 B 点（或 D 点）的蚂蚁将要做出决策，到底是向左行驶还是向右行驶？由于一开始路上没有前面蚂蚁留下的信息素 （pheromone） ，蚂蚁朝着两个方向行进的概率是相等的。但是当有蚂蚁走过时，它将会在它行进的路上释放出信息素，并且这种信息素会议一定的速率散 发掉。信息素是蚂蚁之间交流的工具之一。它后面的蚂蚁通过路上信息素的浓度，做出决策，往左还是往右。很明显，沿着短边的的路径上信息素将会越来越浓（图 1（c） ） ，从而吸引了越来越多的蚂蚁沿着这条路径行驶。2.2 蚁群算法的原理设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必 须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路 径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！ 太复杂了，恐怕没人能够完成这样繁琐冗余的程序。然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过 100 多行！为什么这么简单的程序会让蚂 蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根 据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？2.2.1 蚂蚁觅食规则在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地 方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。2.2.2 蚂蚁移动规则每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住刚才走过了哪些点，如果发现要走的下一点已经在之前走过了，它就会尽量避开。2.2.3 蚂蚁避障规则如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。2.2.4 蚂蚁撒信息素规则每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。2.3 蚁群算法的特点及优缺点2.3.1 蚁群算法的特点（1）蚁群算法是一种自组织的算法在系统论中，自组织和它组织是组织的两个基本分类，其区别在于组织力或组织指令是来自于系统的内部还是来自于系统的外部，来自于系统内部的是自组织，来自于系统外部的是他组织。如果系统在获得空间的、时间的或者功能结构的过程中，没有外界的特定干预，我们便说系统是自组织的。在抽象意义上讲，自组织就是在没有外界作用下使得系统熵增加的过程(即是系统从无序到有序的变化过程)。蚁群算法充分体现了这个过程，以蚂蚁群体优化为例子说明。当算法开始的初期，单个的人工蚂蚁无序的寻找解，算法经过一段时间的演化，人工蚂蚁间通过信息激素的作 用，自发的越来越趋向于寻找到接近最优解的一些解，这就是一个无序到有序的过程。（2）蚁群算法是一种本质上并行的算法每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多 agent 系统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。（3）蚁群算法是一种正反馈的算法从真实蚂蚁的觅食过程中我们不难看出，蚂蚁能够最终找到最短路径，直接依赖于最短 路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程。对蚁群算法来说，初始时刻在环境中存在完全相同的信息激素，给予系统一个微小扰动，使得各 个边上的轨迹浓度不相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素，而更多的信息激素又吸引了更多的蚂 蚁，这个正反馈的过程使得初始的不同得到不断的扩大，同时又引导整个系统向最优解的方向进化。因此，正反馈是蚂蚁算法的重要特征，它使得算法演化过程得以进行。（4）蚁群算法具有较强的鲁棒性相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖子初始路线的选择，而且在搜索过程中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其它组合优化问题的求解。2.3.2 蚁群算法的优点蚁群算法的成果运用激起了人们的极大兴趣，并吸引了一批研究人员从事蚁群算法的研究。研究表明，蚁群算法是一种有效的随机搜素算法，具有如下优点：（1）较强的鲁棒性：无中心控制，不会由于某一个或者某几个个体的故障而影响整个问题的求解；（2）本质并行性：蚁群在问题空间的多点不同时开始进行独立的解搜素，增强了算法的全局搜素能力；（3）正反馈性：蚁群算法能够最终找到最短路径，直接依赖于最短路径上的信息素的堆积，而信息素的堆积就是一个正反馈的过程；（4）易于与其他方法结合：蚁群算法很容易与多种启发式算法结合，以改善算法的性能。（5）自组织性：算法初期，单个的人工蚂蚁无序地寻找解，经过一段时间的烟花，蚂蚁间通过信息素的作用，自发地越来越趋向于寻找到接近最优解的一些解，是个从无序到有序的过程；2.3.3 蚁群算法的缺点虽然蚁群算法有许多优点，但同时也存在一些缺陷，如：（1）与其他方法相比，该算法一般需要较长的搜索时间，计算量较大，蚁群算法的复杂度可以反映这一点；（2）该方法容易出现停滞现象（stagnation behaviour） ，即搜索进行到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。2.5 蚁群算法的核心函数（1）初始化将所有城市设置为没有去过，清空蚂蚁走过的路径编号（置 0），蚂蚁走过长度设置 0，并随机选取一个出发点，以及标识改点走过。void CAnt:Init()for (int i=0;i 0.0) /总的信息素值大于 0dbTemp=rnd(0.0,dbTotal); /取一个随机数for (int i=0;i= ,，则设置 = ； 如果 2 时，则由以下公式来计算：=(1-)(-1)式中 =n/2， =0.5 （3）信息素初始值设为 3.2.2 MAX_MIN 算法流程图MAX_MIN 改进算法与基本的蚁群算法的其他地方一致，仅仅是更新信息素的策略不同，以下是 MAX_MIN 更新信息素的函数流程图：开始 是否是否寻找当前迭代路径最短的蚂蚁根据公式计算公式，计算 MAX 值和 MIN 的值根据公式计算相邻两城市的路径信息素是否超过 MAX信息素是否小于 MIN依次将任意两城市的信息素加上本次新增的信息素将信息素上限设为MAX结束将信息素下线设为MIN第 4 章 蚁群算法在车辆路径问题中的应用4.1 车辆路径问题简介4.1.1 车辆路径问题定义车辆路径问题（VRP）是 Dantzig 和 Ramser 于 1959 年提出的，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。车辆路线问题自 1959 年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。车辆路线问题可以描述如下（如图）： VRP 示意图设有一场站（depot） ，共有 M 辆货车，车辆容量为 Q，有 N 位顾客（customer） ，每位顾客有其需求量 D。车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。车辆路线的实际问题包括场站配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。4.1.2 车辆路径问题分类根据研究的重点不同，VRP 存在多种分类方式：（a）按一直信息的特征，可分为确定性 VRP 和不确定性 VRP，其中不确定性VRP 可进一步分为随机车辆路径问题（SVRP）和模糊车辆路径（PVRP） ；（b）按约束条件，可以分为带有容量限制的车辆路径问题（CVRP） ，带有时间距离约束的车辆路径问题（DVRP）以及带有时间窗的车辆路径问题（VRPTW） ；（c）按需求是否可以分割，可以分为可分割的车辆路径问题和不可分割的车辆路径问题；（d）按每个顾客需求量是否超过车的容量来分，可以分为满载车辆路径和非满载车辆路径问题；（e）按配送中心的多少来分可以分为但车场车辆路径问题（SVRP） 。即一般车辆路径问题（VRP） ，以及多车场车辆路径问题（MVRP） ，其中 MVRP 又可以根据是否每辆车都有固定的重点车场分为重点车场固定的车辆路径问题和重点车场不固定的开放式车辆路径问题（OVRP） ；按优化目标分，又可以分为单目标问题和多目标问题；按路由过程中相关信息是否改变，又可以分为动态 VRP 和静态VRP。4.2 车辆路径问题的求解算法由于情况不同，VRP 数学模型够早及求解算法也有较大的差别。目前有关VRP 模型的研究已经取得了较大的成果。综合过去的相关研究，VRP 模型基本可以分为图模型、数学模型和仿真模型。VRP 的求解算法非常丰富，基本可以分为紧缺算法和 iq 法师算法两大类。求解 VRP 的启发式算法有不同的分类方法。4.2.1 精确算法精确算法指可求出最优解的算法。到目前为止，已提出的精确算法种类较多，有分支定界法、割平面法、整数规划算法和动态规划算法等。另外，还有的认为精确算法指股东认购配股，可认购数量不足 1 股的部分按照精确算法原则处理。即先按照配售比例和每个账户股数计算出可认购数量 的整数部分；对于计算出不足 1 股的部分（尾数保留三位小数） ，将所有账户按照尾数从大到小的顺序进位（尾数相同则随机排序） ，直至每个账户获得的可配股数 量加总与可配售总量一致。另外关于精确算法原则取整，其实举个例子就明白了： 假设有共有 100 手债券发行，四个人认购 ：第 1 人认购 25.8 手，第 2 人认购 25.6 手，第 3 人认购 25.4 手，第 4 人认购 25.2 手 ，结果是每人 25 手。 再假设有共有 101 手债券发行，四个人认购 ：第 1 人认购 25.8 手，第 2 人认购 25.6 手，第 3 人认购 25.4 手，第 4 人认购 25.2 手，结果是第 1 人 26 手，其他人 25 手。 再假设有共有 103 手债券发行，四个人认购 ：第 1 人认购 25.8 手，第 2 人认购 25.6 手，第 3 人，认购 25.4 手 第 4 人认购 25.2 手 ，结果是第 13 人 26 手，第 4 人 25 手。 从这里可以看出，分配原则是先分配整数，如果有剩余按零头的大小分配。实际情况大于 0.5 手可能能分配到 1 手，但也可能分不到。4.2.2 启发式算法由于 VRP 是 NP-hard 问题，难以用精确算发求解，启发式算法是求解车辆运输问题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。车辆运输问题的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工智能方法建立的启发式方法。 简单启发式方法包括节省法或插入法、 路线内间节点交换法、贪婪法和局部搜索法等方法。节省法或插入法（savings or insertion）是在求解过程中使用节省成本最大的可行方式构造路线，直到无法节省为止。交换法则是依赖其他方法产生一个起始路线，然后以迭代的方式 利用交换改善法减少路线距离，直到不能改善为止。1960 年，Clarke 和 Wright6首先提出一种启发式节省法（savings methods）来建立车队配送路线 。简单启发式方法简单易懂、求解速度快，但只适合求解小型、简单的 VRP 问题。 两阶段方法包括先分组后定路线（clusterfirst-route second）和先定路线后分组（routefirst-cluster second）两种启发式策略。前者是先将所有需求点大略分为几个组，然后再对各个组分别进行路线排序；后者则是先将所有的需求点建构成一条路线，再根据 车辆的容量将这一路线分割成许多适合的单独路线。 1990 年以来，人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得到充分应用，很多学者也将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法。禁忌搜索法（TS）基本上是属于一种人工智能型（AI）的局部搜寻方法，Willard 首先将此算法用来求解 VRP ，随后亦有许多位学者也发表了求解 VRP 的 TS 算法。 西南交通大学的袁庆达7等设计了考虑时间窗口和不同车辆类型的禁忌算法，这种算法主要采用 GENIUS方法产生初始解，然后禁忌算法对初始解优化。模拟退火方法具有收敛速度快，全局搜索的特点，