Isci.cl

Multiperiod Synchronization Bus Timetabling Department of Transport Engineerig and Logistics Transit network planning is a difficult task that is usually decomposed into different sub- problems (Ceder, 2007; Desaulniers and Hickman, 2007) such as network design (deter- mines the bus lines: routes, stops), frequency setting (defines a proper frequency for a given bus line based on the transit network behavior), timetable generation (determines the departure times of all trips of lines), vehicle scheduling (assigns vehicles to sets of trips of each bus line), and crew scheduling (assigns trips to drivers). We study the Multiperiod Synchronization of Bus Timetabling problem (MSBT) that determines the departure times of trips of a whole day to maximize the number of synchronization events which allow well timed passenger transfers and avoid bus congestion of different lines at common nodes of the network (Ibarra-Rojas and Rios-Solis, 2012; Ibarra-Rojas et al., 2012). Such syn- chronizations are defined as the arrival of two trips at a common node with a separation time within a specific time window. Figure 1 shows congestion (a) and transfer (b) nodes where large and small separation of arrivals are sought to avoid bus congestion and allow Due to the parameters variability of the transit systems along the day, a common approach to obtain solutions for the transit network planning for an entire day is divide it into several planning periods. This manner a more accurate estimation of parameters can be obtained and then the planner can implement deterministic approaches. Even so, variability in a planning period of two hours may be large, leading to non-representative solutions. Then, to build a timetable for the entire day, several timetables obtained from single-period approaches must be merged using specific techniques (e.g. Ceder, 2007).
However, this kind of approaches lead to suboptimal solutions for the MSBT. Indeed, Figure 1: Two types of synchronization nodes; congestion node and transfer node.
in MSBT each line has specific planning periods, i.e., planning periods may be different for two lines. Moreover, synchronization events between periods are sought. Constraints of the system are service regularity (separation times for consecutive trips limited by headway bounds) and smooth transitions between periods (separation of last trip of a period and first trip of the next one near to average headway). Figure 2 shows a line and two planning periods s and s + 1 with frequency of 5 and 3 trips, respectively. The trips are regular within each period and there is a smooth transition between s and s + 1. The MSBT problem is NP-Hard and the different parameters for each period are a handicap to implement tighter formulations developed for the single-period case that can be solved with commercial solvers (Ibarra-Rojas et al., 2012).
Figure 2: Synchronization between trips belonging to different planning periods.
To solve MSBT, we implement two metaheuristic algorithms; Iterated Local Search (ILS) and Variable Neighborhood Search (VNS) that are based on feasible departure time win- dows obtained by the constraint propagation concept. In particular, our constraint propa- gation takes advantage of the service regularity constraints to define feasible time intervals of departure times for all trips. The main idea is that, given a departure time x for a trip p of some line and assuming we have headway minimum and maximum bounds of h and H, respectively, the departure time of a trip p > p must be within [x+(p −p)h, x+(p −p)H].
If we have more information about the departure times, we can propagate this information to reduce these departure time intervals. In particular, we can build an initial solution simply by randomly generating each departure time within its feasible departure time interval. Moreover, we can also deduce feasible arrival time intervals to each node b by shifting the feasible departure time interval by an amount of time (travel time from depot to node b). These intervals allow to identify if a specific pair of trips could be synchronized and to recompute the departure time for these two trips to guarantee their synchroniza- tion. Therefore, one of the main contributions of this work is a tool to define and explore Using the constraint propagation procedure, we define several neighborhood structures based on shifting departure times of a single trip or an entire line to force the synchro- nization between two different lines. The implemented local searches are first and best improvement strategies to explore each neighborhood structure. Finally, we propose a perturbation function that drastically modifies the current solution with the objective of reach different zones of the solution space of MSBT. Since constructive algorithms and local search procedures have a random factor, we implement multistart approaches for ILS For the case of multiple periods, we generalize the instance benchmark of Ibarra-Rojas and Rios-Solis (2012) that is based on information provided by a real bus transport company.
It is worth noting that a branch and bound algorithm (B&B) for solving a real sized instance of MSBT usually does not give feasible solutions in an hour due to its extremely slow convergence. Nevertheless, when the instance has the same parameters for all its periods, then it is not hard to generalize the valid inequalities of Ibarra-Rojas et al. (2012).
This type of academic instance, allows us to have quality measures for the metaheuristic algorithms we are proposing in this work. Therefore, we implemented the B&B algorithm of CPLEX 12.3 for our academic instance of MSBT. We conclude that our proposed metaheuristics are the only algorithms available for obtaining solutions for MSTB with less than 13.5% of relative mean gap for instances up to 200 lines and 20 synchronization Real life instances have parameter variation along the different planning periods of the day. Moreover, the main advantage of the multiperiod approach is the chance to use small planning periods with representative deterministic parameters. In these cases, the synchronization between trips belonging to different planning period becomes necessary.
To illustrate this case, we designed 10 instances with 10 planning periods of one hour and compare the solution obtained by our multiperiod approach (MSBT) and the procedure of merging solutions of single period synchronization bus timetabling (SBT). The numer- ical results (Figure 3) shown that the number of synchronizations increase drastically by implementing our multiperiod approach for the synchronization of bus timetables.
Figure 3: Results of implement SBT and MSBT to obtain a timetable for 10 hours divided into 10 planning periods of 60 minutes.
In summary, the MSBT is more suitable to model real transit systems. The flexibility of the problem is based on considering small specific planning periods for each line and synchronization events between trips belonging to different planning periods. Although, our proposed solution methodology obtains high quality results in seconds, there is an open door to explore the definition of more complex metaheuristics using our constraint propagation procedure and the computation of tight upper bounds to measure the quality of our algorithms for general cases.
A. Ceder. Public Transit Planning and Operation: Theory, Modeling and Practice. Else- G. Desaulniers and M. Hickman. Public transit. Transportation, Handbooks in Operations Research and Management Science, pages 69–127, 2007.
A. Eranki. A model to create bus timetables to attain maximum synchronization con- sidering waiting times at transfer stops. Master’s thesis, Department of Industrial and Management Systems Engineering, University of South Florida, 2004.
O.J. Ibarra-Rojas and Y.A. Rios-Solis. Synchronization of bus timetabling. Transportation Research Part B: Methodological, 46(5):599–614, 2012.
O.J. Ibarra-Rojas, P. Fouilhoux, S. Kedad-Sidhoum, and Y.A. Rios-Solis. Valid inequal- ities for the synchronization of bus timetabling. Technical Report PISIS-2012-02 78, Graduate Program in Systems Engineering, UANL, San Nicol´

Source: http://www.isci.cl/tristan/data/Public%20Transport/TRISTAN8_paper_168.pdf