Two-stage public transport vehicle scheduling algorithm based on iterative neighborhood search

Abstract

The invention relates to the field of vehicle scheduling, in particular to a two-stage public transport vehicle scheduling algorithm based on iterative field search, which comprises the following steps: (1) analyzing, learning and predicting according to given public transport system GPS data to obtain departure frequency and one-way duration of each time period; (2) fitting a departure time tableaccording to the obtained departure frequency and one-way duration; (3) allocating the train numbers on the departure time table through a greedy algorithm to obtain an initial scheduling plan; and (4) taking the initial scheduling plan as a candidate solution, and performing iteration and optimization in two stages through a neighborhood search algorithm to obtain an approximately optimal scheduling plan under the current constraint condition. The method is convenient to deploy, high in practicability and good in robustness; the algorithm consumes less time, and a feasible scheduling plan can be found in a short time compared with an accurate algorithm; the occupied machine performance is little, the algorithm efficiency is high, and the GAP between the obtained approximate optimal solution and the optimal solution obtained through the accurate algorithm is small; and the method can be quickly transplanted to other systems.

Description

technical field [0001] The invention relates to the field of vehicle scheduling, in particular to a two-stage bus scheduling algorithm based on iterative neighborhood search. Background technique [0002] Vehicle scheduling is an offline vehicle scheduling technology. The basic idea is to calculate the departure frequency and one-way duration in each time period of the day according to the GPS information provided by the vehicle or other means, and to fit the corresponding departure timetable. Carry out scheduling and find an approximate optimal solution that meets the given constraints, so as to realize the optimization of bus scheduling. At present, there have been many related researches and solutions to the problem of vehicle scheduling in the academic and industrial circles, and there are also many application examples. [0003] The current vehicle scheduling algorithm is more academically concerned with how to efficiently obtain the optimal solution. Therefore, there...

AI Technical Summary

Problems solved by technology

However, this article only considers the train chain constraint in scheduling, which is difficult to apply in practical problems

[0005] Another example is "Chen Sunyan, Shen Yingying, Qiu Jiahui. Discussion on Bus Scheduling——Taking Xuzhou No. 2 Bus as an Example [J]. China Collective Economy, 2018,000(024):85-88." Consider The peak period and passenger demand constraints are considered, and multi-objective optimization is carried out from two aspects of passenger waiting time and vehicle number. The constructed algorithm is more suitable for the real scene, but this article is still based on the conditions of the existing departure schedule. Under optimization, it is impossible to reduce the unfeasible train chain by adaptively adjusting the departure time of the train, thereby reducing the number of vehicles

[0006] In summary, some methods and technologies currently have shortcomings such as large differences between the scene and the actual situation, low algorithm efficiency, and poor robustness. Therefore, research on adaptive public transport vehicles that can be applied to real public transport systems with high efficiency and high robustness Scheduling algorithm has important practical significance

Images