文摘

公共交通提供者面临不断提高服务质量和降低运营成本的压力。巴士司机调度是在这个领域研究最多的问题之一。在此基础上,灵活且强大的优化算法被开发和使用多年来帮他们完成这个挑战。特别是,现实生活中的大而复杂的问题实例通常需要新的方法来克服计算在解决他们的困难。因此,我们提出一个基于列生成hyper-heuristic寻找算法的解决方案。我们的方法利用启发式方法提供的好处自列选择模式是由一个使用各种策略hyper-heuristic列生成的子问题。该算法的性能比方法在文献中。计算结果在现实生活中的实例介绍和讨论。

1。介绍

公共汽车司机调度问题(BDSP)是一个极其复杂和重要的运输公司的业务规划过程的一部分。有效的安排可以节省大量的货币为交通运营商由于司机的工资是一个非常大的成本元素。此外,良好的人员计划确保较高的工作满意度。

巴士司机调度的过程需要分区车辆工作为一组法律驱动转变,应该反映效率的操作符的定义(1]。而根据劳动规则的约束和要求不同于国家,即使公司,评估标准和目标可能不同。

大量的研究工作在这个问题上已经取得了自1960年代以来在这一领域。许多科学方法和系统总线潜水员调度已报告在一系列的研讨会(2- - - - - -6]。这些方法有用的评论和相关评论已经由(7]。在这些规划和调度过程中,司机调度仍然是一个具有挑战性的问题,新方法不断寻求解决这个问题(8]。

介绍了列生成的(9),已广泛应用在过去的几年中在运输问题,调度、组合优化等。这种方法需要一个将原问题分解为两个问题,分别称为限制主问题和子问题。在文献中,列生成有效地应用于解决机组调度和其他相关问题(见[9- - - - - -11]),特别是对于现实问题的总线驱动调度(见[12])。然而,众所周知,列生成的缺点之一是所谓的“减弱不谋而合”效应:大量的迭代不显著的修改限制主问题的最优值(RMP)。虽然成功使用,这种方法存在收敛速度慢,有些限制其效率和可用性(13]。与此同时,hyper-heuristic是一个新兴的方法在搜索和优化14]。在大多数列生成而不是使用确切的方法,我们提出一个基于列生成hyper-heuristic方法实现高质量的解决方案在短的运行时间。

本文以以下方式组织。节2,我们给司机调度问题的定义问题。讨论该方法在部分3。节4使用真实的实例,比较结果,有些大的情况下,。最后,我们得出结论5。

2。公共汽车司机调度问题

2.1。术语

安排司机的任务之前,车辆路线必须构造。一个旅行是一个运动的车辆在一个给定的路径。这是服务的基本单位,每个访问都必须由一个单一的汽车。一个车辆阻塞旅行的序列是由一个车辆的时间离开仓库,直到它返回到仓库。从驾驶员的角度调度,司机只能在一些指定的地方叫做松了一口气救援点,这是由字母(A、B和C)在图1。时候车辆救援点,显著水平的时间尺度上,被称为救援的机会。两个连续救援机会之间的工作在相同的车辆的作品(或任务)的司机。一个司机的工作称为一天责任(或改变)。请注意,并不是所有的救济的机会将被用于减轻司机,因此司机可能涉及若干连续的块工作,称为拼写。

责任建立两个车之间的一个例子给出图块1。责任是由两个法术从两个街区。

根据时间职责涵盖,法律责任可分为以下五种类型。早期的责任开始在清晨的早上公共汽车车库前的峰值。一天的工作时间,这责任覆盖和凌晨12点之间。后期的责任下午开始和结束。一天的工作时间,这责任覆盖是12:00至20:00。晚上值班工作在晚上公交车返回车库的公交车。一天的工作时间,这责任覆盖22:00到凌晨。天的责任下午在早上开始和结束。一天的工作时间,这责任涵盖喂饲之间和16:00时。中间的责任工作期间的早上和晚上高峰。一天的工作时间,这个责任包括两个部分。一个是凌晨和喂饲之间,另一个是16至22:00。

用户可能对某些限制这些职责,以确保最终的日程安排不包含特定类型的过多或过少的职责。强加的限制可以开始或重新优化现有的解决方案。

2.2。数学公式

