##
**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.

### MSC:

90B10 | Deterministic network models in operations research |

90B20 | Traffic problems in operations research |

90C59 | Approximation methods and heuristics in mathematical programming |

### Keywords:

transit network design problem; constructive algorithm; heuristic; demand covering constraints### Software:

Tabu search
PDFBibTeX
XMLCite

\textit{A. Mauttone} and \textit{M. E. Urquhart}, Comput. Oper. Res. 36, No. 8, 2440--2449 (2009; Zbl 1179.90053)

Full Text:
DOI

### References:

[1] | Ceder, A.; Wilson, N., Bus network design, Transportation Research B, 20, 4, 331-344 (1986) |

[2] | Desaulniers, G.; Hickman, M., Public transit, (Barnhart, C.; Laporte, G., Hand books in operations research and management science volume 14, Transportation (2007), North-Holland: North-Holland Amsterdam), 69-128 · Zbl 1142.91300 |

[3] | Baaj, M. H.; Mahmassani, H., An AI-based approach for transit route system planning and design, Journal of Advanced Transportation, 25, 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.; 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, (Daduna, J.; Branco, I.; Pinto, J., Proceedings of the sixth international workshop on computer aided scheduling of public transport (1993), Springer: Springer Berlin), 56-75 · 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, 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.; 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.; 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, 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, 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, 1, 63-82 (2004) |

[13] | Chakroborty, P., Genetic Algorithms for optimal urban transit network design, Computer-Aided Civil and Infrastructure Engineering, 18, 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, 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.; 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, 2, 201-211 (1974) |

[17] | Tom, V. M.; Mohan, S., Transit route network design using frequency coded Genetic Algorithm, Journal of Transportation Engineering, 129, 2, 186-195 (2003) |

[18] | Ortúzar, J. de D.; Willumsen, L., Modelling transport (1996), Wiley: Wiley New York |

[19] | Wan, Q.; Lo, H., A mixed integer formulation for multiple-route transit network design, Journal of Mathematical Modelling and Algorithms, 2, 4, 299-308 (2003) · Zbl 1048.90035 |

[20] | Glover, F.; Laguna, M., Tabu search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0930.90083 |

[21] | Reeves, C., Modern heuristic techniques for combinatorial problems (1995), McGraw-Hill: McGraw-Hill New York |

[22] | Pattnaik, S. B.; Mohan, S.; Tom, V. M., Urban bus transit route network design using Genetic Algorithm, Journal of Transportation Engineering, 124, 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.; 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, 2, 122-132 (2006) |

[25] | van Nes, R., Optimal stop and line spacing for urban public transport networks (2000), Delft University Press: Delft University Press Delft |

[26] | Feo, T.; Resende, M., Greedy randomized adaptive search procedures, Journal of Global Optimization, 6, 109-133 (1995) · Zbl 0822.90110 |

[27] | Yen, J. Y., Finding the \(k\) shortest loopless paths in a network, Management Science, 17, 712-716 (1971) · Zbl 0218.90063 |

[28] | Resende, M.; Ribeiro, C., Greedy randomized adaptive search procedures, (Glover, F.; Kochenberger, G., Handbook of metaheuristics (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 219-249 · Zbl 1102.90384 |

[29] | Glover, F.; Kochenberger, G., Handbook of metaheuristics (2003), Springer: Springer Berlin · Zbl 1058.90002 |

[30] | Deb, K., Multi-objective optimization using evolutionary algorithms (2001), Wiley: Wiley New York · 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.; 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.; 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) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.