Abstract:

In order to reduce the number of deadheading trips and realize the equality of working hours with the given bus timetable, this paper formulated a super spatiotemporal based transit vehicle scheduling model and designed an evolutionary algorithm including mixed creation, mutation and mature operators. Firstly, this study used the super-network conception to combine pulling out arcs, pulling in arcs, connectors, actual trips and deadheading trips into a super spatiotemporal network. Based on the flow conservation conception in the super-network, this study built a vehicle scheduling model and transformed the constraint of working time equality into an addable item of objective. In view of the topological feature of the set of trip coverings, this paper designed a mixed creation operator to generate new solution with several known feasible solutions. By searching the connectors with loop feature, this paper realized the mutation operator to the elements of feasible solution. The mature operator consists of formulating an assignment network, computing the cost of links in the assignment network, and obtaining the optimal match by Hungarian algorithm. Based on the above three operators, this paper proposed a new "3M" evolutionary algorithm. The numerical analysis verified the rationality of the new model and the effectiveness of the new algorithm. This research discovers that there is a mutual restriction relationship between reducing deadheading trips and equalizing the actual trip times among trip chains, but the both have no obvious connection with the fleet size.

Key words: public transportation, vehicle scheduling, super-network, intelligent optimization, self-adaptation