《含有车辆限行站的弧形路径问题》由会员分享，可在线阅读，更多相关《含有车辆限行站的弧形路径问题（16页珍藏版）》请在金锄头文库上搜索。
1、含有车辆限行站的弧形路径问题：费城经验11.1 引言在住宅区固体废物收集工作中，车队可能由不同容量、大小和形状的垃圾车组成。每一组相同的车辆组成一种车型。小容量的汽车比大容量的汽车满载更快、配送到到处理设施(如垃圾填埋场)的批次更多。每种车型的路线有一个限制,就是要遍历其服务的街道,而较大车型的车辆不能穿越只能承受特定重量的小巷或桥梁。一些街道允许某些车辆(例如舷侧装卸货环卫车辆)通过但不允许其提供服务，因为街道太窄了这种车型的车辆无法开展服务。由于城市中的一些限制，街上会设有车辆限行站（Vehicle-site dependencies）用来禁止特定类型的汽车穿越街道或者提供服务。因此,一个
2、街道的车辆限行站反映了某类汽车能否服务或遍历这条街。CARP-VSD问题实际上是含有车辆限行站的CARP问题。在目前的学术研究中，CARD-VSD问题是一个几乎不被涉足的领域，Nag的论文是我们唯一熟知的关于解决CARD-VSD的论文。CARP-VSD是CARP的一般化问题。在CARP问题中,有一个定向连接的网络G =(N，A)，其中N为节点集，A为连接弧的集合，还有一个指定车型的车队。在网络G中,弧线上的服务时间已知,可以遍历所有弧，空时返回时间已知。CARP问题里将G中要计算的弧划分为时间相同的几个服务分区(此处的时间指的是服务时间加上空时返回时间),每部分弧有顺序的排列，使得遍历所有弧形
3、成连续路径的总附加空时返回时间最小化。在此类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-
4、VSD。这个算法被称为车辆分析算法(VDA)。VDA的一个基本假设是,如果一个特定容量的车辆可以在特定街段服务(或从中空车返回),那么其他更小容量的车型的车辆也可以在此路段进行服务(或空车返回)。VDA的方法被Philadelplia卫生部门成功应用到解决环卫车辆行驶路线问题中。在11.2节中，我们将定义网络、提出假设和CARP-VSD问题的目标及VDA解法，在11.3中，我们分步骤描述VDA，并且用一个例子来说明VDA的部分内容。在11.4中，我们将陈述在Philadelphia.中应用VDA的结果。在11.5中我们将讨论未来的研究方向。11.2 CARP-VSD的网络、假设及目标 在这一节
5、，将会给出旅行网络，服务网络，CARP-VSD的假设和目标这些定义。这些元素由于在弧上的车辆限行站而不同于普通的CARP，并且这些车辆限行站使得网络更加复杂化。与这种复杂的网络设计对应，VDA算法的设计也很复杂。11.2.1 旅行网络旅行网络G =（N，A）是一个代表底层街道网络的有向网络，这将通过CARP-VSD来解决。 G中的每个节点代表在街上网络的交点。 G中的每个圆弧代表在街上网络一侧的一个街道段，并且弧的方向定为街段上车的行进方向。在底层的街道网络中，每条街段上两个方向的弧被称作为对口弧（见Levy7），并且这些对口弧遵循街道两侧的行驶方向。旅行网络G完全是由定向的对口弧组成；换言之
6、，在底层的街道网络的每一个街段有两个定义的弧。如果在街上段允许双向通行，那么这两个对口弧在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中的两个对口
7、弧被标记为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)相关的街段，而遍历这个街段的路线是回型的，那么，我们认为其他类别的车辆在此服务也是回型路线。对于这个假设，在住宅环卫收集是一个少有的例外：一
8、类车辆作为自动的侧装载车辆，这种车辆无法迂回服务一条街段，而另一类车辆作为后部装载或者前装载车辆，这种车辆有迂回服务的可能。这种情况本章不予以考虑。 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 =
9、 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被分解为四个相互
10、分离集合代表街段，这些街段需要不同类型的服务，并且这些街段存在可以穿过但不需要服务的可能。这四个分离集如下：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
11、 , 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，那么
12、，这个旅行路径生成算法在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。车辆优先列
13、表（如下所述）进一步细化车辆类中的车辆的数量的概念。Mk:车辆类型K的容量。车辆的容量是车辆能够承受的最大体积或者重量。在住宅收集垃圾的行车路线可以包含多个前往集中处理设施的往返旅程。尽管在容量达到最大之前去集中处理设施可能减少总的空时返回时间或路线距离，但是我们要求去集中处理设施时车辆的载重必须达到最大容量。此外,假定在一天结束的时候必须去集中处理设施，即使没有达到车辆的载重能力。DTk:处理时间。即在集中处理设施清空车辆的时间。处理时间是车辆类型的函数。OTK: 办公时间是指分配给K类车辆的员工在车仓中从一天开始到结束的时间。在办公室，员工要做给车辆加油，清洗车辆等工作。11.2.4 车辆
14、的旅行网络和服务网络在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)上服务的最大车辆类型。正如前面提到的，一个街段能够被一种车型遍历，但是可能不
15、能被这种车型服务。由于车辆限行站的存在，一种车辆能够服务的弧集也是这类车型的的函数。车型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 车辆优先列表车辆优先列表指定的车型的车辆，以优先次序递减时，可在该优先级的最大数量。由于运营成本、合约义务或其他原因，某些种类的车辆可能是更为可取的。一个车辆种类
16、可能在车辆优先列表中出现不止一次。一个车辆优先列表的例子如下： 车辆种类可使用的数量331112414在这个车辆优先列表汇总中，用户最喜欢车型3 ，因为用户认为它们最有效率、只需要一个来回到集中处理设施，有最大的容量，同时在此区域内已经被组织者拥有。车型1在车辆优先列表中被分割，因为该组织拥有11辆这种车辆（没有这些车辆的资本成本），但该组织最多可以买4个额外的车辆（但这些车辆需要资本开支）。 该组织还被授权至多可买四辆车辆优先列表中的车型2。 车型2中的4辆车排在车型1中的4辆车之前，因为用户相信车型2的车比车型1的车更有效率。VDA试图使用首选车型中的车辆，从车辆优先列表的顶部开始。不太理想的车型只在必要时使用。11.2.6 其他假设前面已经定义过，GS=(N, DA U
