Search

University timetable scheduling, which is a typical problem that all universities around the world have to face every semester, is an NP-hard problem. It is the task of allocating the right timeslots and classrooms for various courses by taking into account predefined constraints. In the current literature, many approaches have been proposed to find feasible timetables. Among others, swarm-based algorithms are promising candidates because of their effectiveness and flexibility. This paper investigates proposing an approach to university timetable scheduling using a recent novel swarm-based algorithm named Spotted Hyena Optimizer (SHO) which is inspired by the hunting behaviour of spotted hyenas. Then, a combination of SA and SHO algorithms also investigated to improve the overall performance of the proposed method. We also illustrate the proposed method on a real-world university timetabling problem in Vietnam. Experimental results have indicated the efficiency of the proposed method in comparison to other competitive metaheuristic algorithm such as PSO algorithm in finding feasible timetables. Web of Science 5 4 439 421

The article presents issues concerning rail transport (rail, metro and tramway) and factors influencing the planned implementation of the schedule. At the beginning, the scope of application of the robustness concept was analysed, based on scientific and industry literature. Then the attention was focused on the model of the rail transport system and the schedule, the basic indicator of robustness assessment was discussed, taking into account the methods of analysis used and many variables occurring in rail transport. Finally, a review of the state of knowledge is summarised and the most important observations from the analysis are indicated. In the case of a robust schedule there is no propagation of disruption across the network after an adverse event has occurred.

The performance of the West Midlands Metro in the United Kingdom is analyzed in the present study by evaluating the existing timetables of the metro system. Using SIMUL8 computer software, a discrete event-based simulation prototype modeling the metro system is developed and implemented. The model adequately describes the performance of the West Midlands Metro system. By running simulations, the overall utilization level of the metro system is calculated. The results of the simulation model indicate that the metro system is being underutilized. The low utilization rates indicate a potential for the introduction of new services capable of exploiting the existing infrastructure and improving the utilization levels of the existing metro system; For example, the potential of using the current metro system for urban freight transport could be a new service of interest and provide scope for further research.

With the aim of supporting the process of scheduling a hybrid cyclic timetable and adapting traffic needs, this paper is concerned with inserting additional train paths problem for tactical and short-term planning applications with multiple objectives. Focusing on an existing cyclic timetable on a high-speed passenger rail line, the problem is to minimize both the total adjustments for initial trains and the number of required train-sets. The timetable scheduling, train-set planning and rescheduling are three complex optimization problems respectively and usually solved in a sequential manner. In this paper, these phases are integrated in a mixed integer programming model, and the multi-objective adding train paths (ATP) model is proposed, which decides simultaneously initial trains' modifications, additional trains' schedules and train-set circulation. The tolerance of disruption for initial trains including allowed adjustment and periodic structure is taken into account in light of the practical concerns. The difficulty of this integrated problem is that train-sets circulation is usually determined after all of the train lines and timetable have been fixed. However, in the adding train paths problem, the additional trains do not exist in the initial timetable. In order to solve the problem in a reasonable time, a relaxation approach to the adding paths problem is presented. We start from fixed train-set route, and then apply flexible train-set route that provides possible alternative turning activities to decrease the number of required train-sets. A case study based on Shanghai-Hangzhou high-speed rail line in China illustrates the methodology and compares the performance of various settings of perturbation tolerance, time window and train-set applications.

Modern trams typically run along semi-exclusive right-of-way. Although tram lanes isolate trams from other traffic in the running sections, the operation process will be affected by signal control. To improve the service quality of trams and reduce the negative impact on intersections caused by bidirectional priority requests, we propose a timetable optimization method for a single two-way tram line based on active transit signal priority strategy. Combining with the characteristics of bidirectional signal priority strategy, trams can pass through the intersections without stopping by adjusting the running times and dwell times. A multiobjective optimization model of a tram timetable is established to minimize the total travel time, dwell time increment, and negative effect of the signal priority strategy. For obtaining a timetable with equal satisfaction for the three objectives, we adopt the fuzzy mathematical programming approach to transform the problems into mixed integer linear programming (MILP) problems, which can be solved by using standard solvers. The case study of Nanjing Qilin Tram Line 1 shows that the timetable optimization method designed in this paper can effectively improve the service efficiency of trams, and reduce the negative impact of the signal priority strategy on social vehicles. These empirical findings can give us some useful insights on the optimum design of tram timetable.

