GRASP + SPEA2 * Simulation = Allocation and Scheduling of Bus-Networks in Urban Areas

ANA CAROLINA OLIVERA; MARIANO FRUTOS; JESSICA ANDREA CARBALLIDO; NÉLIDA BEATRIZ BRIGNOLE

Buenos Aires, Argentina

Conferencia; 24th IFIP TC 7 Conference on System Modelling and Optimization; 2009

Ministerio de Ciencia, Tecnología e Innovación Productiva de la Nación

The Bus Network Scheduling Problem (BNSP) deals with the task of finding a bus network that fulfills several objectives. In a precise definition for a bus network it is necessary to consider several entities [Ceder, 86]: the user, who is a passenger of the buses, the authorities that impose the system regulations and the operator of the lines. These entities usually have different expectations for the bus network, which are generally confronted. This task involves the determination of many aspects: routes, frequencies, time schedules, fleet size and number of employees [Bielli, 02], [Zhao, 05], [Zhao, 06]. The whole process can be decomposed in several activities [Ceder, 86]. The design of a route for the determination of the number of lines and paths, and the determination of line frequencies comprise the most important ones, since their results are directly used to perform the other activities. The initial crucial activity is to find the route’s design as an arrangement of lines and routes. The second one is to define the frequencies that vary according to the period of the day (midday, midnight, rush hour, etc) and the synchronicity of transfers, fleet size, resources and employees, which should be assigned for each line. Together with these requirements, the BNSP also involves many objectives, such as the maximization of quality of the service and the maximization of the benefit for the transport operator. It is important to notice that BNSP solving, based on decision-support tools, is growing constantly everywhere, not only being important in developing countries. The main challenging edges of this problem lie on its NP-complexity [Ceder, 98], economic and social interests, and technical difficulties. Furthermore, an extra hindrance is constituted by the need to consider temporal features in the model. In this work, we have focused on the activities of line-scheduling and route-design, [Ceder, 98] and the entities user and operator are considered with the same level of importance. In essence, several stages were established for the Time-Dependent Hybrid Algorithm, by means of the combination of a multi-objective Genetic Algorithm (GA) based on Strength Pareto Evolutionary Algorithm 2 (SPEA2) [Zitzler, 2002], a Greedy Randomized Adaptive Search Procedures (GRASP) and a Simulation tool [Olivera, 2008]. The last component was included in order to proportion representative time-related elements for the calculation of fitness values, which are necessary to carry off the dynamics of the real scenarios with precision. The GRASP is the first step, implemented to find the routes between every pair of bus stops. The Genetic Algorithm based on SPEA2 is later used to find the complete configuration of the bus network, together with the simulation features that calculate the values of the environmentally-dependent dynamic variables. Taking into account the preview results obtains in Olivera et al., [2008], the GA stage is based on SPEA2. The main stages of the algorithm presented in this article comprise: the initialization, which constitutes the estimation of the paths between each pair of bus stops and the corresponding distances; and the core, which yields the entire bus network. The Hybrid Algorithm defines the routes and distances from any pair of bus stops by means of the GRASP method. Then, it’s the turn of the multi-objective GA, which is based on the Strength Pareto Evolutionary Algorithm 2 (SPEA2) proposed by Zitzler [Zitzler, 2002] and performs the most important task, assisted by the simulation tool.