集合覆盖模型是公共汽车司机调度的基本模型。在公共交通解决机组调度问题的模型已流行多年(9,15]。在这里采用的配方,我们将考虑我们的方法基于集合覆盖问题的配方。虽然计划最终必须只有一个任务分配给每一块的工作,最好是让制定包括完全覆盖的可能性和使用集合覆盖,而不是设置分区。一方面,整数解有约束由两个或两个以上的非零变量,在调度术语意味着两个或两个以上的职责分配给相同的作品。这样做的原因是可以有危险,可能没有可行的解决方案,“配合”不会造成任何外壳。另一方面,生产解决方案通常没有完全覆盖的工作;集合覆盖模型最常见的结果在两个职责重叠。如果发生完全覆盖,它可以很容易地消除通过编辑日程。

让是法律责任的设置组块的工作要覆盖。我们可以定义问题,建设一个矩阵,在司机出现在列和行工作。为每个元素,,,指示的义务涵盖的作品否则,它是0。它可以制定如下: 受 在哪里是关税的数量;是工件的数量;是成本的责任吗;等于如果责任在解决方案和使用否则。和重量是常数。一般来说,运输公司的主要目标是获得一个解决方案的最小数量的职责。对于这个目标,我们考虑在这里。

约束(2)表明,每件工作必须由至少一个责任。我们考虑到成本在我们的工作基于[15]: 在哪里 在哪里的成本是司机吗;加时赛结束了正常的工作时间由法律建立的司机吗(小时);的空闲时间是司机吗(时间司机不是工作在他的转变);是正常工作时间(小时);任务的完成时间吗;任务的开始时间吗;的第一个任务是吗司机的转变;的最后一个任务吗司机的转变。

3所示。解决方法

BDSP列生成算法是追杀给少量的关税(列)。这些职责构成初始列限制主问题(RMP)。反馈的最优双值RMP用于解决一个定价子问题,旨在确定职责-降低成本,提高了RMP的目标函数值。BDSP通常的定价子问题建模为一个约束最短路径问题解决在一个有向无环图,然后使用动态编程技术解决了(9]。然而,由于缺陷生成的子问题列将在真正的问题实例计算昂贵的(16),列生成解决大型实例没有多大进展。因此,主要工作依赖于子问题加速列生成的整个过程。在这里,我们提出了基于列生成hyper-heuristic方法解决BDSP。这种方法提供了两个显著的优势。首先,由于列生成闻名收敛性差,没有必要只选择一列与降低成本最低;事实上,任何列与消极的成本会降低。使用此观察可以提高整体效率。在我们的研究中“快速添加列”的想法是添加的一组列快速通过迭代求解子问题使用一组低启发式。因此,多个责任与负面降低成本甚至可能将保罗带进每个迭代限制子集。其次,选择不同的列-降低成本,可以有效地执行(或生成),[13),以避免快速增加和无用的RMP大小。事实上,我们的方法可以选择一个好的“多样性”的职责通过使用这些低启发式改进解决方案没有大量增加计算时间。定价步骤中起着重要作用的列生成方法的效率。

大纲的算法如下。

步骤0(预处理)。生成所有有效的职责。然后,这些职责形成一列池。

步骤1(构造一个初始解)。带一个小的子集的职责作为初始设置的列。

步骤2 (RMP)的解决。解决了LP在当前任务子集和计算的一组列的影子价格。

步骤3(任务管理)。控制列池和删除的列RMP如果必要的话。

步骤4(选择的新职责)。选择税与负面降低成本从而提高解决方案,并将它们添加到RMP。

第五步(停止准则)。如果停止准则,然后去一步;去其他步骤。

步骤6(找到整数解)。独立解决,得到一个整数解。

整体执行之间的迭代步骤和。在第一次迭代步中创建它使用列。

在本节的其余部分,我们提供上述每个步骤的细节。

3.1。步骤0:预处理

在我们的方法生成所有可行的预处理步骤中职责明确。,部分工作的所有可能的组合是有效的根据一组劳动合同法规。预先产生关税的好处之一是,不同的任务集可以被识别,这样有经验的调度器可以“共享”自己的知识而不是依靠“黑匣子”生产时间表。纠错或实验变化可以进行相对迅速地在搜索结果时间表(17]。此外,预处理是一个重要的过程来表达“偏好”和“undesirableness”,这是由一个用户定义的策略。如前所述(16),软参数用于限制关税的产生,例如,限制的最大数量责任四个法术。与此同时,一系列的首选职责可以确定相对较快;例如,职责与空闲时间小于平均优先。在这里,这种预处理可以帮助我们找到“好”的一个子集的职责时,我们需要在搜索过程中使用它们。