This work considered a joint problem of train rescheduling and closure planning. The derivation of a new train run schedule and the determination of a closure plan not only must guarantee the satisfaction of all the given constraints but also must optimize the number of accepted closures, the number of approved train runs, and the total time shift between the resultant and the original schedule. Presented is a novel nonlinear mixed integer optimization problem which is valid for a broad class of railway networks. A multi-level hierarchical heuristic algorithm is introduced due to the NP-hardness of the considered optimization problem. The algorithm is able, on an iterative basis, to jointly select closures and train runs, along with the derivation of a train schedule. Results obtained by the algorithm, launched for the conducted experiments, confirm its ability to provide acceptable and feasible solutions in a reasonable amount of time.

In 2016, the construction of the New Suez Canal was completed, enabling most large-size vessels to pass through and causing more ships to queue into the canal. As the queueing problem at the entrance of the canal was anticipated to be serious, an optimal non-queueing toll scheme was previously established to eliminate the queueing phenomenon at the anchorage of the canal. However, no information about each ship&rsquo, s arrival time adjustment under the optimal non-queueing toll scheme is available from the previous literature. To solve this problem, we derive a series of mathematical formulae for each ship&rsquo, s arrival time, length of queuing time and entry time before, and after, implementing the optimal non-queueing toll scheme. The arrival time adjustments, which enable ships to enter the canal without queueing, could then be obtained. These results enable the Suez Canal authorities to draw up the ship&rsquo, s arrival timetable under the optimal non-queueing toll scheme, so that the captain could follow to enter the canal. The above information that we provide would be conducive to the management decision for the canal authorities to implement such a toll scheme. Once a tolled ship could enter the canal at the scheduled time without queueing, the ship owner could accurately control the sailing schedule, and the use of the ship could be more efficient.

Highly utilized railway networks require regular infrastructure maintenance. Different track sections often need to be closed for entire days to carry out engineering works, which makes the regular timetables no longer feasible and thus adjusted railway services and temporary alternative services need to be planned. We introduce the Multimodal Alternative Services for Possessions (MASP) problem to support the planning of alternative services, from the passenger and transport operator points of view, including an adjusted train timetable, bus-bridging services and extra train services. The MASP problem is formulated based on the Service Network Design Problem and the Vehicle Routing Problem. To solve it efficiently, we develop a solution framework that incorporates heuristics based on the column and row generation with mixed-integer linear programming. The developed framework provides the optimized alternative service routes, schedules and passenger flows routing. We demonstrated the performance of the MASP solution framework on the real-life Dutch railway network. The results show that the MASP framework is capable of efficiently generating alternative services to route passenger flows affected by possessions with a very limited increase in the total passenger costs compared to a scenario with no link closures. High computational efficiency is observed even for highly disrupted networks., Transportation Research Part B: Methodological, 154, ISSN:0191-2615, ISSN:1879-2367

Energy conservation is attracting more attention to achieve a reduced lifecycle system cost level while enabling environmentally friendly characteristics. Conventional research mainly concentrates on energy-saving speed profiles, where the energy level evaluation of the timetable is usually considered separately. This paper integrates the train driving control optimization and the timetable characteristics by analyzing the achievable tractive energy conservation performance and the corresponding boundaries. A calculation method for energy efficient driving control solution is proposed based on the Bacterial Foraging Optimization (BFO) strategy, which is utilized to carry out batch processing with timetable. A boundary identification solution is proposed to detect the range of energy conservation capability by considering the relationships with average interstation speed and the passenger volume condition. A case study is presented using practical data of Beijing Metro Batong Line and two timetable schemes. The results illustrate that the proposed optimized energy efficient driving control approach is capable of saving tractive energy in comparison with the conventional traction calculation-based train operation solution. With the proposed boundary identification method, the capability space of the energy conservation profiles with respect to the energy reduction and energy saving rate is revealed. Moreover, analyses and discussions on effects from different passenger load conditions are given to both the weekday and weekend timetables. Results of this paper may assist the decision making of rail operators and engineers by enhancing the cost effectiveness and energy efficiency.

