基于多目标规划的车辆路径问题及其算法优化.docx

基于多目标规划的车辆路径问题及其算法优化摘要：针对带时间窗的车辆路径问题，通过引入模糊层次分析法，首先建立了考虑多目标的全面性的数学模型，然后运用了基于改进型的模拟退火算法，采取实时优化的求解策略，最后通过仿真实验进行计算。由计算结果可以得出本文设计的改进型模拟退火算法运算速度快、计算效率高等特点。关键词：车辆路径问题；多目标规划；模拟退火算法0.引言车辆路径问题(简称VRP)是由Dantzig和Ramser于1959年提出来的，一般指的是对一系列发货点和收货点,调用的车辆,组织适当的行车路线,使车辆有序地访问它们,在满足特定的约束条件下(如:货物的需求量与发货量,交发货时间,车辆可载量限制,行驶里程限制,行驶时间限制等),力争实现一定的目标(如车辆空驶里程最短、运输总费用最低、车辆按一定时间到达,使用的车辆数最小等)，因此车辆路径问题是值得研究的。车辆路径问题是一个NP难题，对于规模稍大的问题，精确算法几乎不可行，因此采用启发式算法来求解。在匹配算法的选择上，因为禁忌搜索算法其受禁忌表（tabu）的长短影响很大直接影响到算法的执行效率【1】，而遗传算法在进化后期的搜索效率低，很容易产生早熟收敛【2】。结合本文中主要是多目标的车辆路径问题的问题，所以，我们选择计算过程简单，鲁棒性强的模拟退火算法。作为一种有效的非线性组合优化算法，模拟退火算法的基本原理来自于固体加热至一定的温度后会由固体结构瓦解变为液体结构，再对其降温过程加以控制，使得分子在变回固体结构时，能重新排列成所预期的稳定状态。模拟退火算法已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法【3】，在实际应用中也被证明是有效的，但是前提是有足够多的模型扰动及迭代次数，并且要配以严密的退火计划。本文对传统的模拟退火算法进行了优化，优化了新解生成函数，加入了用于记录中间最优值的记忆因子和防止陷入局部最优的单调升温过程，这样就能和有效的解决收敛速度慢，执行时间长的问题和因为降温过程过快得不到全局最优解的问题。 对于车辆路径问题的研究，文献【4】提出了一种带时间窗口的车辆路线问题（VRPTW），在Lucio Bianco等人于 1992年提出了带时间窗口和在前约束的旅行售货员问题的基础上构造了一种基于列生成的分枝定界方法来解决此类问题。文献【5】中给出了带时间窗的车辆路径问题，并且求解该问题运用了改进的模拟退火算法，其中主要改进的是邻域操作方法，运用两交换法（2-opt）实施邻域操作。文献【6】同样是研究带时间窗的车辆路径问题，但是它采用的是量子蚁群算法，将量子计算与蚁群算法相结合，解决了蚁群算法容易陷入局部最优等问题。文献【7】研究了跨区域的联合配送的车辆路径问题，对多配送中心以及多车型等实际存在问题进行了分析，并运用云模型和改进的遗传算法对模型进行了实验分析和验证。文献【8】研究了带时间窗的多目标规划的车辆路径问题，它最主要的是在成本最小的基础上增加了准时性和车辆最少这些目标，最后用遗传算法进行求解。然而上述文献主要针对的是单一目标的车辆路径问题进行分析研究，对多目标规划的车辆路径问题研究较少，考虑到多目标的文献对于目标选用等核心问题没有进行详细分析，使得研究结论的实际应用价值不是很大。基于上述分析，本文使用的多目标规划问题，进一步加深对VRP问题的阐述，使用了模糊层次分析法（FAHP）【9】解决对于多目标权重的分配，进一步完善解决VRP问题的解决思路，然后采用了基于改进的模拟退火算法（带记忆和单调升温）对VRP问题进行求解。该改进型的算法具有运算速度快，迭代次数少等特点。最后在仿真实验中证明了该改进型的模拟退火算法具有以上特点。1.车辆路径问题的数学模型1.1模型的目标分析合理运输可以是用最少的费用,走最短的里程,在最少的时间把货物运至用户手中。合理运输中的路径问题实质上往往是多目标的,也就是说,从起点到终点的路线要受到一个以上的目标影响。目标可以是运输费用最少、运行时间最短或需求满足情况最好等。在一般情况下,多目标配送路线选择的各个目标之间常常会发生冲突,例如，运输时间快了,运输费用不一定最省；或运输费用省了,而运输时间却不一定最短。这样就有可能没有任何一条运输路线是最佳的,运输费用最省的路线可能不是运输时间最短的路线。这时,就需要对各种目标进行综合比较分析,在多种可行的方案中,经分析确定出其中一种较为满意的方案。在一般情况下,配送总里程最短、综合费用最省是考虑合理运输的几个主要目标,它集中地体现了货物运输的经济效益。1.2模型的基本假设在构建模型时，我们必须要对模型做一定的假设，提高模型的可行性、可信性。本文对该模型做了以下假设：（1）所有车辆在工作时间内都可以正常运行；（2）每个客户仅能由一辆车为其提供服务；（3）每个客户的需求都为单一品种的商品；（4）运输车辆为同一类型；（5）每辆车可以为多个客户服务；（6）每辆车在发车之后不再进行调度。1.3模型集合、参数及其决策变量（1）集合H客户所在节点集合；K所有运输车辆的集合；P交通网络中可选路线的个数集合；（2）参数 节点i到节点j的运输费用； 车辆k的固定成本； 需求商的需求量； 运输车辆K的容量； 需求商j要求最晚的到达时间；为通过(i,j)路段时的平均运输时间； 为(i,j)路段的里程；为目标n的权重系数；（3）决策变量=1运输车辆k经过节点i到节点j，；否则=0； =1在节点i处有车辆k满足条件；否则=0。1.4车辆路径的数学模型基于以上的假设，现在要求出一个运输费用省、运输时间最少、运输里程短的运输方案，其数学模型如下所示: n=1，2 ，3 pPs.t （1-1） （1-2） （1-3） （1-4）其中：为第P条可选线路在只考虑目标n时的目标值；为只考虑目标n时的最优值。= 为各条运输路径的费用；=为各条运输路径所用的时间；=为各条运输路径的里程。=Min()为只考虑运输费用时，最小运费； =Min() 为只考虑运输时间时，时间最少；=Min（）为只考虑运输里程时，运输里程最短。式（1-1）表示车辆容量的约束条件，是车辆运载的客户需求不超过车辆的容量；式（1-2）表示车辆运输时间不超过客户要求的最晚到达时间的约束条件；式（1-3）和（1-4）保证决策变量为整数。2.模拟退火算法和存在的不足 模拟退火算法最早的思想是由N. Metropolis等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。在加热固体时,固体中原子的热运动不断增强,内能增大,随着温度的不断升高,固体内部粒子随温度的升高而变为无序状。冷却时,粒子逐渐趋于有序,在每个温度下都达到平衡状态,最后在常温下达到基态,同时内能也减为最小。退火过程由一组称作冷却进度表(Cooling Schedule)的参数控制,包括控制参数的初始值T以及衰减因子、每个T值时的迭代次数(称为一个Mapkob链的长度)L和终止条件S。2.1模拟退火算法的模型模拟退火算法的基本思想：(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L(2) 对k=1，L做第(3)至第6步：(3) 产生新解S(4) 计算增量t=C(S)-C(S)，其中C(S)为评价函数(5) 若t0，然后转第2步。2.2模拟退火算法存在的不足（1） 初始温度值的选取和温度的下降幅度较难控制。如果初始温度值选得太大，温度的下降幅度太小，虽然最终能够得到较好的解，但搜索时间过长；反之，则很可能得不到全局最优解.（2）当变量很多，目标函数较复杂时，为了得到一个较好的近似解，参数的控制将变得更加困难。（3）模拟退火算法是一种求解组合优化问题的随机性方法，在搜索的过程中有一个判断概率接受与否的环节，模拟退火算法在该环节有可能把当前遇到的最优解忽略掉，这样既浪费了搜索时间，又影响了解的效果。3.模拟退火算法的改进由于模拟退火算法是一种随机算法,它是通过概率来判断接受新状态，然而在有时候会有当前状态的接受概率低于搜索过程中的某些中间状态差，所以最终得到的解可能并不是它整个过程中所找到的解中的最好的解,另一方面,即使最终输出的解就是它找到的最好的解,虽然可以证明算法对整体最优解的渐进收敛性,但终止解的可接受性也不能不受到怀疑，而且,当最终解在最优解的附近时,算法本身不能迅速逼近或达到最优解。如果给算法加上一个“记忆器”，使它能够记住搜索过程中最好的解，这样就可以提高最终所得解的质量和加快求解的速度。但是对于车辆路径问题，由于路径匹配数量过大，导致搜索时间够长，而模拟退火算法是一种以一定的概率接受目标不太好的状态，这使得算法落入局部最优的陷阱，也要进过很长时间才能跳出，也就是温度充分小时，相应的接受概率就趋于0，陷入局部最优的概率也就越大，跳出局部最优的时间就越长，如果在算法陷入局部最优后，人为的升高温度，提高较差状态接受概率，那么跳出局部最优就相对容易，时间也更短。3.1算法的改进（1） 有记忆的模拟退火算法我们首先设置记忆变量和f(),分别用于记忆当前遇到的最优解和最优目标函数值。算法刚开始时令和f()分别初始化等于初始解x0和其目标函数值f(x0)。迭代开始后,每当接受一个新的搜索解时,将其目标函数值f(x*)与f()进行比较,如果f(x*)优于f(),则分别用x*和f(x*)取代和f()。最后,当算法结束时,从当前解与记忆变量中选取较优者为问题的近似全局最优解。（2） 单调升温的模拟退火算法【10】 当温度T充分大的时候，相应的接受概率趋近于l，此时算法在全局进行搜索；当温度T充分小时，相应的接受概率趋于0，如果在此搜索陷入局部最优，则很难跳出，所花的时间也相应增加。那么就在搜索进入局部最优时,人为地升高温度,提高较差解的接受概率,避免算法在局部极小解处停滞不前。这样,搜索跳出局部最优就容易了。但是要使用单调升温的模拟退火算法，就要解决一下几个问题：(a)确定搜索陷入局部最优假设搜索进入局部最优点P0，那么由模拟退火算法的求解过程可知，当新解的优化程度小于当前最优解的优化程度的时候，新解被接受的概率为100；而当温度足够低的时候，较差解被接受的概率趋近于零。所以，当搜索陷入局部最优的时候，会出现如下特征：由于在局部最优点P0邻域内的所有点的优化程度都小于或等于P0的优化程度，所以在最近的K次搜索中都没有优化程度更高的解出现。由于搜索已经陷入局部最优，所以P0以及在P0邻域内与P0优化程度相同的少数几个点会在最近K次搜索所接受的新解中反复出现。若出现以上特征则说明搜素已陷入局部最优，需要升温来跳出局部最优。(b)升温幅度的判定升温的目的是提高较差解的接受概率,从而帮助算法更快的跳出局部最优。升温幅值过小,达不到效果；升温幅值过大,搜索又会进入漫长的全局搜索,等于重新开始另一次模拟退火。根据经验，升温幅度要以使系统能以大于0.6和小于0.7 的概率为优【11】，这样逃出局部最优的环境最适合。因此规定升温幅度如下:设升温幅度为, 则应满足exp(/),这样可以保证搜索能尽快跳出局部最优,而又可避免进入漫长的全局搜索。3.2算法的步骤（1） 初始化：选择充分高的初始温度，并令=，随机产生初始解及其目标函数值并令和与之相等，使得在不同温度时确定Mapkob链长L；（2） 在此温度T下，对K=1至L做第（3）到第（7）步；（3） 计算增量=C()-C(x)，其中C（x）为评价函数；（4） 若0则接受作为新的当前解，否则以概率exp(-/T)接受作为新的当前解,将目标函数值与相比较，若优于，则分别用和取代和；（5） 内循环：算法在该温度下是否充分搜索，是，转向第（6）步，否，转向第（5.1）步；（5.1）判断搜索是否已经陷入局部最优，是，转向第（5.2）步，否，转向第（2）步；（5.2）设定升温幅度，选定升温函数；（5.3）按一定方式将T进行降温，即，有； (5.4) 以当前解作为最优解输出，转向第（6）步；（6） 外循环：是否满足算法的终止条件，是，转向第（7）步，否，转向第（2）步；（7） 输出最优解。其流程图为：4.仿真分析为了验证车辆路径问题对于改进的模拟退火算法能快速收敛于全局最优和优于一般的模拟退火算法的特性。我们给出了下列实验数据：本实验随机产生10个节点，每个节点都可以相应的看做物流中心和客户所在地，物流中心有15辆车，每辆车的固定成本和平均速度都不相同，而且设定每辆车每公里油耗6.8元、成本0.15元，车辆载重费用2元/吨。仿真环境：在模拟退火算法中我们设定初始温度为10000摄氏度，最大循环次数为500，降温方式为Tk+1=0.95*Tk。经过判断陷入局部最优后改变的升温函数为Tk+1=*Tk，其中为升温倍数，但是随着温度的变化升温倍数也随之而发生变化=*0.7，降温方式变为Tk+1=0.65*Tk。仿真一：比较一般模拟退火算法、单调升温的模拟退火算法和带记忆功能的单调升温的模拟退火算法在不同初始温度下迭代次数的比较，如图一所示：图一 三种算法的迭代次数从图一可以看出带记忆功能的单调升温的模拟退火算法在相同温度下，迭代次数最少，并且随着温度的升高而增多。这说明该改进型的模拟退火算法具有收敛速度较快的特点。仿真二：比较一般模拟退火算法、单调升温的模拟退火算法和带记忆功能的单调升温的模拟退火算法在不同初始温度下运行时间的比较，如图二所示：图二 三种算法的运行时间从图二可以看出带记忆功能的单调升温的模拟退火算法在相同温度下，运行时间最少，并且在温度1000至5000之间，运行时间逐渐增加，在温度5000至10000之间运行时间逐渐减少。这说明改进型的模拟退火算法具有计算效率高的特点。5.结论首先本文建立了基于多目标规划的车辆路径问题的数学模型，该模型考虑了更贴近与实际的约束条件和目标函数，以运输费用省、运输时间最少、运输里程短的整体最优为目标。然后在此基础上构造了求解多目标规划的车辆路径问题的改进的模拟退火算法，最后本文利用设计好的数学模型和算法对该问题进行了仿真实验分析，实验结果表明，用本文设计的改进的模拟退火算法求解基于多目标规划的车辆路径问题，该算法与其他模拟退火算法（一般模拟退火算法和单调升温模拟退火算法）相比不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较