zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A route set construction algorithm for the transit network design problem. (English) Zbl 1179.90053
Summary: The transit network design problem (TNDP) aims to determine a set of bus routes for a public transportation system, which must be convenient from the viewpoints of both users (people who use public transportation) and operators (companies who own the resources to give the service). This article presents a constructive algorithm for the TNDP. It is specially designed to produce a set of routes that fulfils demand covering constraints, while taking into account the interests of both users and operators. Its general structure is inspired in the Route Generation Algorithm (RGA) of Baaj and Mahmassani, where its original expansion of routes by inserting individual vertices is replaced by a strategy of insertion of pairs of vertices. The algorithm proposed, called Pair Insertion Algorithm (PIA) can be used to generate initial solutions for a local improvement or evolutionary algorithm, as well as to complete an unfeasible solution with respect to demand covering constraints. Numerical results comparing PIA with RGA over a real test case show that both algorithms produce solutions with similar quality from the users viewpoint (in terms of in-vehicle travel time), while the former produces better solutions from the operators viewpoint (in terms of number of routes and total route duration) and requires a higher execution time. Since the TNDP arises in a context of strategic planning, a solution that reduces the operation cost of the system is highly desirable, even though it takes more time to be computed. The experimental study of the proposed algorithm also shows its ability to produce diverse solutions in both decision and objective spaces; this is a useful property when looking at the use of PIA as a subroutine in the context of another algorithm such as metaheuristics, in particular for a multi-objective problem like TNDP.

90B10Network models, deterministic (optimization)
90B20Traffic problems
90C59Approximation methods and heuristics
Tabu search
Full Text: DOI
[1] Ceder, A.; Wilson, N.: Bus network design, Transportation research B 20, No. 4, 331-344 (1986)
[2] Desaulniers, G.; Hickman, M.: Public transit, Hand books in operations research and management science volume 14, transportation, 69-128 (2007)
[3] Baaj, M. H.; Mahmassani, H.: An AI-based approach for transit route system planning and design, Journal of advanced transportation 25, No. 2, 187-210 (1991)
[4] Fan W, Machemehl R. A Tabu search based heuristic method for the transit route network design problem. In: 9th international conference on computer aided scheduling of public transport, San Diego, United States, 2004.
[5] Israeli, Y.; Ceder, A.: Transit route design using scheduling and multiobjective programming techniques, Proceedings of the sixth international workshop on computer aided scheduling of public transport, 56-75 (1993) · Zbl 0854.90059
[6] Ngamchai, S.; Lovell, D.: Optimal time transfer in bus transit route network design using a genetic algorithm, Journal of transportation engineering 129, No. 5, 510-521 (2003)
[7] Fan W, Machemehl R. Optimal transit route network design problem: algorithms, implementations, and numerical results. Technical Report 167244-1, University of Texas at Austin, United States; 2004.
[8] Hasselström D. Public transportation planning --- a mathematical programming approach. Doctoral dissertation, University of Göteborg, Sweden; 1981.
[9] Lee, Y. J.; Vuchic, V.: Transit network design with variable demand, Journal of transportation engineering 131, No. 1, 1-10 (2005)
[10] Borndörfer, R.; Grötschel, M.; Pfetsch, M.: A column-generation approach to line planning in public transport, Transportation science 41, No. 1, 123-132 (2007)
[11] Shih, M. C.; Mahmassani, H.; Baaj, M. H.: Planning and design model for transit route networks with coordinated operations, Transportation research record 1623, 16-23 (1998)
[12] Zhao, F.; Ubaka, I.: Optimization of transit network to minimize transfers and optimize route directness, Journal of public transportation 7, No. 1, 63-82 (2004)
[13] Chakroborty, P.: Genetic algorithms for optimal urban transit network design, Computer-aided civil and infrastructure engineering 18, No. 3, 184-200 (2003)
[14] Baaj, M. H.; Mahmassani, H.: Hybrid route generation heuristic algorithm for the design of transit networks, Transportation research C 3, No. 1, 31-50 (1995)
[15] Mauttone A, Urquhart ME. A multi-objective metaheuristic approach for the transit network design problem. In: 10th international conference on computer aided scheduling of public transport, Leeds, United Kingdom, 2006.
[16] Silman, L.; Barzily, Z.; Passy, U.: Planning the route system for urban buses, Computers & operations research 1, No. 2, 201-211 (1974)
[17] Tom, V. M.; Mohan, S.: Transit route network design using frequency coded genetic algorithm, Journal of transportation engineering 129, No. 2, 186-195 (2003)
[18] De D. Ortúzar, J.; Willumsen, L.: Modelling transport, (1996)
[19] Wan, Q.; Lo, H.: A mixed integer formulation for multiple-route transit network design, Journal of mathematical modelling and algorithms 2, No. 4, 299-308 (2003) · Zbl 1048.90035 · doi:10.1023/B:JMMA.0000020425.99217.cd
[20] Glover, F.; Laguna, M.: Tabu search, (1997) · Zbl 0930.90083
[21] Reeves, C.: Modern heuristic techniques for combinatorial problems, (1995) · Zbl 0942.90500
[22] Pattnaik, S. B.; Mohan, S.; Tom, V. M.: Urban bus transit route network design using genetic algorithm, Journal of transportation engineering 124, No. 4, 368-375 (1998)
[23] Krishna Rao KV, Muralidhar S, Dhingra SL. Public transport routing and scheduling using Genetic Algorithms. In: 8th international conference on computer aided scheduling of public transport, Berlin, Germany, 2000.
[24] Fan, W.; Machemehl, R.: Using a simulated annealing algorithm to solve the transit route network design problem, Journal of transportation engineering 132, No. 2, 122-132 (2006)
[25] Van Nes, R.: Optimal stop and line spacing for urban public transport networks, (2000)
[26] Feo, T.; Resende, M.: Greedy randomized adaptive search procedures, Journal of global optimization 6, 109-133 (1995) · Zbl 0822.90110 · doi:10.1007/BF01096763
[27] Yen, J. Y.: Finding the k shortest loopless paths in a network, Management science 17, 712-716 (1971) · Zbl 0218.90063 · doi:10.1287/mnsc.17.11.712
[28] Resende, M.; Ribeiro, C.: Greedy randomized adaptive search procedures, Handbook of metaheuristics, 219-249 (2003) · Zbl 1102.90384
[29] Glover, F.; Kochenberger, G.: Handbook of metaheuristics, (2003)
[30] Deb, K.: Multi-objective optimization using evolutionary algorithms, (2001) · Zbl 0970.90091
[31] Mauttone A, Urquhart ME. Una heurística basada en memoria para el problema del diseño de recorridos en transporte público urbano. In: XIII Congreso Latino Iberoamericano de Investigación Operativa, Montevideo, Uruguay, 2006.
[32] Mauttone A. Optimización de recorridos y frecuencias en sistemas de transporte público urbano colectivo. Master thesis in computer science, Universidad de la República, Uruguay; 2005.
[33] Stopher, P. R.; Shillito, L.; Grober, D. T.; Stopher, H. M. A.: On-board bus surveys: no questions asked, Transportation research record 1085, 50-57 (1986)