正式,我们做以下定义。

定义1。给定一个责任,让表示一种解脱机会起点在一块工作覆盖的责任。对于一个给定的救济的机会,我们定义了一个救援和救灾点的时间作为和,分别。然后,。

定义2。给定一个责任,让表示一种解脱机会终点在一块工作覆盖的责任。对于一个给定的救济的机会,我们定义了一个救援和救灾点的时间作为和,分别。然后,。

基于上述定义,一块工作覆盖的责任用

因此,块的工作组成的一种责任可以被定义为

根据定义1和2,每一个的责任是被迫满足所有下列基本约束: 在哪里最大工作时间(小时+小时);最大有效工作时间;是任务的到达车站;离开车站的任务;必要的时间到达吗从。

在这里,我们提出一个方法来生成有效的算法中潜在的职责如下1。初始化算法通过设置一定数量的金币和等于。救援的机会选择生成一组所有可能的工作根据给定的公交时刻表。注意作品的最大数量,限于组成一种责任,是不同的在一些实际案例中,例如,不超过4个法术(18]。另一个例子是来自[19),在他们的情况下,最大的=。因此,我们将参考所需数量的部分由公共汽车公司。让我们表示对应块的最短长度(行)。然后,我们可以计算的最大数量(职责的最大工作时间除以最短的时间片)。因此,由和。最后,后工作的过程增加了一块一块的工作变成一种责任,直到作品的最大数量。嵌套循环线(7)-(19)迭代逐渐通过每个车辆的所有的工作。行检查工作满足约束(9)- (13),然后添加职责到池中。

3.2。步骤1:建立一个初始解

计算初始影子价格,我们建议一个贪婪的建设性的启发式。最初的解决方案是由一个连续的机制,其主要目的是获取双变量的初始值来选择更多的职责和改善线性解决方案的步骤。中给出的程序算法2。给定一组法律职责和一组的工作要覆盖,让是一组的工作涉及到目前为止。建设性的启发式,添加一个新的任务没有分配在一个贪婪的当前计划在每个迭代的方法。这一目标,我们计算一个新的责任成本作为我们选择的贪婪的函数在每个迭代。成本的新职责可以计算如下: 在哪里是成本的责任吗在迭代;如果没有覆盖的作品覆盖着后迭代,否则。特别是,如果,。

最后,重复这个过程,直到所有的作品。

3.3。步骤2:限制主问题

一个典型的列生成后,IP的LP放松是必要的应用;也就是说,我们放松整数约束(4)。因此,约束(4)可以写成

解决RMP的目的是找到双重价格,或影子价格,对应的工作问题。这些值用于计算新关税的降低成本中所描述的步骤。

3.4。步骤3:任务管理

任务管理(或列管理)是不可分割的一部分,任何成功的列生成算法中讨论(18- - - - - -20.]。

在这项研究中,有两个原因为什么这个过程。

首先,在每个列生成迭代我们插入所有列负面降低成本已经发现的定价算法RMP(参见步骤)。因此,很明显,RMP的过程不是有效的列如果有超过一个特定的最大数量。在我们的测试中,所有的关税降低成本大于给定的阈值时将被删除任务的数量超过50000。类似的策略被用于(21]。这个过程尤为重要,当RMP列生成过程中持续增长巨大。

其次,关税(参见步骤的选择)有时会加速不损失质量如果产生关税的数量可以减少智能(18]。由于关税对一些现实问题的数量可能很大,我们考虑采取措施,防止“坏”的质量责任到我们的程序。下列程序迭代只要职责保持超过100000的数量。每个潜在的责任将排名通过结合两个属性:一个索引,反映了其明显的效率(驾驶时间除以工作时间)和一个比率反映了相同的职责;例如,一个比责任由另一个责任是完全包含。然后,排名最低的关税被丢弃,直到一些明确的条件得到满足。移除这些关税降低了子问题的总体规模,从而降低运行时和内存使用的要求。

3.5。第四步:选择的新职责

