校园巴士路线与站点分布的调研与分析外文翻译资料

英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料

校园车路由问题：评论

提要

本文的目的是提供对校园车路由问题 (SBRP)的全面审查.SBRP寻求为一队校车计划有效的时间表，在时间表里每两校车在不同的车站接送学生并将送他们到制定的学校同时满足各种约束如校车最大容量，学生在车上的最大骑乘时间，以及学校的时间窗口。这类问题包括不同子问题涉及数据准备，车站选择，路线生成，校钟时间调整和校车调度。在本文中总结了SRBP的文献中使用的各种假设，约束和解决方法。还提出了需要进一步的研究的问题列表。

引言

在本文中,我们研究的课题是(SBRP)校车路径问题。校车路径问题不断研究自从由牛顿和托马斯公开发表以后就一直不断的被研究。(1969)。然而, 需要一个针对校车路径问题的通用研究方法成为当务之急，因为大多数研究都是基于具有特定假设和约束的现实世界的问题。李和福 (2002) 指出, 没有单一的主导方法针对校车路径问题。此外, 他们补充说, 许多可用的方法是不可以采用的。关于校车路径问题调查的数量是有限的 (见Desrosiers et al.,1981; Braca et al.,1997) 。有时, SBRP只是掩饰并简要考虑更大的调查类的问题。的例子, 这些都是联合调度车辆和船员的问题 (博丹et al.,1983), 乡村邮递员问题 (Eiselt et al.,1995) 和多目标车辆路径问题 (Jozefowiez et al.,2008) 。

SBRP由更小的子问题。根据分解Desrosiers et al。 (1981), SBRP可以解决通过五个步骤: 数据准备、巴士站选择(学生作业停止), 公交路线生成、学校钟时间调整, 和调度路线。在数据准备阶段, 道路网络组成的家, 学校, 巴士车厂, 叫做(OD)矩阵其中指定。对于一个给定的网络, 公共汽车站选择一步决定停止的位置, 和学生分配给他们。此后, 一个学校的公交线路公交路线生成步骤中生成的。学校的钟时间调整和路线安排多校配置步骤是必要的。校车系统通常由地方教育委员会而不是个别学校。此外, 公共汽车是由多个学校共享。因此, 学校打开和关闭时间的安排和调度多个学校的公交车是必需的。

在大多数现有方法,这些子问题分别考虑和顺序。虽然这些子问题不是独立的而是是高度相关的, 他们分别治疗由于问题的复杂性和规模。此外, 大多数文献中, 只有部分SBRP。特别是, 因为公交车站的位置和开启和关闭时间的学校教育委员会的政策高度相关, 许多研究认为这些信息碎片和集中的路由和调度车辆。表1总结了SBRP和显示了子问题他们认为。

表1

文献中考虑的子问题

尽管SBRP本身是一个独特的和独立的问题,单个子问题或组合的子问题可分为现有优化问题的一个变种。公交路线一代子问题本身非常类似于车辆路径问题(VRP), 这是一个广泛的研究应用运筹学。VRP试图生成有效的路线的车队为了交付(或收集)产品从仓库到一组客户(托斯和比戈,2002) 。在大量的研究中, SBRP称为一个重要的现实世界的应用蚁群 (黄金et al.,1984; Paessens,1988; Ronen,1988; Fernand和福丁,1989; 贝克et al.,1993; Augerat et al.,1998; 罗素和蒋介石,2006; Jozefowiez et al.,2008) 。优秀的编辑工作VRP的作品中可以找到球et al.,1995; 托斯和比戈,2002。

汽车站的结合问题选择和公交路线代落入location-routing问题的类(含)。单体包括确定设备的位置(在SBRP, 公交车站) 服务多个客户和最优的路线的车队 (Min et al.,1998) 。因为是一个NP-难问题, 部队还没有已知多项式时间算法, 可以找到所有问题的最优解实例(拉波特,1988) 。有关含碘的近期发展, 看到伊和Salhi (2007) 。

