Project funded by the Ecuadorian Ministry of Higher Education, Science, Technology and Innovation (US$66,904), August 2013 – May 2015.

Increase in vehicular congestion is a challenging problem experienced in many medium and large cities in South America during the last decades. Besides of having a direct impact upon the living standards of the urban population, it is closely related to other important issues such as air pollution, road accidents, loss of productivity, etc. In Quito, the problem is worsened due to the enlongated topography of this 1.6 million inhabitants city (the urban area being around 30 km long and 8 km wide), so that traffic almost completely breaks down during rush hours.

Local authorities have been working in various mobility strategies as a response to the increasing demand for transportation. On one hand, many efforts have been undertaken to build up the street network, though such alternatives are limited, considering the particular topography of Quito. Another strategy consists in the efficient use of the available transportation resources. A key issue to be addressed in this regard is the improvement of the Integrated Mass Transportation System of the Metropolitan District of Quito METROBUS-Q, the main urban transportation system of the city.

METROBUS-Q is constituted by a network of large capacity bus lines, which move along reserved tracks on certain streets and avenues. Feeder bus lines transport passengers between several integration terminals across this network and the nearby neighborhoods. A main component of the METROBUS-Q network (and the first one to be built, around 20 years ago) is the Trolebús System, composed by a corridor traversing the city longitudinally (i.e., in the north-south direction).

Currently, the Trolebús is served by nine lines, carrying around 250, 000 passengers daily. The fleet of the Trolebús System is heterogeneous and consists of 113 trolley buses of two types, which differ in their technical specifications and operational costs. Trolley buses of the older type I are allowed to travel only in a northern segment of the corridor, while trolley buses of the type II can move along the whole corridor.

Public transportation planning is among the most challenging issues addressed in the fields of combinatorial optimization and operations research in the past decades, mainly due to the size and computational complexity of the problems encountered. Nevertheless, important results for both strategic and operational planning have been reported [DDSS95, GH08, ORW94, BWZ97, S10]. Typically, the operational planning process is focused primarly on minimizing the cost of service and includes the following phases: vehicle scheduling, duty scheduling, and rostering scheduling.The goal of this project is to address the vehicle scheduling problem (VSP) and the duty scheduling problem (DSP) in the context of the Trolebús System.

Given a set of timetabled trips, where each trip is characterized by an origin, a destination, a duration, and a fixed starting time, the VSP consists in assigning these trips to a set of feasible vehicle routes, in such a way that each trip is covered exactly by one route and a certain cost function is minimized. The routes are served by vehicles, which must start and finish their duties at one or more depots. As each bus must be driven by one employee, the duty scheduling (sometimes termed as driver scheduling) must also be considered. The DSP consists of determining tasks (or duties) to be assigned to each driver during his/her workday, such that all vehicle routes are covered, while a wide variety of safety regulations and collective agreement rules are satisfied. In the context of the Trolebús System, feasible vehicle routes are required to fulfill the following conditions:

• each vehicle starts its route at one of three possible depots, covers a sequence of compatible trips, and returns to a depot,
• there are two types of vehicles: vehicles of the older type I can only be assigned to trips in the northern part of the corridor, while vehicles of the newer type II can cover any trip,
• the number of vehicles of each type located in each depot must be the same at the beginning and at the end of operation, and,
• vehicle movements without transporting passengers (deadhead trips) are allowed only at the end of a route.

Two objectives are important for the Trolebús operator: to minimize the number of vehicles required to cover the scheduled trips, and also to minimize the aggregated idle time of all vehicle units at the depots during the day of operation.

Due to administrative requirements, each bus route must be serviced by either one or two drivers, i.e., it has to be split in either one or two driver duties. Moreover, these duties are subject to the following additional constraints:

• each duty consists of two pieces of work that should not exceed 4 hours driving each one,
• each trip is served exactly during one piece of work, i.e., each piece of work starts at one depot, covers a set of compatible trips, and ends in a depot,
• duties are configured either as joint duties or as split duties,
• between two pieces of work in a joint duty there is a break of approximately 20 minutes,
• between two pieces of work in a split duty there is a separation interval of at least two hours,
• the duration of a duty should not exceed eight hours.

Current development:

