Detection of minimal set of trips causing the necessity to use extra vehicle for vehicle scheduling problem

摘要

Vehicle scheduling problem addresses the task of assigning vehicles to cover all trips in a timetable. Minimum number m of vehicles is determined by the number of trips in the peak hours of demand (highest density of trips). In this paper, we propose an approach to detect the minimal set of trips (critical trips), such that omitting them allows to use only m - k vehicles. Results of the algorithm can be used also for increasing the efficiency of the vehicle scheduling problem, which leads to additional cost savings for the transport company. The algorithm was used for public transport vehicle scheduling in several cities within the Czech Republic and the solution stepped up the efficiency by up to 2%.