Optimization of urban transport vehicle tasks for large, mixed fleet of vehicles and real-world constraints
[ 1 ] AGH University of Krakow | [ 2 ] Instytut Transportu, Wydział Inżynierii Lądowej i Transportu, Politechnika Poznańska | [ P ] employee
2024
scientific article
english
- urban public transport
- optimization of vehicle schedules
- fast heuristics
EN Planning the operation of urban public transport vehicles is the first stage of operational planning and consists of combining timetable trips, which are input data, into blocks that constitute the daily tasks of vehicles. For a large mixed fleet of vehicles of various types, especially those with battery power that requires recharging, operating from many depots, with numerous requirements and rolling stock constraints, the problem is a major engineering challenge, even for an experienced team of planners. IT solutions based on realistic, mathematical decision-making models and fast optimization algorithms can be of a great assistance. For the problem formulated this way, a mathematical decision model with a multi-criteria objective function was built, taking into account technical, economic, and ecological criteria and binary decision variables. The model takes into account the real requirements and constraints, a mixed fleet of different types of vehicles, including electric buses, multiple depots, technical trips (deadheads), and battery charging. The considered problem is an NP-hard combinatorial optimization one. The use of classical, exact algorithms to solve this problem is not possible for timetables with many thousands of line trips and fleets of hundreds or thousands of vehicles. This research proposes an original, dedicated heuristic algorithm, enabling to obtain an acceptable, but still suboptimal solution, in a very short time. The tests of the proposed algorithm were carried out on real-life databases of public transport systems of the two selected medium and large Polish cities. In particular, multiple depots, a mixed fleet of different types of vehicles, and real-world constraints were taken into account. The results of the computer experiments carried out using the developed heuristic were compared with the results obtained manually by a team of experienced and expert planners. For the developed multi-criteria decision-making model results comparable to and better than those prepared manually by experts were obtained in a very short time using the proposed heuristic. It is the basis for the further development works on expanding the model and improving the optimization algorithm.
65 - 78
CC BY (attribution alone)
open journal
final published version
public
100