Urban rail transit networks seldom provide 24-hour service. The last train is the latest chance for passengers. If passengers arrive too late to catch the last train, the path becomes inaccessible. The network accessibility thus varies depending on the departure time of passenger trips. This paper focuses on the computation method on the time-dependent accessibility of urban rail transit networks in order to facilitate the itinerary planning of passengers. A label setting algorithm is first designed to calculate the latest possible times for Origin–Destination (O–D) pairs, which is the latest departure times of passengers from the origins such that the destinations can be reach successfully. A searching approach is then developed to find the shortest accessible path at any possible departure times. The method is applied in a real-world metro network. The results show that the method is a powerful tool in solving the service accessibility problem. It has the ability to allow passengers to plan an optimal itinerary. Comparison analysis indicates that the proposed method can provide exact solutions in much shorter time, compared with a path enumeration method. Extensive tests on a set of random networks indicate that the method is efficient enough in practical applications. The execution time for an O–D pair on a personal computer with 2.8 GHZ CPU and 4GB of RAM is only 1.2 s for urban rail transit networks with 100 transfer stations.

Determining the best timetable for vehicles in a public transportation (PT) network is a complex problem, especially because it is just necessary to consider the requirements and satisfaction of passengers as the requirements of transportation companies. In this paper, a model of the PT timetabling problem which takes into consideration the passenger waiting time (PWT) at a station and the vehicle occupancy ratio (VOR) is proposed. The solution aims to minimize PWT and maximize VOR. Due to the large search space of the problem, we use a multiobjective particle swarm optimization (MOPSO) algorithm to arrive at the solution of the problem. The results of the proposed method are compared with similar results from the existing literature.

Článek popisuje nový způsob tvorby ročního jízdního řádu v informačním systému KANGO provozovatele dráhy Správy železnic. Systém je přístupný pro informační systémy dopravců prostřednictvím datového rozhraní, které umožňuje komunikaci pomocí XML zpráv odpovídajících specifikacím TAF / TAP TSI Evropské Unie. Součástí systému je nový modul KANGO-Tras, který zajišťuje zpracování zpráv, správu žádostí a datových jízdních řádů. Pro tvorbu jízdního řádu byly navrženy procesy pro zpracování nové žádosti, modifikaci a zrušení žádosti dopravcem, vymazání datového jízdního řádu provozovatelem dráhy a zpracování údajů, které nejsou potřebné v době konstrukce. The article describes a new way of annual timetable creation in the KANGO information system of the infrastructure manager Správa železnic. The system is accessible to railway undertakings’ information systems of via a data interface that allows communication using XML messages corresponding to the TAF / TAP TSI European Union specifications. The system includes new KANGO-Tras module, which provides message processing, management of path requests and paths. To create a timetable, processes were designed for new request, modifying and canceling request by the railway undertaking, deleting the paths by the infrastructure manager and processing data that is not needed at the construction time.

This work presents a methodology for minimizing costs involved in the operation of a single line bus service. The model developed is based on optimal implementation of operational strategies tailored to passenger demand for a bi-directional single bus line. As a result, the commonly used timetable for Full Route Operation (FRO) will have to change to accommodate three types of strategies: short turn, limited stop, and mixed strategy (a combination of short turn and limited stop). The use of operational strategies will better match supply and demand, and will thus improve operation efficiency. The optimization model determines which trips of the given FRO timetable will be implemented with given strategies considering the trade-offs between passenger and operator costs. Moreover, in applying the model, the availability of real time information for passengers is considered in the calculation of waiting times. The proposed model is interpreted in the context of a small example, which serves as an explanatory devise. Then, it is applied to a real life case study in Dalian, China. The results show an indication that a significant saving could be attained by the use of multiple strategies. These savings were especially observed in the reduction of operational costs involved with the saving of travel times and running empty seats.

