Robust Efficiency in Public Bus Transport and Airline Resource Scheduling

Abstract

In this work we address the concept of robust efficiency of resource schedules in public bus transport and airline industry, dealing with the competing objectives of cost-efficiency and robustness. Generalizing the findings from two research projects we provide techniques that lead to an improvement of the pareto-front between robustness and cost-efficiency. These techniques include the improvement of scheduling and optimization approaches as well as a refinement of delay prediction models enabling a robustness evaluation closer to reality. Additionally, problem characteristics in public transport and airline network topologies and their influence on the degree of freedom for robust resource scheduling and dispatching strategies are examined.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction—Robust Efficiency in Resource Scheduling

In this paper, we aim at the generalization of findings of two closely related research projects, dealing with crew and aircraft or vehicle scheduling in the airline industry and public bus transport, respectively.

In both problem domains, there is a necessity of coping with contrary objectives in scheduling and operations. The planning stage primarily deals with the cost-efficient use of resources like crews, vehicles or aircraft, desirably leading to tight schedules with low idle and buffer times. However, during operations unforeseen disruptions occur frequently and may lead to delayed departure and arrival of flights or service trips. Therefore, additional reactionary costs for delay compensation may occur. In this regard, a main goal during operations is punctuality and reliability, demanding for buffer times and possibilities to adapt resource schedules to the current circumstances.

Consequently, the real costs for resource usage are determined by the sum of planned costs and reactionary costs. Considering planned cost minimization as the only objective leads to an underestimation of the real costs. Therefore, the concept of robust efficiency in resource scheduling can be applied, aiming at the minimization of real costs by already taking into account probable costs of delays during the scheduling stage. Hence, there is a trade-off between cost-efficiency and robustness. Resource schedules are called robust if delays are less likely to be propagated to succeeding tasks. In this context, a distinction can be drawn between exogenous and propagated delays. The former is caused directly by exogenous disruptions and cannot be prevented in scheduling. In contrast, the latter is induced by delayed arrival of previous tasks using the same resources and therefore can be influenced by scheduling decisions.

Fig. 1

Pareto-optimal solutions for the robust resource scheduling problem

Considering this, there are two eligible properties of resource schedules, namely stability and flexibility. Stability describes the capability of schedules to absorb delays by buffer times between tasks so that no or less delay propagation occurs. A high degree of flexibility provides simple possibilities to react to delay occurrences on a cost-neutral basis, e.g. by swaps of resources. If delays occur in operations, resources can be swapped in order to prevent delay propagation. Note that both properties aim at the same target of avoiding delay propagation by absorption. Stability aims at carrying out resource schedules exactly as planned. In contrast, the intention of flexibility is to increase the ability to react to varying circumstances during operations by restricted schedule modifications. For detailed literature reviews on robust resource scheduling strategies please refer to [1,2,3,4].

For a graphical explanation of the trade-off between cost-efficiency and robustness, see Fig. 1. Line I illustrates the case of cost-efficient scheduling as the only objective. By additionally taking into account the robustness as a second objective, pareto-optimal solutions can be generated, see line II.

Based on this, the remainder of this paper considers techniques on incorporating robust efficiency into resource schedules. Therefore, a generic framework for generating robust and cost-efficient solutions is addressed in Sect. 2. Furthermore, techniques for improving the pareto-front are presented. Section 3 examines different problem characteristics arising from differing network topologies and their influence on the degree of freedom for scheduling and dispatching strategies in simulation. Finally, the findings are summarized in Sect. 4.

2 Improving Stability and Flexibility—A Generic Robust Scheduling Framework

In this section we present a generic framework for generating pareto-optimal resource schedules following the concept of robust efficiency. Afterwards, techniques for further improving the pareto-front are provided.

For given flight or service trip schedules, column generation approaches are used with a subsequent IP phase in order to generate resource schedules. The pricing algorithms are modeled as resource constrained shortest path problems and solved by dynamic programming. Both the column generation master problem and the final IP phase are usually solved by standard solvers, e.g. CPLEX. For a simultaneous consideration of different scheduling stages, e.g. integrated vehicle and crew scheduling, column generation is combined with Lagrangian relaxation. This enables us to relax constraints and decompose integrated models that are naturally hard to solve. The column generation approaches are extended by delay propagation mechanisms in order to incorporate stability and flexibility in the resulting schedules, see [1, 3] for further details.

Important robustness measures are the overall punctuality of flights/service trips and the total amount of propagated delays. Therefore, the robustness of resulting crew and aircraft or vehicle schedules is evaluated by simulating delay propagation in an event-based simulation. As an input factor, scenarios for exogenous delays are generated based on delay prediction models during simulation.

Evaluating the impact of stability on the robustness demands for propagation only during simulation as delay management and dispatching strategies may overestimate the robustness. In contrast, for the evaluation of flexibility dispatching strategies must be applied during simulation, e.g. by enabling swapping opportunities.

