Transit network design and frequency setting problem: A case study on Utrecht

Public transport systems are crucial in modern cities, allowing to efficiently and affordable transport people for work, study or leisure purposes. An essential step in the planning and design of transit networks is the line planning problem. It is a strategic decision with significant consequences for the user satisfaction and operating costs. However, despite the importance of this problem there is a lack of optimization techniques applied in practice to solve it. In operations research, this problem is also known as the Transit Network Design and Frequency Setting Problem (TNDFSP) and has received increasing attention on the past years (Ibarra-Rojas et al. 2015, Iliopoulou et al.,2019). It consists in defining the sequence of stops visited by each line and to assign preliminary frequencies to each line, resulting in a very complex problem. Because of this complexity, the benchmark instances available are very small and cannot be used to properly represent real cities. In fact, the most commonly used benchmark instance has only 15 nodes (stops) and the largest one has 127 nodes, but this is only used for a simpler version of the problem. Some studies deal with larger study cases, but they impose extra assumptions and simplifications in order to apply optimization techniques with reasonable computing times. Therefore, the objective of this work is to use a metaheuristic to propose a new bus line plan for the city of Utrecht, The Netherlands, and compare it with the current situation.This work approaches the problem with a bi-objective memetic algorithm proposed in Duran-Micco et al. (2020). This algorithm was initially designed to find approximations of the Pareto frontier considering the passengers travel time and the CO2 emissions generated by the bus network. The algorithm was proven to find good solutions on the classical benchmark instances compared with the state of the art and in reasonable computing times. Besides the multi-objective approach, the algorithm also has other advantages. For example, it performs a transit assignment procedure that assumes that passengers take travel decisions considering the frequencies and expected waiting times, as oppose to previous studies where only the in-vehicle travel time was considered. The main assumptions of this model include that all the lines and edges are considered bidirectional and the travel demand is assumed as fixed and inelastic.In order to model operational constraints, the lines are constrained by a maximum length and the fleet size is limited by a budget constraint. The objective now is to test this algorithm in a real case instance.For the purpose of applying the proposed algorithm, the city of Utrecht is represented by an infrastructure network containing 274 nodes (based on the current bus stops) and 473 edges. Using real data from current demand, an Origins-Destination matrix was generated with 15380 non-zero values. The current bus network was represented by 52 lines with a fleet size of 222 buses. On the first stage of this case study research, the emission are not being considered. Hence the objectives to minimize are the average passenger travel time (including in-vehicle travel time, expected waiting time and a penalization for transfers) and the required fleet size. The preliminary results show that the algorithm is able to find solutions that dominate the current situation in less than 1 hour of computing time. Maintaining the same fleet size (operator costs), the algorithm finds solutions with 8% lower passengers travel times. This is accomplished mostly by lower in-vehicle travel times due to less detours taken by the passengers. It is also interesting to note that better solutions were accomplished when considering a smaller number of lines. In particular, solutions with only 30 lines that tend to have longer lines on average and with higher frequencies, therefore reducing the expected waiting times.

Jaar van publicatie:2020