Research And Application Of Intelligent Public Transport Vehicles, Personnel Scheduling Algorithm

The Vehicle and Crew Scheduling Problem (VCSP ) is the following : given a set of service requirements or trips within a fixed planning horizon , find a minimum cost schedule for vehicles and the crews , such that both the vehicle and the crew schedule are feasible and mutually compatible.At present ,all research on this question aims at single type vehicles and crew scheduling (SVCSP) with the least use of vehicles and crew .But with regard to the local laws and regulations , our application must support multi-type vehicles and crew scheduling (MVCSP). In this paper ,we worked as follows:First, we establish the mathematical model for multi-type vehicles and crew scheduling with the objective of shortest running time .Second, we propose a two-phase Algorithm to solve the problem. We utilize the modified auction algorithm which was usually used for solving single-type vehicles scheduling before to get the minimum cost sequence groups and arrange the bus scheduling type, and then we use the randomization search of genetic algorithm to get the optimized solution.Third, the Auction algorithm can get the minimum number of vehicles and cost's sequence groups. But because of the discontinuous duty in our application, the Auction algorithm can not produces the minimum number of vehicles in our new constraints. Therefore, we made the improvement of the Auction algorithm to support the discontinuous duty.Fourth, because the genetic algorithm has provided the universal model and frame, therefore research on genetic algorithm is mainly concentrates on encoding method, fitness function as well as other kinds of operation operator. In ours application, we proposed a novel encoding method: Sample Code, as well as Dynamic Two-Point Crossover Operator and Dual Simple Mutation Operator. Our sample code can satisfy the 3 standards for code strategy appraisal. Moreover it has the following characteristic:(1) Sample code needs smaller storage spaces, usually 10% -20% of the completely encoded methods;(2) With simple map strategy, sample code makes the selection, Crossover and Mutation operation easier to carry out;...