车辆路径（共10篇）
车辆路径 篇1
路径规划是自主车辆导航的最基本任务[1]。其目的是在特定环境中,按照一定的评价标准或者按照某一性能指标搜索出一条从起始状态到目标状态的最优或近似最优的路径。自主车辆的路径规划主要分为两大类型:环境信息已知全局路径规划和环境信息未知或部分未知的路径规划[2]。目前,对于路径规划应用较为典型方法有可视图法、拓扑法、人工势场法、蚁群算法等。但这些方法在大范围内求解最优路径时就会表现出缺乏灵活性和足够的鲁棒性的缺点。为此,学者们提出了更多新的解决方法,使自主车辆从单纯的路径规划逐渐发展为路径全局搜索、路径优化的问题。
本文在自主车辆无需经过特定点时,应用A*算法,自行建立地图信息,并对原始A*算法进行了技巧性改进,使车辆可以在有效时间内搜索到一条近似优化路径,且不会出现路径长度计算失效,以保证算法的灵活性和准确性;同时当车辆需要经过特定点时,应用Hopfield神经网络思想对算法进行改进,使车辆从起始点到终止点并再次返回起始点时,能够搜索到一条最优路径。最后通过仿真实验验证了算法的有效性。
1 无特定点的车辆路径规划
在常规行驶中,车辆遇到的实际情况会远远超过所预设的理想情况,例如,控制车辆从起始点到目标点不需要经过特定点时,采用全局搜索的方法找到一条最优(距离最短或消耗最小)路径。当车辆行驶在地图信息已知且无须经过特定点时,路径规划采用经典的全局搜索A*算法为最优。
1.1 A*算法改进
A*算法的最大特点是估价函数的建立。在经典的A*算法中,估价函数的表达式为:
式(1)中:f(n)是节点n从初始点到目标点的估计代价,称为估价函数;g(n)是起点到节点n的最短路径值;h(n)是从节点n到目标节点最短路径的估计代价,称为启发函数。
鉴于A*算法存在着随着搜索区间的增大,内部存储数据增加,最终导致路径搜索时间过长、实时性无法保证的问题[5,6],本文在传统A*算法估计函数建立的基础之上将估计函数改进。引入一个权值ω(n),其作用是:当车辆接近目标点时,降低启发函数的重要性,增加路径真实代价的相对重要性,即防止出现h(n)将远远大于g(n)的情况。
其表达式为:
式(2)中:ω(n)是节点n到目标节点启发函数引入的权值。
A*算法能否保证车辆找到一条优化路径,关键在于启发函数h(n)的选取。
1.2 启发函数h(n)选取改进
启发函数h(n)的选取,实际上就是距离的计算。通常在A*算法计算距离时,可以采用平方欧几里得距离(square Euclidean Distance)和欧几里得距离(Euclidean Distance)。
传统算法中,启发函数h(n)选取平方欧几里得距离,主要会出现以下三种明显错误:
(1)出现计算单位失效,路径长度计算错误;
(2)h(n)将远远大于g(n),并且会因为启发式函数评估值过高而停止计算;
(3)对于更长的距离,选取平方欧几里得距离,只会出现f(n)靠近g(n)这种极端情况,车辆会停止计算距离而提前结束路径点的搜索。
为了修正传统算法中存在的这种误差,本文采用欧几里克距离计算h(n),其表达式为:
式(3)中:d是启发系数;n.x和n.y是起始点的横坐标、纵坐标;g.x和g.y是下个目标节点的横坐标、纵坐标。
为了防止以上阐述几点错误的出现,权值ω(n)的选取不能太大,避免出现h(n)将远远大于g(n);也不能选取过小,忽略了h(n)的大小。所以本文中选取ω(n)值为0.8。.
1.3 A*算法流程图
算法在Matlab下主要包括四部分:(1)节点坐标的更新;(2)进入估计函数计算部分;(3)判断计算点是否为最佳节点;(4)如果不是最佳节点,放弃该点后继续寻找下个点。算法流程如图1所示。
2 特定点的车辆路径规划
当车辆从起始点到终止点要经过特定的点时,由于搜索区间增大、搜索点大量增加,A*算法这种经典的启发式搜索法就不再适用。而Hopfield神经网络具有分布式存储、存储与计算相结合的优点,能使搜索速度加快。
2.1 算法原理
Hopfield神经网络是1982年美国物理学家Hopfield首先提出来的。与之前存在的BP前行神经网络的特点不同,它采用反馈连接,考虑输出与输入在时间上传输延迟,所以它表示的是一个动态过程。反馈神经网络由于其输出端有反馈到其输入端,Hopfield网络在输入的激励下,会产生不断的状态变化。当有输入之后,可以求取出Hopfield的输出,这个输出反馈到输入从而产生新的输出,这个反馈过程一直进行下去。如果Hopfield网络是一个能收敛的稳定网络,则这个反馈与迭代的计算过程所产生的变化越来越小,一旦到达了稳定平衡状态,Hopfield网络就会输出一个稳定的恒值,可以求取出Hopfield的输出[3,4]。Hopfield网络一般分为离散型和连续型两种,本文采用的Hopfield网络为连续型网络,其结构如图2所示。
对网络第i个神经元,采用微分方程建立输入输出关系:
以及定义的李雅普诺夫函数:
由式(4)、式(5)可得:
式(6)中:ωij为神经元i和j的连接权值;ui为第i个神经元的输入;vi为第i个神经元的输出;Ii为第i个神经元的外加偏置电流;Ri为第i个神经元的电阻;Ci为第i个神经元的电容。
2.2 算法推导
Hopfield网络已经用于解决一些不同的组合优化问题,现已证明Hopfield网络是一种李雅普诺夫渐进稳定过程。Hopfield网络一般用能量函数来描述,能量函数的最低值表示最优解[7]。
对于车辆到达终点要经过n个目标点的路径规划问题,映射成为一个神经网络的动态过程,可以引入TSP的理念,采用换位矩阵构成一个n×n的矩阵,如表1所示。在该矩阵中各行各列只有一个元素为1,其余为0,采用Oxi表示神经元的输出,ixi表示为相应的输入。
神经网络的能量函数是与目标函数(最短路径)相对应的。同时,考虑到有效路径选取的实际意义,即就是在构成的换位矩阵中,每行、列都只能有一个1。因此,能量函数应该包含目标项(目标函数)和约束项(换位矩阵)两部分内容。
针对Hopfield神经网络方法在求解上存在局部极小、不稳定等问题,本文引用改进后的能量函数,由式(5)可得:
同理,由式(6)可以推导出,路径规划网络的动态方程为:
3 Matlab仿真及结果分析
文中选用的自主车辆为四轮农夫车,属于实验室专用车辆,它是一种场地特种车辆,行驶速度较低,适合校园及其它非结构化道路行驶。车辆的制动、加速踏板和转向走在驾驶舱呈开放状态,且车辆已经过了车体改装。下文以此车建立模型进行仿真实验来验证算法。
3.1 无特定点路径寻优仿真
假设车辆初始坐标(0,0),终止坐标为(0.9,0.9),初始速度为0 m/s,启发系数d=1.8,权值ω=0.8。在自行生成不规则地图的基础上,无特定点路径寻优仿真如图3所示。图3(a)为选取欧几里克距离(square Euclidean Distance)的实际仿真结果,图3(b)为选取平方欧几里得距离(square Euclidean Distance)的实际仿真结果。图中的“o”代表了搜索过程中输出的最佳节点。
仿真结果分析:两种距离下的算法都能达到搜索路径的目的。图3(a)输出的最佳节点较多,搜索结果要明显优于图3(b);同时由于选取Square Eucl-idean Distance所存在计算失衡问题,图3(b)中的路径距离计算结果也出现了明显错误。
3.2 特定点路径寻优仿真
选取6个坐标点代表实际中车辆要经过的特定点:D1(0.1,0.6),D2(0.2,0.3),D3(0.4,0.1),D4(0.5,0.5),D5(0.7,0.2),D6(0.8,0.4),能量函数初始值A=200,D=200,迭代次数num=20 000,采样时间间隔0.000 1。经过特定点路径寻优仿真如图4所示。图4(a)为优化前的仿真路径,图4(b)为采用神经网络优化后的仿真路径,图4(c)为能量函数变化曲线。
仿真结果分析:图4(a)中原始路径的长度Length＿init=2.361 4 m,而利用神经网络优化以后所得到的实际路径如图4(b)所示Length＿end=1.867 4 m,比优化以前路径长度明显缩短了21%。图4(c)中能量函数E在经过20 000次的迭代循环后,单调递减最终达到稳态,且E的最小点对应问题的最优解。
4 结论
(1)在无需经过特定点的路径规划中,全局路径搜索选取了较小的启发函数,扩展的节点虽然有所增加,搜索效率也相对降低,但从路径的准确性上得到了保证;在估价函数中增加权值,降低启发函数重要性的同时增加路径的真实性。
(2)在经过特定点的路径规划中,利用Hopfield神经网络的理念和能量函数,把车辆路径规划寻优问题的目标函数转换成网络的能量函数,把问题的变量对应于网络的状态,解决了车辆在行驶空间各站点的路径规划问题,使总距离达到最短,能量达到最小且稳定。
通过改进后算法的仿真实验,证明了算法的可行性和有效性,使车辆的路径寻优效果得到明显提高。
参考文献
[1]纪寿文,王荣本.国内外智能车辆研究进展.中国交通研究与探索(上册),第三届全国交通领域青年学者会议,1999
[2]王艳平.移动机器人路径规划方法研究.电脑与电信,2009;(1):66—68
[3]李国勇.神经模糊控制理论及应用.北京:电子工业出版社,2009
[4]张丽霞,赵又群.Hopfield神经网络算法求解路网最优路径.哈尔滨工业大学学报,2009;(40):222—224
[5]贾庆轩,陈钢,孙汉旭,等.基于A*算法的空间机械臂避障路径规划.机械工程学报,2010;46(13):109—115
[6] Chabini I,Lan S.Adaptations of the A*algorithm for the computa-tion of fastest paths in deterministic discrete-time dynamic networks.IEEE Transactions on Intelligent Transportation Systems,2002;3(1):60—74
[7]张德丰.Matlab神经网络应用.机械工业出版出版社,2009
车辆路径 篇2
改进的遗传算法在战时油料运输车辆路径问题中的应用研究
文章首先对战时油料运输车辆路径问题(VRP)进行了分析,阐述了战时油料运输车辆路径问题的`优化目标,并建立了多目标的优化模型;接着简介了遗传算法的优缺点,并设计了一种改进的遗传算法运用到问题的求解中;最后举例进行了计算和分析,验证了模型和算法的有效性.
作 者：蒋敬东 周庆忠 李凌 杨方 JIANG Jingd-ong ZHOU Qing-zhong LI Ling YANG Fang 作者单位：解放军后勤工程学院,重庆,400016刊 名：物流科技英文刊名：LOGISTICS SCI-TECH年，卷(期)：32(4)分类号：U116.2关键词：战时油料运输 车辆路径问题 遗传算法
车辆路径 篇3
【关键词】路径优化；节约算法；集送货一体化；时间窗约束
一、背景
在物流运输过程中，运输成本占了60%，部分产品的运输成本甚至高于产品的生产成本，因此对配送进行优化成为公司降低物流成本，实现自身利益最大化的一个重要方面。而运输车辆的行车路线是配送优化的核心问题，在配送的同时回收货物是现代物流的发展方向，因此，一体化集货与配送的车辆路径问题（Vehicle Routing Problem with Back-hauls，VRPB）得到了广泛重视。
二、研究现状
目前国内对于带集货送货车辆路径规划的研究主要有霍佳震，张磊把上述问题分解为两个阶段进行求解：第一阶段对每一项任务内部的集货点与送货点进行内部安排行车路线；第二阶段再对各项任务之间进行外部安排行车路线，以此简化问题。钟石泉，贺国光提出一种改进的禁忌算法来解决这类问题。李华建立多目标优化模型，用混合遗传算法进行仿真求解。
本文重点讨论通过简单节约算法进行修正得到的改进型节约算法，对有集送货双重需求，有硬时间窗约束的车辆路径进行优化，并对某案例进行分析，给出优化方案。
三、研究方法
（一）节约算法
节约算法的基本步骤是先将各客户点分别与配送中心相连形成初始路线，然后将任意两客户点（即i，j）相连并计算节约值： ，S（i，j）越大，节约的费用越多。S（i，j）按由大到小排序后，按照S（i，j）排序顺序依次连接各点。若连接过程中出现该路线运货总量超过车辆载重，则不连接这两点，考虑后面两点的连接。
本案例增加了集送货任务以及硬时间窗要求，要首先判断各点集送货量之和有无超过车辆载重Q，如果超出，需要在满足Q的情况下对该点单独集送货，而超出Q的部分再参与计算。
（二）改进的节约算法
对配送量和集货量有如下改进：各节点配送量和集货量）表示在节点j加入路线后可以留出的空间效益，把差值越大的节点放在运输路线的前面部分，并考虑车辆的载重限制。因此对节约算法进行一定的修正。即。
对于时间窗约束有：设Si为完成任务i所需的时间，Ti为装货或卸货所需的时间，ETi为i的允许最早开始时间，LTi为i的允许最迟开始时间，则Si需满足：ETi≤Si≤LTi ， S0=0令ti，j为车辆由点i行驶到点j的时间，则到达j点时间的推迟（或提前）量EFj可表示为，则有：EFj<0，提前到达；EFj>0，推迟到达。定义参数，分别为j点的到达时间最大可提前量和最大允许推迟量，则有
其具体步骤如下：（1）形成一个初始解。采取单点配送构成各车辆配送点集，令；（2）计算各客户点间的，距离节约值S（i，j）及S'（i，j）；（3）按S（i，j）值的上述顺序，逐个考察其端点i和j，若滿足以下条件，则转下步，否则，不连接。条件是：1）点i和点j不在一条线路上；2）点i和点j均与基点相邻。
（4）考察点i和点j连接后线路上的总配送量要小于车载量且集货量之和要小于车载量减去总配送量，则转下步，否则不连接。 （5）计算EFj，若满足或，弧（i，j）插入到线路中，否则，不连接。（6）计算连接点i和点j后车辆到达各项任务的新时间，返回步骤（3），直至考察完所有的弧为止。
（三）节约算法具体应用
1、案例分析
本文在符合客户可接受送达时间的前提下，不考虑运送次序对客户满意度和运输成本的影响，以赣州YQ农产品配送中心为实例并优化该配送中心的物流配送路径，赣州YQ农产品配送中心主要给赣州市区的15个大客户运送农产品，每天一定的时间段进行配送，配送中心目前有4辆车，核定载重量为10吨。每天运输的速度为50km/h，由配送中心负责配送和集货。A值取0.6。在此情况下为使配送中心自身运输成本最低，合理规划其路径。本案例取配送中心附近的8个点，配送中心为0点，其他赣州国光超市为1、天虹商场2、铁龙大酒店3、汇康大酒店4、赣州格兰云天国际酒店5、江西理工大学6、赣南医学院7、江西环境工程学院8。其各地点的距离以及它们的需求量和配送量如上表所示：
四、优化方案
赣州YQ农产品配送中心的在日常的配送过程中，其农产品配送路线计划主要是依据驾驶员的配送经验来安排，当配送客户点较少时，此类方法才有一定可行性，但在配送客户点很多时，这种方法缺乏科学依据，可操作性不强，同时存在许多不合理的地方，这时候配送成本会增加很多。赣州YQ农产品配送中心，由文献知赣州YQ农产配送中心的原有农产品配送计划和车辆配送对应客户点的实际情况，车辆编号配送线路计划如下：
五、总结
本文从改进C一W节约算法入手，对有时间窗约束的VRPSDP式进行了研究，提出了以集货量和送货量共同作为各客户点归并的判断条件，并与其最短距离结合其来在规定的时间将货物送到以及集货。案例表明文中所提出的算法实现了路径优化，并节约了配送中心的运输费用。
参考文献
车辆路径问题(VRP)算法研究 篇4
关键词：车辆路径问题,经典算法,启发式算法,蚁群算法
车辆路径问题(Vehicle Routing Problem,VRP)是物流配送研究中的一项重要内容。VRP问题的研究目标是，对一系列的顾客需求点设计适当的路线，使车辆有序地通过，在满足一定的约束条件下，达到一定的优化目标。其约束条件一般为：货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等，优化目标一般为:里程最短、费用最少、时间尽量少、车队规模尽量小、车辆利用率高等。对车辆路径问题的研究无论在物流业还是在学术界均有重大的意义。从企业的角度来讲，一个好的车辆路径算法和策略可以为企业带来巨大的收益;从学术界来讲，车辆路径问题是图论中的NP问题，研究其求解方法及理论具有重要的理论价值。
1 VRP问题算法发展的三个阶段
第一个阶段为古典的VRP问题研究阶段。这一阶段主要研究一些具体的问题，并提出了一些著名的算法。但是这时的算法多注重具体问题的派车方案，不太注意路径长度或费用的节省，而且只能处理顾客较少的问题，可移植性较差。第二阶段为基于数学规划或网络分析的VRP问题的研究阶段。这一阶段因为数学规划和网络分析有了一定的发展。人们开始用数学规划和网络的最大和最小流来研究VRP问题，可以说这个阶段的算法是十分精确的。但是因为VRP问题是离散的，所建立的数学规划或者网络模型是整数规划或复杂的网络。它们的求解很困难，甚至不能求解，即使能求解，也只能处理小规模的问题。第三阶段为基于人工智能算法的VRP问题的研究阶段。人们利用模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法和蚂蚁算法等来研究VRP问题。它们能处理较大规模的VRP问题，可移植性强，能在合理的时间内给出问题的接近最优解或者近似最优解，是值得推广的算法。
2 VRP问题中的常用算法
求解车辆路径问题的方法非常多，常用的基本理论方法有：分枝定界法、割平面法、动态规划法、匹配理论、对偶理论、组合理论、线性搜索技术、列生成技术、拉格朗日松弛技术、状态空间松弛技术、Benders分解技术、次梯度优化技术、概率分析、统计分析、最差情况分析、经验分析等。就其本质，这些方法可以归结为3中类型：精确算法、经典启发式算法和现代启发式算法。
2.1 精确算法
精确算法指可求出最优解的算法。精确算法可分为3种类型：有向树搜索算法、动态规划算法和整数线性规划算法。目前主要有分枝定界法、割平面法、动态规划法、集分割和列生成算法等。
1)分枝定界算法。分支定界(branch and bound)算法是一种在问题的解空间树上搜索问题的解的方法，其求解VRP问题的基本思路是，以相应的不含整数约束的VRP问题的最优解为出发点，若此解是整数解，那么这个解就是原VRP问题的最优解，否则以非整数解的相邻整数作附加条件，形成2个分枝，即2个子问题，进行求解。若对上面2个子问题求出最优解是整数解，则停止该子问题的分枝，否则继续分枝求解。这种方法只能适用于求解小型VRP问题。该方法是Laporte等提出来的。而后Kolenatal曾利用此方法求解含时间窗约束的车辆巡回问题，发现当节点数扩大至12时，计算机有内存不足的现象产生。
2)K度中心树算法。先将问题转化为“k度中心树”后，再进行求解。该方法是Christofidest[1]等人提出的。对固定m的TSP进行k度中心树松弛。所以该方法需要知道所需车辆数的下界。其模型是用边的角度建立的，出发点用一条边来表示，其他点用两条边表示。通过拉格朗日松弛法，将其中一个约束条件消去，并进一步将原来的最小化问题转化为3个易于求解的子最小化问题，然后进行求解。目前，M.L.Fisher[2]对它做了进一步改进，可求解有134个客户的VRP。
3)集分割和列生成算法。VRP问题的集分割方法是由Balinski等首先提出。他们直接考虑可行解集合，并在此基础上进行优化。尽管所建立的VRP模型最为简单，但给算法和动态规划算法一样存在状态数过于庞大的问题。另外要确定每个可行解的最小成本也是一件困难的事情。Rao[3]等人引入了列生成方法进行求解。在该方法中，原问题被转化为简化问题，考虑的范围是所有可能的可行解的子集。在此基础上重复求解。通过引入优化对偶变量向量，对该简化问题松弛，通过计算列的最小边际成本，确定最优解。其算法本质上是最短路径算法，同时结合了分枝定界算法。Desrocher[4]用它求解有100个客户的带时间窗口的VRP。
4)动态规划算法。动态规划法求解VRP问题的基本思路是，将VRP问题视为一个n阶段的决策问题，进而将其转化为依次求解n个具有递推关系的单阶段的决策问题，从而简化计算过程。用这种方法可求得VRP的最优解，但仅适用于较小规模的寻优问题。
5)三下标车辆流方程。Fisher[5]等人针对带容量约束、带时间窗口的VRP问题，提出了三下标车辆流方程。在该方程中，xijk表示k是否经过路径(i,j)。基于Benders分解技术，他们提出了一种启发式算法，保证在有限的步骤内找到最优解。Fisher[2]等人用它计算了有50∶199个客户的VRP。Martello[4]和Desrochers[4]分别提出了相应的改进算法。
6)二下标车辆流方程。对于对称的CVRP和DVRP，可去掉表示车辆序号的下标，引入所需车辆数的下界，得到一个更为紧凑的方程。它所对应的算法结合了爬山法的思想，其算法核心仍然是线性规划，若得到的解是分数解，则用分枝定界算法求其整数解。该方法是由Laporte[6]等人提出的，已用它来求解了规模为60的问题。
由于精确算法在求解时引入了严格的数学方法，因而无法避开指数爆炸问题，从而使该类算法只能有效求解小规模的VRP问题，并且通常这些算法都是针对某一特定问题设计的，适用能力较差，因此在实际中其应用范围很有限。
2.2 经典启发式算法
经典启发式算法大致可以分为以下几类：
1)先分组后安排路线的方法。该方法先按客户需求进行分组或划群，然后对每一组设计一条经济的路线。如Gillett等的Sweep算法，其目的在于形成需求点的径向区域，从车场(分配中心)发出的射线扫过这个区域，使不超过车辆容量的需求点组成一个区域，一个区域就是一个组，当形成一系列这样的组后，再对每一组中的各点安排路线。这种算法一般仅适用于装货或卸货问题。
2)先安排路线后分组的方法。该方法首先构造一条或几条很长的路线(通常不可行)，然后再把这些很长的路线划分成一些短而可行的路线。一般是先解一个经过所有点的旅行商问题，形成一条路线，然后根据一定的约束(如车辆容量等)对它进行划分。
3)节约-插入算法。该算法的每一步，把当前的线路构型(很可能是不可行的)跟另外的构型(也可能是不可行的)进行比较，后者或是根据某个判别函数(例如总费用)会产生最大限度的节约的构型，或是以最小代价把一个不在当前构型上的需求对象插入进来的构型，最后得到一个较好的可行构型。
4)改进/交换法。该方法在保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的解，力图使目标函数值得以改进，一直继续到不能再改进目标函数值为止。如Lin提出的2-opt和3-opt交换，Cordone等提出的改进算法，Breedam提出的串置换等均属此类算法。
5)基于数学规划的算法。该方法把问题直接描述成一个数学规划问题，根据其模型的特殊构型，应用一定的技术(如分解)进行划分，进而求解已被广泛研究过的子问题。
6)交互式优化法。该方法把人的因素结合到问题的求解过程中，其思想就是:有经验的决策者应具有确定和修改参数的能力，并且根据知识直感，把主观的估计加到优化模型中去，这通常会增加模型最终实现并被采用的可能性。
必须注意的是，这几种纯启发式算法的划分不是绝对的，有的方法同时属于好几类算法。
2.3 现代启发式算法
现代启发式算法包括禁忌搜索算法、遗传算法、神经网络算法、模拟退火算法、蚁群算法等。这一类算法能有效解决一些较为复杂的VRP问题，改善解的性能。20世纪90年代以来，此类算法已成为有效求解VRP问题的重要方法和新的工具。
1)禁忌搜索算法。Gendreau[5]等人最先将该方法应用于VRP。先构造一系列的解，然后对所得解不断地进行改进。该算法所得到的解不一定是可行解，它们对可行性的偏离程度是通过目标函数里的罚函数来体现的。该算法求解过程中的邻域，是通过GENI过程得到的。它是针对VRP的比较好的启发式算法，可以成功地应用于许多经典的VRP。其后，E.Taillard[7]通过按角度和路径重心对原问题的空间进行分割，再用禁忌搜索结合模拟退火对子问题求解，实现了问题求解的并行化。
2)神经网络算法。神经网络的应用已经成为VRP研究中的新的趋势。神经网络模型由McCulloch和Pitts于1943年提出，模型主要是利用神经网络中神经元的协同并行计算能力来构造的优化算法。它将实际问题的优化解与神经网络的稳定状态相对应，把实际问题的优化过程映射为神经网络系统的演化过程。神经网络算法求解VRP问题可能会导致网络最终收敛于局部极小解，甚至可能收敛到问题的不可行解。此外，网络最优的最终结果很大程度依赖于网络的参数，即参数鲁棒性较差。
3)模拟退火法。模拟退火法是由Met ropolis于1953年提出的，是一种基于热力学原理的随机搜索算法。Osman于1993年对VRP问题的模拟退火算法进行了研究，提出模拟退火方法适合于解决路线分组问题。该算法通过模拟冶金作业的退货过程来搜索解空间，具有收敛速度快、全局搜索能力强等特点。从理论上讲，用这种方法求解VRP问题，可以求得全局最优解，但在实际应用中，由于受计算时间的限制，往往只能给出一个近似的最优解。为了使模拟退火算法求出的近似解更准确，一般重复执行模拟退火法多次，从中选取最好的解作为最终的近似最优解。
4)遗传算法。J.Lawrence最先将该方法用于VRP的研究，并可有效求解带时间窗口的VRP。鉴于传统的遗传算法是个大范围、粗粒度的寻优算法，因此，Barnier将它与约束满足问题(CSP)的技术相结合，通过遗传算法来处理CSP参数的子域(基因的适应度是通过对CSP解的计算得到的)，从而减小搜索空间，降低CSP问题目标函数和遗传算法约束的复杂度。张涛等人则是通过遗传算法来保证搜索的全局性，用3-OPT算法来加强局部搜索能力，得到针对VRP的混合算法。这类算法目前已可以求解较大规模的问题。
5)蚁群算法。蚂蚁算法是一种源于大自然生物界的新型仿生类算法，它于20世纪90年代初由意大利学者Dorigo、Maniezzo首先提出。作为通用型随机优化算法，它吸收了昆虫王国中蚂蚁的行为特征，通过其内在的搜索机制，已在一系列的组合优化问题的求解中取得了成效。其基本原理是模拟蚁群搜索食物的行为:蚂蚁群找到食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时，会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行，并释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大。这样就形成了一个正反馈，最优路径上的激素浓度越来越大，而其他的路径上激素浓度却会随着时间的流逝而消减，最终整个蚁群会找出最优路径。该算法在求解VRP问题方面有良好效果，但存在如计算时间较长、容易陷入局部最优等问题。
此外，近年来也有学者将免疫算法用于求解VRP问题，并根据VRP问题的具体情况提出了一种基于分组匹配的亲和力计算方法。算法中模拟了生物免疫系统对外来抗原的排除，把抗原对应于待求解的问题，抗体对应于问题的一个解。也有学者将粒子群算法应用于VRP问题，构造了VRP问题的粒子表达方法，建立了此问题的粒子群算法。该算法是通过模拟鸟群的捕食行为来达到优化问题的求解。
3 结束语
我国对车辆路径问题的研究是在20世纪90年代以后才逐渐兴起，目前国内对于复杂的车辆路径问题的研究仍处于起步状态，就这方面研究的深度和广度来说，现有的算法远不能满足某些应用场合进行实时动态调度的需要，因此有必要提供有效的快速算法。鉴于纯数学的VRP算法通常要较长的计算时间，因此，应用人工智能技术，采用专家系统，降低对寻优精度的要求，从而提高响应速度，是一种现实的途径。对于大规模客户集的配送路径优化问题或者是多约束的复杂VRP问题，可以考虑利用多种算法相结合的办法来解决。当然，对算法复杂性方面的研究，也是构造快速算法的一个有益的途径。
参考文献
[1]Christofides N,Mingozzi A,Toth P.Exact algorithms for the vehicle routing problem,based on spanning the shortest path relaxation[J].Mathematical Programming,1981(20):255-282.
[2]Rao MR,Ziont S.Allocation of transportation units to alternative trips A column generation scheme with out2of2kilter sub2problems[J].Operations Research,1968(12):52-63.
[3]Dantzig G,Ramser J.The truck dispatching problem[J].ManagmentScience,1959(6):80-91.
[4]祝崇俊,刘民,吴澄.供应链中车辆路径问题的研究进展及前景.计算机集成制造系统—CIMS[J].2001,7(11):1-6.
[5]蔡延光,钱积新,孙优贤.多重运输调度问题基于双表的并行表搜索算法[J].系统工程理论与实践,1998(11):20-26.
[6]Laporte G,Nobert Y,Desrocher M.Optimal routing under capacity anddistance restrictions[J].Operations Research,1985,33:1050～1073.
[7]Taillard E.Parallel interative search method for vehicle routingproblem[J].Networks,1993(23):661-673.
[8]郎茂祥.用单亲遗传算法求解配送车辆调度问题的研究[J].交通与计算机,2006,24(1):119-122.
[9]程世东,刘小明,王兆赓.物流配送车辆调度研究的回顾与展望[J].交通运输工程与信息学报,2004(3):96-100.
车辆路径 篇5
[关键词] MAX-MIN蚁群算法时间窗车辆路径问题优化
一、VRPTW模型的建立
带有时间窗口的车辆路径问题是典型的多目标组合优化NP-hard问题,因此需要通过合理的构造数学模型来安排车辆配送路线，达到提高配送效率同时又能够产生巨大的社会和经济效益的目的。
VRPTW包括一些客户和仓库，每个客户有一定的需求和时间窗口。每个客户只能由一辆车一次服务完成，还要保证每个客户只能被精确的访问一次，同时不能违背时间窗口约束。其目的是要找到一个可行解使得车辆数最少并且总行程最小。
二、最大最小蚁群算法
为克服在Ant．Q中可能出现的停滞现象,Thomas Stutzle等提出了MMAS算法。该算法具有比基本蚁群算法更贪婪的搜索模式，其主要的改进有以下几点:首先,MMAS在运行期间更多的利用最优解信息，即每次迭代后仅允许一只最优的蚂蚁增加信息素。其次,该算法限定了信息素浓度的上下限，有效避免了在搜索中过早收敛于非全局最优解。
将m只蚂蚁随机放到n个客户中，为t时刻支路(i,j)上的信息素强度，每只蚂蚁都可认为是根据状态转移策略来选择下一个客户，并遵循信息素全局更新规则和信息素限制规则。
1.状态转移策略
针对VRPTW自身的特点，我们定义其状态转移概率为:
其中h∈allowedk={n-tabuk};ηij为启发信息;α(α≥0)代表信息素的权重，β(β≥0)代表启发信息的权重;μij=di0+dj0-dij为节约值; δij为紧迫性因子。
2.信息素更新规则
在MMAS中，只允许其中的最优路径更新信息素，其更新规则为:
其中，为该次迭代sib或全局最优路径sgb的目标函数。
3.信息素限制规则
为了降低算法搜索中的早期停滞问题，该算法限定了信息素浓度允许值的上下限，即
。若，则;若，则。
在搜索过程中,当得到最优解时,按下式便得到一个动态变化的:
为了提高算法的收敛性，我们一般先给定一个Pbest，然后根据下式来选定一个 ：
三、算例分析及结论
设某仓库使用完全相同的车辆把货物运往8个客户，车辆的载重能力为8吨，车速为50公里每小时，客户所需货物的重量，服务时间及访问时间窗口的具体要求由Tab.1给出。客户之间的距离如Tab.2所示。问题是寻找合适的路径，使得车辆运行总成本最小。
实验开始，将每个客户都放置一只蚂蚁，蚂蚁的个数与客户数相同。取α=1，β=3，γ=3，λ=1，ρ=0.8，θ=10。采用本文的算法，得到的最优解为:第一辆车：0-2-7-4-0;第二辆车：0-3-1-0;第三辆车：0-8-5-6-0。
将求解的结果与Clarke-Wright算法和遗传算法比较,从Tab.3中可以看出MMAS不失为带时间窗车辆路径问题的一个较优解。
四、结语
本文将MMAS算法应用于VRPTW问题中，充分发挥了其超强的贪婪搜索能力，获得了较为满意的实验效果。这次成功尝试再次表明了该算法在组合优化领域中是具有强大竞争力的，同时也证明了用这种方法解决具有一定的理论参考价值和实际意义。
参考文献:
[1]吴启迪汪 镭:智能蚁群算法及应用[M].上海科技出版社，2004，4
[2]刘云忠宣慧玉:动态蚁群算法在带时间窗车辆路径问题中的应用[J].中国科学工程,2005,12(7):35－40
城市配送车辆路径模型和算法研究 篇6
关键词：城市配送车辆,路径模型,算法,研究
社会商业化和经济全球化的时代的到来, 让服务商和物流商清楚地认识到物流配送车辆优化调度的重要意义, 既可以降低商品物流成本, 更能提高客户服务水平, 可谓一举两得, 也是对物流企业品牌树立和生存发展至关重要的。
一、多配送中心联合配送的车辆动态调度模型的研究
提高配送网络的运行可靠性和有效可达性, 是物流配送运输网络优化的主要目标, 因此, 以物流配送运输网络畅通可靠度最大为目标进行建模。笔者根据现在很多城市物流配送的多品种、小批量、多批次和短周期等特点, 主要考虑以下约束条件:各条配送路线的货物总量不得超过车辆容积及载重量的限制;在物流中心现有运力允许的范围内;在配送过程中, 每个配送点只能访问一次, 且必须访问一次;每辆车只能服务一条线路, 且每辆配送车从配送中心出发, 最后必须回到配送中心;配送费用应当控制在一定水平下。遵循上述约束条件, 建立优化模型如下:
式中:ψn为网络中第n条配送线路的畅通可靠度;q为第n条线路所安排车辆的载重;q为第n条线路上所有配送点货物总量;N为配送线路的总体数目;M为物流中心配送车辆数;
A为某种确定水平下的费用定额, 为常数, 可根据经验值确定。
二、城市配送路线优化的智能算法的研究
城市配送中的多配送中心, 多种类货物的车辆调度问题是NP-Hard问题的组合, 是多目标优化问题。根据物流配送网络系统的具体情况, 笔者选择蚁群算法进行系统优化的研究分析。
所谓蚁群算法, 就是人类在观察自然界真实蚂蚁觅食的过程中总结出来的仿生优化算法, 它在短短的十余年的发展历程中展现出顽强的生命力, 成功地应用于解决旅行商问题 (traveling salesman problem, tsp) , 车间作业调度问题 (job-shopscheduling problem, jsp) , 车辆路径问题等组合优化问题。
我们用蚂蚁替代车辆, 当下一个要服务的配送点会使运载总量超出汽车载重量, 就返回到配送中心, 表示这辆车完成此次运输。然后换一辆车接着出发服务其余配送点, 直到所有配送点都得到了一次服务, 此时代表蚂蚁完成一次巡游。当所有蚂蚁都巡游一次, 记为一次循环。一次循环后, 根据各蚂蚁巡游历程的好坏 (目标函数值) , 计算信息素增量, 更新相关路径上的信息素。具体实现步骤如下:
步骤1初始化各基本参数, 置nc=0;
步骤2计算转移概率;
步骤3根据计算出的转移概率和随机产生的q值, 为每一只蚂蚁选择下一条移动的路径;
步骤4当每一只蚂蚁都走过一条边到达下一配送点后, 就按局部更新规则对这条边进行一次信息素的局部更新;
步骤5对每一只蚂蚁重复以上循环执行步骤2到步骤4, 直到所有的配送点皆有蚂蚁走过且配送点的需求得到满足;
步骤6在生成的全部路径中找出符合模型最优目标的路径, 则走过该路径的蚂蚁就是最优蚂蚁;
步骤7对最优蚂蚁所经过的每一条边, 按全局更新规则对这条路径进行一次信息素的全局更新;
步骤8重复执行步骤2到步骤7, 直到执行次数nc达到指定的最大迭代次数或连续若干代内没有更好的解出现为止。
配送网络畅通可靠度的最优意味着配送的延误出现的概率最小, 也即为对配送的有效可达性的最有力的保障。
三、实时监控的城市配送车辆调度动态管理方案的研究
(一) 降低成本, 提高效率
车辆作业流程的产生源于对物品诸要素 (收件人规定的时间段、重量、体积、货品类型、递送方式、跟踪要求/贵重物品) , 环境诸要素 (收件人地点、车辆禁驶区域和路段、街区宽窄、库房地点) , 车辆诸要素 (容积、载重量、车况、车辆类型、历史路况) 等诸多因素的综合自动规划, 由优化算法产生作业方案 (即目标、资源的合理利用和搭配) , 安排最佳的配送、揽收方式 (人或车, 专递或转递) , 最佳的行车路径, 最佳的收递顺序。目标是以最低的成本、最短的时间、最高的效率处理完成最大的业务量。
(二) 分析数据, 为决策提供依据
原配送体系的低速度、高成本瓶颈被突破后将衍生出基于高速度、低成本的新业务。利用作业系统数据库信息, 结合图形分析技术为管理层提供有力的运作分析数据, 为企业有效的经营决策提供依据。
(三) 提高承载能力
物流速度加快后, 业务承载量将加大, 系统可以方便地实现回程配货, 中心提前在线预知车辆的实时信息及精确抵达时间, 根据具体情况合理安排回程配货。
(四) 提高服务质量, 树立良好的企业品牌形象
车辆路径 篇7
车辆路径问 题 (VehicleRoutingProblem,VRP)由Dantzig和Ramser[1]于1959年第一次提出。该问题是指在客户需求位置已知的情况下,确定车辆在各客户间的行程路线,然后使得车辆路线最短或运输成本最低。车辆路径问题是个NP难题,在寻找满足约束条件最优解的过程中,需要很大的设计空间。设计空间是多维而非连续的,所以用来系统的搜索整个空间的规范搜索集很难找到,导致很难得到全局最优解。关于车辆路径问题的优化算法大致可以分为两类,一类是精确算法,另一类是启发式算法。目前,针对车辆路径问题,主要采用启发式算法。比如,树状搜寻 法[2]、节省法[3]、扫描法[4]、遗传算法[5]等。由于精确算法难以用于求解复杂的车辆路径问题,而启发式算法也只是基于直观或经验构造的算法,所以只能求出问题的某一特殊类型 或者是规 模较小时 的近似最 优解。由于这些问题的存在,本文将基于动态小生境的协同进化遗传算法引入到车辆路径问题中,从而更好地解决车辆路径优化问题。
1车辆路径问题数学模型
对于单配送中心问题,设配送中心共有N个客户,1个中心仓库,K辆车。每个客户的需求量和时间窗都有固定的限制,且均只被某辆车服务一次,每辆车只服务于一条路径。每辆车载重为Q且从配送中心出发,服务所有客户后回到配送中心。建立数学模型如下:
上述模型中,Z为运输距 离;i,j为客户编 号;n为客户量,k为车辆的顺序;Cij为从点i到点j的费用;xijk为1时,表示车辆从i出发到j,否则为0;需求点i的需求量为qi,yik为1时表示客户i的任务由车辆k来完成,否则为0。
式(1)表示以运行总成本最低的目标函数;式(2)保证车辆装载货物的总重量不超过车辆的载重;式(3)为每辆车都从配送中心出发;式(4)为每个客户指被一辆车服务并且所有的车都得到服务;式(5)为车辆完成任务后回到配送中心。
2基于动态小生境的协同进化模型
协同进化是指生物与生物、生物与环境之间在进化过程中的相互依赖、相互协调的依存关系。动态小生境集具有共享和协同进化的优点,通过进化过程形成峰值就是小生境,对于所有个体利用动态来分类这个峰值就是动态小生境。动态小生境集的动态性体现在种群被动态地分为若干个子种群,小生境的 动态性由 小生境的 核心部分 决定。协同进化模型能够自动的实现小生境的定位,这个动态模型能够消除分布不均匀的优化解,所以能够加快计算的速度,进而加快了各子种群的进化速度。
动态小生境的协同进化模型如图1所示。
3动态小生境协同进化遗传算法
(1)编码设计,生成初始种群。此问题采用自然数编码,这种编码比较直观,能够保证算法的性能,减小了编码后的计算量。
(2)适应度计算。染色体编码的欧式距离为:
其中,cx,cy为任意的两条染色体,k为个体索引,L为染色体长度。
个体cx相对于个体cy的共享函数为
其中,σ0为定义的小生境峰半径,α为共享函数的形状参数,α>0。
小生境数为:
N为种群规模大小。
动态小生境的动态适应度函数为:
染色体交叉操作示例如图2所示。
(3)操作算子。1选择算子———选择算子采取线性排序选择策略同时采取 排挤机制 的选择策 略,保留精英 个体;2交叉算子———通过交叉算子可以调整车辆路径,交叉操作是在两个完全不同的个体之间进行的,具体的交叉操作如图2:3变异算子———因为变异的可能性很小而且变异只起到辅助作用,所以对每代种群以变异概率pm进行变异,交换两点基因值。
4实验分析与结论
为了检验动态小生境协同进化遗传算法的性能,下面用该方法对车辆路径优化问题中的典型测试问题F系列:F-70,F-120和C系列:C-50,C-140等4个问题进行仿真实验。结果见表1和表2。
C-50的车辆优化路径如图3所示。
将本文算法与常规遗传算法对车辆路径优化问题的优化结果作横向比较,以进一步评判本文算法的性能。
Ombuki等的论文给出了常规遗传算法对车辆路径优化问题的优化结果,如表3所示。
为了测试新算法的运行效率,表4给出了动态小生境协同进化遗传算法与常规协同进化遗传算法达到收敛时的平均运行时间。当解与平均值差的绝对值小于10%时视为收敛。
车辆路径 篇8
1 建立数学模型
1.1 问题描述
车辆行进路径的优化可描述为:从供货中心使用多辆车向多个顾客点配货,每个顾客点的位置和需求量都是一定的,车辆载重一定,要求合理安排车辆行进路径,使总的行进路程最短,并要求满足下列两个条件:
(1)各个行进路径上各顾客点的货物需求量总和不能超过车辆的额定载荷;
(2)每个顾客点的需求必须能够得到满足,并且只能由其中一辆车进行配送。
1.2 建立模型
假设供货中心拥有K辆车,每辆车的额定载量是Qk,它一次配货的最大行进距离是Dh,需要向L个顾客需求点配货,顾客点i的货物需求量是qi,供货中心到顾客点i的距离是doi,顾客点i到j的距离为dij,再假设nk为第K台车配送货物的顾客数(nk=0指示为未使用第K台车),使用集合Rk表示第k条路径,它们中的元素rki表示顾客点rki在路径k中的顺序为i(不包括供货中心),当rki=0表示供货中心,则可建立以下优化物流车辆路径的数学模型:
2 遗传算法的基本思想
标准的遗传算法包括3个基本的操作:选择、交叉和变异。其步骤描述如下:
(1)产生初始种群,并评价初始种群中每个个体的适应度值。
(2)判断收敛准则是否符合条件。若符合,则输出相应的搜索结果;否则执行以下步骤。
(3)根据适应度大小按照一定方式执行选择操作。
(4)根据交叉概率Pc执行相应的交叉操作。
(5)根据变异概率Pm执行相应的变异操作。
(6)返回步骤(2)。
3 实例计算
根据上述遗传算法在Matlab中进行编程,并针对某轿车焊装车间为实例进行求解。
某轿车焊装车间有一库房供货中心,该供货中心坐标为(74,10),供货中心有5辆拖车,每个拖车最大载量为3 个标准托盘,需要向15个点送货,15个点的坐标和货物需求量见表1。
实验中采用下列参数;种群大小取80,交叉概率取值为0.65,变异概率取值为0.005,终止代数设置为200,在Matlab中随机求解10次,第2次就获得了最优解,最优解为1 524.2336m。各供货点和仓库坐标显示如图2,求解结果如图3。因此车辆路径具体安排如下:
(1)1-7-11-16-1;(2)1-15-9-8-1;(3)1-14-4-5-1;(4)1-2-13-6-1;(5)1-20-3-12-1。
4 结论
实验结果表明,运用遗传算法可以有效地快速地求得该轿车焊装车间车辆路径安排的最优解或近似最优解,很好地解决车辆路径如何安排的问题。
摘要：遗传算法是一种模拟自然进化过程搜索最优解的方法。通过建立某轿车焊装车间车辆路径问题数学模型,然后利用遗传算法求解该问题,最后在Matlab软件中进行编程求解,有效地求解出问题的最优解或近似最优解。
关键词：遗传算法,Matlab,车辆路径,焊装车间
参考文献
[1]蔡希贤,夏士智.物流合理化的数量方法[M].武汉:华中工学院出版社,1985.
[2]Holland J.遗传算法的基本理论与应用[M].李敏强,译.北京:科学出版社,2003.
[3]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社,2001.
[4]赵刚.物流运筹[M].成都:四川人民出版社,2002.
[5]陈国良,王煦法,庄镇泉,等.遗传算法及其应用[M].北京:人民邮电出版社,1996.
[6]姜大立,杨西龙,杜文,等.车辆路径问题的遗传算法研究[J].系统工程理论与实践,1999,19(6):40-44.
物流配送车辆路径优化的仿真分析 篇9
1配送车辆路径优化问题的提出
具体而言,此问题的目的在于完成货物配送任务的过程中,以最少车辆数、最小车辆总行程去完成,这样就可实现时间最短或成本最小的目标,在路径的优化方面,有启发式算法、精确算法等多种类型,但都不够完善,存在各自的缺陷,难以获得最短路径的最优解,而最近几年出现的遗传算法等存在收敛速度慢、求解时间长的缺陷,这使得其往往只能找到近似最优解,存在一定的局限性,而本文研究的蚁群算法表现为一种群智能优化,在巢穴和食物间的最短路径的寻找方面,其借助正反馈并行机制和蚂蚁间协作来实现,优势较多,如求解速度快、具有并行性等,有着广泛的应用前景[1]。
2建立数学模型
具体实施中,走什么样的路线进行运输显然是物流配送车辆调度的实质,在已知客户需求量及车辆载重量的前提下, 为实现需求且车辆的总行程最短的目标至少需要派多少辆车,这就是最小成本的配送方案的由来,需对以下条件进行满足: 首先是以配送中心为起点,对应的配送车辆能最终回到配送中心; 其次,每辆车只能服务一条路线,同时每个客户只被一辆车访问一次; 再次,以车辆的载重量为基础,每条配送路径上客户需求量之和不能超过它; 最后,则是不能重复走每辆车的路线。基于上述要求,显然找到一条最优物流配送路线即为物流配送车辆路径优化的目标,从而实现最小配送费用。 V = { v0,v1,…vn} ,v0为配送中心,客户的所在地用vi表示,设K为配送中心可最多用的车辆数目,对应的Qi则为每辆车载重量,这样,我们就可借助建立的数学模型表现物流配送车辆路径最优化算法问题[2]:
上式中,k辆车所配送的顾客点数用nk表示,而顾客点在路径k中的顺序为i则用rik表示,最优解的限制条件如下:
2蚁群算法主要内容
近年仿生优化算法的发展速度较快,得到了很大的应用, 蚁群算法主要通过模仿来取得问题的解决,该算法的基本思想主要是对蚁群的觅食过程进行必要的模拟,所求问题主要是可行解集,在最优解的求解,是借助蚁群的正反馈和分布式协作机制来进行的,利于对二次分配及作业安排调度等方面的求解。
3配送车辆路径优化的蚁群算法设计
首先进行的步骤为确定蚁群数目,对应的我们设有n个客户数,m为蚁群中的蚂蚁数,则有:
式中,t时间位于客户i的蚂蚁的数目即为bi( t) 。
另外,主要规则是对蚂蚁路径转移规则的研究,本文所探讨的物流配送车辆路径问题中,其转移概率势必要对下一个客户点路径长度和路径上的信息素浓度进行考虑,物流配送中心可用O表示,j表示能够访问的客户点。这样,k到i向j选择转移的公式如下:
若j∈Q,否则( 4) 式中,tij表示i到j所有d时间,tij表示权重系数,β 表示期望启发式因子,α 表示信息启发式因子,ηij( t) 表示与路径( i,j) 相关联的启发式信息值:
再次,为信息素更新规则。为了充分利用循环最优解,需要对不同蚂蚁信息素进行循环,循环之后进行更新,如下公式:
其中,信息素挥发系数为 ρ,表示为[0,1]间的随机数,信息素残留因子用1 - ρ 表示,而本次循环过程中路径( i,j) 上的信息素增量则用 Δτij( t) 表示,对应的,本次循环中残留在路径( i,j) ,第k只蚂蚁的信息素总量用 Δτkij( t) 表示,继而出现:
其中,Q在式中作为常数,既信息素浓度,第k只蚂蚁在一次循环中的路径用Lk表示。
4车辆配送路径算法的实现
当前物流业发展中,对车辆配送路径优化问题的求解方面,借助于蚁群算法的方式,可借助人工蚂蚁替代车辆来服务客户点来实现,返回到配送中心的标准是下一个服务客户点会使运载总量比最大距离超过一次最远行驶距离或是汽车载重量更多的时候,不同车辆完成的此次运输,在此基础上,车辆可以对其他客户进行全方位服务,继而该车辆的人工蚂蚁就可以完成一次巡游标志,该标记是对客户进行的一次服务, 一次服务也可以是一次循环,之后,需要根据蚂蚁巡游路径的好坏程度将其他信息素进行分配,从而更好的对信息素增量进行不同程度的更新,以此进行不断的更新,得到最优路径或是选择相同路径,这样就可以完成求解了。
5结束语
综上所述,本文为达到对物流运输系统中车辆的路径的合理规划,本着对物流企业经济效益提高的目的,积极分析了物流配送车辆路径优化问题,后续研究中利用蚁群算法鲁棒性强等特点,在对此问题进行求解的方面提出一种基于蚁群算法,后续检验证实,本方法提高了寻优效率,对于最优解能快速找出,此方法具备了广阔的应用前景。
摘要：当前物流行业发展中,基于行业的发展需要,以及传统物流在降低物流运输成本方面无法克服的短板,急需进行物流配送车辆路径优化,从而有效地降低物流配送成本,基于此,文中提出一种蚁群算法的物流配送车辆路径优化算法,旨在建立数学模型的基础上,对物流车辆路径的问题采用蚁群算法进行求解优化,后续实验得出,该算法效果显著,利于对物流配送成本的降低,对于当前物流企业的发展意义重大。
车辆路径 篇10
相比弱动态度动态车辆路径问题中等动态度动态车辆路径问题中动态顾客比例较高通常占到50%左右, 对于这类问题, 常常采用基于概率信息模型的A—Priori优化方法求解。与以往研究不同的是本文旨在研究在假设条件下如何构建描述中等动态车辆路径的数学模型, 并构造杂交蚂蚁算法, 进行求解并与Benchmark Problem的基本蚂蚁算法的求解结果进行比较, 证明算法的可行性。
一、数学模型
中等动态度车辆路径问题要兼顾并平衡好行驶总距离和减少顾客平均等待时间这两个目标, 由此可建立如下的目标函数:
Objective min公式 (1)
这里, 是总行驶距离, (符号的意义同公式 (4-1) ) 。是权值, 表示到达顾客v的时间, 是顾客v需求服务的截止时间。
二、杂交蚂蚁算法简介
蚂蚁工作方式的本质是:1.迹越多的路径, 被选中的概率越大, 即选择机制;2.路径越短, 在上面的迹增长得越快, 即迹更新机制;3.蚂蚁之间通过迹进行通信, 即协同工作机制。
选择机制和迹更新机制构成正反馈机制, 在蚁群的协同作用下, 正反馈过程使得越来越多的蚂蚁选择最短的路径。本文用蚂蚁算法和局部搜索算法相结合 (称为杂交蚂蚁算法) 解中等动态度车辆路径问题:
杂交蚂蚁算法是结合局部搜索算法的蚂蚁算法。下面用TSP为例来解释杂交蚂蚁算法。把TSP表示为一个图, V表示城市的点集, E是连接城市的边。算法开始时, 把m只蚂蚁按一定规则分布在各城市, 每只蚂蚁的任务是建立一个解, 即从各自的起始城市开始完成一个环游。环游是一个城市接着一个城市地进行的, 位于城市r的蚂蚁k根据某种选择策略选择下一个要去的城市s (选择策略) , 选择原则就是在与城市r连接的所有边中, 边长越短边上的迹越多的边, 蚂蚁就以越高的概率选中这条边, 当到达下一个城市时, 蚂蚁就适当减少边上的迹 (局部更新) , 从而其它蚂蚁以较低概率选择这条边, 以免得到许多相似的解。当所有蚂蚁都建立了各自的解, 则以各自的解为起始点, 用局部搜索算法 (3-OPT) 求局部最优解。最后, 根据局部最优解的好坏更新其边上的迹, 原则是越短的环游, 增加越多的迹 (全局更新) 。迹更新结束后, 开始下一轮迭代。算法概述如下:
Step1:初始化迹;
Step2:下述过程迭代次:
1.每只蚂蚁根据选择策略建立一个新解, 同时局部更新迹;
2.以所建立的解为起始点, 求局部最优解;
3.根据局部最优解全局更新迹。
三、中等动态度车辆路径问题的杂交蚂蚁算法
把中等动态度车辆路径问题 (P) 表示为一个图, V是n个点的集合, 分别表示解的n个分量, U是L个点的集合, 是分量i的最大可能取值, V中的点i与U中的点有边相连。是边上的迹。如果V中的点i与U中的点j无边相连, 则, 迹矩阵是一个n行L列矩阵。
算法开始时, 所有蚂蚁都集中在第1个分量处, 每只蚂蚁按照选择策略选择一条边, 当选择完一条边后, 马上更新该边上的迹, 当m只蚂蚁都选择好各自的第一个分量的值后, 都集中到第二个分量处, 直到选择完第n个分量的值, 从而建立了m个解。以所建立的m个解为起始点进行局部搜索, 根据得到的局部最优解计算迹的增量, 全局更新迹。全局更新迹后, 继续迭代, 直到满足停止条件, 停止条件是最大迭代次数。
1.初始化。由于杂交蚂蚁算法利用局部最优解计算迹的增量, 因而迹的初始值取为, W是常量, 蚂蚁总数取。
2.改进的选择策略。位于i个分量的蚂蚁, 按下列公式选择边:
该公式表明, 迹最大的边以高概率0.9被选中, 其余的边以概率0.1参与选择, 而在这些初始解中, 的取值范围是所有可能取值, 这样, 按公式 (5-3) 选择时, 迹最大的边仍然以很高的概率被选中, 造成算法太快收敛到次优解。本文缩小了的取值范围, 使得蚂蚁不仅以概率0.9选择迹最大的边, 而且以概率0.1选择非最大迹的边, 这样, 在每次迭代时可以建立不同的解, 在利用最大迹的同时加大对解空间的探测力度, 使算法不会太快收敛。实验结果表明, 改进的算法大大提高了得到最优解的概率。
3.局部更新。当蚂蚁k选中边后, 就更新边上的迹:
其中:是上轮迭代得到的迹矩阵中第i行前i个元素的最小值, 这是动态变化的。从公式 (5-4) 知, 更新后的迹是原来的迹与最小迹的凸组合, 这使得迹的减小基于可供选择的条边上的迹的相对大小。由于公式 (5-2) 以概率0.9选择条可供选择的边中迹最大的一条, 因而蚂蚁常常选中迹最大的边, 第一只蚂蚁选中它后, 就更新该边上的迹, 使迹的值小了一点;第二只蚂蚁选中它后, 也是这样, 结果是当迹最大的边被多次选中后, 迹的量减少到条可供选择的边上的迹的值的平均水平, 从而蚂蚁选中其它边的概率增加, 增加了所建立的解的多样性。
4.局部搜索算法。当m只蚂蚁都建立好各自的解, 分别以这些解为起始点作局部搜索。局部搜索的邻域定义为, 其中是第i个分量为1, 其余分量为0的n维向量。邻域搜索算法如下:
Step 1:任给一初始整点;
Step 2:若是问题的局部极小解, 停机;否则, 检查的邻域, 找到一整点, 使得。
Step 3:令, 转Step2。
5.全局更新。当所有蚂蚁都得到局部最优解, 就全局更新所有边上的迹, 公式如下:
括号中第一个数字为最短距离 (单位:千米) , 第二个数字为等待时间 (单位:分)
括号中第一个数字为最短距离, 第二个数字为等待时间从表1, 2可以看出, 用杂交蚂蚁算法计算的结果好于用基本蚂蚁算法计算的结果。
其中:是参数, ;是边上的迹的增量, 是蚂蚁k建立的解做局部搜索后得到的局部最优解的目标函数值。公式 (5) 表明被越多蚂蚁访问过的边得到越多的迹的增量, 同时所有的边上的迹都蒸发掉一部分, 避免迹的无限增长。
下面具体给出解中等动态度车辆路径问题的杂交蚂蚁算法的描述。
(l) 初始化阶段
令;在内随机产生m个解作为起始点, 做局部搜索, 求出最小的局部最优解, 以及相应的目标函数值;令初始迹;并为每条边赋初始值;
(2) 迭代
for num=1 to Imax do
(1) for i=1 to n do
For k=1 to m do
begin
根据公式 (5-2) 求第i个分量的值
按公式 (5-4) 更新边上的迹;
end
(2) 以得到的m个解为起始点, 根据本文给出的局部搜索算法求局部最优解及目标函数值;求出该轮迭代的最小目标函数值then
更新迭代以来的最小目标函数值及解, 以及该轮迭代所得到的解;
(3)
输出最小目标函数值以及相应的解
四、数值计算结果
我们用http://www.dcs.st-and.ac.uk/apes/apedata.html[1]中的标准中等动态度车辆路径问题数据测试了本文提出的杂交蚂蚁算法的性能。http://www.dcs.st-and.ac.uk/apes/apedata html中的标准中等动态度车辆路径问题是由TAILLARD (1994) , [2]Christophides (1984) [3]和Fisher (1981) 中所提出的标准静态车辆路径问题转化而来的。我们考虑25个顾客和1个仓储中心的中等动态度车辆路径问题。在标准问题中, 位置数据是随机产生的。在计算过程中, 蚂蚁的数目等于当前顾客的数目, 一个顾客分配一只蚂蚁。计算结果见表1, 2。
参考文献
[1]http://www.dcs.st-and.ac.uk/apes/apedata.html
[2]Taillard E.Parallel iterative search methods for vehicle routing problem[J].Networks, 1994, 23 (8) :661-673