An IP-based heuristic for the post enrolment course timetabling problem of the ITC2007

Track 2 of the international timetabling competition 2007 was a post enrolment course timetabling problem. A set of events has to be assigned to a timeslot and to a room such that all students are able to attend their requested events while not violating the hard constraints. There are also soft constraints that make the timetable “nicer”.     

Designing Conferences to Improve Resource Utilization and Participant Satisfaction

We look at a conference scheduling problem with the objective of maximizing the ability of participants to attend sessions of interest. This problem was addressed in an article by Eglese and Rand; conference scheduling has otherwise received little attention in management science literature. Related problems of class- and exam-scheduling have been extensively studied and published, yet few cases consider participant (e.g. student) preferences. Our formulation, which a variation of that used by Eglese and Rand, includes prioritized preferences for conference sessions, as well as schedule resource constraints. The purpose of this paper is to extend the previous work by exploring the impact of various scheduling decisions on participant satisfaction (measured by enrollment in desired sessions). We use a previously published algorithm to look at issues such as conference length and make general observations that may aid the conference-scheduling decision maker.     

基于遗传算法的大学课程表问题研究

课程表问题是时间表问题之一 ,也是 NP难问题 .根据大学授课形式的特点建立了大学课程表问题的数学模型 ,给出了求解该问题的遗传算法 .根据模型和大学课程表问题的特点设计了一种全新的编码 ,提出了一种新形式的交叉方式 .实验结果表明该方法是可行和有效的 .     

Stability evaluation of a railway timetable at station level

This research deals with a real-world planning problem in railway infrastructure operations. It is part of the RECIFE project, which seeks to develop a decision support software to help evaluate the capacity of a rail junction or station. To this end, the project is working on a timetable optimization model, as well as timetable evaluation modules. This paper presents a module for evaluating timetable stability, which uses an original method based on delay propagation and using shortest path problem resolution. A didactic example and a complete case study applying this method to the Pierrefitte-Gonesse junction are also presented.     

Zurückführung des Stundenplanproblems auf ein dreidimensionales Transportproblem

Zusammenfassung Unter den verschiedenen Versuchen, mittels Computer einen Stundenplan zu bekommen, gibt es bis jetzt nur wenige, die das Problem erfolgreich auf mathematischem Wege angingen. Gewöhnlich konnte dabei immer nur eine vereinfachte Form des Problems gelöst werden, und eine Lösung des allgemeinen Problems steht noch aus. Diese Arbeit zeigt eine weitere Möglichkeit für eine mathematische Behandlung, indem ein Stundenplanproblem auf die Form eines dreidimensionalen Transportproblems zurückgeführt wird. Dadurch eröffnen sich neue Möglichkeiten, da für die Lösung dieses Transportproblems eigene Algorithmen existieren. Ferner kann man weitere notwendige Bedingungen für die Existenz eines Stundenplans finden, die über die derzeit bekannten hinausgehen.

---

Summary Among the different approaches to get a timetable by computer there are only a few which succeeded in solving the problem mathematically. Usually, in these cases only a reduced timetable problem could be handled and the solution of the general prolbem still remains. The present paper contains an additional approach of mathematical treatment by formulating a timetable problem as a multi-index transportation problem. Through that the special algorithms for the solution of this transportation problem can be used to solve the timetable problem. Moreover it is possible to find additional necessary conditions for the existence of a timetable which had not been known up to now.

     

Real-time freight locomotive rescheduling and uncovered train detection during disruption

This paper discusses rescheduling of freight train locomotives when dealing with a disrupted situation in the daily operations in Japan. Within the current framework of dispatching processes, passenger railway operators modify the entire timetables and an adjusted freight train timetable is distributed to a freight train operator. For this timetable, we solve the locomotive rescheduling problem by changing the assignment of the locomotives to all the trains and considering their periodic inspections. We then solve the uncovered train detection problem that selects unassigned trains according to their value if the rescheduling phase fails.     

Integration of timetable planning and rolling stock in rapid transit networks

The aim of this paper is to propose an integrated planning model to adequate the offered capacity and system frequencies to attend the increased passenger demand and traffic congestion around urban and suburban areas. The railway capacity is studied in line planning, however, these planned frequencies were obtained without accounting for rolling stock flows through the rapid transit network. In order to provide the problem more freedom to decide rolling stock flows and therefore better adjusting these flows to passenger demand, a new integrated model is proposed, where frequencies are readjusted. Then, the railway timetable and rolling stock assignment are also calculated, where shunting operations are taken into account. These operations may sometimes malfunction, causing localized incidents that could propagate throughout the entire network due to cascading effects. This type of operations will be penalized with the goal of selectively avoiding them and ameliorating their high malfunction probabilities. Swapping operations will also be ensured using homogeneous rolling stock material and ensuring parkings in strategic stations. We illustrate our model using computational experiments drawn from RENFE (the main Spanish operator of suburban passenger trains) in Madrid, Spain. The results show that through this integrated approach a greater robustness degree can be obtained.     

