The Aircraft Routing and Maintenance Planning problems are integral parts of the airline scheduling process. We study these relevant combinatorial optimization problems from the perspective of Answer Set Programming (ASP) modeling and solving. In particular, we contrast traditional single-shot ASP solving methods to a novel multi-shot solving approach, geared to rapidly discover near-optimal solutions to sub-problems of increasing granularity. As it turns out, our multi-shot solving techniques can heavily speed up the optimization process without deteriorating the solution quality in comparison to single-shot solving. We also provide a customizable instance generator and a solution viewer to facilitate intensive investigation of Aircraft Routing and Maintenance Planning as a benchmark problem. Our multi-shot solving techniques are however not limited to this benchmark alone, and the underlying ideas can be naturally applied to a variety of scheduling problems.
Combinatorial optimization problems are usually solved in a single shot, but
sometimes, we can decompose them into sub-problems (for example with a time-window
approach [
An airline operator scheduling process is divided into six major steps [
This paper is organized as follows. In Section 2, we begin with brief introductions of solving techniques for Aircraft Routing and Maintenance Planning from the literature and of ASP. Section 3 presents our customizable instance generator along with a solution viewer enabling comprehensive benchmarking. In Section 4, we develop and experimentally evaluate a variety of multi-shot ASP solving techniques for near-optimal Aircraft Routing and Maintenance Planning. Finally, Section 5 concludes the paper. 2
In this section, we first introduce the works previously done in Aircraft Routing and Maintenance Planning, and then we give a brief introduction on ASP.
Aircraft Routing is usually considered as a feasibility problem, which is NP-hard and
can be reduced to a multi-commodity flow problem [
Answer Set Programming (ASP) is a declarative paradigm oriented towards solving
combinatorial problems [
A logic program consists of atoms, literals and rules. An atom is a proposition, literals are atoms with or without default negation in front of them, and a rule is an implication a1; :::; an
b1; :::; bm; not c1; :::; not co: where a1; :::; an is a disjunction of literals called head, and b1; :::; bm; notc1; :::; notco is the body. From the body, we can derive that the head must be true. A special case of disjunctive rules with head a1; not a1 are choice rules written as
fa1g b1; :::; bm; not c1; :::; not co:
This means that a1 can but need not be derived from the body of the rule. A rule with
an empty head is called a constraint, and it forbids the body to be true:
b1; :::; bm; not c1; :::; not co:
Multi-shot ASP solving is an iterative approach geared for problems where the logic
program is continuously changing [
The following subsections discuss how instances for our benchmarks are generated,
using the generator provided at [
We have developed an instance generator that is able to create random instances along with draft solutions, configured with the following parameters: – number of aircrafts – number of airports – maintenance due limit – number of airports able to perform the maintenance – length of maintenance – average number of flights per aircraft – average length of flights – average length of flights’ TAT – average ground time between two flights The flights per aircraft, flight lengths, TATs and ground times are generated following a truncated normal distribution with a parametric mean, standard deviation, min and max value. We also prevent the creation of flights with the same origin and destination but different flight length or TAT, so that the length and TAT will be the same for all flights from A to B.
Initial maintenance counters, expressing the time left before performing maintenance at the start of a route, are generated following a truncated normal distribution with a mean of 3.5 days, a standard deviation of 1 day, a minimum of 0 and a maximum of 6 days. While the generator builds the flight routes of a solution, it also places maintenance slots to ensure that the solution is feasible from a maintenance perspective. To do so, when an aircraft has reached at least 50% usage (i.e., 3.5 days for our 7 days maintenance), a maintenance slot is included with a probability of the usage plus a random value uniformly sampled between 0 and 0.5, or 1 if the usage is above 90%. In case the end airport of the previous flight is incompatible with the maintenance, we change the destination to a compatible airport, picked randomly among the airports able to perform the maintenance. Moreover, we add the length of the maintenance to the ground time between consecutive flights (meaning that we can have more ground time than needed).
The draft solution generated along with an instance witnesses that all flights can be routed and maintenance due limits be respected. Instead of the entire routes, the generated instance fixes the first flight for each aircraft and dates of remaining flights only, accompanied by information about initial maintenance counters, airports at which maintenance can be performed, the maintenance length and due limit. That is, allocating aircrafts to all but the first flights of routes and incorporating maintenance slots is subject to Aircraft Routing and Maintenance Planning.
Along with the actual instance, our generator reports its draft solution together with a cost indicating the solution quality. The latter is calculated as the sum of cost 500 for each TAT violation (i.e., too short turnaround time) and 101 for each maintenance slot, where the ratio reflects a higher priority of avoiding TAT violations and the odd cost of 101 is taken to facilitate reading off the number of maintenance slots contained in the draft solution. This information can be used for analysis, considering that the draft solution does not include TAT violations and is thus optimal from a flight routing perspective, yet potentially sub-optimal from a maintenance perspective. However, the (a) Gantt chart for a small instance ffffffffllllllliiiiiiiirgggggggshhhhhhhtttttttt((((((((14563127,,,,,,,,13131132),,,,,,,. 43343342690680f1611659i9468794r6116009s1771117t,,,,,,,(51323311,,,,,,,,24344334)2701792.8944922305533587126211771117)))))))....... tttttttaaaaaaattttttt(((((((5423671,,,,,,, 4334234533563520024020000000)))))))....... maintenance(seven_day). airport_maintenance(seven_day, 3). length_maintenance(seven_day, 9000). start_counter(seven_day, 366701, 416288, 1). start_counter(seven_day, 366417, 470841, 2).
limit_counter(seven_day, 604800).
(b) ASP facts for the instance shown in Fig. 2a quality of the draft solution can be assumed to be rather good, given that the usage of each aircraft is at more than 50% before maintenance is performed.
To inspect a solution, we support exporting a graphical representation of it as Gantt chart (Fig. 2a and Fig. 4). Every flight is represented by a bar, using a unique color for each pair of origin and destination airport, and maintenance slots after flights are indicated similarly. The tail at the right of each (non-maintenance) bar represents the TAT of a flight, and a next flight covering part of this tail would point out a TAT violation. Each row gives the route of a separate aircraft, with the first flight on the very left and further flights and maintenance slots to the right. 4
In this section, we present our multi-shot ASP encoding for Aircraft Routing and Maintenance Planning. Then we specify the parameters used to furnish a benchmark suite by means of the generator described in Section 3. The remaining subsections introduce a variety of hyper-parameters for multi-shot ASP solving and experimentally evaluate their impact on the solution quality and convergence of the optimization process.
As customary in ASP, we model Aircraft Routing and Maintenance Planning by facts
describing a problem instance along with a general first-order encoding specifying
(optimal) solutions. Our modeling approach follows the idea of flight connection
networks,3 where two flights can be connected if they are compatible (i.e., flight A arrives
before flight B departs from the destination airport of flight A). In the following, we
present a simplified yet logically similar version of the full encoding provided at [
Fig. 2a sketches (the optimal solution to) the small Aircraft Routing and Maintenance Planning instance described by the facts in Fig. 2b. We have the flights 1 to 7, declared by facts of the flight/5 predicate whose first argument is the flight identifier, the second stands for the start airport, the third for the start time, the fourth for the destination airport and the fifth for the arrival time. For each of the seven flights, a fact of the tat/2 predicate provides the TAT required before the next flight on the route of some aircraft, e.g., 4520 time units (resembling about 75 minutes) for flight 1. Two facts of the 3 We have also devised prototype encodings based on time-space networks and observed drastically increased difficulty of finding feasible routings that incorporate all flights. Hence we chose flight connection networks as basic principle of problem encodings to elaborate further. first/2 predicate indicate that flight 1 is the first on the route of aircraft 1, and similarly flight 5 for aircraft 2. The remaining facts address conditions for a maintenance kind labeled seven_day, declared by a fact of maintenance/1. Such maintenance can be performed at airport 3 and requires at least 9000 units of ground time (amounting to 2.5 hours), as expressed by facts of the predicates airport_maintenance/2 and length_maintenance/2. The two facts of start_counter/4 denote initial time periods in which the seven_day maintenance is (still) covered: This period stretches from time 366701 to 416288 for aircraft 1, and from 366417 to 470841 for aircraft 2. Finally, the fact of the limit_counter/2 predicate expresses that 604800 time units (7 days) get covered when seven_day maintenance is performed for an aircraft. The (optimal) routing, depicted in Fig. 2a, happens to be such that aircraft 1 takes the flights 1, 6 and 7 with a maintenance slot after flight 1, while aircraft 2 does the remaining flights in the order 5, 2, 3 and 4.
Our multi-shot ASP encoding in Fig. 3 starts by defining constants for levels and weights to penalize TAT violations and maintenance slots along the routes of aircrafts. In addition, the constant time_window is crucial for when to consider compatible flight connections in a routing, and the value 3600 expresses that the gap admitted between the arrival and departure of connected flights shall be successively increased by windows of one hour. This gap is reflected by the TIME_G and WINDOW arguments in atoms of the compatible/6 predicate. E.g., we derive the atoms compatible(1,3,379361, 2,6540,2) and compatible(1,3,379361,6,12256,4), indicating a ground time of 6540 time units between the arrival of flight 1 at time 379361 and the departure of flight 2 from airport 3, while this ground time amounts to 12256 time units for flight 6. Given the window size of 3600 time units, the last argument in both atoms expresses that the potential connection between flight 1 and 2 shall be considered from the second step on during multi-shot solving, and the connection continuing with flight 6 becomes admissible from the fourth step on.
The second kind of auxiliary atoms derived from the facts of an instance, those of the maintainable/5 predicate, provide flights FLIGHT1 with their arrival TIME such that performing MAINTENANCE after them covers (later) flights whose arrival and departure times lie in the interval from TIME_M to TIME_N. For our instance in Fig. 2b, we obtain maintainable(seven_day,1,379361,388361,984161) and maintainable( seven_day,5,379077,388077,983877), signaling the possibility of seven_day maintenance after flight 1 and 5, both of which arrive at airport 3 and admit connections to later flights with more than the maintenance length of 9000 time units inbetween. Unlike that, performing seven_day maintenance after flight 3, which also arrives at airport 3, would be meaningless because its single available connection with flight 4 does not include sufficient ground time, i.e., 7440 time units only, so that no maintainable/5 atom is derived for flight 3.
While flight connections are to be made available step-wise during multi-shot solving, an #external declaration introduces respective atoms of the route/4 predicate right at the beginning. This avoids need for re-instantiating conditions expressed by #count aggregates, enforcing a routing with at most one (direct) successor per flight and exactly one predecessor for flights that are not the first on the route of any aircraft, in case new compatible connections become admissible in a step. The same applies to rules for the assign/2 predicate, which trace connections given by atoms of route/4 % constants for levels and weights of costs, and time window for connections #const level_tat = 2. #const weight_tat = 1. #const level_maintenance = 1. #const weight_maintenance = 1. #const time_window = 3600. % compatible flights with number of time window compatible(FLIGHT1, AIRPORT_E1, TIME_E1, FLIGHT2, TIME_G, WINDOW) :flight(FLIGHT1, AIRPORT_S1, TIME_S1, AIRPORT_E1, TIME_E1), flight(FLIGHT2, AIRPORT_E1, TIME_S2, AIRPORT_E2, TIME_E2), not first(FLIGHT2, _), TIME_G = TIME_S2 - TIME_E1, 0 <= TIME_G,
WINDOW = TIME_G / time_window + 1. % feasible maintenance slots after flights maintainable(MAINTENANCE, FLIGHT1, TIME, TIME_M, TIME_N) :compatible(FLIGHT1, AIRPORT, TIME, FLIGHT2, TIME_G, WINDOW), airport_maintenance(MAINTENANCE, AIRPORT), length_maintenance(MAINTENANCE, LENGTH), LENGTH <= TIME_G, limit_counter(MAINTENANCE, LIMIT),
TIME_M = TIME + LENGTH, TIME_N = TIME + LIMIT. % declare incrementally generated routing as external #external route(FLIGHT1, FLIGHT2, TIME_G, WINDOW) :
compatible(FLIGHT1, AIRPORT, TIME, FLIGHT2, TIME_G, WINDOW). % enforce routing sequences that include all flights :- flight(FLIGHT1, AIRPORT_S, TIME_S, AIRPORT_E, TIME_E),
#count{FLIGHT2 : route(FLIGHT1, FLIGHT2, TIME_G, WINDOW)} > 1. :- flight(FLIGHT2, AIRPORT_S, TIME_S, AIRPORT_E, TIME_E), not first(FLIGHT2, _), #count{FLIGHT1 : route(FLIGHT1, FLIGHT2, TIME_G, WINDOW)} != 1. % propagate assigned planes along routing assign(FLIGHT1, PLANE) :
first(FLIGHT1, PLANE). assign(FLIGHT2, PLANE) :
assign(FLIGHT1, PLANE), route(FLIGHT1, FLIGHT2, TIME_G, WINDOW). % generate maintenance slots for planes {maintain(MAINTENANCE, TIME, TIME_M, TIME_N, PLANE)} :maintainable(MAINTENANCE, FLIGHT, TIME, TIME_M, TIME_N), assign(FLIGHT, PLANE). % get covered flights from initial and dynamic maintenance slots covered(MAINTENANCE, FLIGHT, PLANE) :start_counter(MAINTENANCE, TIME_M, TIME_N, PLANE), flight(FLIGHT, AIRPORT_S, TIME_S, AIRPORT_E, TIME_E),
TIME_M <= TIME_S, TIME_E <= TIME_N. covered(MAINTENANCE, FLIGHT, PLANE) :maintain(MAINTENANCE, TIME, TIME_M, TIME_N, PLANE), flight(FLIGHT, AIRPORT_S, TIME_S, AIRPORT_E, TIME_E),
TIME_M <= TIME_S, TIME_E <= TIME_N. % enforce coverage of all flights :- maintenance(MAINTENANCE), assign(FLIGHT, PLANE),
not covered(MAINTENANCE, FLIGHT, PLANE). % associate costs with dynamic maintenance slots :˜ maintain(MAINTENANCE, TIME, TIME_M, TIME_N, PLANE).
[weight_maintenance@level_maintenance, TIME, PLANE] #program step(t). % incremental program to generate routing % generate new flight connections for current time window {route(FLIGHT1, FLIGHT2, TIME_G, t)} :
compatible(FLIGHT1, AIRPORT, TIME, FLIGHT2, TIME_G, t). % enforce sufficient ground time for dynamic maintenance slots :- compatible(FLIGHT1, AIRPORT, TIME, FLIGHT2, TIME_G, t), maintainable(MAINTENANCE, FLIGHT1, TIME, TIME_M, TIME_N), length_maintenance(MAINTENANCE, LENGTH), TIME_G < LENGTH, maintain(MAINTENANCE, TIME, TIME_M, TIME_N, PLANE), assign(FLIGHT2, PLANE). % associate costs with TAT violations :˜ route(FLIGHT1, FLIGHT2, TIME_G, t), tat(FLIGHT1, TAT), TIME_G < TAT. [weight_tat@level_tat, FLIGHT1]
Fig. 3: Multi-shot ASP encoding for Aircraft Routing and Maintenance Planning and associate each flight with its corresponding aircraft. Maintenance slots can then be scheduled for aircrafts assigned to flights indicated by the maintainable/5 predicate, and the arguments TIME_M and TIME_N in maintain/5 atoms provide the respective time period covered. The flights included in the initial interval or by performing maintenance for an aircraft are signaled by atoms of the predicate covered/3, where a subsequent constraint makes sure that each assigned flight is indeed covered. Reconsidering the instance in Fig. 2b, the initial seven_day maintenance period for aircraft 2 includes all flights that can belong to its route, while the flights 4 and 7 exceed the initial interval for aircraft 1. Hence, aircraft 1 needs to be maintained after its first flight, as indicated by the atom maintain(seven_day,379361,388361,984161,1) in an (optimal) answer set. The allocation of maintenance slots is however penalized by a weak constraint, and the particular instance :˜ maintain(seven_day,379361,388361, 984161,1). [1@1,379361,1] associates the weight 1 at level 1 with the maintenance of aircraft 1 at time 379361.
In contrast to the upper part of the encoding in Fig. 3, the one below the #program directive is instantiated in steps during multi-shot solving, where t is replaced by successive integers starting from 1. The choice rule for route/4 atoms, which were declared external before, then allows for taking the connections newly admitted at the current step or integer for t, respectively. E.g., route(1,2,6540,2) is introduced as a potential connection in the second step, and route(1,6,12256,4) in the fourth step. The subsequent constraint enforces sufficient ground time when a maintenance slot is allocated in-between two connected flights.4 This rules out route(1,2,6540,2) for an aircraft subject to seven_day maintenance after flight 1, as it is the case for aircraft 1 whose first flight is 1. Hence, the routing given by an (optimal) answer set is such that the flights 1, 6 and 7 are assigned to aircraft 1, and aircraft 2 takes 5, 2, 3 and 4. One can check that this schedule does not involve TAT violations, which would otherwise be penalized by a weak constraint according to the corresponding level and weight. As the greatest step associated with some flight connection in the routing happens to be 4 (indicated by the last argument in route(1,6,12256,4)), the multi-shot encoding requires four steps to lead to an answer set, which then describes an optimal solution for the instance in Fig. 2b.
Finally, let us note that a traditional single-shot version can be easily derived from the
more sophisticated multi-shot encoding in Fig. 3 by simply omitting the WINDOW and t
arguments from atoms related to flight connections, as well as dropping the #external
and #program declarations. A respective single-shot encoding is also provided at [
Our benchmark suite comprises 20 random instances, generated with the parameters:
– number of aircrafts: 25
– number of airports: 30
– average number of flights per aircraft: 20 X N (50; 10) 80 flights5
– average length of flights: 80 X N (140; 120) 600 minutes
– average length of flights’ TAT: 30 X N (45; 10) 60 minutes
– average ground time between two flights: 0 X N (240; 120)
1000 minutes
4 Our full encoding at [
The main bottleneck of flight connection networks is the large number of arcs when flights with long ground times in-between are taken as connection candidates, e.g., linking the first flight arriving at an airport to the last flight in the planning period departing from it. Such connections could be dropped by imposing a hard constraint on the maximum admissible ground time, yet to the risk of ruling out (optimal) solutions up to making Aircraft Routing and Maintenance Planning infeasible for tricky instances where some connection with long ground time has to be taken.
Rather than constraining ground times, our multi-shot ASP solving approach works by successively increasing the maximum ground time of the considered connections over iterations. For guaranteeing the progress to connections with longer ground times (and eventually all connections), we limit the runtime allotted for optimizing the routing and maintenance allocation in each iteration by means of the following intra-iteration stop criterion: An iteration is aborted when the empirically determined timeout of 60 seconds for finding some better solution is reached, in which case we continue to the next iteration with an increased maximum ground time of connections. The rationale of this strategy is to avoid getting stuck on infeasible sub-problems, when the admissible ground time is yet to small in the first iterations, or on (near-)optimal solutions that can neither be improved nor verified as optimal in reasonable runtime. Note that the timeout is reset to 60 seconds whenever the optimization comes up with a better solution, as we do not want to abort iterations in phases where the optimization makes progress. Upon proceeding to the next iteration, either due to timeout or search space exhaustion, we check that new connections become admissible, or increase the maximum ground time further without relaunching the optimization otherwise. Moreover, the cost of the best solution found so far, if any, is passed on as upper bound to admit better solutions only.
Our experiments consider the 20 random instances whose generation has been described in the previous subsection. As time window for increasing the maximum ground time of connections, we use the value 3600 (one hour), corresponding to the default of our encoding in Fig. 3. Unless noted otherwise, we also stick to the level 2 for weight (a) Solution costs per runtime for instance 14 (b) Solution costs per runtime for instance 15 constraints penalizing TAT violations, and the smaller level 1 for maintenance slots implies strictly lower priority of minimizing their number, where each maintenance slot or TAT violation is counted with the weight 1. Note that this scheme is different from the weighted sum taken to calculate the cost of a draft solution in Section 3.3, and we reuse the latter for comparability when plotting solution costs in the sequel. All experiments were run with Clingo version 5.4.0, each run limited to one hour wall clock time, on an Ubuntu 18.04 machine with two 8-Core Intel Xeon E5520 processors and 48GB RAM.
Fig. 5 plots the costs of best solutions found in one hour with traditional single-shot solving, where the full problem with all flight connections is considered, and with our (basic) multi-shot solving approach in relation to the costs of draft solutions generated together with the instances. Although multi-shot solving with its intra-iteration stop criterion merely probes the search space of sub-problems without guaranteeing that a globally optimal solution will be obtained, it usually finds better solutions than singleshot solving in the time limit, and sometimes its best solution also improves on the draft solution that is of good quality by construction.
Fig. 6a and 6b show the optimization progress in detail for two representative instances, where single-shot solving leads to a better solution for one instance and multishot solving for the other.6 We observe that multi-shot solving finds its solutions much faster and gets then stuck on unsuccessful iterations aborted after 60 seconds each. Tackling the full problem by single-shot solving makes finding the first feasible routing and then achieving improvements much harder and time-consuming, so that granting 6 Occasionally rising solution cost over time is due to the weighted sum function used for plotting the solution quality, while the optimization strictly reduces TAT violations in such cases and also leads to lower weighted sum values in the long run. (a) Solution cost per iteration for instance 7 (b) Solution cost per iteration for instance 8 non-negligible runtime is a necessity to obtain solutions of good quality. Notably, all runs exhaust the time limit of one hour due to the size and combinatorics of instances.
Picking again two representative instances, Fig. 7a and 7b indicate the optimization progress over the iterations of multi-shot solving, where we observe substantial improvements by step-wise increases of the maximum ground time at the beginning, followed by little and then no improvement at all for a substantial number of unsuccessful iterations aborted after 60 seconds. This suggests the addition of an inter-iteration stop criterion to avoid spending time on unpromising iterations, and our early-stop multi-shot solving approach thus aborts the entire run after timing out without any improvement for three iterations in a row. The deliberate stop of runs constitutes a trade-off between solution quality and computational efforts, and the number of three consecutive timeouts of iterations without improvement is again problem-specific and determined empirically.
The plot in Fig. 8a shows that runtimes are indeed substantially reduced by early-stop multi-shot solving, with the median around 20 minutes instead of fully exhausting the one hour per instance. Comparing the solution costs in Fig. 8b yields a rather modest quality decline in exchange for runtime savings, which can presumably be tolerated in application scenarios where the time taken for decision making is critical.
The results reported so far rely on distinct priority levels for TAT violations and maintenance allocation, and now we compare the performance of optimization relative to the weighted sum function given in Section 3.3. Switching to the latter can be easily done by (a) Runtimes for weighted sum and level function (b) Solution costs for weighted sum and level function setting the values for the constants level_tat, level_maintenance, weight_tat and weight_maintenance used by the encoding in Fig. 3 to 1, 1, 500 and 101.
Fig. 9a and 9b plot runtimes and solution costs for early-stop multi-shot solving with either the weighted sum function or distinct priority levels to penalize TAT violations and maintenance slots. Switching to the weighted sum greatly reduces runtimes, yet because optimization turns out to be much harder and the three iterations in a row without improvement are reached way more quickly. Accordingly, the solution quality suffers heavily, even despite the previously considered optimization based on distinct priority levels merely approximates the weighted sum function used for plotting and now in the optimization process as well. The quick outage of improvements after more or less substantial progress in the first iterations becomes also apparent on the detailed inspections of two instances in Fig. 10a and 10b. We conjecture that higher weighted sum values due to incorporating costs from several sources at the same level complicate recognizing and discarding partial assignments that can eventually not lead to any improvement, so that more search efforts are spent on such fruitless assignments.
While we merely considered single-threaded Clingo before, it also allows for running multiple solver threads with complementary search strategies in parallel. The remarkably reduced runtimes and solution costs obtained with eight parallel solver threads are summarized in Fig. 11a and 11b. Notably, the best solutions found by early-stop multi-shot solving with parallel threads consistently improve on the draft solutions for instances, thus showing that high-quality results can be achieved with reasonable com(a) Runtimes for sequential and parallel solving (b) Solution costs for sequential and parallel solving putational efforts. Fig. 12a and 12b additionally plot the much more rapid optimization progress for two representative instances. This robustness is certainly related to the parallel use of complementary search strategies, also considering that the discovery of a better solution by one thread resets the timeout to another 60 seconds for all threads. 5
The Aircraft Routing and Maintenance Planning problem lends itself to multi-shot ASP
solving based on successively increasing ground times of flight connections, given that
long ground times are undesirable in practice and should thus be avoided if possible.
A direct use of the incremental mode shipped with Clingo [