英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
校车调度问题
Byung-In Kim，Seongbae Kim，Junhyuk Park
1.介绍
本文介绍了一种校车调度问题，其中给出了每一所学校的行程。行程包括了一系列的汽车站和他们指定的学校。行程所需的服务时间以汽车站，学生人数和学校行程为基础。每所学校都有固定的时间窗，在此窗口内应该完成行程。一辆校车可以为多所学校提供多次行程。考虑到学校的时间窗，本文提出的校车调度问题旨在优化公交时刻表，以服务所有给定的行程。
图1显示了校车调度问题的一个例子。假设ti是由一系列汽车站和他们的学校组成的行程，sm是一所学校。在该图中，学校sa，sb和sc分别有三次，三次和四次行程。让[sm_st，sm_et]成为学校m的时间窗。所有上学的学生都应该在钟点时间窗内到达学校。如果在不违反汽车容量限制和他们指定学校的时间窗的情况下可以在同一辆汽车上为两班车服务，他们可以安排在同一班车上。图2展示出了一个针对图1问题的样本解。{t2, t6, t9}, {t1, t4, t8}, {t3, t7}和{t5, t10}分别由总线1,2,3和4服务。假定sa_et le;sb_st 和sb_et le;sc_st。
在本文中，我们首先将问题模拟为具有时间窗（VRPTW）的车辆路径问题，将行程视为虚拟停车。然而，由于原始问题的不对称性，模拟VRPTW具有特殊的特征。由于学校的时间窗彼此相距很远，与行程的服务时间相比并不宽，因此假定当两次行程可由同一班车服务时，它们的顺序是固定的。因此，当一次行程可以由同一辆汽车进行另一次行程时，另一个顺序是不可能的。
我们展示了一种特殊的情况，即行程的开始和结束时间是固定的，并且给出一各同类的汽车车队，可以被模拟为一个分配问题并且很容易解决。然后我们提出一个基于分配问题的分枝定界方法，用于一般情况下假设同类车队的汽车辆。最后，假设了一个异构总线的假设，给出了一般情况下的启发式算法。计算实验显示了所提出方法的有效性。
本文的其余部分安排如下：在第2节中对现有文献进行简要回顾。第3节和第4节分别介绍了两个混合整数规划模型和算法。第5节展示了第6节的计算结果和结论。
2.文献综述
校车路线问题包括三个主要的子问题，即每个学校的汽车站选择，每个学校的路线（或行程）的生成以及汽车调度问题。本节重点介绍公交调度问题的回顾。Park and Kim（2010）中详细介绍了一般学校汽车路线问题的详细说明和相关文献的调查。总线调度指定每条路线的确切起始时间和结束时间，并形成可同一总线依次执行的一系列行程。
Gavish等人（1978）解决了一个总线调度问题，其中给出了行程的时间表（即出发时间和结束时间）这个问题被制定为运输问题（TP）。Orloff（1976）和Carraresi和Gallo（1984）处理了相同的汽车调度问题，但将其作为一个分配问题（AP）。
图1.一个示例问题 图2.样本解决方案
Louml;bel（1998a，b）考虑了公共交通中的多车库车辆调度问题（MDVSP），这与异构车队校车调度问题类似，将其作为多商品流问题进行了整合，结果表明即使给出了行程时间表，它也是NP完全的，并且提出了一种列生成方法作为解决方法。在MDVSP中，有多个仓库，每个车辆属于一个仓库，它应该从自己的仓库开始并结束，我们的问题没有这个限制。Hadjar等人（2006） 提出了MDVSP的分支-价格-剪切算法。Pepin等人（2009）比较了五种基于分解技术的启发式方法和MDVSP的启发式算法。Desaulniers 等人（1998）开发了一个整数非线性数学模型和一个带时间窗的MDVRP（MDVRPTW）的列生成嵌入式分支定界算法。Hadjar and Soumis(2009) 还提出了一种针对MDVRPTW的具有动态窗口缩减方法的分支和价格算法。
Orloff（1976）证明，当行程的到达时间不固定并给予学校时间窗时，同类的车队校车调度问题是NP完全的。他提出了一个基于匹配的构造算法和3-opt改进方法。
Newton and Thomas (1974), Bodin (1975), and Bodin and Berman (1979)假设有一些特殊的时间段，例如在一段时间开始的时候，汽车将完成他们前一段时间的任务，并将位于他们上一时期的目的地学校。在每个时间段内，每辆汽车都只能为一所学校转运学生，并且最多只能一次出行。 这个调度问题通过应用一系列TP解决方案来解决。但是，他们的假设过于简单。
Swersey和Ballard（1984）提出了校车调度问题的非线性规划模型及其离散近似MIP模型，将每个学校时间窗划分为固定数量的到达时间。他们使用线性松弛求解模型，并在解决方案具有非整数值时手动调整解决方案。
Graham and Nuttle（1986）测试了Orloff（1976）和Swersey和Ballard（1984）的算法。还测试了基于AP的算法，其中通过使用AP制定而不考虑时间窗限制来获得初始解，然后手动处理其可行性。该研究得出的结论是希望解决方案可行性和计算时间短的替代启发式方法。
Braca等人（1997）描述了纽约市校车路线问题。 虽然大多数文献解决了每所学校的独立问题，并确定了每辆汽车的路线安排，但他们使用随机插入式启发式解决了一个阶段所有学校的整个问题。
Spada等人（2005）考虑了多学校路由问题并提出了启发式方法。学校按其开课时间的顺序逐渐增加，每所学校的路线均采用贪婪方法，考虑到最小车辆的容量。之后，如果可能的话合并路线。再之后，通过模拟退火或禁忌搜索来改进合并路线。
Desrosiers等人（1981，1986）描述了一个计算机化校车路线选择系统，包括由学生停车分配，路线生成，学校启动时间调度和路线调度模块。他们认为可以从候选名单中选择一所学校的开课时间，以减少所需的汽车数量。关于作为本文主题的路由调度模块，他们制定并解决了一系列的TP。Desrosierset 等人（1986b）开发了三种算法，并对八个校车问题进行了测试。他们考虑了各种设置，例如问题发生在早上还是下午，以及时间窗的不同间隔长度。
Fuuml;genschuh（2009）也认为校车调度问题可以调整学校的出发时间和学生之间的转运。他将问题提出为一个基于VRPTW的整数规划模型，该模型是一种具有多种预处理机制和有效切割的分支-切割方法。然而，假设同类车队被给予，由于问题的复杂性，一些小问题在计算时限内（例如，一小时）不能被最优地解决。此外，假设学校的开学时间和行程开始时间都是针对现实世界问题集的实验。
总之，具有固定开始和结束时间的同类汽车的公交调度问题可以通过AP或TP来解决。AP方法也用于本文中的问题。但是，时间窗的公交调度问题很困难，目前还没有广泛使用的方法。尽管有人试图解决综合路由和调度问题（Braca 等人，1997; Spada等，2005; Newton and Thomas，1974; Bodin and Berman，1979），有些分别关注调度问题（Swersey和Ballard，1984;Desrosiers等人，1981， 1986A，B; Fuuml;genschuh，2009）。 本文分为后一种情况。除Spada等人（2005）和Fuuml;genschuh（2009），所有以前的作品都研究了同类车辆问题。我们将处理同质和异质的问题。据我们所知，目前还没有针对校车调度问题的公开可用的基准问题集，这使得难以测量算法的效率。本文预先发布了许多基准问题实例。
3.制定公交调度问题
公交日程安排问题可以按照以下方式建模为VRPTW。设vi为与行程ti相对应的虚拟停靠站，由一系列公交站点及其目的地学校组成。设pi为行程服务时间ti及其相应的虚拟停靠点vi。然后，可以将作为服务开始的可能时间范围的vi时间窗[ai，bi]确定为[sm_st pi，sm_et pi]，其中[sm_st，sm_et]是行程指定学校的时间窗（sm）。行程时间dij从虚拟停车vi到虚拟停车vj，可以通过由指定行程学校ti到第一个行程时间行程tj来确定。
在该模型中，使用以下指数：
以下常数用于简化公式的表述：
Eik= 1，如果公交k有资格服务行程ti; 0，否则
（i）=可以直接从停靠站i连接而不违反时间窗限制加上仓库索引（n 1）的一组虚拟停车索引，
-（j）=可以在不违反时间窗限制加上仓库索引（0）的情况下直接停在j之后的虚拟停靠索引的集合，
M0=足够大的数字
M =big M（Mge;M0)
决策变量如下：
xijk= 1，如果vj在vi乘坐汽车k后立即到达; 0，否则
Wik= 在vk处的服务开始时间，乘坐汽车k。
我们针对异构问题（MIPHE）的混合整数规划（MIP）模型如下：
目标函数(1) 是以字典方式最小化需要的车辆数量和总行程距离。约束条件（2）确保应将合格的汽车分配给每个虚拟车站。约束条件（3）是流量平衡约束条件，它可以确保汽车到达车站的次数与汽车从出发站出发的次数相匹配。约束条件（4）规定，当汽车k为停靠站i提供停靠站j后，停靠站j的服务开始时间大于或等于停靠站i的出发时间加上停靠站之间的行驶时间。约束（5）是时间窗的限制。约束条件（6）和（7）确保所有汽车从车站开始并结束。
请注意，该模型与普通VRPTW有两个不同的特征。首先，汽车和站点之间有资格。虽然假设所有车辆都有资格为任何服务停在一般的VRPTW中，只有当汽车有足够的停车容量，即Eik= 1时，汽车才能提供虚拟停车。例如，处理60名学生的行程不能由50个座位的校车服务。其次，我们的问题没有考虑学生沿公交时间表的积累。虽然在一般的VRPTW中负荷的积累不能超过车辆容量，但是由于每个虚拟车站都包含其学生乘客的指定学校，所以学生的积累不需要在我们的问题中检查。在学校访问后，汽车的容量可以更新。这个特点使得这个问题类似于满载的卡车负载问题。
用于同类车队问题的MIP模型更简单，因为只需要按组的顺序排列车站，并且不需要将特定车辆分配给序列。决策变量略有变化如下：
Xij= 1，如果vj紧接在vi之后由同一汽车服务; 0，否则
Wi= vi的服务开始时间
我们关于同类车队问题的MIP模型（MIPHO）如下：
约束的含义与MIPHE的相应约束相同。
4.解决方案
在下面的章节中，我们针对不同假设的问题提出解决方法。
4.1假设同类汽车和固定起动时间的问题
在这一小节中，处理了一个特殊的问题。如果我们假设虚拟站点的开始和结束服务时间是固定的，并且给出了同类车队，即所有车辆都可以服务任何车次，则可以将该问题模拟为AP。在最近的一个工业研究项目中，我们遇到了这些问题。
假设的问题可以模拟为一个AP（如图3所示）。节点i和节点j之间的成本cij定义如下：当虚拟站点i可以跟随虚拟站点j而不违反给定的开始和结束服务时间时，cij被设置为dij。 换句话说，当服务站点i之后在停靠站j处的汽车的到达时间（即，站点i的服务结束时间加上从停止站i到停止站j的行驶时间）不迟于停靠站j的服务开始时间，cij设为dij。 如果到达时间晚于开始服务时间，则cij被设置为M0 1。注意，当cij具有小值时，cij应该是M0 1这是由于上一节中解释的问
全文共15095字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[17095]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
