资源描述：
《含有车辆限行站的弧形路径问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、含有车辆限行站的弧形路径问题：费城经验11.1引言在住宅区固体废物收集工作中，车队可能由不同容量、大小和形状的垃圾车组成。每一组相同的车辆组成一种车型。小容量的汽车比大容量的汽车满载更快、配送到到处理设施(如垃圾填埋场)的批次更多。每种车型的路线有一个限制,就是要遍历其服务的街道,而较大车型的车辆不能穿越只能承受特定重量的小巷或桥梁。一些街道允许某些车辆(例如舷侧装卸货环卫车辆)通过但不允许其提供服务，因为街道太窄了这种车型的车辆无法开展服务。由于城市中的一些限制，街上会设有车辆限行站（Vehicle-sitedependencies）用来禁止特定类型的汽车穿越街道或者提供服务。
2、因此,一个街道的车辆限行站反映了某类汽车能否服务或遍历这条街。CARP-VSD问题实际上是含有车辆限行站的CARP问题。在目前的学术研究中，CARD-VSD问题是一个几乎不被涉足的领域，Nag的论文是我们唯一熟知的关于解决CARD-VSD的论文。CARP-VSD是CARP的一般化问题。在CARP问题中,有一个定向连接的网络G=(N，A)，其中N为节点集，A为连接弧的集合，还有一个指定车型的车队。在网络G中,弧线上的服务时间已知,可以遍历所有弧，空时返回时间已知。CARP问题里将G中要计算的弧划分为时间相同的几个服务分区(此处的时间指的是服务时间加上空时返回时间),每部分弧有顺序的
3、排列，使得遍历所有弧形成连续路径的总附加空时返回时间最小化。在此类CARP问题中,任何车辆可以分配给任何服务分区,在解决方案中也可以任意采用,具体见AssadandGolden,Eiselt,Gendreau,andLaporte,Bodinetal.GoldenandWong,Pearn,andLaporte.等人的论文。本章的重点是研究解决CARP-VSD问题的有效方法。因为解决CARP-VSD的合理方法是存在的,并且这些方法可以用于很好地解决CARP-VSD中一般旅行路线方面的问题。本章重点是求解CARP-VSD的实用分区方法。这些分区方法结合旅游路径生成过程来获得一个整体
4、算法来解决CARP-VSD。这个算法被称为车辆分析算法(VDA)。VDA的一个基本假设是,如果一个特定容量的车辆可以在特定街段服务(或从中空车返回),那么其他更小容量的车型的车辆也可以在此路段进行服务(或空车返回)。VDA的方法被Philadelplia卫生部门成功应用到解决环卫车辆行驶路线问题中。在11.2节中，我们将定义网络、提出假设和CARP-VSD问题的目标及VDA解法，在11.3中，我们分步骤描述VDA，并且用一个例子来说明VDA的部分内容。在11.4中，我们将陈述在Philadelphia.中应用VDA的结果。在11.5中我们将讨论未来的研究方向。11.2CARP-V
5、SD的网络、假设及目标在这一节，将会给出旅行网络，服务网络，CARP-VSD的假设和目标这些定义。这些元素由于在弧上的车辆限行站而不同于普通的CARP，并且这些车辆限行站使得网络更加复杂化。与这种复杂的网络设计对应，VDA算法的设计也很复杂。11.2.1旅行网络旅行网络G=（N，A）是一个代表底层街道网络的有向网络，这将通过CARP-VSD来解决。G中的每个节点代表在街上网络的交点。G中的每个圆弧代表在街上网络一侧的一个街道段，并且弧的方向定为街段上车的行进方向。在底层的街道网络中，每条街段上两个方向的弧被称作为对口弧（见Levy[7]），并且这些对口弧遵循街道两侧的行驶方向。旅
6、行网络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)在旅行网络中被重复了两次，一次对于街道的一边。为了计数的目的
7、，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)相关的街段，而遍历这个街段的路线是回型的，那
