Optimal Routing Design for Shuttle Bus Service

Abstract

A growing concern for public transit is its inability to encourage people to switch their mode of transportation from solo to shared driving. For example, most people arrive at rail stations via private cars; this creates traffic congestion and parking overloading in station areas. As a means of overcoming this problem, automated methods for designing circulated (shuttle, feeder) bus routes were developed. The problem input comprised an urban network with trip generation links and a single destination (main) node, average travel time between each link to the main node, and a constraint defining the maximal travel time along the route. The research components were threefold: (a) a method for estimating potential passenger demand for a circulated (shuttle) bus route, (b) an operations research model focusing on optimal route design, and (c) a heuristic algorithm designed to account for road networks of all sizes. The optimal model and its heuristic alternative were compared in different scenarios on a small real-life road network. It was shown that the heuristic algorithm indeed provides good (optimal in the test case) results. The heuristic procedure was also implemented with medium and large networks, generated randomly, and found to provide good results within a reasonable running time.

Get full access to this article

View all access options for this article.

References

Woyciechowicz

and Shliselberg

. Wayfinding in Public Transportation. In Transportation Research Record: Journal of the Transportation Research Board, No. 1903, Transportation Research Board of the National Academies, Washington, D.C., 2005, pp. 35–42.

Cervero

The Transit Metropolis: A Global Inquiry. Island Press, Washington, D.C., 1998.

van Nes

and Bovy

P. H. L.

. Importance of Objectives in Urban Transit-Network Design. In Transportation Research Record: Journal of the Transportation Research Board, No. 1735, TRB, National Research Council, Washington, D.C., 2000, pp. 25–34.

Spiess

and Florian

. Optimal Strategies: A New Assignment Model for Transit Networks. Transportation Research, Vol. 23B, No. 2, 1989, pp. 83–102.

J. H.

Florian

and Marcotte

. Transit Equilibrium Assignment: A Model and Solution Algorithms. Transportation Science, Vol. 28, No. 3 1994, pp. 193–203.

Lampkin

and Saalmans

P. D.

. The Design of Routes, Service Frequencies and Schedules for a Municipal Bus Undertaking: A Case Study. Operations Research, Vol. 18, No. 4 1967, pp. 375–397.

Silman

L. A.

Barzily

and Passy

. Planning the Route System for Urban Buses. Computers and Operations Research, Vol. 1, 1974, pp. 201–211.

Kuah

G. K.

and Perl

. A Methodology for Feeder-Bus Network Design. In Transportation Research Record 1120, TRB, National Research Council, Washington, D.C., 1987, pp. 40 –51.

Dubois

Bel

and Libre

. A Set of Methods in Transportation Network Synthesis and Analysis. Operations Research, Vol. 30, No. 9 1979, pp. 797–808.

10.

Marwah

B. R.

Umrigar

F. S.

and Patanik

S. B.

. Optimal Design of Bus Routes and Frequencies for Ahmedabad. In Transportation Research Record 994, TRB, National Research Council, Washington, D.C., 1984, pp. 41–47.

11.

Hasselstrom

Public Transportation Planning—A Mathematical Programming Approach. PhD thesis. University of Gothenburg, Gothenburg, Sweden, 1981.

12.

Ceder

and Israeli

. Design and Evaluation of Transit Routes in Urban Networks. Proc., 3rd International Conference on Competition and Ownership in Surface Passenger Transport, Toronto, Ontario, Canada, 1993.

13.

Chien

and Schonfeld

. Optimization of Grid Transit System in Heterogeneous Urban Environment. Journal of Transportation Engineering, Vol. 123, No. 1 1997, pp. 28–35.

14.

Chien

and Yang

. Optimal Feeder Bus Routes on Irregular Street Networks. Journal of Advanced Transportation, Vol. 34, No. 2 2000, pp. 213–248.

15.

Ramirez

and Seneviratne

. Transit Route Design Applications Using GIS. In Transportation Research Record 1557, TRB, National Research Council, Washington, D.C., 1996, pp. 10–14.

16.

Malucelli

Crainic

T. G.

Guertin

and Nonato

. Adaptive Memory Programming for a Class of Demand Responsive Transit Systems. In CASPT Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin, 2000, pp. 253–273.

17.

Cervero

Walk-and-Ride: Factors Influencing Pedestrian Access to Transit. Journal of Public Transportation, Vol. 3, No. 4 2001, pp. 1–23.

18.

Eiselt

H. A.

Gendreau

and Laporte

. Link Routing Problems, Part I: The Chinese Postman Problem. Operations Research, Vol. 43, No. 2 1995, pp. 231–242.

19.

Ceder

Public Transport Timetabling and Vehicle Scheduling. In Advanced Modeling for Transit Operations and Service Planning ( Lam

and Bell

, eds.), Elsevier Science, New York, 2003, pp. 31–57.

20.

Dijkstra

E. W.

A Note on Two Problems in Connection with Graphs. Numerische Mathematik, Vol. 1, 1959, pp. 269–271.

21.

Floyd

R. W.

Algorithm 97—-Shortest Path. Communications of the ACM, Vol. 5, No. 6, 1962, p. 345.