СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 656
A COMPUTATIONAL TOOL FOR OPTIMIZING THE URBAN PUBLIC TRANSPORT: A REAL APPLICATION*
© 2010 г. A. Álvarez, S. Casado, J. L. González Velarde, J. Pacheco
Mexico, Universidad Autónoma de Nuevo León, Campus Monterrey, NL Burgos, Departamento Economía Aplicada, Universidad de Burgos Received April 02, 2009
In this work, we have conducted a study to evaluate and improve the performance of an urban transportation system. Specifically, we have designed an algorithm for obtaining new routes and assigning buses to these routes. The objective is to optimize the service level, measured as the sum of the time the passengers have to wait at the bus stops plus the duration of their journey. As a result, a user-friendly computational tool has been designed, which is currently used by the Burgos City Council. The tool has an attractive graphic interface and is flexible, allowing modifications in the input data. The solutions yielded by the system show an improvement of almost 10% in the service level. The work includes an analysis to identify which set of stops could be "repositioned" to improve even more the service level.
Introduction. A substantial proportion of movements in large and medium-sized cities are made using public urban transportation. Therefore, to have efficient methods for planning public transportation has become increasingly important.
It is common that cities grow with the building of new neighborhoods, schools, sanitation and recreational facilities, but adjustments in the routes of public transit are made at the fly, to meet the mobility requirements of these new centers as they have emerged, without being supported by scientific studies.
In this paper we conduct a study to evaluate and improve the performance of an urban transportation system, designing strategies for obtaining new routes and assigning buses. The objective is to optimize the service level, measured as the sum of the time the passengers have to wait at the bus stops plus the duration of their journey.
We will consider that each route is made up of two half-routes, one of which can be called "going" (for example with the first stop at A and the last stop at B), and the other "returning" (with the first stop at B and the last stop at A). Thus, the final stop of a half-route is the first stop of the other. The number of routes will be considered fixed, as well as the first and last stops for each half-route. These constraints have been imposed because commonly it is not desired neither to make dramatic changes (due to the possible social cost) nor modify the bus drivers' work shifts, already agreed upon with the labor unions. Demand varies from day to
* Authors are grateful for the financial support from the Spanish Ministry of Education and Science and FEDER founds (SEJ2005-08923/ECON and ECO2008-06159/ECON); Regional Government of "Castilla y León" ("Consejería de Educación" — Project BU008A06) and National Council of Science and Technology of Mexico (grants 61903, 61343).
day, such as workdays, holidays, schooldays, etc. In the same way, the frequency and number of buses assigned to each route varies. A fleet of vehicles with known characteristics is at hand.
Considering the above mentioned, this work does not intend to find neither the optimal number of routes nor the optimal number of buses, as they are fixed. Specifically, this work is aimed at designing a fixed number of routes and assigning buses to them in order to improve the service level (measured as the mean of the sum of waiting time and traveling time per passenger). To do that, several procedures were designed and assembled in an algorithm that was implemented in a computational tool with an attractive graphic interface. This algorithm finds an initial set of routes and bus assignment and then improves them it-eratively. In addition, the computational tool has been provided with an Update module which allows modifying the input data. The system has been validated with real data from the city of Burgos, Spain, where it is currently used.
1. Related research. In the last years several studies have been conducted to define appropriate models and algorithms in order to obtain optimal transport network configurations. In most cases such models generate network configurations, in terms of topology and capacity, which aim to achieve specific objectives such as a reduction in overall travel time, congestion control, optimization of investment resources, etc. Most of the models and algorithms form part of the classical field of Network Design Problem (NDP) and involves concepts and problems like routing, scheduling, transportation, assignment, among others.
In general routing and scheduling problems are difficult combinatorial optimization problems and several heuristics and metaheuristics methods have been
developed to handle them [1]. In the case of large assignment and transportation models that have a high degree of detail, aggregation/disaggregation techniques have been developed to facilitate the analysis. Aggregated models are simplified, yet approximate, representations of the original complex model and may be used in various stages of the decision making process [2—4].
In general, the NDP and the solutions algorithms deal with the problem of network design for road transport and for the transit services. In the former case, an optimal configuration of links and intersection capacities is generated, while in the latter an optimal configuration in terms of topology and optimal frequency of transit lines is carried out.
Specifically, the urban transit network design problem (UTNDP) involves the development of bus routes on an existing road network with associated link travel times in such a way that the routes optimally satisfy some decision-maker defined objectives.
The first tools for routes and schedule design emerged in the 1970s, based on intuitive ideas, lacking a formulation of the model and the objective function. In the 1980s, some objective functions were formulated and some relevant design parameters, such as demand coverage, load factor (proportion of standing passengers to the number of seats) and bus transfers were incorporated into the analyses [5]. In the 1990s, specific models were developed such as the Multi-objective Model developed by Israeli and Ceder [6], among others.
It is known that traditional optimization methods have difficulty solving this problem. Various attempts have been made to formulate UTNDP as a Mathematical Programming Problem (MP) [7—9]. However, none of these MP formulations performs the task of route building, that is, none of them actually determine the routes through the mathematical program. The difficulty is due to the problem involves concepts that are difficult to represent mathematically, such as transfers and continuity (a proper transit route is formed only when links are connected in a manner such that they make a continuous path, that is, any arbitrary juxtaposition of links does not constitute a route). Furthermore, as is remarked in [7], the UTNDP problem is a discrete, NP-Hard, combinatorial problem with a difficult-to-calculate objective function.
Given the difficulties in representing and solving the UTNDP through exact optimization methods, it is not surprising that most of the existing methods are based on heuristics, although at various levels of sophistication [7—11].
Nevertheless, it should be mentioned the recent work of Borndorfer et al. [12] which uses a column-generation approach to transit network design in public transport. Here a multicommodity flow model is proposed for designing the routes and their frequencies in a street network such that a transportation vol-
ume (given by a so-called origin-destination matrix) can be routed. Such a model can be used to optimize the network design of a medium-sized town.
Recently, methods based on tabu search and simulated annealing [13], genetic algorithms [14, 15] have been proposed to deal with the Transit Network Design Problem. Evolutionary algorithms are also used in decision support systems for urban transportation networks as the presented in [16] for a real-time regulation of traffic within a disrupted transportation system. In this work, the decision making task can be considered as a reactive scheduling process, where new schedules of the vehicles are generated according to the actual network state. Another decision support system for the design of public transit networks that uses heuristics is the one presented in [17]. This is a visual interactive decision support system which was tested on real data from the city of Milan.
2. Problem description. As it has been mentioned, in this work we conduct a study to evaluate the performance of an urban public transportation system, proposing suitable improvements that fulfil the imposed constraints. This means that it is necessary to develop appropriate solution techniques and implement them in a computational tool to undertake integrated and complete planning with the following basic objective: to improve service levels using the available resources.
The number of routes, the initial and final stops of each route as well as the operating hours is already established. The number of buses and their capacities are known. The travel time is obtained from the distances between stops and the speed in each segment and is considered known.
Given an urban network with its characteristics (crossroads, streets, authorized driving directions, distances, speeds, prohibited turns, etc.), the main parameters involved in this problem are: A set P = {1, 2, 3, ..., np} of np bus stops located on the city's street network; A number nlns of routes; OF = {(Oj, f) ; j = = 1, ..., nlns}: the set of pairs of bus stops that are the origin and destination of each route; nbus: the number of buses available; tir: the travel time between a pair of bus stops i, i e P; d
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.