A simultaneous bus route design and frequency setting problem for Tin Shui Wai, Hong Kong

• Published in: European journal of operational research 2011-03, Vol.209 (2), p.141-155
• Main Authors: Szeto, W.Y., Wu, Yongzhong
• Format: Article
• Language: English
• Subjects: Applied sciences; Bus network design; Buses; Exact sciences and technology; Frequency setting problem; Genetic algorithm; Genetic algorithms; Ground, air and sea transportation, marine construction; Heuristic; Inventory control, production control. Distribution; Neighborhood search; Operational research and scientific management; Operational research. Management science; Optimization algorithms; Road transportation and traffic; Route design problem; Route optimization; Studies; Suburban areas; Transportation; Transportation Bus network design Route design problem Frequency setting problem Genetic algorithm Neighborhood search
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2010.08.020

A bus network design problem for Tin Shui Wai, a suburban residential area in Hong Kong, is investigated, which considers the bus services from the origins inside this suburban area to the destinations in the urban areas. The problem aims to improve the existing bus services by reducing the number of transfers and the total travel time of the users. This has been achieved by the proposed integrated solution method which can solve the route design and frequency setting problems simultaneously. In the proposed solution method, a genetic algorithm, which tackles the route design problem, is hybridized with a neighborhood search heuristic, which tackles the frequency setting problem. A new solution representation scheme and specific genetic operators are developed so that the genetic algorithm can search all possible route structures, rather than selecting routes from the predefined set. To avoid premature convergence, a diversity control mechanism is incorporated in the solution method based on a new definition of hamming distance. To illustrate the robustness and quality of solutions obtained, computational experiments are performed based on 1000 perturbed demand matrices. The t-test results show that the design obtained by the proposed solution method is robust under demand uncertainty, and the design is better than both the current design and the design obtained by solving the route design problem and the frequency setting problem sequentially. Compared with the current bus network design, the proposed method can generate a design which can simultaneously reduce the number of transfers and total travel time at least by 20.9% and 22.7% respectively. Numerical studies are also performed to illustrate the effectiveness of the diversity control mechanism introduced and the effects of weights on the two objective values.