Basic Vehicle Scheduling Problem (BVSP) is described by assigning the minimal number of vehicles to trips such that all of the trips are operated by vehicle stationed at a single depot and the overall operational costs are minimized. 
A graph G(V,A) can be defined based on compatibility criteria where V denotes the trips and a depot and A contains the arcs corresponding compatible trips and linking trips from and to the depot. When the node (n+1) representing depot is removed from graph (GI), the GI is going to be an acyclic graph therefore each cycle in G containing node (n+1) represents an acceptable trip. BVSP can be described as determining the least cost set of cycles in G that covers each trip. Polynomial time algorithms are known for this problem based on network flow, etc. Vehicle scheduling problem with a fixed number of vehicles is the variation of BVSP such a way that the number of vehicles is predefined.

Multiple-depot Vehicle Scheduling Problems (MVSP) is described by finding minimum number of vehicles needed to operate a sequence of pair-wise compatible trips returning to its originating depot while minimizing the overall operational cost. When D>=2, no polynomial time algorithm is known for this problem and MVSP is NP-hard. Note that if the vehicles are allowed to return to a depot different from its originating depot, the problem can be solved as a single depot instance by combining all depots into one depot node. 

Vehicle Scheduling Problems with Trip Shifting allows shifting the trip times within certain intervals so that timetable construction and vehicle-scheduling problems are connected.

Vehicle Scheduling Problems with Multiple Types of Vehicles:
Since the demand on each line trip may be different, allowing different type of vehicles results in solutions with better operational cost. Therefore, the objective is to find out a solution minimizing the operational cost and assigning to each trip a vehicle with an adequate capacity (Costa et al. 1993). 

Vehicle Scheduling Problem with Maximum Time constraint arises (Freling et al. 1993) because of technical restrictions (fuel capacity, etc.) and legal or in-company restrictions. A special case of this version can be defined as a Vehicle and Crew Scheduling Problem by using the maximum length of the duty for maximum vehicle trip length. SPP modeling can be applied to this problem (Mingozzi et al. 1993).  

Real challenging problem in VSP is MVSP, Crew Scheduling and multiple-type vehicles.

Each driver can not be appointed to each type of vehicle. Translocations of manpower or vehicle capacity between the depots are often prohibited because of in-company problems.

J.R. Daduna and J.M.P.Paixao, Vehicle Scheduling for Public Mass Transit- An Overview, 6th International Workshop on Computer-Aided Scheduling of Public Transport (1993), pg:76-90, Springer-Verlag, 1995, ISBN: 3-540-60193-7
R. Freling and J.M.P. Paixao, Vehicle Scheduling with Time Constraints, 6th International Workshop on Computer-Aided Scheduling of Public Transport (1993), pg:130-144, Springer-Verlag, 1995, ISBN: 3-540-60193-7
A. Costa, I. Branco and J.M.P. Paixao, Vehicle Scheduling Problem with Multiple Type of Vehicles and a Single Depot, 6th International Workshop on Computer-Aided Scheduling of Public Transport (1993), pg:115-129, Springer-Verlag, 1995, ISBN: 3-540-60193-7
A. Mingozzi and L. Bianco and S. Ricciardelli, An exact algorithm for Combining Vehicle Trips, 6th International Workshop on Computer-Aided Scheduling of Public Transport (1993), pg:145-172, Springer-Verlag, 1995, ISBN: 3-540-60193-7


When objective functions are expressed in different units, it is complicated and perhaps undesirable to combine them into one unit scale without an accompanying information loss. 

Generally, there can exist no optimal solution, but a variety of compromise solutions between the objective functions can be generated.