UMD Theses and Dissertations

Permanent URI for this collectionhttp://hdl.handle.net/1903/3

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a given thesis/dissertation in DRUM.

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Filters

20191

Settings

Author: search.filters.author.Wang, ZhongxiangSubject: search.filters.subject.Column Generation

Search Results

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Solving the integrated school bell time, and bus routing and scheduling optimization problem under the deterministic and stochastic conditions
    (2019) Wang, Zhongxiang; Haghani, Ali; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The school bus planning problem (SBPP) has drawn significant attention in research and practice because of its importance in pupil transportation. The major task of the SBPP is to simultaneously optimize the school bell times, the routing plan (a set of trips) and the scheduling plan (the assignment of buses to serve these trips) while maintaining the minimum level-of-service requirements with the objective that the total number of buses and the total vehicle time are both minimized. Many subproblems of the SBPP have been well studied, but the integrated problem lacks much research due to its complexity. A Mixed Integer Programming (MIP) model is proposed for the integrated SBPP. A novel decomposition method is developed to solve the model. It distinguishes itself from the literature with the consideration of trip compatibility in the routing stage, which is a piece of essential information in the following scheduling stage. This ‘look ahead’ strategy finds a new balance between the model integration and decomposition, which solves the problem efficiently as a decomposed problem but with the high solution quality as the integrated model. Three heuristic algorithms are proposed to solve the deterministic SBPP with the trip compatibility. Then, two mathematical programming models and a Column Generation-based algorithm are proposed for the SBPP under traffic congestion and stochastic travel time in a real uncertain world. These innovative algorithms incorporate the merits of the Simulated Annealing, Tabu Search, Insertion Algorithm, and Greedy Randomized Adaptive Search Procedure and gain the computational power that the existing methods do not have. The experiments are conducted on randomly generated datasets, benchmark problems, and real-world cases. The results show that the proposed models and algorithms outperform the state-of-the-art method in all test problems by up to 25%. In a real-world case study, after the bell time adjustment, up to 41% of current buses can be saved with even better service with respect to the higher punctuality and shorter student ride time.