铺沙车最短路径规划的优化算法

铺沙车最短路径规划的优化算法

1铺设路径及轨迹优化问题在车辆路径优化中，车辆路径优化实际上存在两个情况。其中之一是交通路径优化（rp），该模型以抽象为服务对象，物流中心对超市的商品销售。其次，道路优化（arcrobottal.a）包括城市照明路径配置和铺沙道路配置。为了从不同角度说明问题,分两层模拟:第一层假定卡车的载沙量足够大,即装载一次就可以完成所有街道的铺设任务;第二层加入铺沙车运量的限制,即装满一车沙只能铺设一定距离;对于第一层而言,就是让一辆铺沙车以最短的距离将图中的每一条单行线按所指示的方向遍历一遍。对于第二层,显然是不能将所有的单行线铺上沙的,需要安排若干辆车去完成铺沙任务,在确定铺沙车数量的情况下,对所有车的路径进行整体的优化。1节点选择导致的算法针对此问题,笔者建立如下合理的假设:起点站的运沙车数量不受限制;铺沙车在铺完沙以后,最终要回到起点站;铺沙车在对一条路进行铺沙时,不会半途而返,即一旦驶入某一条路,那么就一定要将该路铺完;在第二问中,车行驶单位路径的费用是恒定的。首先给出所要求的目标函数:其中,eij表示第i个节点到第j个节点的街道的长度,如果第i个节点到第j个节点之间没有直接的单行线连接,则令eij为∞,xij表示eij被走过的次数。对于xij进一步的说明为:接着,考虑约束条件,对于每一个节点,出度与入度要相等:上式左边表示对所有从i发出的单行线条数求和,即出度之和,等式右边表示对所有进入i的单行线条数求和,即入度之和。约束条件二,对于存在街道eij的节点i,j,则eij前的系数一定要大于等于1,于是得到最终的规划模型为:紧接着,着手第二步,即按照欧拉回路的方法寻找出一条路径作为铺沙车的巡行路径。定义图G(V,E),V为节点集,E为边集,对于任一节点v0∈V,deg(v0)≠0,deg(v0)表示节点v0的度,所以一定可以找到e1=〈v0,v1〉∈E,若v1=v0,则找到了G的一条回路。否则,又由于deg(v2)为偶数,可以找到e3=〈v2,v3〉∈E,且e3≠e2,e3≠e1。若v3=v0,则找到G的一条回路。如此进行下去,每边仅取一次,并且没到一个节点就沿着该节点的关联边中没有走过的一条边走,只有当没有其他选择时才选未走过的边所构成子图的割边走。因为E是有限集,故一定存在e1e2Len,使en的终点为v0,从而构成G的一条欧拉回路C:v0e1v1e2Lvkek+1Lvn-1env02车辆数和容量限制当加入了对铺沙车运输量的限制,也就是说,仅用一辆车是不能把它铺完的,而如果一定要使用一辆车的话,那么这一辆车就要走若干趟,在此有必要首先弄清楚车的辆数与每一辆车需要走的趟数之间的关系。目标函数为使所有路径的总花费值最小,即:其中,Ti表示第i辆车巡行所产生的圈;cost(Ti)表示第i辆车的花费;k表示车辆数,在此经过前面的分析确定为4。容量限制条件:针对一辆车完成一个圈这一任务,设每个路径Ti中包含的铺沙任务为Ti1,Ti2,LTijL,Tini(Tij表示圈Ti中的需要铺沙的第j条单行线,ni表示圈Ti中要铺沙的单行线的总数目),一条单行线被某一辆车铺了以后就不能被其它的车铺。q(Tij)表示Ti中的需要铺沙的第j条单行线的长度。Wi表示第i辆车的装载量。则即某一辆车完成其铺设任务所铺下的沙量要小于等于它的装载量。花费函数:圈Ti的花费为:从道路养车站出来,到第一个任务街道的最短距离,加上第二条街道的长度,加上第二条街道到第三条街道的最短距离,累加到最后一条街道,然后加上最后一条街道长度和最后一条街道到道路养车站的最短距离。即:其中,q(Tij)表示Tij的长度,d表示最短路。每个服务边都被服务:表示要铺设街道总数目)定义了集合Rk,Rk中的元素由第k条路径中的要铺沙的街道组成。任意两条路径中不能有重复的服务边,也就保证了每个单行线只能被一辆车服务一次:综上所述,目标函数与约束条件,目标函数为:3遗传算法编码实质上检讨的是一个容量约束的边寻路问题(CapacitatedareRoutingProblem)。已经证明出这个问题是一个NP难的问题,所以利用常规方法难于求解,现利用遗传算法求得满意解。算法可分为以下几个部分:(1)输入预处理。首先,要输入图的邻接矩阵。其次采用Floyd算法得到任意两点之间的最短距离矩阵D,以及前驱矩阵P(用以记录路径)。第三对边按照一个顺序进行编号,构造一个矩阵,矩阵的第一列表示了边的序号,第二列表示了边的起始节点的编号,第三列表示了边的终止节点的编号。(2)遗传算法的编码方式。首先,染色体数据结构为一维数组,长度为m(弧的总条数),由m个不同的整数组成(取值范围是1-m)。其中每一个整数就代表了一条服务弧,例如整数i(i∈1,…,m)就代表了弧i。初始化染色体就是生成CNum条染色体,对每条染色体进行随机赋值从而生成初始种群。假设有5条边需要铺设沙子,初始种群需要生成3条染色体,则初始后的种群可能为(Chrom1=2,1,4,3,5;Chrom2=5,2,3,1,4;Chrom3=1,5,3,2,4)。其次,由于上面的编码方式要求每个染色体的元素不等,不方便于实际问题的处理,将原自然数编码转变成为grefenstette码。grefenstette码的优点在于对于变异函数的要求低,对于编码元素没有互异的要求。(3)遗传算法的解码方式。利用congrefenstette解码方法将grefenstte码转变成为自然数编码;再将自然数编码对应成为相应的的路径。4双向街道铺沙优化模型现给出南方某一城市某一街区的示意图,弧表示街道,数据表示街道的长度,单位:m;结点表示街道的交汇处,一共有12个结点。假设街道养路站位于交汇点1处,铺沙的任务由养路站负责,所需要的沙和所使用的卡车都在该养路站内。箭头表示单车道方向,对于双向街道,必须按方向要求为每个方向的车道分别铺沙;对于某条单行线,允许因铺沙需要而多次通过(见图1)。现需解答如下的问题:(1)假设卡车的载沙量足够大,即装载一次就可以完成所有街道的铺设任务,在此情况下为铺沙车选择一条路线,使得完成所有路面铺沙任务所需的路程最短。(2)现在加入铺沙车运量的限制,如装满一车沙仅能铺设1500m,此种情况下又该如何完成铺沙任务。(3)进一步加入限制条件,每辆车不仅装载量有限,而且空车与载重车所需要的运输费用也有差别,又该如何完成任务。根据建立的模型,第一问结果如下:这两条路径的总长为6059m。其中,数字1到9分别表示图1中的前9个节点,字母ABC分别表示节点10、11、12。第二问结果:共需要4辆卡车,4辆卡车的路线如下:四条路径的总长6943m5启发式算法的优缺点建立的模型具有推广性,可适用于铺沙车、洒水车等多种针对路径服务的公共问题。其中3个模型步步加强,越发的贴近实际,可分别从3个方面、3个层次指导实际中的铺路问题。其中,小规模、简单的约束问题就可直接用lingo规划求解。约束复杂时,就采用启发式算法,而且问题的规模越大时,越可以体现出启发式算法的优点。对结果的分析细致、到位,在短时间内尽量多地考虑到了各方面的问题。如在解决问题一时,还考虑到了某一条街道不铺的情况,在这种情况下对总的费用的影响,由此对于原问题就有了比较性和指导性,从而可以对有关的部门提出合理的建议。详细地突出了各个问题及模型之间的主要区别,并妥善地处理了这些差别。但是,模型在问题中未能给出加入某一条街道后对总的费用所造成的影响,这主要是由于难以确定加入的路径的具体长度,而这一长度对总费用又是有所影响的。同时,问题未能确定给出的是否是最优解,而仅能确定给出的是满意解,这是