Near Optimal Large Scale Vehicle Scheduling
VS-OPT
Characteristics
In the vehicle scheduling planning, rotations are created from a timetable. The timetable contains the information on timetabled trips, that is, their start and end times and their starting point and their destinations.
Problem
Vehicle rotation planning is a step in the operational planning of transport companies. It is based on the timetable defined in the previous timetable planning step. The timetable defines the so-called passenger trips, which are announced to the customer in the timetable display. In the planning phase, these passenger trips are covered by appropriate vehicles. In order to create a round trip (also called rotation), the driver’s trips are linked by means of various types of operational trips, such as trips from and to a depot, empty trips (also called deadhead trips), or simply waiting at the stopping point. Also vehicle types have to be assigned to the rotations.
Three types of rules have to be taken into account when creating rotations. Firstly, there are different types of vehicles that are not all equally suitable for each trip.
Reasons such as capacities, quality standards, throughput heights, etc. may necessitate or exclude the use of one or more types for a trip. Secondly, when connecting passenger trip, minimum changeover times, line changes, type of driving, etc. must be observed. Thirdly, there are capacity limits in the depots for the use of vehicles of different types.
The main focus of the planning process is usually the minimization of the vehicle requirements and thus a minimization of fixed costs. Subordinate objectives are, for example, minimization of variable costs (per driven kilometer or per minute outside of a depot), stability criteria such as the number of line changes or also anticipated criteria of duty scheduling such as the presence of suitable break times in the rotations.
Three types of rules have to be taken into account when creating rotations. Firstly, there are different types of vehicles that are not all equally suitable for each trip.
Reasons such as capacities, quality standards, throughput heights, etc. may necessitate or exclude the use of one or more types for a trip. Secondly, when connecting passenger trip, minimum changeover times, line changes, type of driving, etc. must be observed. Thirdly, there are capacity limits in the depots for the use of vehicles of different types.
The main focus of the planning process is usually the minimization of the vehicle requirements and thus a minimization of fixed costs. Subordinate objectives are, for example, minimization of variable costs (per driven kilometer or per minute outside of a depot), stability criteria such as the number of line changes or also anticipated criteria of duty scheduling such as the presence of suitable break times in the rotations.
Illustration 1-Network plan and graph-model of timetabled and deadhead trips of a timetable.
Illustration 2-Timetabled trips (black) and potential deadhead trips (grey) of a regional public transit company
Illustration 3– simplified graph model of the vehicle scheduling problem
Methodology
Scheduling is a combinatorial problem that is very well suited to mathematical optimization. It can be translated directly into a graph-theoretical “multi-commodity flow problem”, which is processed by means of integer optimization.
Practice
VS-OPT is not only in use at some local transport companies, it is also an integral part of our integrated duty and vehicle scheduling optimizer IS-OPT.
Optimization studies with VS-OPT are documented for data collected by the Berlin transport companies (BVG), Hamburger Hochbahn AG (HHA) and Hamburg Hamburg (VHH) (see Löbel1997). The local bus scheduling scenarios have up to 28,000 passenger journeys, 10 depots, 14 vehicle types, and 100 million deadhead trips. Since then, VS-OPT has been continuously developed. In the meantime, the running times are only a fraction of those of 1997; also a sensitivity analysis for timetables based on VS-OPT was developed. This allows the planner to specify how far start and end time of a timetabled trip can be shifted to save even more vehicles or empty trips. Subsequently, VS-OPT is used to calculate a circulating schedule that attempts to reduce the number of vehicles with minimal shifts of trips.
VS-OPT is integrated into the IVU.run planning system MCF of VS-OPT is part of the SPEC CPU2000, SPEC CPU2006 und SPEC CPU2017 benchmark suite of the chip industry.
Optimization studies with VS-OPT are documented for data collected by the Berlin transport companies (BVG), Hamburger Hochbahn AG (HHA) and Hamburg Hamburg (VHH) (see Löbel1997). The local bus scheduling scenarios have up to 28,000 passenger journeys, 10 depots, 14 vehicle types, and 100 million deadhead trips. Since then, VS-OPT has been continuously developed. In the meantime, the running times are only a fraction of those of 1997; also a sensitivity analysis for timetables based on VS-OPT was developed. This allows the planner to specify how far start and end time of a timetabled trip can be shifted to save even more vehicles or empty trips. Subsequently, VS-OPT is used to calculate a circulating schedule that attempts to reduce the number of vehicles with minimal shifts of trips.
VS-OPT is integrated into the IVU.run planning system MCF of VS-OPT is part of the SPEC CPU2000, SPEC CPU2006 und SPEC CPU2017 benchmark suite of the chip industry.