Research On Model And Algorithm Of The Vehicle Scheduling Problem

Traffic problems are deteriorating more and more seriously because of developing urbanization in the world. In order to solve the problems, the public traffic should be highly developed, In the meanwhile, public traffic system must be improved continually to face the increasingly traffic pressure. Vehicle scheduling problem is an important factor to improve the public traffic capacity and efficiency. Scientific and reasonable vehicle scheduling can not only save the cost of the operations, but also increase the efficiency and level of departure management.Given a set of timetabled tasks, the multiple depot vehicle scheduling problem(MDVSP) consists of determining the least cost schedules for vehicles assigned to several depots at the same time each task is accomplished exactly once by a vehicle. Because MDVSP is NP-hard, exact methods often cannot solve large instances encountered in practice. For tackling these instances, various heuristic approaches have been developed.On the basis of the previous studies, this paper uses the heuristic procedure based on the deficit function to solve the factual problem of MDVSP. This thesis summarizes the theories and models of the vehicle scheduling problem home and abroad, and analyzes the constraints in practice. On this basis, this paper builds the model of multiple depots vehicle scheduling problem with the theory of deficit function. A three-stage solving process is proposed to generate the final vehicle schedule, and firstly a stronger fleet-size lower bound which can reduce the ergodic times of the heuristic procedure in stage-two effectively is found by deadhead dispatch and variable trip-departure time. Second stage use the heuristic procedure to solve the minimal number of required vehicles which aims at lowering the peak value of the defict function of each depot by decreasing the number of required vehicle unit. The third stage is constructing vehicle schedules by using first-in-first-out rule with the new timetable generated in stage one. At last, this thesis takes a algorithm validity check based on hypothetical data, and makes an experiment based on the real timetables of the 3 routes from Beijing Bus Company, and the result proves the applicability of the model and algorithm.