Transcript Crew Pairing Optimization with Genetic Algorithms

Crew Pairing Optimization
with Genetic Algorithms
Harry Kornilakis and Panagiotis Stamatopoulos
Department of Informatics and Telecommunications
University of Athens
{harryk,takis}@di.uoa.gr
 The Crew Pairing Problem
 Solution to the Crew Pairing Problem
Pairing Generation
Optimization Using Genetic Algorithms
 Experimental Results
 Conclusions
The Crew Pairing Problem (1/2)
 The Crew Pairing Problem (CPP) is an important
optimization problem that is part of the airline
crew scheduling procedure.
 Crew scheduling = Crew pairing + Crew assignment
 Given a timetable containing all the flight legs
that an airline company must carry out, the
objective of the crew pairing problem is to
generate leg combinations (pairings) of
minimum cost that cover all given flight legs.
The Crew Pairing Problem (2/2)
 A pairing is a round trip, consisting of a
sequence of legs, which starts and ends at the
crew's home base.
 Each pairing is composed of a number of legal
workdays, called duties, which are separated by
rest periods.
 The CPP is the problem of finding a set of
pairings, covering all legs that the airline has to
carry out, with a minimal cost.
Constraints of the CPP
 Temporal constraints
 Spatial constraints
 Constraints concerning the type of airplane used
(fleet constraints)
 Constraints due to laws and regulations (e.g.
maximum duration of a duty, minimum rest
period between two duties etc.)
Further Considerations on the
CPP
 Deadheading: Crew members travelling as
passengers, in order to move to a specific airport and
continue a round trip.
 Cost Function: Usually depends on the crew’s wages
and can be quite complicated.
 Modeling of the Constraints: Highly non-linear and
hard to model constraints. Linear programming
inadequate.
 Huge size of the search space
Solving the Crew
Pairing Problem (1/2)
 Two Phase Procedure
1. Pairing Generation: A large number of legal
pairings, composed of the legs in the timetable, is
generated.
2. Optimization: A subset of the generated pairings
is selected, so that every flight leg in the schedule is
included in at least one pairing and the total cost is
minimized.
Solving the Crew
Pairing Problem (2/2)
 Pairing generation is also divided in two phases:
 We generate a large set of legal duties from the flight
legs
 We generate the set of pairings by using the duties
previously found
Pairing Generation
Timetable
with Flight
Legs
Duty Generation
Application
of
Constraints
Pairing Generation
from Duties
Duties Application
of
Constraints
Optimization
Pairings
Set Covering
Problem
Final
Solution
Pairing Generation (1/2)
 L : Set of all the flight legs
 Constraints: defined as a function C : 2L  {0,1},
where 2L is the powerset of L, C (p)=1 if p is a legal
pairing and C (p)=0, if not.
 We want to generate a set of pairings
P = {p  2L | C (p)=1}, i.e. the set of
pairings that satisfy all the constraints.
 Checking for the satisfaction of the constraints is
independent of the optimization phase.
Pairing Generation (2/2)
 First Phase: Generation of duties from legs
 Implemented as a depth-first search in the space of all
possible subsets of the set of all flight legs.
 The number of legal duties found might be too large,
so we also perform an algorithm that selects the best
in order to use them in the next phase.
 Second Phase: Generation of pairings from duties
 Works similarly to the first phase but instead of duties
it generates pairings.
Optimization (1/2)
 Modeled as a set covering problem:
 Given a set M with m elements and n subsets Μj of M
with associated costs cj , j = 1,2… n, select a number
of these subsets such that every element of M is
contained in a least one selected subset and the total
cost of all selected subsets is minimum.
 Set covering has been proven to be NPcomplete (Garey & Johnson, 1979)
Optimization (2/2)
 Existing Methods for the set covering problem:
Exact Methods: For average sized problems
Approximate Methods: Give approximate solution
to large sized problems
 Our Method is a modification of an algorithm by
Beasley & Chu (1996)
Genetic Algorithms (1/2)
 Genetic algorithms (GA): Methods for random
search based on the evolutionary process of
species, found in nature.
 Each possible solution is encoded as a string