列生成的主要组件是选择的过程(生成)候选人的职责把限制在每个迭代中子集。的目标是提高LP放松限制主问题。因此,该子问题的目标是选择消极的降低成本的职责没有限制子集。我们现在为这个过程的细节确定职责提供负面降低成本在每一个迭代。降低成本从成本和获得双重价值每个对应的集合覆盖约束的在前一节中给出。只有负廉租路线可以进入限制主问题,降低成本应该最小化或约束是负的。使用对偶变量的LP方法,计算每个任务的降低成本 在哪里降低成本的责任(列);是成本的责任;双重任务的价格吗。

在这个研究中,我们开发一个基于hyper-heuristic的想法,启发式方法虽然有效,不能保证识别的所有列。加快搜索列与消极的降低成本,我们执行启发式定价。除了节省计算时间,这也使得在每次运行生成多个列。一个启发式方法是贪婪的,通过应用不同的启发式方法,我们可以保持列的多样性,避免陷入局部最优的方向。基于该框架hyper-heuristic [14,22),竞争规则应用于指导低级的选择启发式搜索过程中。当一个低级启发式,这个低级的启发式的表现将被选择的一个函数。防止持有大量计算时间表现不佳的启发式低,简单的排名(23)是用来排除最糟糕的启发式根据其成绩在过去应用在每一个迭代。有四种不同情况下(如表所示1),以反映低级启发式的重要性能。

在每一次迭代,计算每个低级的启发式 在哪里的分数是。

注意,如果每个low-heuristic总分在给定迭代相同,没有low-heuristic会被排除在外。五个启发式选择在同一时间开始征收新的关税。

3.5.1。交换启发式

作者在24)认为,如果一个专栏中获得的最优解适当修改,它可能会得到一个新的列-降低成本。出于这个原因,我们尽量选择这一启发式的列数。

交换启发式正式书面如下。给定一个责任从最优解限制的主问题,我们分解责任连续随机选择的部分责任,块的工作(战俘)。此外,假设和,然后分解为,。因此,所有包含的职责或中可以找到(参见步骤)。因此,我们可以选择的义务与RMP -降低成本。执行这个过程,直到至少有一个新的责任负可以找到降低成本或预定义的尝试没有成功。

3.5.2。本地搜索版本1

我们知道,搜索空间的元素由不同的职责。因此,我们可以考虑几个邻里关系根据任务的性质,也就是说,任务类型,施法数量和成本。然后,邻居之一是随机选择以获得足够的“好”的责任在应用本地搜索。在下面,我们将描述一个邻里关系,我们考虑在我们的案例中。

正是前面提到的五种指定一种责任:责任,初末责任,晚上义务,责任,和中层的职责。让是职责的一个子集,每个的责任执行相同的任务类型。如算法的伪代码3,社区允许搜索(步骤的算法3)。然后,本地搜索从一种责任通过使用2-exchange,遵循随机序列的职责(步骤(5)-(7)的算法3)。如果用更少的降低成本,将被替换(步骤的算法3)。所有上述步骤将被重复,直到达到预定义的迭代次数。

3.5.3。本地搜索版本2

这种启发式方法是类似的本地搜索版本1,除了贪婪策略是使用邻域选择模式。我们定义一组社区使用法术的数量。因此,这些不同的社区可以排名顺序后裔。法术的最大数量的义务将检查在每个迭代。然而,另一个邻居会选择根据排名如果责任-降低成本无法找到在这个邻居尝试没有成功。等等这样的搜索方式,整个搜索满足适当的停止条件时停止(在这里我们使用一个最大允许基于CPU时间)的迭代次数。

3.5.4。Greedy-Based启发式版本1

而不是搜索整个空间,第一个启发式试图推动搜索的区域空间。我们保持一个合理的大小的职责被认为有效地搜索(即。,数量有限的职责)。然后我们找一个“理想的”责任在这个子集。

更确切的说,让只能存储池,关税的成本不到一个自适应的阈值。这个阈值是动态控制参数。然后,后代的职责要求根据他们的成本。将要检查职责,因此,根据这个排名顺序一个接一个,直到一些停止标准之一是满足,这是时间限制或找到一个责任与负面降低成本。事实上,启发式不能找到一个“理想的”责任一定时间后整个搜索停止;这也许意味着门槛应该增加。在这里,我们定义的阈值将被更新。

3.5.5。Greedy-Based启发式版本2

这种启发式方法类似于greedy-based启发式版本1,除了池中随机选择的责任在每一次迭代时将检查。

3.6。第五步:停止准则

在这项工作中,定义了两个停止标准在我们的方法:()不与负面发现降低成本和责任()的期限。