本文的其余部分组织如下:第二部分描述SBRP五项子问题的细节。之后, 接下来的两个部分从不同的角度呈现SBRP分类方案。第三节介绍了从他们的问题角度分类方案。第四节分类的数学模型和启发式解法SBRP文学。这种双向分类方法所使用的方法类似于最小et al.(1998) 单体, 但不同的详细清单。最后, 第五部分提出了未来工作的挑战和机遇, 并提供我们的结束语。

2。问题描述

在本节中,我们提出五个SBRP子问题,介绍了对这些子问题的研究工作。

2.1。数据准备

数据准备的子问题准备数据的其他子问题。在这个子问题, 指定道路网络, SBRP准备和四种类型的数据: 学生、学校、车辆、和OD矩阵。学生的数据包括家中的位置(地址), 目标学校的一个学生, 和学生类型。学生的类型一般或残疾 (详情, 参见3.5节) 。

学校数据包含关于学校的位置信息,开始和结束时间的公共汽车到达学校,和学生的最大骑行时间在一辆公共汽车。在大多数研究中, 学校巴士的开始和结束时间到达。然而, 一些可用的研究假设的起始和结束时间在学校可以确定钟时间调整在2.4节总结。

车辆的数据包括原点位置和总线类型的可用的校车。每个总线类型可能有不同的能力一般的学生和特殊教育的学生。OD矩阵存储最短旅行时间或对节点之间的距离(学校、学生位置和总线起源位置)。OD矩阵可以计算使用地理信息系统(GIS)和各种最短路径算法。金姆和宋(2009) 相比几个最短路径算法的性能和发展OD矩阵生成的近似方法。

2.2。巴士站的选择

汽车站选择试图选择一组公共汽车站和学生分配给这些停止。学校在农村环境, 学生们认为是在他们的家园。然而, 在城市地区, 学生认为从家里走到一个公共汽车站, 乘公共汽车停下来。

如第1部分中所述,汽车站选择是在文献中常常省略。许多研究认为, 公交车站的位置。只有少数论文认为汽车站的选择, 其中大部分是使用启发式算法。表2总结了研究汽车站的选择。

