The periodic service intention as a conceptual framework for generating timetables with partial periodicity
The periodic service intention as a conceptual framework for generating timetables with partial periodicity
复制标题
DOI：
10.1080/03081060.2011.577151
复制
发表时间：
2011-05
影响因子：
1.6
通讯作者：
G. Caimi;M. Laumanns;Kaspar Schüpbach;Stefan Wörner;M. Fuchsberger
中科院分区：
文献类型：
--
作者：
G. Caimi;M. Laumanns;Kaspar Schüpbach;Stefan Wörner;M. Fuchsberger
摘要欧洲许多铁路公司实行定期列车时刻表。然而，大多数时间表并不完全是周期性的，而是有不同的周期和许多例外的混合，以科普不断变化的需求。目前的自动时间表生成方法不能处理这种部分周期性的结构，但只考虑完全周期性的输入。因此，我们引入定期服务意向（pSI）作为一个框架，客户相关的信息，火车服务，包括其周期性信息可以被描述。然后，我们解决的问题，找到一个可行的时间表，满足规定的要求，而不需要手动后处理的pSI。我们解决这个问题，预计列车运行超过等价类，从而减少了pSI的一个增强的实例周期性discoverabling。因此，有可能使用现有的周期性调度模型，如周期性事件调度问题，以生成具有部分周期性的周期性时间表，这些时间表最终被推出，以根据pSI的商业要求获得所需的每日时间表。2008年瑞士中部时间表的测试案例结果表明，这种方法只需要比完全周期性实例稍长的计算时间，但额外的时间被后处理变得不必要和解决方案的质量更好所补偿。这种方法特别适合于周期性很强但有些不规则的报盘，现有方法无法适当处理这些报盘。
Abstract Many railway companies in Europe operate periodic timetables. Yet most timetables are not entirely periodic but have a mixture of different periodicities and many exceptions to cope with changing demand. Current approaches for automatic timetable generation are not able to deal with such partially periodic structures but consider only fully periodic inputs. We therefore introduce the periodic Service Intention (pSI) as a framework where customer-relevant information about train services can be described, including their periodicity information. We then address the problem of finding a feasible timetable that fulfills the requirements specified in a pSI without the need for manual post-processing. We solve this problem by projecting intended train runs over equivalence classes and thereby reducing the pSI to an augmented instance of periodic timetabling. Thus it is possible to use existing models for periodic scheduling, such as Periodic Event Scheduling Problem, to generate periodic timetables with partial periodicity, which are finally rolled out to obtain the desired daily schedule according to the commercial requirements of the pSI. Results for a test case from the timetable for central Switzerland in 2008 show that this approach needs only slightly longer computation time than for a fully periodic instance, but the additional time is compensated by the fact that post-processing becomes unnecessary and by the better quality of the solution. The approach is particularly well suited for offers with a strong periodicity but some irregularities, which could not be treated properly by existing methods.