Vehicle Scheduling Problem with Multiple Type of Vehicles and a Single Depot

This work is concerned with the vehicle scheduling problem with multiple type of vehicles, which consists on the scheduling of a set of trips so as to establish the individual services of vehicles that operate in a certain area. One e it is known both the set of trips to be undertaken and the types of vehicles adequated to each trip, we wish to determine the chains (a sequence of trips) for the vehicles, while minimizing all the operational costs involved. Every vehicle leaving the considered depot must return back to that depot, and there exists a limited number of vehicles of each type. The path assigned to each vehicle can only include trips which can be carried out by that type of vehicle. We present three different folmulations for this problem. For the purpose of obtaining lower bounds on the optimal value of the problem we studied the linear relaxation for two of the formulations and the lagrangean relaxation for the remaining one. We also considered a heuristic technique in order to produce a upper bound on the optimal value of the problem. In the end we present the accomplished computational experience.