公交车优化调度中的几个问题的研究

本文将 2 0 0 1 CMCM B题公交车调度的最优化问题分成两个相对独立的问题来讨论 ,由所要运送的乘客数来决定公交公司的最小车辆数 ,由乘客到达来决定发车时刻表 .我们求出了最小车辆数和一个可行的最优时刻表 .     

A 2-generated just-infinite profinite group which is not positively generated

We construct a 2-generated profinite group which is just-infinite and not positively generated. This paper was mainly conceived during the workshop “Groups and Probability” organized in Budapest (June 30 – July 4, 2003) by the Erdős Center. Stimulating conversations during the conference led to this result and the author is grateful to both the organizers and the participants.     

Adjusting a railway timetable in case of partial or complete blockades

Unexpected events, such as accidents or track damages, can have a significant impact on the railway system so that trains need to be canceled and delayed. In case of a disruption it is important that dispatchers quickly present a good solution in order to minimize the nuisance for the passengers. In this paper, we focus on adjusting the timetable of a passenger railway operator in case of major disruptions. Both a partial and a complete blockade of a railway line are considered. Given a disrupted infrastructure situation and a forecast of the characteristics of the disruption, our goal is to determine a disposition timetable, specifying which trains will still be operated during the disruption and determining the timetable of these trains. Without explicitly taking the rolling stock rescheduling problem into account, we develop our models such that the probability that feasible solutions to this problem exist, is high. The main objective is to maximize the service level offered to the passengers. We present integer programming formulations and test our models using instances from Netherlands Railways.     

Comprehensive approach to student sectioning

Student sectioning is the problem of assigning students to particular sections of courses they request while respecting constraints such as course structures, section limits, and reserved spaces. Students may also provide preferences on class times and course alternatives. In this paper, three approaches to this problem are examined and combined in order to tackle it on a practical level: student sectioning during course timetabling, batch sectioning after a complete timetable is developed, and online sectioning for making additional changes to student schedules. An application and some practical results of the proposed solutions based on actual data are also included.     

Flexible <Emphasis Type="Italic">versus</Emphasis> fixed timetabling: a case study

This case study presents the timetabling problem of the Flight Training Department at Embry-Riddle Aeronautical University. The problem consists of scheduling the flight resources to students to various time blocks. This problem represents a well-studied field in operations research, mainly adopting variations of mathematical programming models. This paper initially presents the efforts towards developing a fixed timetable using optimization models for the case under study. It is, however, demonstrated that implementation of optimum solutions obtained using this approach cannot be sustained, mainly because of the dynamic nature of the governing parameters. A flexible and dynamic timetable utilizing the university computer network, allowing the instructors and students to make their own decentralized flexible timetables, is proposed. A simulation study is initiated to compare the performance measures under both timetables. The analysis shows that implementation of a flexible system generates higher utilization of flight resources as well as improving key performance measures.     

Universiti Malaysia Pahang examination timetabling problem: scheduling invigilators

This paper presents a real-world examination timetabling problem from Universiti Malaysia Pahang (UMP), Malaysia. The problem involves assigning invigilators to examination rooms. This problem has received less attention than the examination timetabling problem from the research community partly because no data sets are available in the literature. In modelling, and solving, this problem we assume that there is already an examination timetable in place (this was the subject of our previous work) and the task is to assign invigilators to that timetable. The contributions of this paper are to formally define the invigilator scheduling problem and to present a constructive algorithm that is able to produce good quality solutions that are superior to the solutions produced when using the university's current software. We also include additional constraints taking into account the comments made by the invigilators, which the current system fails to capture. The model we present, we believe, accurately reflects the real-world problem, capturing various aspects of the problem that have not been presented before in the scientific literature. Moreover, the proposed approach adheres to all hard constraints, which the university's current system fails to do.     

A probabilistic (max, +) approach for determining railway infrastructure capacity

We consider the problem of determining the capacity of a planned railway infrastructure layout under uncertainties. In order to address the long-term nature of the problem, in which the exact (future) demand of service is unknown, we develop a “timetable”-free approach to avoid the specification of a particular timetable. We consider a generic infra-element that allows a concise representation of many different combinations of infrastructure, safety systems and traffic regimes, such as mixed double and single track lines (e.g., a double track line including a single tunnel tube), and train operations on partly overlapping routes at station yards. We translate the capacity assessment problem for such a generic infra-element into an optimization problem and provide a solution procedure. We illustrate our approach with a capacity assessment for the newly built high-speed railway line in The Netherlands.     

Iterative algorithms for the curfew planning problem