The nature of the electricity consumption in TPS makes the loading of traction substations. On the basis of previous studies of qualitative characteristics of the DC traction power system, the shortcomings related to work of driven power transformers at DC substation and at the electric locomotives were identified. Thus, further increasing of electric railway equipment with adjustable converters sets the problem to investigate the influence of its work on the magnitude of harmonic of voltage and current in the catenary system. Aim: The aim of this research is to develop a simulation model of instantaneous electrical and power parameters of mode and quality of electricity for DC traction power systems under conditions of current distortion. Materials and Methods: Using the methods of the theory of electrical engineering, the model for continuous calculation of instantaneous mode parameters of the DC traction power systems is developed. Results: Based on the analysis of the structure of modern traction electric part of electric locomotives that get energy via DC catenary system, we found that the electricity regime may be described qualitatively only considering the higher harmonic settings of the operation mode. Influence of parameters of a catenary system, due to the presence of harmonic components in the current and voltage requires consideration in the calculation regime the effective resistance as well as the inductance of circuit elements. The obtained results can be used in the formation of the requirements for electricity metering at sites of railways where operated electric locomotives with traction electrical complex, which has a semiconductor converters.

Railway system is one of the most expensive systems of each country, from aspect of construction and of maintenance, as well. On the other hand, it is a necessity, especially in cities and densely populated areas. Accuracy of the railway system is directly related to the stability and robustness of all technological processes in it, including timetable, as one of the most important among them. The aims of this paper is to define the mode of implementation of time reserves in the timetable in order to increase its robustness, as well as the dimensioning the size of those reserves, given the constraints arising from the utilization of railway line capacity. The developed model take into account the various limitations resulting from the technology of railway traffic itself. The model is of algorithmic type step-by-step, and on the basis of that, the place of application of time reserves at observed section of the railway line can be reached, in order to increase the robustness of the timetable.

The quick growth of energy consumption in urban rail transit has drawn much attention due to the pressure of both operational cost and environmental responsibilities. In this paper, the timetable is optimized with respect to the system cost of urban rail transit, which pays more attention to energy consumption. Firstly, we propose a Mixed-Integer Non-Linear Programming (MINLP) model including the non-linear objective and constraints. The objective and constraints are linearized for an easier process of solution. Then, a Mixed-Integer Linear Programming (MILP) model is employed, which is solved using the commercial solver Gurobi. Furthermore, from the viewpoint of system cost, we present an alternative objective to optimize the total operational cost. Real Automatic Fare Collection (AFC) data from the Changping Line of Beijing urban rail transit is applied to validate the model in the case study. The results show that the designed timetable could achieve about a 35% energy reduction compared with the maximum energy consumption and a 6.6% cost saving compared with the maximum system cost.

An airport bus service, which is newly introduced in a multi-airport region, commonly leads to a gradually increasing market share of airports until a new state of equilibrium is reached. With the goal of speeding up and enlarging the increase in market share, this paper proposes a timetable optimization model by incorporating reactions of airport-loyal passengers to bus service quality. The simulation part of the model, which uses cumulative prospect theory to formulate discrete airport choices, results in predicted passenger demand needed in the optimization part. Then a genetic algorithm for multi-objective optimization problems called NSGA-II is applied to solve the model. To illustrate the model, the "Lukou airport-Wuxi" airport bus in China is taken as an example. The results show that the optimized timetables shorten the cultivation period and impel the market share to grow rapidly.

This contribution in a cross section way focused on the analytical determination of practical capacity of main tracks and the issue of the required capacity in the context of the comparison of national methodology used by the ŽSR and the recommended international UIC methodology. Methodology for the calculation of permeable performance within the national conditions is stipulated by ŽSR´s regulation – D24, the methodology within the international conditions for members of the UIC railway union is recommended by UIC Code 406. Both of presented methodologies have their pros and cons, which are consistently derived from this text.

In this paper, we propose an approach to deriving public transportation timetables of a region (i.e. country) based on (i) large- scale, non-GPS cell phone data and (ii) a dataset containing geographic information of public transportation stations. The presented algorithm is designed to work with movements data, which are scarce and have a low spatial accuracy but exists in vast amounts (large-scale). Since only aggregated statistics are used, our algorithm copes well with anonymized data. Our evaluation shows that 89% of the departure times of popular train connections are correctly recalled with an allowed deviation of 5 minutes. The timetable can be used as feature for transportation mode detection to separate public from private transport when no public timetable is available.

In this paper, we present a new Adaptive Local Search approach (ALS) and its implementation for the NP hard Timetable Scheduling Problem. This approach uses graph heuristics to generate the initial solution and the Aspiration criterion with Random moves strategies to improve a guided local search procedure for the search process. Experimental results on a collection of data sets from the popular Carter's benchmark demonstrated very promising results when compared with several existing state of the art approaches. 2017 IEEE. Scopus