The framework is used to evaluate several techniques that may lead to an improvement of the pareto-front for robust efficiency. On the one hand, prediction models for exogenous delays can be improved. The desired result of more realistic delay prediction is that buffer times or swap opportunities are considered only for tasks that imply a considerable delay propagation risk. As a consequence, the pareto-front is moved downwards, i.e. the robustness is further improved without an additional increase of planned cost, see Fig. 1 (line III). Reference [5] examine the potential of data-driven delay prediction models for airline resource scheduling. Based on this study, [6] generate delay prediction models with different degrees of prediction accuracy and compare their effects on robust crew and aircraft scheduling.

On the other hand, both delay propagation and planned costs of resource schedules can be further reduced by an improvement of scheduling approaches, resulting in additional degrees of freedom for scheduling, see Fig. 1 (line IV). In this context, [3] examines the potential of different scheduling approaches in public bus transport resource scheduling. In particular, sequential, partially integrated, and integrated vehicle and crew scheduling schemes are investigated. The results show that sequential scheduling allows the computation of robust schedules, but it is (far) away from obtaining the cost-to-robustness ratio attained by integrated scheduling. Due to the combined consideration of delay propagation between tasks, and the mutual dependencies between vehicle and crew schedules during optimization, the proposed integrated scheduling scheme is able to build both robust and cost-efficient resource schedules. In addition, it is shown that a further integration of planning stages results in further improvement of the pareto-front. Therefore, integrated scheduling is combined with the ability to shift service trips within time windows in order to modify the given timetable.

3 Examining the Degrees of Freedom in both Problem Domains

The ability of generating resource schedules with high degrees of cost-efficiency and robustness is closely related to the degree of freedom determined by decisions taken in previous planning stages. In particular, this includes the timetabling and network design which show substantial differences in the airline industry and public transport. In this section the emerging consequences are examined with regard to potential differences in the degree of freedom that limit decisions during the resource scheduling stage (Study A) as well as for dispatching strategies during simulation (Study B).

Study A: Figure 2 shows the number of different successor tasks in all crew duties generated in the pricing steps during column generation. With 202 flights for the airline case and 210 service trips for the public transport case, the underlying problems are comparable in size. The airline hub-and-spoke network implies fixed successor flights for about one fourth of all flights. This unexceptionally appears at spoke airports as a result of the out-and-back principle in hub-and-spoke structures. In these cases, scheduling decisions cannot be made, irrespective whether the connection is likely to propagate delay or not. On average there are 5.1 possibilities to connect flights during pricing. Note that deadheading for crews or ferry-flights for aircraft are not allowed.

In contrast, the considered public transport network provides a significantly higher degree of freedom for resource scheduling. This may depend on the consideration of vehicle deadheads, and transfer/walking of drivers allowing different locations for starting or finishing work or having a break. On average there are up to four times as many connection possibilities for every service trip. For only 1.5 % of all service trips the succeeding service trip is fixed.

Fig. 2

Different degrees of freedom for the generation of exemplary airline and public transport crew schedules

Study B: Figure 3 presents the reduction of average propagated delay for each task during simulation for exemplary crew and aircraft or vehicle schedules with an increasing degree of stability (from left to right). The overall benefit of allowing resource swaps in case of delays is obvious. On average 26.7 and 28.5 % of propagated delay can be prevented in the airline and public transport resource schedules, respectively. Furthermore, the different degrees of freedom resulting from the network topologies is not apparent here as the amount of delay absorbed due to swapping crews and aircraft or vehicles is in the same order for both problem domains.

Fig. 3

Impact of swapping during simulation for schedules with different stability degrees

Referring to the assumption that stable schedules do not tend to imply a high necessity of dispatching, it is also important to see that an increasing degree of stability does not necessarily decrease the impact of dispatching strategies. Instead, this effect is superimposed by the fact that stable schedules often contain more resources than cost-efficient schedules, offering additional possibilities for dispatching.

This behavior can be observed in the public transport example. In contrast to the less stable solutions (1)–(5), the solutions (6)–(11) contain additional resources that imply more swap possibilities. However, if stability is increased further by incorporating additional buffer times, less swaps are necessary. This leads to the recurrent decrease between solutions (6) and (11).

4 Summary and Conclusions

In this paper, we addressed the concept of robust efficiency in resource scheduling for both airlines and public bus transport. In both problem domains there is a trade-off between cost-efficiency and robustness. We presented two fundamental techniques to improve the resulting pareto-fronts. Firstly, the prediction accuracy can be improved in order to place buffer times only at connections between tasks with a certain delay propagation risk. Secondly, the degree of freedom for resource scheduling can be improved by partial or full integration of planning stages that previously have been solved separately. Sophisticated modeling and optimization techniques are necessary to cope with the resulting increase in complexity.

Comparing the network topologies, they imply different degrees of freedom for resource scheduling. Airline hub-and-spoke networks contain a certain number of fixed connections between flights, mainly at spoke airports. In contrast, public bus transport networks provide a higher degree of freedom for scheduling decisions. However, it becomes apparent that resulting resource schedules provide a considerable degree of flexibility in both domains.