The curfew planning problem is to design an annual timetable for railway track maintenance teams. Each team is capable of handling certain types of repairs and replacement jobs. The jobs are combined into a set of projects according to their locations and types. The timetable shows which project should be worked on by each team on a weekly basis throughout an entire year. Our objective is to design a schedule with minimum network disruption due to ongoing maintenance projects that require absolute curfew. Absolute curfew projects are those that cause complete closure of the rail traffic. For tackling this problem, we develop four optimization-based iterative algorithms. We also present very promising computational results obtained within a few minutes using data provided by a major North American railroad.     

Scheduling a non-professional indoor football league: a tabu search based approach

This paper deals with a real-life scheduling problem of a non-professional indoor football league. The goal is to develop a schedule for a time-relaxed, double round-robin tournament which avoids close successions of games involving the same team in a limited period of time. This scheduling problem is interesting, because games are not planned in rounds. Instead, each team provides time slots in which they can play a home game, and time slots in which they cannot play at all. We present an integer programming formulation and a heuristic based on tabu search. The core component of this algorithm consists of solving a transportation problem, which schedules (or reschedules) all home games of a team. Our heuristic generates schedules with a quality comparable to those found with IP solvers, however with considerably less computational effort. These schedules were approved by the league organizers, and used in practice for the seasons 2009–2010 till 2016–2017.

     

公交网络时刻表再协同设计的多目标优化模型

为了改善公交服务质量,公交运营者试图调整现有时刻表的发车时间,使不同线路的车次协同到达换乘站点以方便乘客换乘。针对此场景,研究了公交时刻表重新协同设计问题,提出了求解该问题的多目标模型。模型考虑了对发车间隔灵敏的乘客需求、灵活的车次协同到站方式和发车时间的规则性,分析了该多目标模型的特征和计算复杂性,表明本文研究的问题是NP-hard问题,且它的帕累托最优前沿是非凸的,设计了基于非支配排序的遗传算法求解模型。算例表明,与枚举算法相比,提出的求解算法在较短的时间内可获得高质量的帕累托解。     

A Boolean matrix iteration in timetable construction

The annoying experience in timetable construction is that usually a complete timetable cannot be found without violating or diminishing some preconditions, even if the problem is theoretically solvable. Neither the control of the Hall conditions by Gotlieb's process of reducing availabilities nor the application of elaborate exchange operations guarantees a solution. In this paper an iteration of elementary implications is described which is expected to improve this situation, if applied in the final period of construction. In the course of these investigations, some formulas on Boolean matrices are derived, and a Galois connection between sets of Boolean vectors and Boolean matrices is exhibited.     

Metaheuristics for High School Timetabling

In this paper we present the results of an investigation of the possibilities offered by three well-known metaheuristic algorithms to solve the timetable problem, a multi-constrained, NP-hard, combinatorial optimization problem with real-world applications. First, we present our model of the problem, including the definition of a hierarchical structure for the objective function, and of the neighborhood search operators which we apply to matrices representing timetables. Then we report about the outcomes of the utilization of the implemented systems to the specific case of the generation of a school timetable. We compare the results obtained by simu lated annealing, tabu search and two versions, with and without local search, of the genetic algorithm. Our results show that GA with local search and tabu search based on temporary problem relaxations both outperform simulated annealing and handmade timetables.     

A decision making procedure for robust train rescheduling based on mixed integer linear programming and Data Envelopment Analysis

This paper presents a self-learning decision making procedure for robust real-time train rescheduling in case of disturbances. The procedure is applicable to aperiodic timetables of mixed-tracked networks and it consists of three steps. The first two are executed in real-time and provide the rescheduled timetable, while the third one is executed offline and guarantees the self-learning part of the method. In particular, in the first step, a robust timetable is determined, which is valid for a finite time horizon. This robust timetable is obtained solving a mixed integer linear programming problem aimed at finding the optimal compromise between two objectives: the minimization of the delays of the trains and the maximization of the robustness of the timetable. In the second step, a merging procedure is first used to join the obtained timetable with the nominal one. Then, a heuristics is applied to identify and solve all conflicts eventually arising after the merging procedure. Finally, in the third step an offline cross-efficiency fuzzy Data Envelopment Analysis technique is applied to evaluate the efficiency of the rescheduled timetable in terms of delays minimization and robustness maximization when different relevance weights (defining the compromise between the two optimization objectives) are used in the first step. The procedure is thus able to determine appropriate relevance weights to employ when disturbances of the same type affect again the network. The railway service provider can take advantage of this procedure to automate, optimize, and expedite the rescheduling process. Moreover, thanks to the self-learning capability of the procedure, the quality of the rescheduling is improved at each reapplication of the method. The technique is applied to a real data set related to a regional railway network in Southern Italy to test its effectiveness.