Appropriate public transport systems are crucial in modern cities. Given the high costs that they represent and the impact they have on people's lives, effective tools are required to support their design. The Transit Network Design and Frequency Setting problem (TNDFSP) has been extensively studied in operations research. This problem consists of designing a set of public transport lines and a service frequency to each line. The main contribution of this work is to consider, for some links of the underlying network, a maximum ‘combined’ frequency among all the lines using that link and addressing the crowding issues that can result from that. These additional constraints intend to limit, for instance, the number of buses circulating in certain areas, in line with current urban design policies. A bi-objective memetic algorithm is proposed to solve the problem. The algorithm generates a set of non-dominated solutions that comply with the link-capacity constraints in 1 h of computing time. Additionally, alternative solutions are generated by designing the line plan without considering the link-capacity constraints and adapting the frequencies afterwards, to compare the two approaches. The algorithm is tested on an instance representing the bus network in the city of Utrecht, The Netherlands. The algorithm that takes into account the link-capacity constraints during the optimization process, generates better results. Moreover, the algorithm generates transit networks with less lines traversing the city centre, allowing higher individual frequencies for those lines. The algorithm could become an important tool for policy makers and transit operators, allowing the design of efficient transit systems that adjust better to contemporary urban requirements.

@en

Demand for railway transportation keeps on growing. Therefore, a thorough understanding of the capacity of railway networks is crucial. In this paper, the well-known compression method based on max-plus algebra is extended. A number of challenges are addressed to apply this compression method to large and complex networks, such as the one considered in this paper. Some trains have to be split artificially, while keeping the parts together during the compression. The trains should also be ordered explicitly, since there is no part of the infrastructure used by all trains. The results in this paper indicate that it is possible to thoroughly analyse the capacity by the adjusted compression method for large and complex networks, but the results should be interpreted with care. The results show, for instance, that the capacity occupation heavily depends on the size of the network that is considered and that it is not easy to give a clear, practical interpretation of the capacity occupation. Nevertheless, the method allowed to determine a number of critical paths and, even more importantly, a number of critical resources in the zones considered.

@en

This paper presents an approach to design better line plans for realistic cases. The planning problem is modelled as a realistic instance of the Transit Network Design and Frequency Setting Problem (TNDFSP). It incorporates additional assumptions taken from practice such as discrete frequencies, a subset of allowed terminal nodes and circular lines. A bi-objective memetic algorithm minimizes the average travel time (ATT) of the passengers and the fleet size. The method to generate the TNDFSP instance from real data is described in detail. Moreover, a new metric is proposed to compare different transit networks. In order to illustrate the approach, it is applied to the area of Utrecht, The Netherlands. The results show that the current network is modelled accurately and that the algorithm successfully generates alternative bus line plans within reasonable CPU time. It returns a subset of non-dominated solutions from which a compromise solution can be selected for practice. There are solutions with the same fleet size as the current solution, but a 6% lower ATT, or solutions with the same ATT, but a fleet size which is 19% smaller. Compared to the current network, the algorithm finds that it is convenient to substantially reduce the number of lines and to leave a small portion of demand unsatisfied. This paper also presents extensive experiments to test the impact of different assumptions about demand, bus capacity and minimum frequency.

@en

Appropriate public transport systems are crucial in modern cities. Given the high costs that they represent and the impact they have on people’s lives, effective tools are required to support their design. With this in mind, the Transit Network Design problem (TNDP) and the Transit Network Design and Frequency Setting problem (TNDFSP) have been extensively studied in the domain of Operations Research. However, due to the complexity of these problems, multiple simplifications are typically made when modelling and designing solution algorithms. Therefore, still no optimization techniques are available to address these problems in practice. Moreover, different studies address different versions of the problem, with varying assumptions and constraints, complicating the comparison of results or solution approaches. This paper presents an extensive survey of studies addressing the TNDP and the TNDFSP. It discusses the different assumptions, constraints, objectives, solution approaches and testing instances that have been considered in the literature. Furthermore, a detailed analysis is done regarding the case studies considered for the TNDFSP. Moreover, the variants of the passenger assignment subproblem that have been applied within the TNDP and the TNDFSP are discussed. The analysis shows that extensive research has been done regarding these problems. However, it also identified the significant gap that still exists between theory and practice, even in the studies addressing case studies.

@en

