The Research On Vehicle Scheduling Problem Based On Multi-Objective Optimization Algorithms

With the continuous development of our society, public transit is becoming one of most popular type of urban transport among people. In addition, the development of public traffic can mitigate urban traffic congestion effectively and be helpful in preventing and reducing air pollution. In public transportation operation system, vehicle scheduling problem of urban bus line is complex and involves multiple objectives. A good vehicle scheduling solution can not only reduce operation costs of bus company, but also improve the efficiency of public transport greatly and reduce passengers waiting time, which encouraging more people to choose public transportation. The problem is to assign vehicles to cover a set of trips contained in a timetable of bus line to minimize multiple objectives, such as the number of used vehicles and crews, which usually conflict with each other. Currently, existing approaches for vehicle scheduling usually incorporate multiple objectives in a linear fashion to form a single objective and then use a single objective optimization approach to solve it. However, they can produce only one solution and it is not easy to assign a proper weight for each objective to obtain a superior solution that can balance different objectives.Based on the bus companies’ actual operation status in china and the achievements and methods on the vehicle scheduling problem, the paper proposes a multi-objective optimization approach to solve this problem and produces a set of Pareto solutions. Each Pareto solution represents a satisfactory vehicle scheduling solution. The approach includes:(1) a set of initial vehicle blocks is produced;(2) a multi-objective optimization model is built for selecting subset from the candidate vehicle blocks set. The optimization objective is to minimize the num of vehicles and crews;(3) an improved multi-objective genetic algorithm is used to produce Pareto solutions from the set of vehicle blocks. To encode a solution, the paper propose a coding scheme that has relatively short coding length and low decoding complexity;(4) an departure time adjusting process (DTAP) is embedded into the algorithm to adjust the departure times of vehicles to improve the quality of solutions. The proposed approach is applied to a real-world vehicle scheduling problem of a bus company in Nanjing City of China. Experimental results show that this approach is able to generate satisfactory Pareto scheduling solutions within several minutes, which outperform the actually used experience-based solution.