To evaluate the potential of optimization with respect to the solution currently used by the Trolebús operator, we formulated in a first stage a simple arc-based integer programming model for a relaxed version of the Trolebús VSP, where bus routes were not constrained to be compatible with the driver scheduling requirements.

Computational tests revealed improvements of between 6% and 8% for an objective function that measures a weigthed combination of the number of required buses and the total idle time. Table 3 shows the values obtained for the test instances provided by the Trolebús operator. The four instances correspond to four configurations for daily operation used at the Trolebús: monday to thursday, friday, saturday, and sunday.

Finding bus routes that fulfill the duty scheduling constraints turned out to be very hard. In fact, most routes in the currently implemented solution do not satisfy these requirements. Hence, we relaxed the DS requirements in the following way, while penalizing deviations from the prescribed original values in the objective function:

• pieces of work having lengths between 3 and 5 hours are accepted,
• the break in joint duties is required to be of at least 15 and no longer than 90 minutes, and,
• the duration of a duty must not exceed 9 hours and 30 minutes.

We devised a primal heuristic to build bus routes that satisfy the relaxed requirements. The heuristic comprehends three stages: at first, individual trips are aggregated into pieces of work for the drivers, minimizing the idle time within a piece of work; then, pieces of work are joined into feasible duties for the drivers, minimizing the deviation from the DS requirements; finally, driver duties are assigned to buses, minimizing the number of bus units used. In general, our solution requires more bus units than the currently implemented solution. However, up to 9% of the vehicle routes in the current (manual) solution still do not comply with the relaxed DS requirements. The average idle time of a driver in our solution ranges from 6.6% to 8.0%. More results about the performance of our heuristic are reported in [TTFPZ16].

In a second approach, we tested a solution scheme based on the column generation method. The problem of finding feasible driver duties and bus routes was formulated as a generalization of the set partitioning problem. Starting from an initial set of heuristically found routes, new routes that have the potential to improve the solution, with regard to a score function that measures the deviation from the original DS requirements, are dinamically generated by solving shortest path problems with resource constraints. When compared to the currently implemented solution, the solution found by our model required in general 15% to 30% more bus units, but presented savings of between 40% to 60% in the score function. Moreover, all routes in our solution satisfy the relaxed DS requirements, while this is not the case for the routes in the manual solution, as observed above. First results about the application of this scheme are presented in [Z15].

In Table 4 the score function values and number of required bus units are shown for the currently implemented solution, for the solution provided by the primal heuristic, and for the solution from the column generation scheme. Solutions from both models require in general more bus units than the manual solution, but comply to all relaxed DS requirements and are closer to satisfy the original DS requirements, as shown by the lower score function values. Solutions from the column generation scheme are in general better than those obtained with the primal heuristic, but of course at the cost of higher computation times (a few seconds for the primal heuristics against days for the column generation method).

References

• [DDSS95] J. Desrosiers, Y. Dumas, M. M. Solomon, and F. Soumis. Time constrained routing and scheduling. In M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, editors, Network routing, 35–139, North- Holland, 1995.
• [TTFPZ16] L.M. Torres, R. Torres, M. Flores, R. Pineda and E. Zúñiga. Vehicle and Duty Scheduling for a Public Transportation System in Quito. ModeMat Report, No. 16-01, 2016.
• [GH08] Valérie Guihaire and Jin-Kao Hao. Transit network design and scheduling: A global review. Transportation Research Part A: Policy and Practice, Vol. 42(10):1251–1273, 2008.
• [ORW94] A. R. Odoni, J. M. Rousseau, and N. H. M. Wilson. Models in urban and air transportation. In S. M. Pollock, M. H. Rothkopf, and A. Barnett, editors, Operations Research and the Public Sector, 107–150, North-Holland, 1994.
• [BWZ97] M.R. Bussieck, T. Winter, and U.T. Zimmermann. Discrete optimization in public rail transport. Math. Prog., Vol. 79(1–3):415–444, 1997.
• [S10] Anita Schöbel. Optimization in Public Transportation: Stop Location, Delay Management and Tariff Zone Design in a Public Transportation Network. Optimization and its Applications, Springer, 2010.
• [Z15] Elizabeth Zúñiga. Algoritmo de generación de columnas para la asignación de tareas en el sistema Metrobús-Q. Graduate Thesis in Mathematical Engineering, Escuela Politécnica Nacional, 2015.