A railway timetable is typically planned one year in advance, but may be revised several times prior to the time of operation in order to accommodate on-demand slot requests for inserting additional trains and network maintenance. Revising timetables is a computationally demanding task, given the many dependencies and details to consider. In this paper, we focus on the potential of using optimization-based scheduling approach for revising train timetables during short term planning, from one week to few hours before the actual operation. The approach relies on a MILP (Mixed Integer Linear Program) model which is solved by using the commercial solver Gurobi. In a previous experimental study, the MILP approach was used to revise a significant part of the annual timetable for a sub-network in Southern Sweden to insert additional trains and allocate time slots for urgent maintenance. The results showed that the proposed MILP approach in many cases generates feasible, good solutions rather fast. However, proving optimality was in several cases time-consuming, especially for larger problems. Thus, there is a need to investigate and develop strategies to improve the computational performance. In this paper, we present results from a study, where a number of valid inequalities has been selected and applied to the MILP model with the aim to reduce the computation time. The experimental evaluation of the selected valid inequalities showed that although they can provide a slight improvement with respect to computation time, they are also weakening the LP relaxation of the model. RELÄET

International audience; This paper discusses the formulation of crowding in public transport and its implications for pricing, seating capacity and optimal scheduling. An analytical model is used to describe the user equilibrium and the optimal equilibrium for different stylized conditions. For the one OD pair case with identical desired arrival time, we derive the optimal dynamic pricing and optimal share of seats. For the uniformly distributed desired arrival times case, we derive the optimal time table and the optimal pricing. Next we generalize the results to the case of a small network with several stations, stochastic choice and allocation of seats.

Spręsti optimalaus mokyklos tvarkaraščio sudarymo problemą yra labai svarbu mokyklos darbo efektyvumo didinimui. Užduotis yra sudaryti patogiausią tvarkaraštį iš visų galimų. Visi nepatogumai yra vertinami baudos taškais. Šio tyrimo tikslas yra išanalizuoti optimizavimo atžvilgiu keletą Lietuvoje paplitusių komercinių mokyklos tvarkaraščio sudarymo programų bei palyginti jas su šiuo metu veikiančia Matematikos ir informatikos instituto (MII) Optimizavimo skyriaus programa. Mūsų tyrimo objektas yra šių programų optimizavimo algoritmų kokybės tyrimas ir palyginimas. Vienas uždavinių yra nustatyti esamas rinkoje mokyklos tvarkaraščio sudarymo programas, kurios tiktų Lietuvos profiliuotoms mokykloms. Kitas uždavinys yra MIMOSA, aSc Timetables ir MII tvarkaraščio sudarymo programų tyrimas ir eksperimentinis palyginimas optimizavimo atžvilgiu. Programų tyrimą vykdėme trimis etapais: 1) tvarkaraštis sudaromas be apribojimų, t.y. leidžiama sudėti iš eilės du vienodus dalykus, maksimalus pamokų skaičius per dieną – 10, mokytojai dirba be laisvų dienų; 2) maksimalus pamokų skaičius per dieną sumažinamas iki 9; 3) realios Vilniaus vidurinės mokyklos tvarkaraščio sudarymas ir optimizavimas. Solution of the problem of optimal school scheduling is very important to make the work of comprehensive schools more effective. Here the sequence of teaching subjects, regarded as tools, can be changed. One needs to reduce the sum of gaps (“empty” hours) in the teacher schedules. There should be no gaps for students. Different classes are considered as different tasks. The classrooms, including the computer and physics rooms and studies, are the limited resources. The most difficult example is scheduling of profiled school. Here eleventh and twelfth grade students are choosing several subjects from the list of available ones. This means that each student works by his own schedule. We search for the most convenient feasible schedule. The inconveniences are evaluated by penalty points. The purpose of the study is to analyze several commercial scheduling programs which are prevalent in Lithuania at the moment and to compare them with existing timetable version of Optimization Department of Lithuanian Institute of Mathematics and Informatics (IMI) from optimal scheduling point of view. Therefore our research object is to study and compare the quality of optimization algorithms of these programs. One of the tasks is to identify existing commercial scheduling programs which might be right for Lithuanian profiled comprehensive schools. Another task is to perform the tentative comparison of scheduling programs MIMOSA, aSc Timetables and IMI timetable version from the point of view of quality of optimal scheduling. We used three stages for study of these programs: 1) scheduling without any confines – it’s allowable to consecutively add two equal subjects, the ultimate number of lessons per day is 10 and teachers are working without day offs; 2) reduction of ultimate number of lessons to 9 lessons per day; 3) optimal scheduling of real Vilnius secondary school.