启发式的解决方案方法汽车站选择分为 位置分配路由(政治)策略或 配路-路由-位置(支持策略(拉波特,1988;鲍尔曼et al .,1995)。图1, 图2显示这两个策略的概念。政治策略首先判断一组公共汽车站学校布置给学生这些停止。路线生成这些选择停止。然而, 由于公交车站和学生的任务是确定没有考虑它们对生成路线的影响, 这种方法往往会产生过度的路线。博丹伯曼,1979; 霍华斯et al.,1980; Desrosiers et al., 1981提出了一种基于政治策略的启发式方法。陆军研究实验室的策略, 学生被分配到集群, 同时满足车辆容量约束。随后, 选择公交车站, 路线为每个集群生成。最后, 学生们在一个集群中(路线)被分配到一个公共汽车站, 满足所有的需求给出最大步行距离等问题, 最大数量的学生, 可以分配给一个公共汽车站, 公交车站之间的最小距离分开。Chapleau et al.,1985; 鲍尔曼et al., 1995使用一个算法基于陆军研究实验室的策略。最近, Schittekat et al (2006) 从可能的站点和巴士路线生成开发了简单为了单学的校巴士站点选择的一个数学模型。然而他们的模型是单学校有限的而且是经过小尺寸随机测试问题实例的 10个巴士站，50个学生。

2.3 公交线路生成

学校校车路线是在巴士路线生成过程中构建的。用于车辆路径生成的算法可以分为“先排路线再分群”方法或“先分群再排路线”的方法（Bodin and Berman,1979）。“先排路线再分群”的方法是通过利用旅行商问题的演算法建立一条大的路线，这个演算法考虑了所有的站点和约束条件，并将其划分成更小的区块路径。Newton and Thomas（1969）和Bodin and Berman（1979）均实施执行过这种方法。“先分群再排路线”的方法是把学生分组成集群，并使每个群集可以作为一个路径，进而满足所存在的约束条件。Dulac等人（1980）、Chapleau等人（1985）和Bowerman等人（1995）已经把这种方法运用到了校车车辆路径问题中。想知道更多有关这两种方法的信息可参考Dulac等人的和Laporte and Semet (2002) 的文章.

学校路线生成后，改进的启发式算法可以应用于路线。有很多改进的启发式算法和元启发式方法。林（1965）提出的启发式算法也被称为多路径k-opt交换算法正广泛应用于车辆路径问题研究中。该算法从路径中删除k个边，然后加入K边形成一个可行的新旅行。多路径k-opt交换算法的只可应用于少数车辆路径问题研究中。Newton and Thomas（1969），Dulac等人（1980）、Chapleau等人（1985）和Desrosiers等人（1986a）已应用2-opt算法改进可行解。Bennett and Gazis (1972) 和 Bodin and Berman (1979) 已采用3-opt算法。

2.4 校钟时间调整 (学校时间窗调整）

在大多数的研究中，学校的开始和结束时间都是约束条件。然而，也有一些文献认为时间是决策变量，它们试图找到最佳的开始和结束时间以使同一校车依次送达的路径数最大化，减少使用的巴士数量。Desrosiers等人（1981，1986）采用列生成法确定了学校的开始和结束时间。1983年Bodin等人也采用了这种方法，他们声称小问题大约是可以手动解决的。Fuuml;genschuh (2009)在允许学生从一条路径换乘到另一条路径的同时考虑到了学校的出发时间安排问题。通过分支切割的方法和几个预处理机制以及有效的削减，混合整数规划（MIP）的模型得到了进一步的开发和解决。

2.5. 路径调度（路线安排）

路由调度指定每条路由的确切开始和结束时间，并形成一条可以由同一公交连续执行的路由链。Newton and Thomas (1974)开发了一个多校区模型来确定一个学区的所有公交线路。他们假设有不同的时间段，学校在不同的时间段开始。

Bodin (1975) and Bodin and Berman (1979) 还假设学校的时间窗口可以被划分成不同的时间段，以使路由问题可以逐期解决，进而总的路线可以稍后合成。然而，他们的方法可能在学校上课时间或上课的时间段重叠的情况下行不通，因为上一阶段的完成时间可能对接下来的时间段而言太晚了。Desrosiers等人（1981，1986a）使用启发式方法，解决了一系列交通问题。Graham和Nuttle（1986）对校车调度不同启发式的程序进行了比较。Desrosiers等人（1986b）开发了三种算法并在各种背景设置下，如是否考虑被认为是不同时间窗的间隔长度即早上或下午的问题，测试了这些算法对八所学校的交通问题带来的影响.

Braca等人（1997）描述了纽约的校车路径问题。而在大多数文献中，每个学校都只解决了独自的问题，然后确定了每个巴士路线的时间表，换句话说他们在一个阶段解决了所有学校的整个问题。李和福（2002）采用 了Lawler (1972) 提出的kth最短路径算法，生成了一个初始路线和改进方案，在这个初始路线中较大的路线上的站点被移动到较小的路线上。对于具有相同承载量的公交车而言，分配问题的解决是以最小的旅游巴士空调度时间为目标的.

Spada等人（2005）考虑到多学校路由问题，并提出了启发式算法。学校被认为是在以递增顺序增加它们的开始时间，而且每个学校的路线也是在建立在贪心算法上的。在这之后，如果可能的话路径就得到了合成。在此之后，模拟退火或禁忌搜索算法也使合并后的路径得到了提高。

三.基于问题特征的分类

在这一部分中，我们试图根据问题的特点对校车路径问题进行分类。虽然这里有许多分类方法，但我们主要关注的是问题的实践方面。表3体现了从问题角度的分类标准。这些标准的细节将会在下面的小结里讨论。表4总结了校车路径问题在文学角度的分类标准。

表3

基于问题特征的分类。