(chromosome). Each character of the
chromosome is called a gene.
 The quality of each solution is represented by a
real valued function defined over the set of all
chromosomes (fitness function).
Genetic Algorithms (2/2)
 Two of the fittest members of the population are
selected and combined to produce a new
solution (crossover). Then a few random genes
of the new solution are changed (mutation) in
order to avoid local minima in the search.
 New individuals replace the weaker members of
the existing population.
Genetic Algorithm for Crew
Pairing Optimization (1/4)
 Binary String Coding: Each chromosome has length
equal to number of pairings. Each gene corresponds to
one pairing. If the gene is 1 then the corresponding
pairing is in the solution, otherwise it is not.
 Fitness Function:
Σi




ci ·gi +deadheadingPenalty ·deadheadedFlights
ci is the cost if the i-th pairing
gi is the value of the i-th gene of the solution
deadheadingPenalty is a constant to penalize deadheaded flights
deadheadedFlights is the number of deadheaded flights
Genetic Algorithm for Crew
Pairing Optimization (2/4)
 Selection of Parents: based on their order in the
population, sorted in descending order based on their
fitness function, not on the absolute value of the fitness.
 Crossover: Uniform crossover, i.e. if the i-th gene of
both parents is 1 (respectively 0) then the i-th gene of
the offspring is set to 1 (respectively 0). Otherwise its
value is randomly selected.
 Mutation: A few genes of the new solution are
randomly set to 1 or 0 with probability that depends on
the density (the percentage of genes equal to 1) of the
fittest individual of the population.
Genetic Algorithm for Crew
Pairing Optimization (3/4)
 Correcting the Solution: After crossover and
mutation the new solution might be infeasible.
 Correction Algorithm: The value of some genes is
changed to 1 until every flight leg is covered and the
solution becomes feasible. For each uncovered leg in the
solution, we add a pairing that covers that leg. To select
one pairing among all the pairings which contain that
particular leg, we use a heuristic that favors pairings of
low cost that cover as many uncovered legs as possible
and as few legs already covered as possible.
Genetic Algorithm for Crew
Pairing Optimization (4/4)
Randomly generate an initial population of chromosomes.
Repeat until a satisfactory solution is reached
Select two of the fittest members of the population for
parents.
Apply the crossover operator on the two parents to
produce a child chromosome.
Apply the mutation operator on the child chromosome.
Correct the child chromosome so that it becomes a
feasible solution.
Select one of the weakest members of the population to
be replaced.
Replace the selected individual with the child.
Experimental Results
 Input data: Real data from the flight schedule of
Olympic Airways (737-200 fleet, April 1998), which was
composed of 2100 flight legs, passing through 29
different airports.
 Constraints: Based on the regulations of the Olympic
Airlines for cockpit crews.
 Pairing Generation: 22090 legal duties and then
11981 legal parings were generated and stored.
 Optimization: After 20000 generations a solution of
cost 976004 and of zero deadheading was found.
Progress of the Optimization (1/2)
Generation
Cost
100
1000
1247776 1121057
3000
5000
8000
1064647
1036596
1008276
Pairings
635
592
567
551
537
Deadheading
71
10
6
6
4
Generation
10000
13000
16000
20000
Cost
996994
988418
980344
976004
Pairings
531
529
526
525
Deadheading
4
2
0
0
Progress of the Optimization (2/2)
Comparison of our Method and
Parachute (1/2)
 We compared our result with the result found by
the project PARACHUTE, a project that
combines constraint programming with parallel
computing. We ran PARACHUTE on the same
data set and used the same constraints.
 Our method gave a solution of cost lower by
194148 (16.5%).
Comparison of our Method and
Parachute (2/2)
Total Cost
Our Method
976004
No. of
Pairings
525
PARACHUTE
1170152
611
Deadheaded
Legs
0
25 (1.1%)
Conclusions
 We separated the Crew Pairing Problem in two
phases.
 A depth-first search was used in the first phase
and a genetic algorithm in the second.
 Experimental results with real data were
satisfactory improving on previous result and
showing that the solution is viable.