International audience; Declarative techniques such as Constraint Program- ming are very useful in modeling complex requirements. They have the added benefit of being executable specifications and, when properly tuned, high-performance ones. In this paper we argue that Information Systems ought to include constraint-based techniques in their design and imple- mentation. We support this claim by introducing tools based on constraint programming, which we apply to an actual use-case: the academic timetable construction and maintenance problem, asdevelopedattheUniversityofE ́vora.Thesystemwebuiltwas implemented using the GNU Prolog language. Moreover, Constraints have the potential to describe global properties that a model must observe, which makes them a semantically very interesting extension to the capabilities of present model-driven techniques and tools.

International audience; In the context of scheduling and timetabling, we study a challenging combinatorial problem which is very interesting for both practical and theoretical points of view. The motivation behind it is to cope with scheduled activities which might be subject to unavoidable disruptions, such as delays, occurring during the operational phase. The idea is to preventively plan some extra time for the scheduled activities in order to be "prepared" if a delay occurs, and absorb it without the necessity of rescheduling all the activities from scratch. This realizes the concept of designing robust timetables. During the planning phase, one should also consider recovery features that might be applied at runtime if disruptions occur. This leads to the concept of recoverable robust timetables. In this new concept, it is assumed that recovery capabilities are given as input along with the possible disruptions that must be considered. The main objective is the minimization of the overall needed time. The quality of a robust timetable is measured by the price of robustness, i.e., the ratio between the cost of the robust timetable and that of a nonrobust optimal timetable. We show that finding an optimal solution for this problem is NP-hard even though the topology of the network, which models dependencies among activities, is restricted to trees. However, we manage to design a paeudopolynomial time algorithm based on dynamic programming and apply it on both random networks and real case scenarios provided by Italian railways. We evaluate the effect of robustness on the scheduling of the activities and provide the price of robustness with respect to different scenarios. We experimentally show the practical effectiveness and efficiency of the proposed algorithm.

We developed a web-based time schedule system as an important feature of the university portal along with our university's long-term ICT (Information and Communication Technologies) plan. By using the system, students and professors can get their own course timetable in collaboration with the Student Information System (SIS). Each course name on the timetable is linked to the corresponding course page on the Learning Management System (LMS) through the Single Sign-On (SSO). The system is adapted to multiple LMSs which can be selected by the course professor. In order to widely cooperate with other systems, the system is designed by using global standards (IMS Enterprise, JSR-168 Portlet, etc.) and open source software (uPortal, CAS, JSF, Hibernate, etc.) as possible as we can. This paper shows the major functions, the measured use of the portal and the time schedule system over eight months, and the implementation especially for supporting multiple LMSs, syllabus and grade books.

We consider efficient algorithms for exact time-table queries, i.e. algorithms that find optimal itineraries for travelers using a train system. We propose to use time-dependent networks as a model and show advantages of this approach over space-time networks as models.

A heuristic approach is presented to solve the Naval Postgraduate School's quarterly scheduling problem for academic courses and final examinations. The current scheduling system is studied and an automated system for data collection is developed and implemented. An automated system for the scheduling of final examinations is designed and implemented. Results using real data from one quarter produced feasible solutions to the final examination scheduling problem of 1700 students, 267 courses and 850 sections. The academic course scheduling heuristic is discussed including an integer linear programming approach to the timetabling and distribution problem of students among segments of the same course. An example with an optimal solution to the single course scheduling problem is presented. http://archive.org/details/thenavalpostgrad1094521459 Captain, German Army Approved for public release; distribution is unlimited.

Two algorithms for coloring large order graphs by partitioning, as related to class scheduling with a computer, are developed. Although, the two main algorithms failed to produce acceptable results for application to class scheduling, a coloring algorithm developed for use in the two main algorithms, is an improvement over known existing coloring algorithms. http://archive.org/details/agraphoreticppro1094515737 Lieutenant, United States Navy Approved for public release; distribution is unlimited.