基于遗传算法的多辆洒水车最优路径求解(其中包含MATLAB的一些关键语句说明和FloydDijkstraEuler算法的综精品资料.doc
《基于遗传算法的多辆洒水车最优路径求解(其中包含MATLAB的一些关键语句说明和FloydDijkstraEuler算法的综精品资料.doc》由会员分享,可在线阅读,更多相关《基于遗传算法的多辆洒水车最优路径求解(其中包含MATLAB的一些关键语句说明和FloydDijkstraEuler算法的综精品资料.doc(47页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、广西工学院毕业设计(论文)说明书摘要车辆路径问题可以分为以点为服务和以边为服务两种,洒水车问题是以边为服务的一个子问题。作为容量限制弦路径车辆行驶问题(CARP)的一种实际应用,洒水车路线规划涉及带有一定容量限制的总行程最小,以及多辆洒水车工作的合理分配问题,属于复杂的N-P难车辆路径优化问题。因此,在容量限制下实现作业车的总行驶路径最小,节约成本,提高效率,成为我们研究的中心环节。本文采用了遗传算法,对多辆洒水车线路优化问题进行了容量均衡性方面的研究。首先在矩阵计算过程中采用了Floyd和Dijkstra算法求解了作业区域上任意两点之间的距离,以及指定两点之间的具体路径,为车辆的部分路段行驶
2、获得了指向。接着对洒水车作业图的奇数度点进行随机匹配,从而把洒水车的作业图补成了每个顶点都是偶数,这样就可以获得一条Euler回路,即对应一个花费数值。然后通过遗传算法,初始化,编码,解码,适应度函数的计算以及选择,交叉,变异等一系列操作,最终获得一条花费最小的Euler回路。最后对这条回路进行分割,从而实现多辆车之间的作业分配。本文通过引用柳州市区的一部分区域地图进行实验,获得了比较理想的结果,并服合一定的现实意义。关键词:路线优化 遗传算法 匹配 Euler算法AbstractVehicle routing problem can be divided into the service f
3、or points and the service for sides, while sprinkler service is a subset of the side problem. As a practical application of CARP(Capacitated ARC Routing Problem) ,the sprinkler route planning demanks the total trip Minimum with a certain capacity and shares alike the work .So it is the complexity of
4、 VRP(Vehicle routing problem).In order to achieve the total trip minimum, to increase the least cost and increase the efficiency that becomes the central link of our research.In this paper, we use the genetic algorithm to research how to finishes the sprinklers work equal. First of all, we apply the
5、 the Floyd and Dijkstra to achieve the distance between any two points and the specific path between two cettain points, which provide a method for the car to some setions road.Then the point of odd-degree random match in the routing graph,in this way, we can change the degree of every vertex into e
6、ven.This can be an Euler circuit, which corresponds to a cost value.Whats more, through the genetic algorithm, initialization, encoding, decoding, the calculation of fitness function, as well as selection, crossover, mutation, such as a series of operations, eventually we get the answer.In the paper
7、,we use Part of the liuzhou mapto experiment,and obtain a more satisfactory results,in the same time show the algorithm has practical significance. Key words: path optimization , Genetic Algorithm,matching; Euler Algorithm目 录Abstract21绪论41.1 研究的目的和意义41.2 车辆路径问题的国内外研究现状41.3 主要研究内容52洒水车路线优化问题72.1 路径优化
8、问题72.2图论的相关知识和算法72.2.1Floyd与warshall算法92.2.2Dijkstra算法92.2.3Euler算法102.2.4奇数度路口的匹配112.2.5遗传算法113单辆洒水车的路线优化143.1问题及模型描述143.2 路径优化设计思路143.3 实例分析154多辆洒水车路线优化184.1多辆洒水车路线优化的描述184.2 多辆洒水车路线优化的设计思想194.3 实例的设计与实现204.3.1洒水车路线优化问题的编码214.3.2奇数度点的初始化214.3.3解码及洒水车行进路线的获取224.3.4计算目标函数254.3.5选择算子264.3.6交叉算子274.3.
9、7变异算子284.3.8参数设计294.3.9多辆洒水车行进路线的分配29结束语32参考文献33致谢341绪论1.1 研究的目的和意义在经济高速发达时代,人们绞尽脑汁地节约投入的成本,人们费尽心血地研制出更加高效的生产工具,人们不断完善人力资源的调度理论,其目的就是为了获得高效的工作效率,合理地人力资源配置。人们生活方式的自动化水平是一个反映时代的发展的标志,随着人们生活水平的提高,人们也更加地关注着他们所生存和发展的环境,人们所生活的环境,空气的清净度对人们的健康有着重要的意义。为了能够更地完成城市的除尘工作,实现最低的成本花费,高效的工作效率,合理的人力资源配置这一目标。如何合理地对洒水车
10、的作业线路进行优化将成为本课题的核心。由于洒水车的作业是一个N-P难问题。如何合理地规划洒水车的作业路线,从而减少不必要的行驶路程,不但可以更好地提高工作效率,而且可以可以有效地节约燃油的成本,对本课题的研究具有重要的现实意义。同时当我们为了提高洒水车对城市除尘工作的效率,而使用了多辆洒水车同时工作时,如何地分配好各辆车之间的作业路线,在保证高效的同时做到燃油的花费最小,将比单辆洒水车的除尘应用更加具有现实意义。1.2 车辆路径问题的国内外研究现状洒水车问题是以边为服务的问题。类似的还有冬季除冰车,城市垃圾回收,以及最古老的中国邮递员问题都属于ARP问题,由于它们都存在有一个共同的特点,即容量
11、限制的问题,因此洒水车的问题又称为CARP问题的一个扩展问题。而CARP问题属于N-P难问题。对于小数量的(20条边或弧以内) 还可以用精确算法来来解决(分为整数规则和分枝定界),但是实际问题往往规模较大,如果仍采用精确算法,在运行时间和计算的复杂度将出现瓶颈。到目前为至,虽然国外对边服务的论文仍比较少,但较于去年的研究情况。关于洒水车方面的论文开始有一些了,如邓欣等人在2007年,针对单车场洒水车线路优化问题,将路径优化问题转化CARP的扩展,提出了改进遗传算法OX交叉和局部搜索(local search)的方法,通过实际生活的例子验证了算法的可靠性和适用性,从而保证算法在解决一定规模的CA
12、RP具有一定的实用价值1。李小花等人在2008年针对多车场洒水车路线优化的问题,将传统遗传算法的种群结构进行改进,提出了车辆的时间约束来保证各辆车工作时间的均衡性,即使效果并不理想,但仍有一定的参考价值2。刘建辉等人在2008年,针对多车场路线优化的问题,提出了一种双层遗传算法,处理了车场与路径的分配,以及每条路径的服务弧之间的优化问题,对人力资源的优化和减少车辆总行程,取得了很好的效果3。朱征宇等到人在2008年针对复杂CARP问题中的多车型,多路型等因素,以传统的遗传算法为基础,提出了一种高性能遗传算法(HEGA),使得染色体代表的含意截然不同,同时加入了重优化措施的收入,防止了随着迭代次
13、数的不断增加,优化曲线逐渐平缓,算法将会收敛,而此时可能并没有达到全局最优,这些算法和设计思想均对现实问题的考虑提供了很有价值的参考4。但正刚等人在2006年针对CARP的求解问题,研究了CARP与CVRP的转化,提出了小环路方法(实质为禁忌)来求解CARP,验证了算法的准确性和效率,为实际应用奠定了基础5。 同时针对车辆线路优化的均衡性问题,认识到了LU算法在时间对车辆的均衡性的约束不够,从而提出了一种新的算法,主要的思想为牺牲了车辆路径的饱和来实现车辆路径的均衡性6。贾立双等人在2008年针对,单车场车辆调度问题,提出了一种综合运用最邻近算法和遗传算法的相关原理组合实现了单车场多车型的调度
14、7。李松等人在2007年针对大规模车辆路径中存在的缺陷,提出了Sweep分区技术和分区的禁忌搜索算法与相邻区域的优化技术相结合,有效解决了大规模车辆路径的优化问题8。付彤等人在2006年针对一般网络上单车型车辆配送问题,借鉴Floyd算法与节约路径法,构造出一种在所用车辆数最少的条件下,使总配送里程最短9。张涛等人在2002年针对车辆数目不确定的车辆路径优化问题,提出了遗传算法GA和禁忌搜索算法TSA相结合,主要以GA为主,把TSA用在GA的变异操作中,从而获得了最小化距离和最小化车辆的双目标优化10。陈文兰在2007年讨论了VRP问题的分类,以及介绍了近年来的相关算法的主要成果11.。相对于
15、(容量限制弧的边路径问题)CARP,国外的应用相对国内而言,就多一点。Maria Candida Mourao在2004年针对垃圾回收问题的求解,提出了一种新颖的HM启发式算法12。Anita Amberg等人针对M-CARP问题提出了一种禁忌搜索算法,不过对于M-CARP的问题的研究还处于初步探索阶段,能查到的相关文献不多13。Dino Ahr在06年针对中国邮递员问题利用了一种禁忌搜索算法,但是中国邮递员的最大最小解属于N-P难问题,因此,在论文中主要依赖启发式算法产生近似解。同时,在许多情况下人们所能得到的解也是近似或更优的解14。Jose Brandao在2006年针对CARP问题提出
16、一种基于禁忌搜索的启发式算法,在应用到标准例子的各种情况下,得到结果,说明了算法处理的过程可以在合理的计算时间内得到较高的准确性15。 洒水车的路径优化的问题,要考虑的问题还是有很多的。就单一的目标:要求路径最短而言。当道路的情况多种时,如单行道(要求只能从某个方向行驶),双边道路(中间有绿化带),道路中有上下坡的(要求下坡时洒水),还有在某个十字路口只能左转或右转的限制是时,都需要对算法作出一定的修改。当在城市的道路中加入了一定数量的加水点(水桩)时,就要对洒水车加水点选择的优先性进行考虑。当为了提高洒水车除尘的效率,引入多车辆同时工作时,就要对洒水车间的路径分配的均衡性问题进行考虑。还有当
17、有多个车场时,道路与车场的分配问题,对道路除尘时,对车型容量的选择(多车型)等等都会限制算法的适用性1.3 主要研究内容在原来单辆洒水车的基础上,实现多辆洒水车的线路优化问题。由于原来做的是单辆洒水车在无限容量下的情况,这样一来,只要形成一条最短回路就可以了。现在要做的是,把这种无限容量下的路线优化变得现实一点,即把无限容量的的情况考虑成有容量限制的情况,这样不但增加了课题的复杂性,而且实现了课题的现实性,在单辆洒水车现实性的前提下,为了可以更好地提高洒水车的作业效率,实现多辆洒水车同时进行城市的除尘工作。本文的研究内容主要有以下几个方面首先从线路优化问题出发,介绍了常见的两类线路优化问题VR
18、P和CARP,分析了两者的应用区别,明确洒水车线路优化问题的数学模型,并说明了洒水车在线路优化的具体设计时用到的一些算法,其中遗传算法是整个寻优求解的中心环节,而warshall,Dijkstra,Euler算法只是作为遗传算法解码计算的辅助算法。其次介绍了单辆洒水车线路优化的总体设计思路结果。最后对多辆洒水车线路优化问题以多辆车作业分配和总行程最小为目标,提出了容量分割的方法并进行了详细的设计,包括路线优化的模型描述,设计原理,编码的方式与确定,种群的初始化,如何对染色体进行解码,转换到问题的现实解(难点),计算目标函数及适应度函数和各种操作算子进化方式的确定(重点)。本文用MATLAB7.
19、0在Window XP下进行编程并调试,并对实验结果进行了比较和分析。2洒水车路线优化问题2.1 路径优化问题说到路径优化问题,我们会很自然地就想起车辆路径问题(Vehicle Routing Problem,VRP),因为配送问题在商业领域的应用十分广泛。VRP的一般描述为:用于送货的若干辆相同型号的车从配送中心出发,到不同的地理位置的客户那里去送货,然后返回配送中心,要求每辆车只能出发一次,任何一个客户有且只有一辆车访问,并且所配送的货物不能超过车辆的载重量,求解一种配送方案使得配送总成本最少。VRP问题根据不同的标准可以分为不同的类别。根据车辆是否有容量约束,可分为有容量约束的VRP问题
20、(货担郎问题),和无容量约束的VRP问题(TSP问题);根据货运任务的完成是否有时间要求,又可分为有时间约束和无时间约束两种。对于有时间约束的VRP还可以进一步分为带软时间窗的VRP和带硬时间窗的VRP。从1959年的VRP问题的开始提出到现在的半世纪以来,国内外对VRP的研究已经相当成熟,在各类VRP(如有时间窗、多车场等)的研究上都取得了丰富成果,采用的解决方法也多种多样,可分为精确算法(如整数规划、分枝定界等)和启发式算法(禁忌搜索、遗传算法、蚁群算法等)两大类。还有另外一种路径问题,也是本文的路径优化问题,那就是与VRP相类似的弧路径规划问题(Arc Routing Problem,A
21、RP)这类问题在基础设施中的应用就相对就要多一些。本文研究的洒水车的路径优化问题就属于特殊的ARP问题,由于洒水车的城市除尘作业,车辆本身带有容量限制,因而洒水车路径优化问题属于“容量限制弦路径车辆行驶问题”。有容量限制的ARP,在现实中拥有广泛的应用背景,如前面提到的洒水车作业路线安排,以及冬季除冰车作业路线安排,城市垃圾车作业路线安排,还有城市输电线路的检查等。这时,我们会提出这样一个疑问:在前面的提到的两种路线优化问题中(VRP问题与CARP问题),它们都可以有容量限制方面的约束条件,到底是怎样的一种分类方式把它们分成了两种不同的路线优化问题。这个划分的关键就在于它们在线路优化中的具体服
22、务的对象是不一完全一样的,对于VRP问题而言,它主要是以点的服务主,而对于CARP问题,它主要是以边的服务为主。如果说到了这里还是不大清楚,也许可以通过一个问题的对比来说明。例如VRP问题中的车辆的配送问题(不带时间窗的),因为车辆要装载货物,因此有一定的装载容量。同样的对于CARP问题中的洒水车路线优化问题,车辆本身就有一定的装水容量。这是相同的地方。然而不同的就是它们的服务对象是不同的。车辆的配送只要把货物送到指定的点就可。配送的本质在于遍历所有的点,所以不用遍历所有的边。而洒水车的路线优化则要遍历完所有的边。边集往往包含了点集,而点集不一定可以包含边集。也正是因为这点的不同这两类问题在路
23、线优化时,即有相似点,但又不相同。2.2图论的相关知识和算法图论中所讨论的”图”,不是微积分,解析几何,几何学中讨论的图形,而是客观世界中某些具体事物间联系的一个数学抽象。如二元关系图,在关系图,在关系图中,我们不考虑点的位置及边线的长短曲直,而只关心哪些点之间有线相连通。这种数学抽象就是”图”的概念。图论在洒水车路线优化过程中起到的作用是:实现客观道路网到数学模型上的抽象。图是一个三元组,包括结点集合,边集合以及关联函数。无向图:每条边都是无向边的图称为无向图。有向图:每一条边都是有向边的图称为有向图。连通图:如果无向图G中每一对不同的顶点X和Y都有一条路,则称G是连通图。强连通图:如果有向
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于遗传算法的多辆洒水车最优路径求解其中包含MATLAB的一些关键语句说明和Floyd,Dijkstra,Euler算法的综
链接地址:https://www.taowenge.com/p-96699212.html
限制150内