Minimum Cost Vehicle Scheduling with Different Types of Transit Vehicles

This work addresses the problem of how to allocate vehicles efficiently for carrying out all the trips in a given transit timetable, where each vehicle is assigned a chain of trips, some of which may be deadheading (empty) trips. The methodology presented takes into account the association between the characteristics of each trip (urban, peripheral, intercity, etc.), and its required vehicle type. The problem is based on given sets of trips and vehicle types, where the categories are arranged in decreasing order of vehicle cost. Therefore, each trip can be carried out by its vehicle type, or by other types listed in prior order. This problem can be formulized as a cost-flow network problem with an NP-hard complexity level. Thus, a heuristic algorithm is developed in this work, based on the deficit function theory. A simple example is used as an expository device to illustrate the procedures developed.