含有车辆限行站的弧形路径问题.doc_第1页
含有车辆限行站的弧形路径问题.doc_第2页
含有车辆限行站的弧形路径问题.doc_第3页
含有车辆限行站的弧形路径问题.doc_第4页
含有车辆限行站的弧形路径问题.doc_第5页
已阅读5页,还剩11页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

含有车辆限行站的弧形路径问题:费城经验11.1 引言在住宅区固体废物收集工作中,车队可能由不同容量、大小和形状的垃圾车组成。每一组相同的车辆组成一种车型。小容量的汽车比大容量的汽车满载更快、配送到到处理设施(如垃圾填埋场)的批次更多。每种车型的路线有一个限制,就是要遍历其服务的街道,而较大车型的车辆不能穿越只能承受特定重量的小巷或桥梁。一些街道允许某些车辆(例如舷侧装卸货环卫车辆)通过但不允许其提供服务,因为街道太窄了这种车型的车辆无法开展服务。由于城市中的一些限制,街上会设有车辆限行站(Vehicle-site dependencies)用来禁止特定类型的汽车穿越街道或者提供服务。因此,一个街道的车辆限行站反映了某类汽车能否服务或遍历这条街。CARP-VSD问题实际上是含有车辆限行站的CARP问题。在目前的学术研究中,CARD-VSD问题是一个几乎不被涉足的领域,Nag的论文是我们唯一熟知的关于解决CARD-VSD的论文。CARP-VSD是CARP的一般化问题。在CARP问题中,有一个定向连接的网络G =(N,A),其中N为节点集,A为连接弧的集合,还有一个指定车型的车队。在网络G中,弧线上的服务时间已知,可以遍历所有弧,空时返回时间已知。CARP问题里将G中要计算的弧划分为时间相同的几个服务分区(此处的时间指的是服务时间加上空时返回时间),每部分弧有顺序的排列,使得遍历所有弧形成连续路径的总附加空时返回时间最小化。在此类CARP问题中,任何车辆可以分配给任何服务分区,在解决方案中也可以任意采用,具体见Assad and Golden,Eiselt,Gendreau,and Laporte,Bodin et al.Golden and Wong,Pearn,and Laporte.等人的论文。本章的重点是研究解决CARP-VSD问题的有效方法。因为解决CARP-VSD的合理方法是存在的,并且这些方法可以用于很好地解决CARP-VSD中一般旅行路线方面的问题。本章重点是求解CARP-VSD的实用分区方法。这些分区方法结合旅游路径生成过程来获得一个整体算法来解决CARP-VSD。这个算法被称为车辆分析算法(VDA)。VDA的一个基本假设是,如果一个特定容量的车辆可以在特定街段服务(或从中空车返回),那么其他更小容量的车型的车辆也可以在此路段进行服务(或空车返回)。VDA的方法被Philadelplia卫生部门成功应用到解决环卫车辆行驶路线问题中。在11.2节中,我们将定义网络、提出假设和CARP-VSD问题的目标及VDA解法,在11.3中,我们分步骤描述VDA,并且用一个例子来说明VDA的部分内容。在11.4中,我们将陈述在Philadelphia.中应用VDA的结果。在11.5中我们将讨论未来的研究方向。11.2 CARP-VSD的网络、假设及目标 在这一节,将会给出旅行网络,服务网络,CARP-VSD的假设和目标这些定义。这些元素由于在弧上的车辆限行站而不同于普通的CARP,并且这些车辆限行站使得网络更加复杂化。与这种复杂的网络设计对应,VDA算法的设计也很复杂。11.2.1 旅行网络旅行网络G =(N,A)是一个代表底层街道网络的有向网络,这将通过CARP-VSD来解决。 G中的每个节点代表在街上网络的交点。 G中的每个圆弧代表在街上网络一侧的一个街道段,并且弧的方向定为街段上车的行进方向。在底层的街道网络中,每条街段上两个方向的弧被称作为对口弧(见Levy7),并且这些对口弧遵循街道两侧的行驶方向。旅行网络G完全是由定向的对口弧组成;换言之,在底层的街道网络的每一个街段有两个定义的弧。如果在街上段允许双向通行,那么这两个对口弧在G都是冲着相反的方向。如果街段只允许单向交通,则在G中的两个对应的弧被定向在同一个流量的方向。如果在街段只允许单向通行,并且直接从f到g,那么这两个对应的弧a(f , g) 和 a(f , g)具有不同的属性。在旅行网络中的的每个弧a(f , g)的属性定义如下:D (f , g):在弧a(f , g)上空车行驶的时间。W(f , g): =1。如果弧a(f , g)是从f到g的一个单向街段对应弧。在这种情况下,弧a(f , g)在旅行网络中被重复了两次,一次对于街道的一边。为了计数的目的,G中的两个对口弧被标记为a(f, g) 和a(f , g)=2。如果弧a(f , g)代表的是一个允许双向通行的阶段的对口弧,在这种情况下,a(f , g) 和 a(g , f)都将弧在旅行网络中出现。M(f, g):=0。与阶段相关联的的弧a(f , g)一次只能被服务一边。=1。与阶段相关联的的弧a(f , g)的街道能够蜿蜒或之字移动。当一个街道段可迂回,街道路段的两侧都一次遍历就可以全被服务,遍历的路线是回型的。假定如果一种车型的车服务了一个与弧a(f , g)相关的街段,而遍历这个街段的路线是回型的,那么,我们认为其他类别的车辆在此服务也是回型路线。对于这个假设,在住宅环卫收集是一个少有的例外:一类车辆作为自动的侧装载车辆,这种车辆无法迂回服务一条街段,而另一类车辆作为后部装载或者前装载车辆,这种车辆有迂回服务的可能。这种情况本章不予以考虑。 L (f , g): 弧a(f , g)的长度。假定L(f , g)=L(g , f)。SC(f , g):能够服务弧a(f , g)的最大车量种类。如果SC(f , g)=s,那么车辆类型1.s能够服务弧a(f , g)。假定SC(f , g)=SC(g , f)。TC(f , g):能够单独完成弧a(f , g)上服务的最大车辆种类。如果TC(f , g)=t,那么车辆种类1.t能够在弧a(f , g)上服务。假定TC(f , g)= t = SC(f , g)=s 并且 TC(f , g)=TC(g , f)。S( f, g):在弧a(f , g)上的服务时间。如果弧a(f , g)是作为可迂回的弧被服务(即:Mf , g=1),那么S(f , g)代表在弧a(f , g)上服务时间的一半。Q(a(f, g):表示在弧a(f , g)上被服务的总量(体积或者重量)。当弧a(f , g)没有被服务时,Q(a(f, g)=0。之所以用标记Q(a(f , g)而不是Q (f , g)来定义弧a(f , g)的体积是为了帮助11.2.2中定义弧集MA 和 SE。11.2.2 服务网络在Gs的服务网络中,旅行网络中的弧集A被分解为四个相互分离集合代表街段,这些街段需要不同类型的服务,并且这些街段存在可以穿过但不需要服务的可能。这四个分离集如下:DA:空车返回的集合。DA=a(f , g)|Q(a(f , g)=0.在弧a(f , g)没有要求的服务,并且弧a(f , g) 只用来让空车行驶。RA:被要求服务的弧集,不能迂回,并且在相应的街段允许双向通行。因此,RA=a(f , g)|Q(a(f , g)0, M( f, g)= 0。如果弧a(f , g) RA,弧a(f , g)的服务必须只能是弧a(f , g),而不能是它的对用弧。MA: 被要求服务的弧集,服务是迂回的,街段只允许单向通行,MA=a(f, g)| Q(a(f , g)+Q(a(f , g) 0, M(f , g)=1,W (f , g)=1 。虽然弧a(f , g)在集合A中重复出现两次,但是一次只能在街段的一边,弧a(f , g)在MA中作为有向弧出现一次。SE: 代表街道段允许双向通行的边缘集合,要求被服务,而且服务要求必须能够迂回。SE=e(f , g)1|Q(a(f , g)+Q(a(g, f)0, M( f, g)=1,W(f , g)=2。在弧集A中有弧a(f , g)和弧a(g , f),但是在SE中,边缘弧e(f , g)代表了旅行网络的两条弧,只出现一次。如果边缘弧e(f , g)是服务从节点f到节点g或从g节点到节点的f,那么,这个旅行路径生成算法在VDA已经确定了。服务网络GS被描绘成:节点集合N,弧集合DA、RA、MA和边缘集合SE,能够被表示为GS=(N, DA U RA U MA U SE)。11.2.3 车辆类型在车队中车辆类型上,将CARP-VSD从传统的CARP中分离开来。尽管车辆种类代表了不同类型的车辆,但每种车型的容量等属性是被假设为相同的。CARP中像车辆容量和工作日的长度等有代表性的属性在CARP-VSD中可以取不同的值。下面是对车辆类型K的属性的定义:Qk:车辆类型K的可用数量。例如,如果车队有5个1吨的车辆,3个5吨的车辆和4个10吨的车辆,那么Q1=5, Q2=3, Q3=4。车辆优先列表(如下所述)进一步细化车辆类中的车辆的数量的概念。Mk:车辆类型K的容量。车辆的容量是车辆能够承受的最大体积或者重量。在住宅收集垃圾的行车路线可以包含多个前往集中处理设施的往返旅程。尽管在容量达到最大之前去集中处理设施可能减少总的空时返回时间或路线距离,但是我们要求去集中处理设施时车辆的载重必须达到最大容量。此外,假定在一天结束的时候必须去集中处理设施,即使没有达到车辆的载重能力。DTk:处理时间。即在集中处理设施清空车辆的时间。处理时间是车辆类型的函数。OTK: 办公时间是指分配给K类车辆的员工在车仓中从一天开始到结束的时间。在办公室,员工要做给车辆加油,清洗车辆等工作。11.2.4 车辆的旅行网络和服务网络在VDA算法中,每一种车辆类型都有它自己的旅行网络和服务网络。这些网络并不是在VDA算法中建立起来的,而是隐含在CARP-VSD中的旅行网络G和服务网络Gs中的指标变量。在旅行网络G的每个弧中,TC(f , g)指的是能在弧a(f , g)上旅行的最大车辆类型。每种车型可能有一组不同的弧线,这组弧线能够被此种车型的车辆遍历。车辆类型i的旅行网络Gi=(Ni,Ai),指能够被车辆类型i遍历的网络弧,但是不能保证Gi是一个连通的网络。在旅行网络G中的每个弧,SC(f , g)指的是能在弧a(f , g)上服务的最大车辆类型。正如前面提到的,一个街段能够被一种车型遍历,但是可能不能被这种车型服务。由于车辆限行站的存在,一种车辆能够服务的弧集也是这类车型的的函数。车型i的服务网络是Gi s=(Ni,Ai=DAi U RAi U SAi U SEi)。车型i的服务网络Gi s是从旅行网络Gi中车型i的基础上建立起来的,和11.2.2中描述的服务网络Gs是从旅行网络G的基础上建立起来的方法是完全一样的。在Ai中能够被服务的弧被放置在RAi、SAi和 SEi中,在Ai中不能够被服务的弧被放置在DAi中。11.2.5 车辆优先列表车辆优先列表指定的车型的车辆,以优先次序递减时,可在该优先级的最大数量。由于运营成本、合约义务或其他原因,某些种类的车辆可能是更为可取的。一个车辆种类可能在车辆优先列表中出现不止一次。一个车辆优先列表的例子如下: 车辆种类可使用的数量331112414在这个车辆优先列表汇总中,用户最喜欢车型3 ,因为用户认为它们最有效率、只需要一个来回到集中处理设施,有最大的容量,同时在此区域内已经被组织者拥有。车型1在车辆优先列表中被分割,因为该组织拥有11辆这种车辆(没有这些车辆的资本成本),但该组织最多可以买4个额外的车辆(但这些车辆需要资本开支)。 该组织还被授权至多可买四辆车辆优先列表中的车型2。 车型2中的4辆车排在车型1中的4辆车之前,因为用户相信车型2的车比车型1的车更有效率。VDA试图使用首选车型中的车辆,从车辆优先列表的顶部开始。不太理想的车型只在必要时使用。11.2.6 其他假设前面已经定义过,GS=(N, DA U RA U MA U SE) 代表了服务网络。车辆分析算法(VDA)假定RA U MA中所有的弧和SE中的每个边都可以被车辆优先列表中最小的车型服务覆盖到。旅行网络G以及服务网络GS 都假设是连通的网,服务网络Gs1假设为具有强连通性的网。如此,如果车辆优先列表中的车型1有足够车辆的话,所有需要服务的弧都有可能被服务到。如果Gs1不具有强连通性,那么所有与仓库和集中处理设施没有强连通性的服务弧在最后的解决方案中都不会被服务覆盖到。不论车型,在所有车辆的路线起始点及终点都会存在一个停停车场。在所有车辆清空的地方都会有一个集中处理设施。不论车型,所有车辆在一天结束时都必须先回到集中处理设施处清空车辆然后回到停停车场。目标路径时间TRTk被指定为车型k。这个目标路径时间可以是各车型或某一车型内。目标路径时间是一个分区从一特定车型获得服务的目标时间长度。为了模拟在一车型中目标路径时间的区别,这个车型在车辆优先列表中被分割成2类或更多,但是对于每个车型,弧上的车辆限行站是相同的。关于分区形成的一个软性约束为:每个分区的长度p在车型k中处于区间Lower p,Upper p ,这里的Lower p=TRTk-AK ,Upper p =TRTk +Bk ,AK和Bk通常认为为15分钟。然而,我们有一个组织设置的AK和Bk等于3分钟。11.2.7 CARP-VSD的目标和约束条件和其他CARP 类型问题一样,CARP-VSD问题的一个较好的解决方案有如下特征。l 只要服务网络Gs是连通的,每个在服务网络Gs中需要服务的街道都被分到一个分区。l 在车型k中所有路线的路线长度都在区间TRTk-Ak,TRTk+Bk。这样的解决方案被称为平衡方案。在CARP-VSD问题中,VDA的工作量的估计更加复杂,因为VDA必须决定每个车型中需要多少车辆以提供服务。在CARP-VSD使用VDA分区更加复杂,因为要作出将车型配给每个成长变化的分区的决定(即要给每个新创建的分节点配上一种车型)。这个车队组成结构是在任何分区成长变化前的初步决定。不过VDA设立使得这个估计可以在后续迭代的VDA中更新。车辆优先列表给了我们决定车队组成结构的有效方法。l 和每个分区关联的旅行路径使得非生产性时间(或者叫空时返回时间)最小化。在大部分弧路径问题中,需要服务的分区中需要服务所有的街道分区的总时间里,空时返回时间所占比重很小。如前所述,在费城内实现VDA,我们使用在智能路径软件系统(RouteSmart software system)中生成的旅行路径,来决定每个分区中的最小的空驶返回时间,而不去开发新的旅行路径生成程序。l 分区之间的重叠尽可能小。如果分区之间没有重叠,每个区域的的责任人就更容易确认。如此,给任何一个服务错误找到对应的责任人就更简单了。11.3 VDA车辆分析算法VDA通过将CARP-VSD分解成几个较小的单一车型的CARP来解决整个CARP-VSD问题。每个较小的CARPS问题通过智能路径软件中的分区程序得到解决。这些较小的问题的解决方案通过整合到一起形成最终的CARP-VSD问题解决方案。分区一旦形成,RouteSmart中传统的旅行路径生成技术被用于在每个分区中的弧换个边中找到空驶返回时间近似最小的遍历路径。VDA包含以下5个步骤:步骤A:创建和验证车型网络。步骤B:估计总的工作,并确定初始车队组合。步骤C:服务网络分区。步骤D:确定旅游路径并平衡各分区。步骤E:修订估计的总工作,调整车队结构。VDA最初完成步骤A和B,然后重复步骤C- E,直到它终止。 在那个时候,路由和行进路径可以打印和绘制。 输入到VDA中的是第11.2节中所述的各种数量,如旅行和服务网络,车辆优先列表,以及各种参数,如有需求的分区的数量,每个分区的目标路由时间。11.3.1 步骤A:创建和验证车型网络车型旅行网络Gi = (Ni,Ai)的创建是为了旅行网络G=(N,A)中的所有车型,每个Gi都进行了连通性检验。如果Gi不是一个强连通性的网络,那么能被车型i中的车辆服务到的弧是那些和停车场及集中处理设施具有强连通性的弧。Gi中所有的与停停车场和处理设施没有强连通性的弧都会被移出Gi。这样,整体服务网络Gs和车型服务网络Gsi就建好了。11.3.2 步骤B 评价整体工作并且决定初始车队配合比在步骤B中将会决定一个初始车队配合比的估算。这个估算结果将会在VDA的第一次迭代中被用作车队配合比。设V=V(i, j)作为下三角矩阵。V(i, j)是j型车辆能够服务到所有服务网络的弧和边缘所需要的车辆数量,其最大可行车辆类型是i型车辆,i j。所以,V (2, 1)是车型1能够服务到所有服务网络的弧和边缘所需要的车辆数量,其最大可行车辆类型是车型2。我们对V (i, j)的计算过程将在11.3.2.7节中给出,同时V (i, j)不需要是整数。在下一个章节中,我们将介绍VDA的程序,也将给出一个完整的例子。11.3.2.1 步骤B的第一遍计算在这个过程中的第一遍计算(k=1),V(1, 1)是通过对车辆优先列表的查找并找到最小车型的第一个示例来检验的。设W1为从具有车辆优先列表特点的最小车型中选取的车辆数量。设U=min(V(1, 1), W1)为最小车型中分配去服务与V ( l , 1)有关工作量的车辆数量。如果U不是一个整数,那么就近似为相邻的最大整数。在车辆优先列表的适当条目中,已知U且V(1, 1)被设置等于V(1, 1)-U并且W 1被设置等于W1-U。那么,以下三种情况可能会发生。1、 如果V(1, 1)0,如果我们在车型1中没有找到足够服务V(1, 1)的需求的车辆数的话,我们继续在车辆优先列表中寻找下一个最小车型。如果可以找到另一个最小车型,重复上述过程。如果无法找到另一个最小车型,那么VDA过程结束,因为这个问题不可行,即在车型1中没有足够数量的车辆可以满足需求。2、 如果V(1, 1)=0,所有在V行的需求都可以被车型所满足。则第一遍步骤B的计算结束,第二遍计算开始,设k=2并且执行11.3.2.2中提到的程序。3、 如果V(1, 1)0,则我们有过量的对V的第一行需求的服务能力。当U被设置等于非整数V(1, 1)时,V(1, 1)0。那么U近似为相邻最大整数。假设这部分多余的服务能力去满足V矩阵的第二行的需求。为了满足以上情况,对V矩阵第二行进行如下改进:举例来说,如果我们初试时设W1=3, V(1,1)=1.1,V(2, 1)=3.2, V (2, 2)=2.7,那么在步骤B的第一遍计算中将出现以下结果:1、 U=2, W 1=3-2, V(1, 1)=1.1-2=-0.9.2、如果V(l,l)0, 则V (2, 1)=3.2-0.9=2.3 ,V (2, 2)=2.7-(0.9 * 2.7/3.2)= 2.7-0.759=1.941如果把V(2, 1)1)在步骤B的第k遍计算中,V矩阵的第k行将被检验,且车辆优先列表扫描出的第一个结果不能大于k。假设如下:j: 在车辆优先列表中车型的第一个结果中的车辆数量,且不大于k的。Wj:车型j中的可以分配给其工作量的车辆数量,Wj在车辆偏好表中被指定,且是整数。U:在车型j中可以分配去满足V (k, j)相关需求的车辆数量,U=min(V(k, j), Wj)。如果U不是整数,则近似到相邻最大整数。已知U,在车辆优先列表的适当条目中设Wj等于Wj-U,V矩阵第k行做如下调整:V (k, i )=V (k, i)一U*Vk, i)/V(k, j), i =1,k则下述三种情况可能发生:1、 如果V (k, j)0,我们继续在车辆优先列表中查找下一个不大于k的可行车型。如果找到下一个结果,重复本部分的程序。如果没有可行车辆类型,VDA结束,这个问题不可解决,即车辆类型k中没有足够车辆数量能满足需求。2、 如果V (k, j )=0,则结束本次计算,可以继续进行k=k+1遍计算,并重复上述程序。3、 如果V (k, j )0,则拥有多余的服务能力,这部分多余服务能力可用来满足V矩阵剩下的需求。为了解释这部分多余能力,第k+1行做如下调整:调整后,完成步骤B的第k遍计算,可以继续进行下一遍计算。11.3.2.3 举例假设有三种车型且V矩阵如下:进一步假设车辆优先列表如下:11.3.2.4 步骤B的第一遍计算可知V(1, 1)=4.7 ,W 1=7, U = min(4.7, 7)=4.7, U近似等于5。那么,车型1的五辆车被分配给车队组合。那么W 1=7-5=2,V(1, 1)=4.7-5.0=-0.3。因为V(1, 1)j。现在描述计算V(i,j)的工作程序。计算V(i,j)的工作量估计程序的所需元素如下:K1: K1是所有最大可用车型为i的弧的总容量。K1=EQa( f, g) for all a f, g)SC( f, g)=iK2:所分析车型的车辆载重能力,也就是说,K2= QJ。K3:所有最大可用车型为i的弧的服务时间,也就是说, K3=K3=S( f, g) for all a( f, g)SC( f, g)=i.K4:所有最大可用车型为i的弧之间的预计空时返回时间。K5:j型车辆的目标路线时间。 K5是由用户指定的,即,K5= TRTjK6a:j型车辆在一个分区的办公时间。 K6a是由用户指定的,即,K6A= O FJK6b:j型车辆的垃圾处理时间。 K6b是由用户指定的,即,K6b= DTJK6c:j型车辆从垃圾处理中心到停停车场的时间, K6c旅行网络计算确切知道。K6d:j型车辆从分区到垃圾处理设施中心的时间。K6d是在旅行网络中计算,以每一个弧到处理设施中心的平均时间来估计,SC(F,G)=(F,G)K6:总固定时间。 K6的计算方法如下:K6= K6a+ K6b+ K6c+K6d。由于K6d是一种估计,因而K6也是一个估计值。K7:j型车辆前往集中处理设施的预计额外时间。 K7是从分区到集中处理设施的平均往返旅行时间(2 *K6d),再加上垃圾处理时间(K6b)。因此,K7= 2*K6d+ K6b。 K7是一个估计值,因为K6d是一种估计的关于车型的函数。 令X为从每个分区到垃圾处理中心的旅程的次数(X为整数),令V (i, j)=MinX(max(PV(X), PT(X),其中P V (X): .能够操使用街道总容量的最小分区数量,可以用PV (X)=K1/(K2*X)来计算PT (X ): 完成指定时间内的所有工作量需要的最小分区数量,可以用下面的式子计算: PT(X)=(K3+K4)/(KS一K6一K7*(X一1) ,由于 K6是估计值,PT (X ) 也是估计值。问题是计算出最佳的X值的计算中使用的V(i,j)。最初,X是未知的。然而,可以观察到,作为X增加时,PV(X)随之减小,PT(X)随之增加。 PV(X)和PT(X)是X的连续函数,如图11.1所示。 要确定X的值,就要最大限度地减少V(i,j),我们令PV(X)= PT(X)来求出X它可能不是整数。然后,我们计算使得V(i.j)最小的与X相邻的最大整数值。11.3.2.8 举例这个例子说明了工作量估算的过程。假设如下:K 1: 总容量=100吨,K2: 车辆的运输能力=10吨,K3: 在弧上的服务时间=1200分,K4: 在服务弧间的空时返回时间=120分,K 5: 路线时间=480 分,K6a: 办公时间=30 分,K 6b: 垃圾处理时间=60 分,K6c: 从垃圾处理设施到仓库的时间=10 分,K6d: 从一个区域到垃圾处理设施的时间=20 分,K6: 固定消耗时间=K6a+K6b+K6c+K6d=120 分,K7:可变消耗时间=2*K 6d+K6b=100分,那么PV(X) 和PT(X)可如下述计算:PV (X)=K1/(K2*X)=100/(10*X)=10/ X,PT (X)=(K3+K4)/(K5一K6一K7(x一1)=1320/(460一100X)等值P V (X ) 和P T (X )给出了X *,其是X的估算。X*=(K 1*(K5一K6+K7)/(K 1*K7)+(K2*(K3+K4)=1.98.因为X等于1.98,我们计算V (i, j)=min(PV(1), PT(2),其中PV(1)=10和PT (2)=5.08。所以V (i, j )=5.08且5.08是需要满足工作量的区域的估算数量。11.3.3步骤C划分业务网对于同类型的车队,划分算法运用在VDA问题中远远难于用于CARP问题。CARP的运算法则中,由于所有车辆是相同的,所以仅仅需要把所有业务网中的弧度分配给区域。而在VDA问题中,除了为使每个区域正常运作,必须对车辆种类进行判断,还需把所有必要的弧度和边分配给每个区域。在11.2.6中,车辆优先列表中一个目标路径所需时间是指车辆到某个区域中某地所需的时间,而且目标路径所需时间会随车型的不同而不同。之前提到,CARP-VSD中的限制条件即使不够明确且可能被违反,但它们依然用于划分区域,使得每个区域内的总工作量分配到到K型号车辆时,K型号车辆的工作量在内。求解VDA的区域问题的五个子步骤如下。这五个步骤在车辆组合中每种车型中进行迭代,从车辆组合中可用性最小的车型开始,在可用性最大的车型结束。步骤C1创立一个临时业务网络(TSN)。临时业务网络中的服务弧和边缘属于SA、SE并集。SA、SE并集中的弧和边必须在迭代中被分配完,如果没有,那么它们要被分配给某个区域。步骤C2临时业务网络被划分为一个与车辆地点无关的CARP。具体是用现存车辆的容量来划分,而现存车辆是指那些由步骤B确定且没有被分配的车辆。这种划分涉及到解决与地点无关的非齐次CARP。斯尼泽克11对如何以最佳方式完成划分进行了研究。对于本章节的研究对象费城,用现有的CARP程序去划分一个与地点无关且有不同型号车辆的车队,其中地点可在RouteSmart软件系统得到。 在此步骤中,有可能比由步骤C确定的区域中在可利用的车辆类型获得更多同型号的车辆,这里可利用的车辆类型是指在在步骤B中确定的车队中某一种。例如,最小车型的TSN可能只有少量的工作量,这些工作量必须是由最小车型的车辆完成。然而如果小型车辆可取的,在车辆优先列表中我们可能有好几种小型车。但是,在算法的这一步中增加全部或大部分小型车辆所对应的分区数量,可能会导致工作量不均或者分区严重交错的低劣方案。在这里,我们以取min(R1,R2)的规则来确定增加的分区数量。其中:R1:1.5*(完成TSN工作量所需区域的最小数量)R1四舍五入至整数。R2:现可利用的车型中车辆数量将最后一次迭代中,可超出目标路径的时间的范围,以确保服务网络Gs中所有的弧和边缘被分配至某区域。目标路径的时间有宽松的上、下限,以确保在最后一次迭代中在Gs中所有的弧边缘被分配至各区域。步骤C3服务网络Gs和所有车型服务的网络在步骤C2的基础上更新。在步骤C2中TSN中被分配到某区域的服务弧和服务边不是中的弧和边,因为步骤C2只把弧分配给的区域。因此,服务网络不需要在这点进行更新。步骤C4现在创建第二个临时服务网络TSN2。TSN2的服务弧和边是两部分弧和边的总和,这两部分分别是指TSN在步骤C2中已经被分配给区域的弧和边外和SA 、SE并集中剩余的弧和边。在步骤C4中,将TSN2中弧和边分配后,步骤C2中增长的区域大大扩大了。区域不停扩大直至每个区域增大到相应车辆的目标路径时间的一个特定百分比。步骤C5如果所有需要服务的弧和边缘已被分配给相应的区域,区域的划分算法终止。否则,服务网络Gs和所有车型的服务网络根据在步骤C4中的划分更新(在步骤C3中),在返回到步骤C 1运算。11.3.3.1 案例图11.2中的例子说明当处理不同类型车队的CARP-VSD中时,先划分TSN再划分TSN2的重要性。图中有6个节点(A,B,C,D,E,F)和九条边(A,B,C, D,E,F,G,H,I)。每条边上的容量是一个单位,边B、边C和边D由小车或大车负责,其他边只能由小车型负责。下面考虑三种情况。11.3.3.2 情况1:同类型的CARP假设该车队有三辆小型车辆,并其忽略在边上的位置。这三辆车的区域被标注a,c和e。ze则分区为:Partition 1 (seed a)=A, B, FPartition 2 (seed c)=D, E, GPartition 3 (seed e)=C, H, 1.11.3.3.3 情况2:CARP-VSD(只运用TSN2)在这种情况下,车队由三辆车组成,其中两辆属于车型1的小型车和一辆属于车型2的大型车。如上所述,B,C,和D只能由车型2的车服务。在这种情况下,不运用步骤C2和C3中。 首先,我们依据整个服务网络(TSN2)而不是TSN来划分两种车型。如果区域被标为A和C分区,然后创建以下两个分区:这些区域有容量,但边H和边I,必须由车型1的车服务,不能被划分至任何一个区域中。再接下来迭代至步骤C, TSN2由边C组成。边H和边I是不包含在TSN2中的,因为这些边不能由大型车服务。所以区域2不是因为这些边缘TSN2不能由大型车辆提供服务。因此,区域3如下:Partition 3 (seed e)=C.因此,在这种情况下的最终解决方案中,边H和边I个未分配到任意一个区域,区域1和区域2有容量。11.3.3.4 情况3 CARP-VSD (既用TSN和TSN2)在这种情况下,车队和情况2中一模一样。但是,我们先形成TSN再形成TSN2来分区。最小型车型的原始TSN又边A、E、F、G、H和I。边B、C、D(这些边能由车型2中的车辆服务)不在TSN中。用a、c作为划分点,分区如下:这两个区域都用容量,而从车型1中分配各分配一辆车至所有必须由车型1服务的边。最小车型的TSN2包括整个网络。由于最小车型的两个区域已饱和,没有新的边被分配到这些分区。该算法在较大车型再次进行。TSN由边B,C和D组成。得到的分区如下:Partition 3 (seed e)=B, C, D.11.3.3.5分析这三种情况说明了接下去涉及的内容。同类型车型解决方案(情况1)从间隔的角度看,给出了最好的区域划分并覆盖所有边。当考虑地点后,情况3的方案(TSN和TSN2)比起方案2(只有TSN2)更好,因为所有的边在情况3中都被分配了而情况2中部分边没有被分配。情况1的解决方案比起情况3的有所优化,因为情况3的方案有更多的隔断。然而,情况1方案不如情况2和情况3那样适用于考虑地点的问题。情况2和情况3中车队由两辆小型车和一辆大型车构成,因为在每个区域内至少有一段弧只能由小型车服务。11.3.4 步骤D.确定遍历路线,使各分区均衡在步骤D中,无法保证已经被服务过的街道网络中在步骤C中找到任何分区都是连通的,因此,找到空时返回时间最短的遍历每个分区的路线的过程实际上是解决了一个农村邮递员路线问题(RPP)。RPP的解决方案可以找到一个连续的、最低空驶返回时间的行进路径,这个路径涵盖了所有存在服务需求的分区的弧和边缘,开始和结束于停停车场,并且包含拥有前往综合处理设施中心的路径。适当的车队旅行网络在RPP解决方案中用于在找到最小空时返回时间的遍历路线之后确定空车返回的街道。一旦空车返回的最短时间已知,分区中遍历路线的实际时间便可以确定。解决RPP是非常复杂的。算法必须考虑到在一个分区中所需计算的街段可能形成一个非连通网络;部分街段是单向的,其他街段是双向的;有些街段必须以一段曲线的轨迹被服务;还有指定的转弯限制和穿过街道的困难也必须加以考虑。如果不属于车队遍历任意分区的路线的时间没有落在分配给该分区的目标时间的上下限之间,那么一个自动交换的程序将会在各分区之间交换弧和边.交换的主要目标是改善路线的平衡性。交换过程保持了依赖车辆网点的可行性。所有交换完成之后,每个分区的RPP重新得以解决。令车队k服务分区p。在第11.2.7节中,我们定义了一个均衡的解决方案,每个分区p的路线全长在区间T RTk-Ak, T RTk+Bk=LowerP, UpperP内。在解决每个分区p 的RPP之后,如果我们有一个均衡的解决方案,那么结果就将被保存并且在算法终止时输出。如果我们没有均衡的解决方案,就会有一个现有方案绩效的评估指标SG,SG= T1 + T2,其中T1:(Time p一Upper p)2,包括 Time p Upper p 的所有分区p的总和。T2:(Time p一Lower p)2,包括Time pLower p的所有分区p的总和。Time p是遍历分区p的行驶路径的总时间。如果采取SG之后的结果比之前所有的迭代结果都更好,那么就会以最佳方案被保存。均衡的解决方案在相应的SG=0的时候得到。当均衡解决方案被找出或已经进行了指定数量的迭代时该算法终止。如果没有找到一个均衡方案,以已方案中的最佳方案为解决这个问题的最佳方案。如果算法没有达到指定迭代次数,均衡方案也没有找到,那么算法将继续执行下面的步骤E。11.3.5 步骤E 修订并估计总工时,调整车队组合步骤E和B类似,但步骤E.每个分区的空车返回旅行时间和实际的路线都是已知的。因此,在步骤B中建立的估计值是到了步骤E中更加准确。这些信息用于确定一个可能的新车队这次修订的预计工作量部分建立在步骤D的方案中不均衡分区数量的基础上。例如,如果车队1中的所有车辆的工作都过分饱和,而车队2的车辆产能过剩,在车队2已经被分配到一个分区的情况下,车队1中的车辆仍会被分配到这个分区进行服务。交换假设车辆优先列表中有一个来自车队1的可用的额外车辆。确定修改车队组合后,该算法将返回到步骤C进行新一轮迭代。11.4在费城实施VDA在许多大城市中,住宅的卫生设施的线路普遍由监事手动制作,这个结果是非常不平衡的。有的线路规划需要工人加班,然而部分线路只需要4至5小时的工作。因为这些路线严重不平衡,并且员工加班要支付一定的加班费,管理层已经看到这些线路的规划是极其没有效率的。此外,员工也看到了这些不公平,并且这种不公平还造成他们的不满。管理层和员工都认为设计均衡的路线和妥善的日程安排是最佳的状态。VDA的目标之一是规划均衡的路线。规划均衡的路线是接受费城发展VDA线路规划的首要条件。住宅环卫车辆的线路设计在一个引进了GIS的项目里是一个非常大的部分,以费城为例。费城想要提高其住宅环卫收集效率,需要一个基于GIS的电脑系统来展开他的线路。RouteSmart系统作为其中的一个组件是为了解决算法设置中脱离地点限制的CARP,并且在一个GIS系统即可实施RouteSmart。 VDA用于制定并实施RouteSmart系统特别是为解决车辆通行限制问题。 RouteSmart可以在个人计算机和以UNIX平台上的多种GIS上运行。费城卫生署在基于UNIX的RS-6000机使用ARC / INFO作为本土GIS来运行RouteSrnart。内嵌入VDA的RouteSmart的版本具有下列功能:l 系统可以把街道分割高达20,000个街段,以及成多达100种不同的车辆类的分区。RouteSmart产生通常很少有重叠或交错。然而,RouteSmart CARP-VSD可以提出比没有车辆位置信息更多的解决方案。ll 系统给每个分区分配适当车型的车辆。该系统通过解决分配给每个分区的街道弧上的RPP问题构建了一个遍历时间路径

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论