M.Sc Thesis
M.Sc Student Shirin Azzam Optimal Transit Scheduling with Multiple Vehicle Types Department of Civil and Environmental Engineering Professor Emeritus Ceder Avishai

Abstract

This work is concerned with the vehicle scheduling problem based on multiple types of vehicles; this problem consists on a given set of scheduled trips.

The vehicle-scheduling task described in the literature considers only one type of transit vehicle. In practice, however, more than one type is used; e.g., a bus operation may employ minibuses, articulated and double-decker buses, and standard buses with varying degrees of comfort and different numbers of seats.

The main question is how to allocate vehicles efficiently for carrying out all the trips in a given transit timetable, while taking into account the association between the characteristics of each trip (urban, peripheral, intercity, etc.), and its required vehicle type; and to minimize the total costs of this operation.

This research consists three major parts. First, a literature review is conducted. This part provides also the background of the methodology of the deficit function which is used in the heuristic procedures of this research.

The second part provides the definition and constrains of the math formulation of the problem that based on the set partitioning problem.

The third part in this work develops a heuristic procedure based on the Deficit Function Theory for Transit Vehicle Schedules.

The heuristic algorithm developed is titled the Vehicle Type Scheduling Problem (VTSP) algorithm. It begins establishing lower and upper bounds on the fleet size. The upper bound is attained by creating different deficit functions, each associated with a certain vehicle type where it includes only the trips whose lower level required the same vehicle type. The lower bound on the fleet size is attained by using only one vehicle type-the most luxurious one ; the costs required is high. In between these bounds on the fleet size, the procedure searches for the best solution.

The main research’s conclusions are:

• Constructing an efficient model and algorithm for the problem of allocating different types of vehicles to carry on a given transit timetable; the model developed is heuristic in nature, but provide optimal or close-to-optimal solution in term of minimum cost. This model has a high potential to help transit schedulers in their cumbersome scheduling undertaking.
• Implementation of the model developed will result in a meaningful cost saving to the transit operator; in addition it will produce better fit between required vehicle type for each trip in the timetable. A by-product of this implementation is to improve passenger level of service because of a better fit between vehicle comfort and the type of trip.