3.7。第六步:找到整数解

如前所述,列生成用于解决轻松掌握的问题。因此,由此产生的资讯解决方案产生了一个解决方案部分的职责和整数必须找到解决方案。在这种情况下,一个分支界限法过程的使用是为了提供一个整数解。几个分支策略兼容列生成技术进行了讨论(21,25]。约束分支,最初提议在26),广泛用于分支策略。理论上,约束分支用于设置分区模型和可能导致次优性如果应用于不等式约束,但由于当前最优整数解问题不一定等于最优时间表和用户很少可以指定他们所说的最优性,重点是找到一个好的快速整数解。正式,让是一组变量的最优RMP部分解决方案,其中每个变量覆盖任务和同时作为解决方案的总和值变量的集合。在[26),任何最优部分解决方案包含至少一个约束,,是严格在0和1之间(见证明(27):

相当于零分支,一个分支,分别

应用上面的分支策略问题,分支是由解决方案空间划分成两组。分支可以对0-branch:

0-branch部队职责覆盖这两个任务都是被禁止的。第一分院,

第一分院意味着任何责任涵盖(或),但不(或)必须被排除在外。

而不是解决线性规划的最优性,我们可以选择提前结束这个过程如果上界和下界之间的相对差距小于。上限的客观值是整数解。

可以获得一个下界。

磅是最优解的下界值计算解决(LP放松1)和围捕相应的值。列生成迭代时可以终止这种差距小于一个用户定义的宽容,给算法定义质量的解决方案。

定义3。 公共汽车的总运行时间,可以计算从公共汽车时刻表。

假设用户预先确定作为一个司机每天的最大工作时间,给估计司机计算预期的数量

命题4。 是一个紧低。

证明。给定一个公共汽车时刻表,是恒定的。让职责的集合在一个最佳的解决方案。请注意许多司机在吗。
情况下 。责任的有效工作时间最大工作时间吗。因此,
情况下 。它发生在至少有一个责任这样的有效工作时间是不平等的: 在哪里和整数。
因此是一个紧低。

这个流程将继续,直到差距小于一个用户定义的宽容,给算法定义质量的解决方案。然而,这可能是耗时的大问题。因此,分支过程将终止搜索一旦一个整体的解决方案被发现如果超过给定的执行时间。

4所示。计算结果

在本节中,我们提出建议的方法的结果在几个真实的实例。这些实例大小不同和复杂性。的情况下,用一个——一个在表2来自毛里和罗瑞拉(15]。在过去的两个实例,测试数据来自两行总线在北京。表2显示了大小(部分工作)和最著名的现实问题的结果。

为了评估解决方案的质量得到这里介绍我们的方法,测量质量的启发式调度显示如下:

个人电脑中的所有计算实验与英特尔酷睿2双核处理器的CPU T5870GHz, 1.99 GHz 2.00 G RAM内存Microsoft Windows 2002。整个实现是c#语言开发的,并符合使用网络框架的版本。独立工党解决实验中使用术语。这个软件被用来解决RMP每次迭代定价。阈值被设置为最小值在步骤。子问题的计算时间探索搜索空间是有限的时间(3600秒)。

结果表3表明,在大多数情况下的实例——一个我们的方法可以找到解决方案,最著名的是一样的解决方案。我们也可以发现,我们的方法不执行像一个在一些小型实例——一个PTA / LP和助教/ LP相比,SA。然而,随着实例的大小增加,我们的方法执行得更好。这是因为,对于小实例,我们的方法太过复杂,计算时间长。但对于大型实例,经典方法满足组合爆炸的问题,这是典型的NP问题的特性,而我们的方法开始显示其节省计算时间的优点。

在表4我们提出“手动”解决方案的两个实例目前使用的公司,与我们的方法获得的解决方案。我们的解决方案表示减少和分别在手动解决方案。这个改进的时间表非常接受用户。

5。结论

我们描述一个方法寻找算法解决司机调度问题。合适的列生成和hyper-heuristic可以受益很多从协同作用,表现出更高的性能对解决方案的质量和时间某些情况下,而列生成的组合和hyper-heuristic也需要大量的进一步的研究,使他们全面发展。我们的未来在这种混合方法将仍然继续工作。

利益冲突

作者宣称没有利益冲突有关的出版。

承认

这项工作是支持的基础研究基金为中央大学(2014 jbm072)。