new Efficiency of drivers and vehicles



IS-OPT


Introduction

Vehicle scheduling and duty scheduling are two of the most important operational planning steps in public transport. In the vehicle scheduling phase, the use of vehicles is determined on the basis of the planned passenger trips (also called timetabled trips) and in the duty scheduling step duties for the drivers are formed. Thus, these two planning steps determine the efficiency of the use of the most important two resources of transport companies: drivers and vehicles.

Approach


The main problem of integrated planning is the large number of degrees of freedom. So there are many possible rotations for each vehicle. Typically, two timetabled trips can be in the same rotation if they are executable one after the other by the same bus, i.e. if it is possible for a vehicle to come from the end of the first trip in time to the start of the second trip. This applies to most pairs of trips. The same applies to the formation of duties. In addition, there are many different rules for the validity of duties. The working time legislation, the driving time regulation and a large number of company agreements must be respected. Many of these limitations are mathematically difficult to check.
If, however, one considers the vehicle and duty scheduling integrated in one step, the degrees of freedom of the individual problems multiply. In the case of the sequential approach, the connections to be used in the duty scheduling step are already defined by vehicle schedules, but in the case of an integrated view all possible connections between timetabled trips must be taken into account in the duty scheduling and synchronized with the vehicle scheduling.
IS-OPT now combines many different mathematical methods to deal with these difficulties. These methods come on the one hand from linear and combinatorial optimization, e.g. MCF, rapid-branching, column generation, and various approaches to solving shortest path problems with resource constraints. On the other hand, the core of IS-OPT is a convex optimization method, a bundle algorithm for optimizing convex functions. Details can be found in Weider2007.
This makes it possible to reverse an artificial separation of the planning process in subsequential steps.


  • Figure 1 – vehicle scheduling graph


  • Figure 2 – duty scheduling graph


  • Figure 3
    integrates vehicle and duty scheduling graph


Performance Characteristics

In addition to the equation of integration = more degrees of freedom, there are also other aspects that are less obvious, but equally important. One of these is the so-called subcontractor planning, that is, the question of which parts of an operation should be outsourced. In order to plan this outsourcing, you need to select an inherent mass of vehicle rotations that are covered by duties, thus solving an integrated vehicle and duty scheduling problem (with sequential planning this is not possible). With IS-OPT, it is possible to optimize this selection such that, in addition to operational planning, IS-OPT can also be used for decision-making support in important management questions. This increases planning quality and speed, thereby revolutionizing regional planning.

Application


IS-OPT is integrated into the planning system IVU.plan of IVU Traffic Technologies AG and has been in use by many customers for over 10 years. In particular, regional bus transport companies have great advantages through the use of IS-OPT. PostAuto Schweiz AG, ÖBB Postbus and DB Regio Bus are users of IS-OPT.
The benefit of IS-OPT is not only theoretically enormous, but also very concrete. For example, a major reference customer has mentioned savings of more than 13% of the vehicles and almost 6% of the vehicles