Urban transportation contributes significantly to CO₂ emissions. Public transport systems are a good strategy to reduce these, but the emissions generated by public transport vehicles should not be neglected during the design of the service. The Transit Network Design and Frequency Setting Problem (TNDFSP) has usually been addressed considering only the passengers’ and the operator's point of view. However, we show it is worthwhile to consider also the emissions already during this planning phase. This paper proposes a memetic algorithm to address the bi-objective TNDFSP where both the total travel time and the CO₂ emissions are minimized. The analysis considers a heterogeneous fleet, meaning that buses of different sizes and technologies can be assigned under a budget constraint. The results on benchmark instances show that the proposed memetic algorithm performs as well as state-of-the-art algorithms where CO₂ emissions are not considered. In addition, several experiments are carried out to observe the effect of incorporating emissions and heterogeneous fleet into the model. The heterogeneous fleet allows reducing travel times and emissions at the same time, compared to solutions without a heterogeneous fleet. Moreover, the explicit minimization of CO₂ emissions within a bi-objective framework allows illustrating the trade-off between both objectives. Reductions of about 30% in the emissions can be achieved by increasing the travel time only 1%, while the costs for the operator remain the same. This clearly demonstrates the benefits of considering both the CO₂ emissions and a heterogeneous fleet during the design stage of public transport systems.

@en

In this paper, a matheuristic iterative approach (MHIA) is proposed to solve the line planning problem, also called network design problem, and frequency setting on the Chinese high-speed railway network. Our optimization model integrates the cost-oriented and passenger-oriented objectives into a profit-oriented objective. Therefore, the passenger travel time is incorporated in the ticket price using a travel time value. As a result, transfers and detours will result in lower ticket prices and thus lower revenues for the operator. When evaluating the performance of a given line plan, the way in which passengers will travel through the network needs to be modelled. This passenger assignment is typically a time-consuming calculation. The proposed line planning approach iteratively improves the line plan using easy-to-determine indicators. During the process, a mixed integer linear programming model addresses the passenger assignment and optimizes the frequency setting in order to maximise the operational profit. Extensive computational experiments are executed to show the effectiveness of the proposed approach to deal with the real-world railway network line planning problem. Through extensive computational experiments on the small example network and real-world-based instances, the results show that the proposed model can improve the profits by 22.4% on average comparing to their initial solutions. When comparing to an alternative iterative approach, our proposed method has advantage of obtaining high quality of solutions by improving the profit 10.8% on average. For small, medium, and large size networks, the obtained results are close to the optimal solutions, when available.

@en

Though timetabling can account for some possible delays, in practice, external events still regularly lead to delays. Once trains are deviating from their schedule, conflicts can occur. A conflict implies that (at least) two trains require the same part of the infrastructure at the same time. Conflicts need to be resolved quickly in a way that disturbs the system as little as possible. Therefore, the impact on the whole network should be taken into account when solving conflicts. This paper discusses a heuristic conflict prevention technique capable of solving multiple conflicts together by reordering, retiming and locally rerouting trains. Based on a close-to-practice simulation tool where a simplified prediction horizon up to 10 minutes is considered, this technique is compared to FCFS. Results show significant improvements when comparing to FCFS.@en

In practice, unexpected events frequently cause delays, often leading to conflicts, since multiple trains simultaneously require the same infrastructure. Currently, such conflicts are manually resolved by dispatchers, although it is impossible for them to anticipate the impact of their actions on the entire network. Conflict detection and resolution tools can help dispatchers make informed decisions. This research introduces a new heuristic that uses rescheduling and rerouting in station areas and is innovative due to strong similarities with real-life situations. The algorithm for rescheduling is based on limiting the total delay caused by conflicts, through analyzing the predicted progress over the following hour. If the conflict arises in a station area, an optimization procedure checks first whether rerouting leads to a solution with (almost) no delays. Because some trains have a needless amount of alternative routes, a routing filter is applied before the rerouting procedure. This rerouting procedure is based on a flexible job shop problem aiming to minimize the actual travel time of passengers. This fast and effective method is experimentally tested using a close-to-practice simulation tool and compared to commonly used dispatching rules. @en

Traffic Management and Logistic Optimization have been extensively studied as two separate classes of problems, for which numerous methodologies, mathematical models and algorithmic solutions were made available in literature. However, little attention has been devoted to the interactions between the variables involved in these problems and the consequences of the decision making processes carried independently by Traffic Managers and Logistic Players. We believe this to be of considerable importance, since partial or incomplete knowledge on one another's decisions might yield sub-optimality for either or both of them. In this work, we propose an integrated view on both classes of problems, providing mathematical formulations to support the assessment of the impact which the two players may have on each other.

@en