Cargo Loading Process Paper
Cargo Loading Process Paper
Cargo Loading Process Paper
Problem
genehmigte
Dissertation
von
Felix Brandt
The Air Cargo Load Planning Problem
A major operational planning problem in the air cargo industry is how to arrange cargo
in an aircraft to fly safely and profitably. Therefore, a challenging planning puzzle has to
be solved for each flight. Besides its complexity, the planning is mostly done manually
today, which is a time consuming process with uncertain solution quality. The literature
on loading problems in an air cargo context is scarce and the term is used ambiguously for
different subproblems like selecting containers, packing items into containers, or loading
containers into aircraft. All of the presented models only focus on certain aspects of what
is in practice a larger planning problem. Additionally, some practical aspects have not
been covered in the literature.
In this work, we provide a comprehensive overview of the air cargo load planning problem
as seen in the operational practice of our industrial partner. We formalize its require-
ments and the objectives of the respective stakeholders. Furthermore, we develop and
evaluate suitable solution approaches. Therefore, we decompose the problem into four
steps: aircraft configuration, build-up scheduling, air cargo palletization, and weight and
balance. We solve these steps by employing mainly mixed-integer linear programming.
Two subproblems are further decomposed by adding a rolling horizon planning approach
and a Logic-based Benders Decomposition (LBBD). The actual three-dimensional packing
problem is solved as a constraint program in the subproblem of the LBBD.
We evaluated our approaches on instances containing 513 real and synthetic flights. The
numerical results show that the developed approaches are suitable to automatically gen-
erate load plans for cargo flights. Compared to load plans from practice, we could achieve
a 20 percent higher packing density and significantly reduce the handling effort in the air
cargo terminal. The achieved costs of additional fuel burn due to aircraft imbalances and
reloading operations at stop-over airports are almost negligible. The required runtimes
range between 13 and 38 minutes per flight on standard hardware, which is acceptable
for non-interactive planning.
Cargo airlines can significantly profit from employing the developed approaches in their
operational practice. More and especially the profitable last-minute cargo can be trans-
ported. Furthermore, the costs of load planning, handling effort, and aircraft operations
can be significantly reduced.
i
Contents
Abstract i
1 Introduction 1
1.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Research questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organization of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4 Aircraft configuration 23
4.1 Related literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 The Aircraft Configuration Model . . . . . . . . . . . . . . . . . . . . . . . 25
4.2.1 Input parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.2 Decision variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.4 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.5 Model overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5 Build-up scheduling 31
5.1 Related literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.2 The Build-up Scheduling Model . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2.1 Input parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2.2 Decision variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2.4 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
iii
Contents
8 Benchmark instances 71
8.1 The ACLPP data model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
8.2 Analysis and insights into real world instances . . . . . . . . . . . . . . . . 73
8.3 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
8.3.1 Master data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
8.3.2 Generation of synthetic flights . . . . . . . . . . . . . . . . . . . . . 82
8.3.3 Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.4 Performance indicators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
iv
Contents
10 Evaluation 119
10.1 Implementation and testing environment . . . . . . . . . . . . . . . . . . . 119
10.2 Preliminary parameter tuning . . . . . . . . . . . . . . . . . . . . . . . . . 120
10.2.1 Aircraft configuration . . . . . . . . . . . . . . . . . . . . . . . . . . 120
10.2.2 Build-up scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
10.2.3 Palletization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
10.2.4 Weight and balance . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
10.3 Results of the sequential approach . . . . . . . . . . . . . . . . . . . . . . . 129
10.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
12 Conclusion 151
12.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
12.2 Research questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
12.3 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
12.4 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Bibliography 157
Glossary 165
v
1 Introduction
“A recession is when you have to tighten your belt; depression is when
you have no belt to tighten. When you’ve lost your trousers – you’re in
the airline business.”
— Sir Adam Thomson, founder of British Caledonian
The airline business is highly competitive. Over the past decades this fierce competition
has lead to numerous innovations to utilize the most expensive assets, the aircraft, to
the maximum and to reduce costs wherever possible. Operations research has played an
important role in this process by providing theory and tools for creating flight and crew
schedules, optimizing revenue management, and supporting many more application areas.
Staying in the airline business today without such support is not imaginable.
Besides the well-known passenger airline business, a lot of airlines also transport cargo
and many passenger flights carry cargo next to baggage in their lower decks. Furthermore,
as of 2015 there are around 1,770 large cargo-only aircraft operated by airlines worldwide
(Crabtree et al., 2016). Although all these aircraft transport less than 1 percent of world
trade tonnage, this accounts for around 35 percent of world trade by value (Crabtree et al.,
2016). Albeit its economical importance, air cargo has gained far less R&D attention than
the passenger airline business and therefore has considerable potential to be improved by
applying current technologies and developing new tools like decision support systems.
One major operational problem present specifically in air cargo is how to arrange the
cargo in an aircraft. At first, loading cargo into an aircraft might seem to be a simple
task. But, in reality the loading must be carefully planned. For each single flight an
airline that transports cargo has to answer a set of delicate planning questions to operate
safely and profitably. And there are more challenges: Cargo rates have fallen by around
35 percent over the last 20 years (Crabtree et al., 2014). Therefore, airlines must aim
for a high utilization of the aircraft on each flight. On the other hand, there is a soaring
overcapacity in the air cargo market, see Murray (2016) and The Economist (2016), which
leads to historically low average load factors of the aircraft. Accordingly, airlines are forced
to also reduce their operating cost for ground handling and fuel wherever possible to stay
in business.
In the past, there have been a couple of scientific contributions addressing “air cargo
loading” problems. However, the term is used ambiguously for different decisions to be
made in the load planning process. This ranges from selecting the containers to load
(Mongeau and Bes, 2003), over solving three-dimensional packing problems (Paquay et
al., 2016), to balancing the aircraft for fuel efficiency (Lurkin and Schyns, 2015). All of
the presented models only focus on certain aspects of what is in practice a larger planning
problem. In this work, we consider the overall problem of operational load planning for
airlines that transport cargo and therefore we coin the term Air Cargo Load Planning
Problem (ACLPP).
1 Introduction
This work was partially supported by our industrial partner Lufthansa Cargo AG, the
cargo division of the Lufthansa Group. Therefore, the described planning problems are
derived from the current operational practice of our partner, but apply to other airlines
transporting cargo nonetheless. Besides an insight into practice and access to its planning
experts, our partner also provided benchmark data for the analysis of the problem at hand
and the evaluation of our approaches.
1) What are the requirements and drivers of air cargo load planning in practice?
In the literature, the term “air cargo loading” is used ambiguously and no general models
exist. Therefore, we develop a unified nomenclature of the covered aspects and a compre-
hensive model of the problem as seen in practice. We describe the decisions to be made,
which restrictions have to be adhered, and what the overall objective is.
2
1.3 Organization of the thesis
2) Can valid and competitive load plans be generated with reasonable effort? De-
scribing an optimization model is only halfway. We develop and implement a solution
approach based on the current manual planning process of our industrial partner. There-
fore, we split the problem into multiple steps and solve them one after the other. We
evaluate the approach on numerous test instances, stemming from real flights and ex-
treme scenarios to get insights into the quality achieved and the runtimes required.
3) Does splitting the problem lead to adverse effects and what can we do about it?
From a practical point of view, the steps performed during load planning should be as
independent and self-contained as possible. However, this limits the scope of optimization,
which might lead to local optimization and to results that represent extreme cases. This
in turn can lead to adverse results in the solution process. We analyze, where such effects
may occur in our approach and develop ways to mitigate them.
3
2 Air cargo primer
In this chapter, we present a basic introduction into the world of air cargo and the
operational planning problems faced by airlines that handle cargo. The topics are selected
with the required aspects of load planning in mind. In Section 2.1, we describe the business
of airlines that provide cargo services. Afterwards, we characterize the typical cargo in
Section 2.2, the used loading devices in Section 2.3, the airlines’ modes of transport
in Section 2.4, and the relevant airport processes in Section 2.5. For a more in depth
introduction we refer to the Air Cargo Guide by Grandjot et al. (2007).
Table 2.1: Main differences between the passenger airline and air cargo business
they provide a one-stop-shop solution for shippers. These carriers provide a more
standardized and automated service specifically designed for small shipments and
documents. Therefore, these carriers usually apply limits on the maximum size,
weight, and handling requirements of the shipments.
• Combination carriers operate both passenger aircraft and cargo aircraft. Similar
to the passenger airlines, they transport cargo on their passenger aircraft as a by-
product. However, they couple this service with their backbone network of cargo-
only flights. This way, the smaller passenger flights can feed cargo into the cargo-
only network to increase its overall utilization. Additionally, some combination
carriers also provide trucking services, to transport cargo from/to smaller airports
that are not serviced by cargo-only aircraft. Shipments in the cargo-only network
and trucking services can be of almost any size respecting the aircraft dimensions
and also contain hazardous goods. Carriers from this category often operate as a
special cargo division of large airlines. Examples are Lufthansa Cargo, Emirates
Sky Cargo, or Cathay Pacific Cargo.
• Cargo-only carriers operate exclusively cargo aircraft. They have a significantly
smaller network than the combination carriers. Typically, they operate between
large markets, like China and the USA, to fill their capacity. Thus, they leave
the main part of feeding and consolidation to their forwarders. Examples for large
cargo-only carriers are Cargolux, AirBridgeCargo, or Nippon Cargo Airlines.
• Charter carriers provide the most flexible and the most expensive air cargo trans-
portation service. With them, the shipper can transport nearly any good between
any pair of airports as required by his own schedule. Therefore, these carriers are
6
2.1 Air cargo business
typically used for large machine parts, for example, power transformers or drilling
equipment, or for emergency cases requiring an entire aircraft. There are few ded-
icated charter carriers like Atlas Air, Southern Air, or Antonov Airlines, but most
other carriers will also offer their aircraft for charter.
This work mostly applies to combination and cargo-only carriers. The loading problems
faced by the other types of carriers are usually easier to solve. The shipments transported
by express carriers and passenger airlines are mostly small, have little requirements, and
do not interfere with other shipments. Charter carriers often transport only a single bulky
item or mostly homogeneous pallets, like in humanitarian aid.
Besides the business models, the passenger and cargo business differ in several ways:
In the passenger business one seat equates to one passenger. Managing the cargo capacity
of a flight is much harder. To estimate the remaining cargo capacity, the airline has
to track weight, volume, and a variety of handling requirements, e.g., incompatibilities
between shipments. Furthermore, it must solve a three-dimensional planning puzzle,
defining how all items can be safely arranged inside the aircraft.
Transporting air cargo involves extensive ground handling operations. First, the cargo
needs to be transported by conveyors or fork lifts inside the terminal. Furthermore, it
must be packed onto ULDs, lashed, and tracked on its way. Especially the packing part
gets more difficult the more heterogeneous the cargo is.
Another difference between the air cargo and passenger business is the geographic struc-
ture of transport demands. Passenger flows are usually bidirectional as most passengers
return to their origin. Therefore, passenger aircraft are typically operated as shuttles be-
tween an airline’s hubs and other airports. In contrast, cargo flows are highly imbalanced
and cargo airlines often operate flights with stop-overs, i.e., only a part of the payload is
(un)loaded at a stop-over airport and the aircraft continues its journey under the same
flight number.
To be able to describe certain subsections of a flight with stop-overs we define three terms
that appear frequently throughout this work. We define a flight as any sequence of aircraft
movements performed under the same flight number. A leg is a nonstop aircraft movement
between two airports. A segment is a subsequence of legs of a flight on which cargo can
be transported. We note, that these terms are not used consistently in the airline world,
but we stick to the above definitions for simplicity.
Flights contain stop-overs mostly for two reasons. First, there might not be enough cargo
demand between two airports to justify the use of a large cargo aircraft. By adding
more stop-overs in between, the airline can attract more shipments and thus increase the
utilization of the aircraft. Lufthansa Cargo for example operates flight LH8272, depicted
in Figure 2.1, from Frankfurt to Santiago de Chile with stop-overs in Dakar, Senegal, and
Viracopos, Brazil. The second reason is that splitting a long flight into two shorter legs
with a stop-over for refueling allows the airline to load less fuel on each leg and instead
to load more cargo into the aircraft. In the latter case, the amount of loaded/unloaded
cargo at the stop-over airports is usually smaller than in the former case. An example
is the Lufthansa Cargo flight LH8475 from Hong Kong to Frankfurt with a 60 minute
stop-over in Almaty, Kazakhstan, at half-distance.
7
2 Air cargo primer
FRA-DAK
FRA-VCP
FRA-SCL
Segments
DAK-VCP
DAK-SCL
VCP-SCL
Figure 2.1: Illustration of the definition of flights, legs, and segments: Flight LH8272
consists of three successive legs and technically cargo could be transported on
each of the six segments.
From a sales perspective, the air cargo business is split into two phases. In the first
phase, customers with a regular demand, typically forwarders, negotiate long-term con-
tracts (LTC) with the airline. An LTC allows the customer to ship a certain amount
of cargo on a defined set of flights for a fixed rate. This way, the airline increases its
planning reliability and the customer gets a better price. Nevertheless, the actual cargo
that will be on a flight is only booked a few days in advance. Depending on the contract
the customer is able to resign from a flight at short notice, sometimes even without any
cost.
The second phase of capacity sales is the regular booking process, which works similar
to the one for passengers. The customer requests a quote, books capacity for a certain
route, and specifies the cargo properties like size, weight, and handling requirements.
Most bookings only take place a few days before the flight, much shorter than in the
passenger business.
To conclude, the air cargo business has some major differences to passenger airlines.
Unidirectional cargo flows and late bookings make it hard to predict and plan ahead.
When it comes to loading an aircraft, a lot of handling manpower is involved to solve a
complex three-dimensional planning puzzle in short time.
8
2.3 Unit load devices
land transport. Therefore, it is usually only chosen for goods with at least one of the
following four properties:
• urgent: The goods need to be at a distant place within short time. Typical goods
include spare parts, fashion, or living animals.
• perishable: The goods degrade when they are not properly handled, for example
cooled. Therefore, they should be in a controlled environment and arrive at the
destination as fast as possible. Typical goods include flowers, drugs, or fresh food.
• valuable: The goods are of high value and have to be transported in a secure way.
Typical goods include semiconductors, banknotes, or works of art.
• dangerous: The goods may harm their environment when they are not properly
handled, which could mean tilting, too high surrounding temperature, or shock.
Therefore, they have to be handled with care and the airline needs to be prepared
for accidents by training its crews and, for example, installing an automated fire-
extinguishing system on the aircraft. Typical goods include chemicals, batteries, or
radioactive materials.
Although some shipments can be quite small, a significant share of the cargo transported
by combination or cargo-only carriers is at least the size of a wooden pallet, like those
defined in the ISO 6780 standard (ISO, 2003). Depending on the originating world region
typical pallet sizes are 1,016x1,219 mm (North America), 800x1,200 mm (Europe), or
1,100x1,100 mm (Asia) (Wikipedia, 2016). Throughout this work we refer to the Euro-
pean pallet format 800x1,200 mm as EUR-pallet. Most shipments are box-shaped but
irregular shapes, barrels, or just sacks occur frequently. Often multiple boxes are already
consolidated onto a wooden pallet by the shipper and should not be separated by the
airline. The packaging is often made of cardboard, wood, or styrofoam and optionally
wrapped with plastic foil or protected by reinforced metal edges.
Accordingly, one challenging task in load planning is to find a good combination of these
strongly heterogeneous shipments to fill the aircraft capacity in a secure and efficient way.
9
2 Air cargo primer
Figure 2.2: Loaded PMC pallet with main deck contour (left). Lower deck AKE container
(right). Source: Lufthansa Cargo AG, Photographer: Stefan Wildhirt (left),
Ingrid Friedl (right)
a) b) c) d)
Figure 2.3: Example ULD types in original proportions. Dashed lines mark the allowed
contour of a filled pallet while solid lines mark floor sheets and walls of con-
tainers. a) main deck pallet (PMC) used in freighter aircraft b) lower deck
pallet (PMC) and c) half-size lower deck container (AKE) used in freighter and
wide-body passenger aircraft d) lower deck container (AKH) used in narrow
body passenger aircraft.
Table 2.2: Common ULD container types. The given dimensions are the usable space
inside the ULD. Tare is the empty weight of the ULD.
10
2.4 Modes of transport
Table 2.3: Common ULD pallet types. Tare is the empty weight of the pallet including
net and straps. The loadable volume depends on the constructed contour.
Figure 2.4: Cross sections of typical modes of transport (from left to right): lower deck of
narrow-body aircraft (A320), lower deck of wide-body aircraft (A350), main
deck and lower deck of freighter aircraft (MD11F), and road feeder trucks.
pallet needs to be covered by a net and straps after it is built, which requires extra
handling effort. Containers on the other hand have a predefined contour and side walls
such that usually no net or straps are required. Accordingly, they can only be placed at
positions where their contour fits in and less handling effort for securing the ULD contents
is required. They are preferred for smaller shipments or baggage.
11
2 Air cargo primer
Table 2.4: Common aircraft types and their cargo capacities. The columns give (from left
to right): The aircraft type, model name, maximum number of passengers, the
maximum payload (passengers + cargo) the aircraft can bear, the typical cargo
payload after loading (passengers + baggage + fuel), the usable volume of the
cargo compartments, the number of standard PMC pallet equivalents on the
main deck and the number of standard AKE container equivalents on the lower
deck. All numbers are only indicative and can vary between different aircraft
versions and even airlines. (Source: Airport planning manuals of Airbus and
Boeing)
ULDs, and have a medium payload between 10 and 27 tonnes. The largest cargo aircraft
are cargo-only aircraft, like the freighter versions of the McDonnell Douglas MD-11 or
the Boeing B747/B777. They carry no passengers, are loaded with ULDs on the lower
deck (LD) and main deck (MD), and have a typical payload of 90 to 130 tonnes.
12
2.5 Airport processes
break-down unloading
import
piece store uld store
export
build-up loading
Figure 2.5: Typical material flow in an air cargo terminal (gray arcs represent items, black
arcs ULDs). Cargo is unloaded at the terminal from incoming flights or trucks,
or it is dropped by the customer at the export interface. Inside the terminal
the cargo is broken down from ULDs into single items, stored, and build up
into ULDs. The cargo leaves the terminal to be loaded into an aircraft or
truck, or to be picked up by the customer at the import interface.
porarily or directly sent to the build-up process. During build-up the items are packed
onto ULDs. The ULDs are weighed and then loaded into an aircraft or RFS truck.
After unloading at the next station the ULDs are again stored as a whole or broken down
into their items. These can then be picked up by the customer through the import point
or continue their journey towards their final destination.
In the following, we describe the two processes relevant for load planning, namely the
build-up and aircraft loading. The corresponding unload and break-down processes are
simpler and do not require as much description.
Build-up process
The build-up process is the most time consuming physical step done in an air cargo
terminal. Here the ULDs are packed with cargo. See Figure 2.6 for a sample view into
the terminal build-up area. The workers start with one or more empty ULDs and an
assortment of items assigned to the same transport segment. They have to pack the
items onto the ULDs in a legal and safe way. Large or heavy items are placed by using a
fork lift. Smaller items are usually placed by hand.
This task is challenging for several reasons: The majority of ULDs is built several hours
before the flight departs. Therefore, the items at the workstation are generally a subset
of the cargo that already arrived at the terminal for the considered flight. As this amount
of cargo can be quite large, see the stated volumes in Table 2.4, it is hard to keep track
of and to combine the shipments such that all items fit onto the ULDs. Furthermore, the
workers have to make sure that the weight limit for each ULD is not exceeded and the
13
2 Air cargo primer
Figure 2.6: Build-up workstations in a cargo terminal. Source: Lufthansa Cargo AG,
Photographer: Werner Bartsch
given maximum contours for each ULD are respected. Single over-sized items might be
placed on a ULD with overhang and another ULD, which then has to be placed on an
adjacent position in the aircraft, needs to leave some free space at the adverse position.
The items have to be packed in a stable way, i.e., no tipping, slipping, or breaking because
of too much top load is acceptable. This load stability is also required during takeoff,
flight, and landing, when the aircraft is tilting or exposed to accelerating forces. To
secure the items on pallet ULDs the workers use nets and straps. Furthermore, dunnage
materials like wooden boards or empty wooden pallets are used to distribute point loads
across larger surfaces, to lock items into position, or to provide an even loading surface
for further items.
In addition, there is a constant pressure of time. Each aircraft has a scheduled departure
time and will rarely wait for a single missing ULD. Therefore, the decisions once made
during build-up should not be revised too often.
Aircraft loading
The final physical step of the loading process is to load the built ULDs into the air-
craft. The containers and pallets are loaded into special ULD compartments equipped
with rollers and latches on the floor, see Figure 2.7. Most aircraft have two separate
compartments on the lower deck, one in front of and another behind the center wing box,
see Figure 2.8. Cargo aircraft also have a main deck compartment spanning along the
fuselage. Most compartments only have a single door for the ULDs to enter and leave.
Accordingly, loading is often a first-in-last-out (FILO) process. This is especially impor-
tant for cargo aircraft as they frequently fly on multi-leg flights, i.e., they are not fully
unloaded at each airport and some ULDs will continue their journey on the same aircraft.
Main deck compartments often have two separate lanes. Nevertheless, lateral movements
and rotations of ULDs can only be made near the door, where rotatable rollers are installed
on the floor. Lower deck compartments usually have a single full width lane that can be
14
2.5 Airport processes
Figure 2.7: Aircraft loading: Empty main deck of a cargo aircraft with rollers and latches
on the floor (left). Loading of packed ULDs into the aircraft (right). Source:
Lufthansa Cargo AG, Photographer: Jannah Baldus (right)
15
2 Air cargo primer
AR BR CR DR ER FR GR HR JR KR LR MR
P R
AL BL CL DL EL FL GL HL JL KL LL ML
11P 12P 13P 21P 22P 23P 31P 32P 33P 41P
Figure 2.8: Layout of the loading positions of an MD11F freighter aircraft (top: main
deck, bottom: lower deck). Doors are marked as thick lines along the fuselage.
Standard loading positions are marked in gray. Alternative loading positions
for larger ULDs (e.g., CR+DR or GR+GL) and smaller ULDs (e.g., 11L/R)
are marked as dashed lines.
and Bes (2003) report that a CG shift of 75 cm on an Airbus A340 might lead to 4 tonnes
of wasted fuel per 10,000 km flown.
2.6 Summary
In this chapter, we provided a short introduction into the air cargo business and the
components one needs to understand the loading problems faced by cargo carriers.
We started with pointing out the differences between the passenger and air cargo business,
introduced the typical cargo characteristics, the container types (ULDs) into which the
cargo is packed, as well as the types of aircraft used.
After that, we introduced the outbound cargo handling processes, namely the build-up
and aircraft loading. In the next chapter we define the general load planning problem in
more detail and the steps the carriers have to undertake before a cargo flight can start.
16
3 Air cargo load planning
In the last chapter, we introduced the two main physical processes conducted before a
cargo flight: the ULD build-up and aircraft loading. In this chapter, we look at the
planning tasks that go along with these physical actions.
Our contribution here is twofold. First, we describe the full operational load planning
problem as faced by airlines that transport cargo. Only separate parts of it have yet
been studied in the literature. Second, we discuss the challenges of current manual plan-
ning approaches, which will lead us to our computerized planning approach proposed in
Chapter 9.
In the following, we introduce the decisions made during load planning in Section 3.1 as
well as the airline’s stakeholders and their respective objectives in Section 3.2. We discuss
the current state of the planning practice in Section 3.3 and identify current challenges
in Section 3.4.
maximize minimize
load effort
ground
sales
maximize handling even
revenue workload
aircraft
operations
separately in the literature. To our knowledge, there is no published work yet that de-
scribes the planning problems and related processes in the practically required level of
detail. We introduce the ACLPP by its four subproblems in detail in the upcoming
Chapters 4 to 7.
18
3.3 Traditional planning practice
Table 3.1: Overview of subproblem objectives and how they align with the goals of the
stakeholders, i.e., sales, ground handling, and flight operations. We mark three
levels: conformity (+), conflict of interest (−), and no influence (◦).
airport. This reduces the turnaround time as well as the wear and tear of the aircraft,
and results in less risk to damage the cargo.
In Table 3.1 we give an overview where the stakeholders’ goals echo in the objectives of
the defined subproblems and how they affect the goals of the other stakeholders. For
example, the minimization of effort during palletization might have a negative impact on
the sales goals (−) as it reduces the aircraft utilization. It has a positive impact on the
handling goals (+) as it reduces the number of handling operations. The goals of flight
operations are not influenced (◦) by the handling effort
From our experience, there is no clear hierarchy of objectives. What is most important
strongly depends on the overall situation. On a highly booked flight load maximization
seems to be the top priority. However, if the flight departs during a rush hour, it might
also be important to keep the handling effort low to be able to meet all deadlines. Finally,
weight and balance might become a driving factor on long-haul flights that operate at the
aircraft limits.
19
3 Air cargo load planning
Corresponding to the four subproblems introduced in Section 3.1, the planning process is
split into four stages each performed by appropriately trained workers.
In the first stage, denoted as load planning, the planners select the ULD types and their
respective number to built for each destination airport of the flight. They do this based
on the booked cargo weight and volume for each destination, the aircraft specifications,
internal regulations, as well as their personal experience. Furthermore, they add some
extra ULDs that should be filled with low priority cargo. These ULDs will be built and
sent to the aircraft but will only be loaded into it if an originally planned ULD is not
loadable. This might happen if a ULD arrives too late or is not properly packed and thus
rejected by the ramp agent at the aircraft. Usually, items are not assigned to specific
ULDs yet, but the planners might already suggest a certain ULD or ULD type for special
cargo. The list of ULDs to build and the suggested assignments are forwarded to the next
stage.
In the second stage, denoted as build-up planning, the planners decide about the schedule
of build-ups for all outgoing flights. They trigger the build-up of groups of ULDs and
assign an available workstation to them. Only nonstandard ULDs are scheduled on an
individual basis. The basic weekly workstation schedule, defining which flights are built
when and where, is predetermined usually for a full six-month flight plan. Accordingly,
the planners mostly supervise the task queue at each workstation and manually inter-
vene when disruptions occur. Furthermore, the planners make sure that enough cargo is
available at the workstations. They release batches of shipments from the warehouse and
send them to the workstations. Except for the suggested assignments from the first stage,
still no individual items are picked at this stage. Thus, the result of the second stage are
workstations set up with empty ULDs and an assortment of cargo.
In the third stage, denoted as palletization, the workers pack the cargo into the ULDs.
They decide which item is placed onto which ULD and where. The goal is generally to put
as much cargo as possible onto the ULDs. On overbooked flights, as few items as possible
should be left behind at the cargo terminal. Even if a flight is not fully booked, dense
packing is a goal as the remaining space can be filled with shipments booked on later
flights to the same destination that already arrived at the terminal. The workers usually
decide ad-hoc about the item placement based on their experience and the available
cargo within visual range. To get an impression of what is stackable and what is not,
the workers frequently touch and feel the items. Usually, they start with large, heavy, or
other critical items and finish with small undemanding cargo. Furthermore, they might
use dunnage material to provide an even base for further items or to protect and secure
items. During the entire build-up process, the workers have to ensure the load safety and
loading restrictions, like those stemming from dangerous goods regulations (DGR) defined
by IATA (2016). The workers are responsible for a safe and legal build-up. At the very
last, the workers close the ULDs. ULD pallets are covered with a net and lashed with
straps. Inside ULD containers the items are locked into position by straps if necessary
before the container’s doors are closed. The finished ULDs are sent to a weigh station
and stored until they are sent out to the aircraft.
In the fourth stage, denoted as weight and balance, the planners assign the assembled
ULDs to loading positions inside the aircraft. They usually apply a greedy strategy
starting to place heavy ULDs at the center of the aircraft and then moving outwards.
20
3.4 Challenges of current practice
After all ULDs have been placed, the planner might apply local modifications changing
the aircraft’s center of gravity to reduce its fuel consumption. During this manual process
the planner is supported by tools that calculate the aircraft’s performance indicators.
Tools that check the feasibility of a load plan are usually already provided by the aircraft
manufacturer. The final plan is delivered to the aircraft, where the ramp agent loads the
ULDs accordingly. He can still make final adjustments if a ULD cannot be loaded and
has to be replaced by one of the available low priority ULDs.
21
3 Air cargo load planning
Aircraft configuration
number and
Build-up scheduling
types of ULDs
loaded and
Weight and balance
weighed ULDs
Another issue in practice is that the palletization workers only see the shipments that
are present at their workstation. They continuously pack the items onto the ULDs while
further shipments are released by the build-up planners and arrive at the workstation. If
a large item arrives late, the worker might not find a suitable empty space for it although
the total volume and weight capacity of the ULD is not fully utilized. So, the large item
must be rebooked.
In the weight and balance stage, the weights of all the ULDs are already fixed. They are
a result of the palletization. As the palletization workers try to fully utilize the ULDs,
they typically build some heavy ULDs first and lighter ones later. This might result in an
unfavorable weight distribution between the ULDs. So, the weight and balance planner
might only find suboptimal solutions that consume more fuel or need more ULD reloading
operations at the stop-over airports than necessary. Both results in higher cost.
3.5 Summary
In this chapter, we provided an overview of the load planning problems faced by cargo
airlines. We introduced the three stakeholders: sales, handling, and aircraft operations,
and their objectives: maximizing revenue, minimizing physical handling effort, and min-
imizing operational cost of the flight. Furthermore, we discussed the challenges of the
currently implemented planning approaches. The identified challenges motivate the work
of this thesis and lead to our solution approaches presented in Chapters 9 and 11.
Prior to that we define the identified subproblems one by one in the next four chapters,
discuss the related literature and present a comprehensive mathematical formulation.
22
Aircraft configuration
Build-up scheduling
Palletization
4 Aircraft configuration Weight and balance
The first decision of air cargo load planning we address is what types of ULDs and their
respective amounts should be used for each transport segment of a flight. We denote this
subproblem of the ACLPP as the Aircraft Configuration Problem ACP.
As an introductory example, we consider a cargo flight from airport A to airport C with
a stop-over stop at airport B where some cargo is loaded and unloaded. The task is to
select a set of ULDs for each transport segment (A-B, A-C, B-C) of the flight, into which
the cargo can later be packed. The demand volume and weight for each segment is given
as well as the minimum required number of special ULD types like double-sized ULDs
for bulky items. The primary restriction is that on each individual flight leg (A-B, B-C)
the chosen ULDs must fit into the given aircraft. The objective is to be able to load as
much cargo of each segment as possible or, if everything can be loaded, to select the least
expensive set of ULDs.
This task becomes challenging when the aircraft can be loaded with different types of
ULDs and when multiple types of ULDs could be placed at a certain loading position in
the aircraft. Both is the case for most commercial passenger and cargo aircraft. These
aircraft typically contain multiple cargo compartments and each compartment can usually
accommodate different layouts of ULD types. However, there is normally a preferred
configuration which maxes out the aircraft volume and requires the least handling effort.
For our example, we take a McDonnell Douglas MD-11 freighter aircraft (MD11F), whose
specification can be found in Boeing (2011). Let us assume that only two ULD types
(PMC, PGE) can be loaded in the main deck and two types (PMC, AKE) in the lower
deck. Table 4.1 gives exemplary transport demands for a flight with two legs and presents
a valid aircraft configuration. Figure 4.1 visualizes the solution, i.e., the utilization of
the decks on both flight legs. In our example, we assume PMC ULDs should be used as
a default, because it is the standard ULD pallet type with the largest volume capacity.
However, there are also some over-sized items requiring the larger PGE ULD type and
items that require a closed container, like the AKE ULD.
Leg A − B Leg B − C
MD 15PMC 1* 7PMC MD 15PMC 1* 4PMC 1*
Figure 4.1: Visualization of the aircraft configuration resulting from Table 4.1. Differ-
ent colors depict the different transport segments. Striped areas represent
remaining capacity. The * marks double-sized PGE ULDs.
4 Aircraft configuration
Table 4.1: Example aircraft configuration for a flight with two legs. The “#ULDs per
segment” rows give the number of selected ULDs per compartment. The total
demand (volume, weight) is given inside the parentheses. The last two rows
give the total number of ULDs flown on each leg.
From a theoretical perspective the ACP combines two nested packing problems. The inner
problem is that enough ULDs must be reserved for each segment of the flight to cover
the cargo demand. To fully solve it, one would also need to solve the three-dimensional
packing problem that is the subject of the palletization stage presented in Chapter 6. From
the operational practice of our industrial partner we learned that this level of detail is not
necessary to find suitable aircraft configurations. Instead, a simplified one-dimensional
consideration, with respect to cargo volume and weight, seems sufficient in practice.
The outer problem is that on each leg the ULDs of all segments using this leg must fit into
the aircraft. This problem must be solved in parallel for all legs of a flight as the set of
loaded ULDs might change at each stop-over airport. We assume that each compartment’s
capacity can be described by a set of linear restrictions of the present ULD types.
In the following, we give a few examples of typical compartment combination restrictions.
In the simplest form the compartment has a number of capacity units and each ULD type
consumes a certain amount of them. On our sample aircraft the main deck has 26 units.
Here, a PMC ULD consumes one unit and a PGE ULD two units. So, the restriction can
be stated as 2|P GE| + |P M C| ≤ 26. Depending on the valid ULD combinations more
than one linear restriction might be needed to express the configuration space. Let us
assume in our example that we can choose one of the configurations shown in Figure 4.2
for the lower deck aft compartment (not all ULDs must be present). Note that the
configuration space is not convex with respect to the loadable number of ULDs per type.
Then, besides our general restrictions, |AKE| ≤ 14 and |P M C| ≤ 4, either |AKE| ≤ 4
and 16 − |AKE| ≤ 4|P M C| must hold or 14 − |AKE| ≤ 4|P M C|.
In the next section, we discuss the present literature related to the ACP followed by its
mathematical formulation in Section 4.2.
24
4.1 Related literature
1 PMC, 10 AKE
3 PMC, 4 AKE
2 PMC, 6 AKE
14 AKE
4 PMC
Figure 4.2: Exemplary ULD configurations inside a compartment. Starting on the left
with 4 PMC pallets and replacing them by AKE containers until the com-
partment is filled with 14 AKEs.
25
4 Aircraft configuration
set of ULDs for each transport segment of a flight that minimizes the total cost, i.e., the
sum of the cost of all selected ULDs plus the penalties for offloaded cargo.
We start by defining the input parameters and decision variables followed by the problem’s
constraints and objective. At last, we present a short overview of the model.
Flight parameters
• onk ⊆ L: set of flight legs of transport segment k
• startl ⊆ K: set of transport segments starting with flight leg l
Aircraft parameters
• limitf ∈ R: total ULD limit in combination restriction f
• mf,v ∈ R: factor of ULD type v in combination restriction f
ULD parameters
• availl,v ∈ N: available units of ULD type v at departure airport of leg l
• capvol
v ∈ R≥0 : volume capacity per ULD of type v
• capwgt
v ∈ R≥0 : weight capacity per ULD of type v
• costv ∈ R: handling cost per ULD of type v (preparation, loading, unloading)
Demand parameters
• demvol
k ∈ R≥0 : total volume of shipments on segment k
wgt
• demk ∈ R≥0 : total weight of shipments on segment k
• mink,v ∈ N: minimum required number of ULDs of type v on segment k
• offloadvol
k ∈ R≥0 : penalty for offloaded shipment volume on segment k
wgt
• offloadk ∈ R≥0 : penalty for offloaded shipment weight on segment k
26
4.2 The Aircraft Configuration Model
4.2.3 Constraints
In the following, we introduce the constraints that define a valid aircraft configuration. We
note that a solution to this subproblem alone does not guarantee a feasible ULD loading
since only a simplification of the three-dimensional packing constraints is considered.
Further constraints to guarantee the feasibility will be added in Chapter 6.
Capacity reservation For each transport segment k the capacity of the selected ULDs
must be large enough to accommodate the transported shipments by volume and weight.
The transported amount is the difference of the demand and the offloaded shipments:
Combination restrictions On each flight leg l the ULDs of all present segments must
add up to a valid aircraft configuration. We model the valid configurations implicitly by
the allowed ULD type combinations. The given restrictions F are organized in groups.
Similar to a logic formula given in conjunctive normal form, for all groups G ∈ F at least
one restriction f ∈ G must hold. Thereby, alternative non-convex combinations can be
modeled. Each restriction f represents a valid linear combination of ULDs, which can
be loaded into the aircraft. Each ULD type v is weighted by a parameter mf,v and the
sum is limited by parameter limitf . Furthermore, we introduce an auxiliary variable bl,f
indicating if restriction f is fulfilled on leg l and make sure that at least one bl,f equals 1
for each group:
X X
mf,v xk,v ≤ limitf + (1 − bl,f )M l ∈ L; G ∈ F ; f ∈ G (4.3)
k∈K:l∈onk v∈V
X
bl,f ≥ 1 l ∈ L; G ∈ F (4.4)
f ∈G
Required ULD types For each segment some ULDs of certain types might be required
to load special cargo. In practice this requirement arises when very large, heavy or fragile
items are among the shipments. Large items might require a larger ULD type, heavy
items a ULD type with a reinforced floor area, or fragile items should only be loaded into
a closed ULD container. Another source of required ULD types is that in practice cargo
might already be loaded on a ULD and this ULD should be used for further build-up.
All these requirements can be precalculated and the number of the respective ULD types
limited accordingly:
Airport ULD type limits The airline might not have an unlimited supply of all ULD
types at all departure airports. Therefore, we need to respect the availability limits for
27
4 Aircraft configuration
ULDs that should be build-up at an airport. This restriction applies only to transport
segments whose first leg starts at the given airport:
X
xk,v ≤ availl,v l ∈ L; v ∈ V (4.6)
k∈K:k∈startl
4.2.4 Objective
While satisfying all the given constraints, we want to load as much cargo as possible
and choose the least expensive set of ULDs for it. The parameter costv for ULD type v
represents the fixed handling cost for build-up and break-down, the transport to and from
the aircraft, the loading into and out of the aircraft, as well as the wear and tear of the
wgt
ULD itself. The penalty for offloaded volume offloadvol k and weight offloadk comprises
the lost revenues and the impact on customer satisfaction for shipments on segment
k. The penalties can only be estimated, but reasonable values can be chosen based
on the segment’s travel distance or the effective delay of offloaded shipments based on the
frequency at which the airline serves this route.
Thus, the objective is to minimize the total cost:
!
ykwgt offloadwgt + ykvol offloadvol
X X
minimize k k + xk,v costv (4.7)
k∈K v∈V
Note that this formulation can tackle both bin packing and knapsack style problems. If
there is little demand the number of ULDs is reduced. If the demand exceeds the aircraft
capacity the least important cargo is offloaded.
!
ykwgt offloadwgt ykvol offloadvol
X X
minimize xk,v costv + k + k (4.8)
k∈K v∈V
subject to
28
4.3 Summary
X
availl,v ≥ xk,v l ∈ L; v ∈ V (4.14)
k∈K:k∈startl
xk,v ∈ N k ∈ K; v ∈ V (4.15)
ykwgt , ykvol∈ R≥0 k∈K (4.16)
bl,f ∈ {0, 1} l ∈ L; G ∈ F (4.17)
The objective, given in Equation (4.8), is to minimize the total cost from the used ULDs
and offloaded cargo. Equation (9.3) and (9.4) model the capacity reservation, Equa-
tions (9.5) and (9.6) the ULD combination restrictions, Equation (9.7) the minimum
required ULDs, and Equation (9.8) the airport ULD type limit.
4.3 Summary
In this chapter, we introduced the Aircraft Configuration Problem (ACP) in detail, which
is to decide what ULD types and amounts should be selected for each transport segment.
Furthermore, we analyzed the related literature and presented a formal model, denoted
as Aircraft Configuration Model (ACM), of its features.
The literature containing aspects of aircraft configuration from a load planning perspec-
tive is very scarce. In most works on aircraft loading, only a single configuration is
considered or only one ULD type can be placed on each loading position. In both cases
the problem becomes much easier, but significant parts of the configuration space of a
typical cargo aircraft are not covered. Aspects of aircraft configuration have also been
present in papers dealing with weight and balance. Here, the ULDs are already built and
weighed. Therefore, only one part of the problem remains, which is to combine different
ULD types into the compartments.
The presented model contains two nested packing problems. The inner is a vector packing
problem, with respect to weight and volume, that assigns demand to ULDs. The outer
matches the ULDs to aircraft compartments and fulfills aircraft specific loading restric-
tions. The overall objective is to minimize the costs from offloaded demand and used
ULDs.
29
Aircraft configuration
Build-up scheduling
Palletization
5 Build-up scheduling Weight and balance
The second step of air cargo load planning we discuss is to decide when to actually pack
the cargo into ULDs. We denote this subproblem of the ACLPP as the BSP.
Throughout the day an air cargo terminal handles many outgoing flights. All these
flights compete for the same scarce build-up resources, namely workstations and workers.
Therefore, some planning is needed to build-up all ULDs on time. As speed is a major
sales argument for air cargo, shipment itineraries often only have a short transfer time
between their incoming and outgoing flight. So, part of the cargo only becomes physically
available for the build-up shortly before its outgoing flight. Therefore, we need to take
the cargo arrivals into account to decide when to pack cargo into ULDs.
As shown in Figure 2.5, cargo arrives at the terminal in two ways. Either it is dropped at
the export point by the shipper or his forwarder, or it arrives on an inbound flight. On
both ways the arrival times are usually predictable. If a time window management system
is used at the export point, a rough handover time is known. Similarly, the arrival time
of an inbound flight is known and even unlikely to change during the last hours when it
is already on its way.
On the other end, the built ULDs need to be transported to the aircraft on time. At
major airports, where the distance between terminal and aircraft can be quite long, this
ready-for-delivery due date might be an hour or more ahead of departure. Within the
window of item arrivals and ULD due dates the ULDs have to be built.
For economic reasons, there is usually only a limited capacity of workstations and workers
available at the terminal. Both should be used evenly over time to limit stress and provide
flexibility. During outbound rush hours the build-up capacity is usually too low to handle
all outgoing ULDs. For example Figure 5.1 sketches the total outbound capacity of the
Lufthansa Cargo Hub in Frankfurt during one day. There is a peak at noon where more
than 15 percent of the day’s capacity departs within one hour. Under the assumption of
a constant build-up rate, the workload of the peak hour alone takes nearly four hours.
Accordingly, some ULDs have to be built earlier than their due date. But, packing ULDs
before all shipments arrived leaves fewer options in combining items. In a previous study
we have shown that the best possible bin utilization reduces if a part of the items arrives
after the first bins are built (Brandt et al., 2014). The study considered one-dimensional
packing only. We measured a loss of utilization if less than 70 percent of the remaining
cargo volume was available on average when a bin is built. For each 10 percent less
available cargo the best possible utilization reduced by around 1 percent. To give an
example, we would expect a loss of 3 percent in utilization if on average only 40 percent
of the cargo is available at each build-up. We note that the study only considered one-
dimensional packing. The effects for three-dimensional packing will presumably be larger.
5 Build-up scheduling
100 200 300 400 500
outgoing cargo [t]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
time [h]
Figure 5.1: Hourly cargo capacity of Lufthansa Cargo out of Frankfurt on 21.10.2016
So, one scheduling objective is to minimize the earliness of the build-up to be able to pack
as much cargo as possible. The later a ULD is planned for build-up the more shipments
are available and more item combinations are possible. Further objectives are to use as
few workstations as possible or to reduce the peak worker demand. We note that the exact
build-up schedule is typically determined only a few hours before the flights. Therefore,
the number of available workers and workstations is essentially fixed. But, using less
workstations or workers can provide flexibility throughout the day to react to delays or
other disruptions.
The BSP requirements comprise scheduling and organizational rules. Building a ULD
requires a compatible workstation and a crew of workers. Each workstation and crew can
only process one ULD at a time. Each ULD has to be build-up before its due date or
must not be scheduled. We expect that a suitable number of workstations and workers
was predetermined by tactical planning out of scope of this work.
From a theoretical perspective the BSP is a Multi-Resource Job Shop Scheduling Problem
with the objective of minimizing the total job earliness.
In the next section, we discuss literature related to the BSP followed by a mathematical
formulation of the problem in Section 5.2.
32
5.2 The Build-up Scheduling Model
2008a). Both previous works are also published as Yan et al. (2006a) and Yan et al.
(2008b) with negligible changes.
Nobert and Roy (1998) present a MIP model to select shift patterns and determine the
amount of workers for a typical day. Their goal is to minimize the total shift cost. The
total handling demand is given as a matrix of cargo arrivals and their corresponding
departures for each period. Rong and Grunow (2009) present a similar model but also
schedule the amount of cargo of each individual flight in the break-down and build-up for
each period.
Both models do not consider individual ULDs or workstations. Instead they only limit
the total handling capacity across all flights for each time slot. While this seems fine to
estimate the total workforce demand, it is not sufficient to plan ULD build-ups. In our
case both approaches might lead to undesired solutions where many ULDs are partially
built in each period. In reality, this would lead to many started ULDs blocking the
workstations for several periods before they can be finished. Furthermore, both papers
do not aim at a particular early or late build-up.
For further reading, we refer to a recent review of publications concerning air cargo ter-
minal operations which is given by Feng et al. (2015).
Segment parameters
• availvol
k,t ∈ R≥0 : cargo volume of segment k arriving up to period t
• demvol
k ∈ R≥0 : total cargo volume on segment k
33
5 Build-up scheduling
ULD parameters
• durv ∈ N: number of periods to build a ULD of type v
• capvol
v ∈ R≥0 : volume capacity per ULD of type v
Capacity parameters
• costs ∈ R≥0 : cost of one build-up crew in shift s
• ends ∈ T : last period after shift s
• maxs ∈ N: maximum available build-up crews in shift s
• openv,t ∈ N: number of workstations that can handle ULD type v during period t
• starts ∈ T : first period of shift s
5.2.3 Constraints
In the following we define the constraints that define a feasible build-up schedule.
Schedule ULDs All requested ULDs have to be scheduled to a period before the due
date or marked as offloaded.
X
start k,v,t = uldk,v − offload k,v k ∈ K; v ∈ V (5.1)
t∈T :
t≤duek −durv
34
5.2 The Build-up Scheduling Model
Unused cargo capacity Only physically available cargo can be packed onto a ULD. If
a ULD is scheduled before enough cargo is available, some space in the ULD will be lost.
We add this constraint to determine the amount of lost volume dead k,t of scheduled ULDs
for segment k during period t.
We introduce an auxiliary variable pack k,t to represent the packed amount of cargo of
segment k until period t, and derive it from the previous period t − 1 as:
We restrict the packed amount of cargo at a period t by the available cargo volume availvol
k,t
during that period:
Parallel build-ups There is no technical reason to restrict the number of ULDs that are
built in parallel for a segment. However, in practice there might occur problems during
a build-up when an item cannot be packed onto the planned ULD. In this case, the load
planner has to find another ULD with enough remaining capacity under massive time
pressure. The more ULDs that are not started yet, the more options and time he has
for replanning. Furthermore, if only a few ULDs for a segment are built in parallel, they
can be assigned to spatially close workstations. This might reduce transport distances
and improve overview during build-up. We note that, during a period t, the ULDs that
were started during period (t − durv + 1) to period t are still work in progress. For each
segment k we limit the number of simultaneously built ULDs by splitk as:
X X
start k,v,t0 ≤ splitk k ∈ K; t ∈ T (5.5)
v∈V t0 ∈T :
t−durv <t0 ≤t
Workforce capacity Similar to the workstation limit, we limit the total number of all
ULDs that can simultaneously be processed by the available build-up crews during each
period.
X X X X
start k,v,t0 ≤ crews s t∈T (5.7)
k∈K v∈V t0 ∈T : s∈S:
t−durv <t0 ≤t starts ≤t<ends
35
5 Build-up scheduling
5.2.4 Objective
While satisfying all the given constraints, we want to load as much cargo as possible and
release not required build-up crews for short-term dispatch. To maximize the load, we
minimize the cost of lost capacity. We sum up the lost capacity of ULDs that are not
scheduled offload k,v and where not enough cargo is available dead k,t . At last, we add the
cost of the selected crews crews s . In short-term planning this is probably not the real cost
but the expected profit of having spare crews.
!
losscost capvol
X X X X
minimize k dead k,t + v offload k,v + costs crews s (5.8)
k∈K t∈T v∈V s∈S
!
offloadvol capvol
X X X X
minimize k dead k,t + v offload k,v + costs crews s (5.9)
k∈K t∈T v∈V s∈S
subject to
X
uldk,v = offload k,v + start k,v,t k ∈ K; v ∈ V (5.10)
t∈T :
t≤duek −durv
The objective, given in Equation (5.9), is to minimize the sum of the cost of the lost
profit due to early build-ups or unscheduled ULDs and the cost of the deployed crews.
36
5.3 Summary
Equation (5.10) models the ULD scheduling, Equations (5.11) to (5.13) the unused cargo
capacity, Equation (9.20) the parallel build-ups, Equation (9.21) the workstation avail-
ability, and Equation (9.22) the workforce capacity.
5.3 Summary
In this chapter, we introduced the Build-up Scheduling Problem (BSP) in detail, which is
to find a feasible and cost-efficient schedule for the assembly of the ULDs of all outgoing
flights in a given time horizon. Furthermore, we analyzed the related literature and
presented a formal model, denoted as Build-up Scheduling Model (BSM), of its features.
Build-up scheduling itself has not been dealt with in the literature. The closest publica-
tions cover the shift design and workforce planning for build-up operations in air cargo
terminals where no individual ULDs are considered.
The presented model comprises a typical job-shop scheduling, with the extension that up
to any point in time no more cargo of a flight can be built than is physically available at
the terminal. The overall objective is to maximize the amount of ULD capacity scheduled
on time, i.e., before the respective flight’s departure time, with as few build-up crews as
possible.
37
Aircraft configuration
Build-up scheduling
Palletization
6 Air cargo palletization Weight and balance
The most prominent part of air cargo load planning is to decide how the items are ar-
ranged inside the ULDs. Technically the task to solve is a three-dimensional container
loading problem with a multitude of constraints stemming from physical, regulatory, and
operational requirements.
The objective is to load as much cargo as possible while keeping the necessary physical
handling effort low. In practice the palletization determines the handling efforts for both
build-up and the corresponding break-down at the destination. During build-up complex
three-dimensional arrangement patterns increase the effort. At the break-down additional
effort results from the consolidation of shipments that have been split across multiple
ULDs or the separation of shipments on one ULD but with diverging ongoing processes.
Physical requirements contain typical volume constraints: items have to be fully inside
the ULD contours and are not allowed to intersect. Furthermore, items might only be
placed in certain orientations. Finally, if items need to be stacked on top of each other
the load-bearing strength of the lower item and a stable placement of the upper item have
to be satisfied.
Regulatory requirements comprise rules for the handling of dangerous goods (DGR) or
for clearing customs. DGR rules as defined by IATA (2016) typically state that certain
types of substances must not be placed on the same ULD or within proximity, for ex-
ample, chemicals that easily react with each other. Loading positions for items might
be restricted. For instance, only low dense cargo is allowed right behind the cockpit or
radio-active materials must be placed on the floor where they are farthest away from any
passenger. Furthermore, the total net weight of certain substances, such as explosives or
dry ice, inside all the loaded items might be limited per compartment for safety reasons.
Finally, in some countries customs regulations require that all items of a shipment must
arrive with the same flight, effectively creating an all or nothing rule for the airline.
Operational requirements mostly align the palletization result with the neighboring pro-
cess steps. Items need to be assigned to a ULD that is scheduled for build-up after the
item arrives at the terminal. Furthermore, the weight limits of the ULD type and the
weight distribution limits inside each ULD must be respected, to allow easy and error free
aircraft loading.
We define the APP as the subproblem of the ACLPP to decide about the assignment of
items to ULDs and the positioning of the items therein. In our APP model, each flight
and segment is considered independently since all interdependencies with respect to time
and ULD types are considered in the previous subproblems. Afterwards, the built ULDs
of all segments of a flight can be combined for upcoming planning steps. This means all
items put into a ULD will join and leave the flight at the same airport. Thereby, any
6 Air cargo palletization
multi-drop restriction is postponed to the weight and balance step, which we present in
Chapter 7. The input parameters of the APP are the item and ULD attributes as well
as a set of palletization rules. We refrain from modeling logically similar domain specific
rules, like net weights or sorting constraints, individually. Instead we present them in an
abstract format that can be instantiated as needed.
In the next section, we discuss literature related to the APP followed by a mathematical
formulation of the problem in Section 6.2.
40
6.1 Related literature
Weight limits
Weight distr.
Orientation
Availability
Grouping
Stability
Stacking
First author Year Objective
Techanitisawad 2004 X - X - X X - 1. min cost, 2. max load
Chan 2006 X X X X X - - 1. min cost, 2. max load
Lin 2006 X - X X - X - min cost - load + effort
Ceschia 2011 X - X X - X - min cost - load - free space
Paquay 2014 X - X X X X - min unused ULD volume
Hong Ha 2016 - - - X - - X min unused ULD volume
Table 6.1: Recent literature on feature-rich container loading problems addressing mul-
tiple aspects present in the APP. The columns show the considered features
and objective. Technical constraints like non-overlapping and placement in-
side container, which are present in all the papers, are not shown. We also
omit those of the constraints mentioned by Bischoff and Ratcliff (1995) that
are not considered by any of the papers above, e.g., positioning, separation, or
complexity constraints.
and then use heuristics to pack each bin with respect to the covered constraints. Ceschia
and Schaerf (2013) present a local search procedure and a fast wall-building heuristic to
evaluate the updated bins.
The literature regarding feature-rich problems in an air cargo context is even more scarce.
The main distinction here is that the approaches must be able to deal with irregular
shaped containers. Chan et al. (2006) present a two-stage approach. In the first phase,
they solve a MIP model to select a promising set of ULDs. In the second step, they
apply a heuristic that loads the items in descending priority while keeping track of empty
spaces. If no more items can be loaded, the procedure is repeated for the remaining
items. The approach considers only five of the twelve aspects introduced by Bischoff and
Ratcliff (1995), namely: orientation, grouping items, physical stability, weight limits, and
weight distribution. The procedure is evaluated on instances with up to 671 items of
around 50 different formats from a forwarding company. No runtimes are reported but
the authors state that the heuristic can place between 20-100 items per minute.
The work of Paquay et al. (2016) introduces a MIP model with a detailed mathematical
definition of the considered constraints: orientation, fragility (a binary version of a stack-
ing constraint), physical stability, weight limits, and weight distribution. However, only
small instances with up to 12 items can be solved in a reasonable amount of time.
Hong Ha and Nananukul (2016) also present a MIP model for ULD packing from a for-
warders perspective. Their model incorporates item release dates and only items of similar
dates can be placed on the same ULD. The model is evaluated on one box-shaped ULD
type and solved successfully for instances with 15 items. To be able to solve larger in-
41
6 Air cargo palletization
stances the authors relax the three-dimensional constraints and instead cap the maximum
volume utilization of the ULDs. The three-dimensional packing is then solved for each
ULD in a separate postprocessing step. If no feasible solution is found for a ULD, the
main MIP model is solved again with a reduced utilization cap.
Some more papers deal with palletization problems from a forwarders view: Wu (2008)
presents a MIP model and Lau et al. (2009) a genetic algorithm to select ULDs and assign
items to them. However, they do not consider practical constraints. Both papers aim to
minimize the rental and transport fees of the built ULDs.
Moreover, there exist papers considering packing problems in air cargo in the military do-
main like Heidelberg et al. (1998), Guéret et al. (2003), and Nance et al. (2011). However,
these problems are fundamentally different because the loaded cargo is homogeneous or
is not placed on ULDs such as trucks or large machinery, which are loaded directly.
To sum up, there is a large number of publications regarding container loading and the
majority of practical constraints is known. But, all the works are missing important
aspects of our problem at hand and only cover parts of the constraints. We give an
overview of the mentioned papers, their covered features and objectives in Table 6.1.
42
6.2 The Air Cargo Palletization Model
• To facilitate fine-grained item sorting, we add soft allocation constraints that can
be seen from two perspectives. On the one hand, we want to split a group of items
across as few ULDs as possible. On the other hand, we want to load only few
different groups of items into a ULD.
We start by defining the input parameters and decision variables followed by the problem’s
constraints and objective. At last, we present a short overview of the model.
6.2.1 Parameters
The APM primarily contains two sets of entities, items I and ULDs U , and considers a
time horizon t. To describe the constraints we introduce another three sets of entities:
• Rotations R: We consider only orthogonal item rotations. Each rotation is de-
scribed by its permutation of item dimensions. Accordingly, there are six possible
rotations: R = {XYZ, XZY, YXZ, YZX, ZXY, ZYX}. XYZ is the original item rota-
tion. For example, rotation ZYX represents a turn by 90 degrees around the y-axis.
In this case the item’s z-axis corresponds to the bin’s x-axis and vice versa.
• Sorting criteria Q: During palletization we want to group or separate certain
items. For example items of the same shipment should be grouped together, while
express items should be kept separate from standard items. Each sorting criterion
describes such a constraint to group or separate by. For each criterion q ∈ Q let Qq
denote the union of groups all the considered items belong to.
• Weight categories G: Besides the gross weight of each item we need to consider
the net weight of certain substances inside the items. Each considered substance
like dry ice or explosives represents a weight category.
In the following we use the respective lower case indices to represent single entities: g ∈ G,
i, j ∈ I, u ∈ U , q ∈ Q, r ∈ R, t ∈ T .
Item parameters
• A ⊆ I × I: pairs of items that are not allowed within one ULD (hi, ji ∈ A)
• availi ∈ T : first period that item i is physically available for build-up
• cliquei ∈ I: item that must be loaded iff item i is loaded
• dimxi , dimyi , dimzi ∈ R≥0 : dimensions of item i
• disti,j ∈ R≥0 : minimum required distance between items i and j
• offloadi ∈ R≥0 : penalty when item i is offloaded
• roti ⊆ R: allowed rotations of item i
• sortq,i ∈ Qq : group of item i for sorting criterion q
• suppi ∈ [0, 1]: minimum required supported floor area of item i (ratio)
• stackxi , stackyi , stackzi ∈ R≥0 : maximum load-bearing strength of item i
• Ui ⊆ U : ULDs that item i can be loaded into
• weightgrsi ∈ R≥0 : gross weight of item i
• weightnetg,i ∈ R≥0 : net weight of item i for weight category g
43
6 Air cargo palletization
• xac ac ac ac ac ac
i , xi , yi , yi , zi , zi ∈ R: bounding box of the position of item i inside the aircraft
x uld
• ← ←
−uld y uld , ←−uld z uld , ←−uld
− u,i , x u,i , ←
−u,i y u,i , ←−u,i z u,i ∈ R: box of the start position of item i in ULD u
x uld
• → → − uld z uld , →
− uld y uld , → − uld
− − u,i y u,i , →
u,i , x u,i , → − u,i z u,i ∈ R: box of the end position of item i in ULD u
ULD parameters
• Cu : set of contour planes of ULD u in Hesse normal form (hx, y, z, ai ∈ Cu )
• limitu ∈ R≥0 : gross weight limit of ULD u
• startu ∈ T : Period the ULD u is scheduled for build-up
• startxu , startyu , startzu ∈ R: starting coordinate of ULD u
• udimzu , udimyu , udimxu ∈ R≥0 : dimensions of ULD u
• xcg cg cg cg cg cg
u , xu , yu , yu , zu , zu ∈ R: box of the valid CG of ULD u
Sorting parameters
• penaltyq ∈ R≥0 : linear penalty for sorting errors of criterion q
• powq ∈ N: exponential penalty for sorting errors of criterion q
• Qitem ⊆ Q: sorting criteria to group items by
• Quld ⊆ Q: sorting criteria to separate items by
6.2.3 Constraints
In the following we define the constraints that describe a valid packing of items into the
ULDs. We note that a solution to this subproblem alone does not guarantee that all
44
6.2 The Air Cargo Palletization Model
planned ULDs can be loaded into the aircraft. Further constraints regarding the aircraft
loading are presented in Chapter 7. Along the upcoming constraints further auxiliary
variables are defined that are only relevant inside the defining constraint.
ULD assignment Each item i needs either be assigned to a compatible ULD from the
set Ui or marked as offloaded:
assign off
X
i + assign u,i = 1 i∈I (6.1)
u∈Ui
Item orientation and size The rotation of each item determines the effective size of
the item in each dimension. Therefore, we combine the calculation of the start and end
coordinates of each item with the determination of its rotation. To describe the rotation
of item i, we use a 3 × 3 rotation matrix ri of auxiliary binary decision variables. The
following examples show such a matrix representing the original item orientation XYZ
and a horizontal rotation around the y-axis ZYX:
1 0 0 0 0 1
XYZ = 0 1 0
ZYX = 0 1 0
(6.2)
0 0 1 1 0 0
By using the coordinates of the front left bottom corner (xi , yi , zi ) of item i, its dimensions
(dimxi , dimyi , dimzi ) and the rotation matrix of the item, we calculate the coordinates of
the rear right top corner (x0i , yi0 , zi0 ) of item i as follows:
ri11 ri12 ri13 dimxi x0i
xi
21 22 23 y 0
yi + ri ri ri dimi = yi i∈I (6.3)
zi ri ri32 ri33
31
dimzi zi0
To give a complete example, let us assume item i has orientation ZYX. Then, the item
dimensions along the x- and z-axis are flipped and the rear right top corner is calculated
as follows:
dimxi dimxi xi + dimzi x0i
xi xi 0 0 1
y y y 0
yi + ZY X dimi = yi + 0 1 0 dimi = yi + dimi = yi (6.4)
The matrix only contains a valid orthogonal rotation if each row and column of the matrix
contains exactly one 1. Accordingly, we add the following constraints for each row and
column:
3
riab = 1
X
i ∈ I; a ∈ {1, 2, 3} (6.5)
b=1
3
riab = 1
X
i ∈ I; b ∈ {1, 2, 3} (6.6)
a=1
Finally, we restrict the rotation matrix to rotations that are explicitly allowed for item i:
/ roti ⇒ ri11 + ri22 + ri33 ≤ 1
XYZ ∈ i∈I (6.7)
45
6 Air cargo palletization
y startxu + udimxu
y
startyu + udimu
startzu + udimzu
c1 ∈ C u
startxu
x
startyu
c2 ∈ C u
startzu
Figure 6.1: Modeling of irregular shaped bins: The bounding box of the bin is given by
its start (start∗u ) and end (start∗u + dim∗u ) coordinates. The two planes c1 and
c2 describe the contour. All items must be placed inside the gray region.
XZY ∈
/ roti ⇒ ri11 + ri23 + ri32 ≤1 i∈I (6.8)
YXZ ∈
/ roti ⇒ ri12 + ri21 + ri33 ≤1 i∈I (6.9)
ZXY ∈
/ roti ⇒ ri13 + ri21 + ri32 ≤1 i∈I (6.10)
YZX ∈
/ roti ⇒ ri12 + ri23 + ri31 ≤1 i∈I (6.11)
ZYX ∈
/ roti ⇒ ri13 + ri22 + ri31 ≤1 i∈I (6.12)
Item position inside ULD Each loaded item i must be positioned fully inside its assigned
ULD u. Note that we use a single coordinate system for all ULDs. This allows us to easily
state positioning and segregation constraints within the whole aircraft:
assign u,i ⇒ startxu ≤ xi i ∈ I; u ∈ U (6.13)
assign u,i ⇒ startyu ≤ yi i ∈ I; u ∈ U (6.14)
assign u,i ⇒ startzu ≤ zi i ∈ I; u ∈ U (6.15)
assign u,i ⇒ x0i ≤ startxu + udimxu i ∈ I; u ∈ U (6.16)
assign u,i ⇒ yi0 ≤ startyu + udimyu i ∈ I; u ∈ U (6.17)
assign u,i ⇒ zi0 ≤ startzu + udimzu i ∈ I; u ∈ U (6.18)
Besides the orthogonal bounding box of the ULD, many ULD types have a convex con-
toured shape inside which the items must be placed. This shape is defined by the aircraft
fuselage. Examples of ULD types were given in Figure 2.3. We describe such shapes as a
set of planes as shown in Figure 6.1. Inside the bounding box of the ULD the intersection
of the lower half spaces of these planes defines the feasible region in which items have to
be placed. Accordingly, for each item i placed in ULD u we check that it is fully below
each plane from Cu . For each plane hx, y, z, ai ∈ Cu we only need to check the corner of
the item that is closest to the plane when the item is in the feasible region. We determine
the coordinates (x̃, ỹ, z̃) of the closest corner as follows:
( ( (
xi if x ≤ 0 yi if y ≤ 0 zi if z ≤ 0
x̃ = ỹ = z̃ = (6.19)
x0i else yi0 else zi0 else
46
6.2 The Air Cargo Palletization Model
The following constraint ensures that the item is placed in the feasible region:
xx̃ + yỹ + zz̃ ≤ a (6.20)
Item non-overlapping If two items i, j are loaded, then their positions must not overlap.
Note that this constraint is independent of the assigned ULD because all ULDs share the
same coordinate system in our model. We describe the position of item i by its front left
bottom corner (xi , yi , zi ) and its rear right top corner (x0i , yi0 , zi0 ). The two items i, j do
not overlap with respect to a certain dimension if i is either in front of j (x0i ≤ xj ) for
dimension x or behind j (x0j ≤ xi ). In three-dimensional space items do not overlap if
they do not overlap in any dimension. Accordingly, we formulate the following constraint:
x0i ≤ xj ∨ x0j ≤ xi ∨
zi0 ≤ zj ∨ zj0 ≤ zi
Item availability Each item i can only be assigned to a ULD u whose build-up period
startu is not before the item arrival time availi . For transferred items, availi can be
determined by the inbound connection plus a suitable transfer time. For items delivered
to the terminal by the customer the parameter can be derived from the agreed hand-over
time.
availi assign u,i ≤ startu u ∈ U; i ∈ I (6.22)
ULD weight limit For each ULD u the sum of the item gross weights weightgrs i of all
items placed on the ULD is limited. We expect that the weight limit limitu is already
adjusted to allow for the weight of the ULD itself, the weight of the covering net and
straps, the weight of possibly necessary additional loading devices like wooden boards, as
well as a suitable tolerance. We calculate the total weight of the ULD as weight u and will
reuse it in the upcoming weight distribution constraint.
weightgrs
X
i assign u,i = weight u u∈U (6.23)
i∈I
weight u ≤ limitu u∈U (6.24)
Net weight limits Besides the gross weight of each item, some items may contain sub-
stances (dry ice, radiation, chemicals, explosives) whose total sum needs to be limited
within a subset of ULDs, typically all ULDs that will be put into the same compartment
of the aircraft, for safety reasons.
We denote the set of restricted substances as G and the constraints related to substance
g ∈ G as Dg . For each constraint d ∈ Dg the subset of ULDs in which the substance must
be limited is given as uldsd . The weight limit itself is given as limitnet
d . We denote the
net weight of substance g inside item i as weightnet
g,i . The loaded net weights can now be
restricted as follows:
weightnet net
X X
g,i assign u,i ≤ limitd g ∈ G; d ∈ Dg (6.25)
u∈uldsd i∈I
47
6 Air cargo palletization
ULD weight distribution For safety reasons, the items must be packed in a way such
that the center of gravity (CG) of each ULD u is within a defined bounding box. We
denote the coordinates of the front left bottom corner of this bounding box as (xcg cg cg
u , yu , zu )
cg cg cg
and the rear right top corner as (xu , yu , zu ). As a simplification, we assume that the CG
of each item is at its geometric center. In dimension x, for example, this geometric center
can be calculated as (xi + x0i )/2. To determine the CG of a set of items for a dimension
we calculate the weighted sum of their geometric centers. Accordingly, for dimension x
the CG can be calculated as:
weightgrs xi + x0i
! !
i
X
(6.26)
i total weight 2
To limit the weight distribution inside the ULD u, we restrict the CG for each dimension
to stay within the defined bounding box (xcg cg cg cg cg cg
u , yu , zu ) − (xu , yu , zu ). Only items loaded
into the ULD u need to be considered which is indicated by variable assign u,i . From the
ULD weight limit constraint we know the total weight of the loaded items weight u . The
CG can now be restricted for each dimension as follows:
1
xcg weightgrs 0 cg
X
u ≤ i (xi + xi ) assign u,i ≤ xu u∈U (6.27)
2weight u i∈I
1
ycg weightgrs 0 cg
X
u ≤ i (yi + yi ) assign u,i ≤ yu u∈U (6.28)
2weight u i∈I
1
zcg weightgrs 0 cg
X
u ≤ i (zi + zi ) assign u,i ≤ zu u∈U (6.29)
2weight u i∈I
Stacking When loading multiple items into the same ULD, some items might have to
be stacked on top of others. As most items carry significant weight and the load-bearing
strength of each item is limited, we need to properly restrict the stacking in our model.
Modeling exact stacking constraints is hard for two reasons. First, modeling the dynamics
between stacked items is usually done via finite element simulations. Integrating such a
simulation into any optimization model would most probably render it impossible to solve.
Second, the real load-bearing strength of each item is seldom known, it depends on where
the forces act, at the center or along the edges, and it cannot easily be determined without
breaking the item.
Therefore, we model a simplified stacking constraint that considers only vertical forces
and no torque. We assume that an item’s weight is equally distributed across its volume
and that the load-bearing strength is the same all across the top surface. Each item passes
its weight onto the items below proportional to their overlapping area. The item below
adds the received weight to its own weight and again passes the sum to the items below.
This way, we can calculate the stress, i.e., the weight per area unit, transferred between
two items and limit it to an acceptable level.
Figure 6.2 gives an example how the stacking restriction works. There are four items with
different weights (A: 100 kg, B: 500 kg, C: 600 kg, D: 1,000 kg). Item A has no items on
top, so its total weight is 100 kg. It passes its weight to item B resulting in a pressure of
50 kg · m−1 at the contact area. The total weight of item B is 600 kg, the weight received
48
6.2 The Air Cargo Palletization Model
y
A: 100 kg
(100 kg) 50 kg/m
B: 500 kg
(600 kg) 200 kg/m
C: 600 kg D: 1,000 kg
400 kg/m (800 kg) (1,400 kg) 700 kg/m
0 1 2 3 4 x
Figure 6.2: Illustration of the stacking model: The item weight is passed to the supporting
items. Numbers in braces show the effective item weight including all weight
stacked on top of it. Arcs show the respective stress at the contact areas.
from A plus B’s own weight. Item B distributes its total weight onto items C and D
proportionally to their contact areas, i.e., 200 kg onto item C and 400 kg onto item D.
There are other concepts in the literature to model stacking restrictions. A model where
items are tagged as fragile or non-fragile, and non-fragile items are not allowed on top
of fragile ones is given by Fuellerer et al. (2010). In a similar approach Egeblad et al.
(2010) only allow lighter items to be stacked on top of heavier ones. For the strongly
heterogeneous items seen in air cargo these models do not fit well, because none of them
limits the total weight that is allowed to be put onto a certain item. A similar model to
ours, where stress is transferred between the items is presented by Junqueira et al. (2012).
However, the authors discretize the three-dimensional space, which limits their approach
to small instances. Furthermore, they require that all items are fully supported. As ULDs
on the lower deck of aircraft have to contain overhanging items to fill the loading space,
this limitation is not acceptable in an air cargo environment.
To model the stacking restrictions, we describe a constraint to calculate the horizontal
overlap between stacked items. Then, we model the transfer of weight between the over-
lapping items. Finally, we derive the stress at the contact areas from the overlap and
transferred weights and limit the stress to the allowed level. The maximum allowed stress
for item i is given for each dimension as stackxi , stackyi , and stackzi . We choose the limiting
parameter depending on the item rotation.
As a new feature, we add a tolerance parameter to our stacking constraint. In practice
larger items are often stacked on top of multiple other items, which are placed next to
each other but are not exactly the same height. This is feasible because most packagings
are a bit flexible. They will deform or compress a little, such that weight can be equally
distributed between the stacked items. Optionally, a worker could fill the gap with dun-
nage material like a wooden board. Therefore, we accept height differences within the
tolerance for this constraint. A similar idea was introduced in Egeblad et al. (2010), where
the maximum height difference of the supporting items was limited. However, this was
only checked a-posteriori and the size of the supporting area was not considered at all.
First, we calculate the overlapping lengths oxi,j and ozi,j between a lower item i and upper
item j in both horizontal dimensions x and z. We consider i and j as overlapping if they
are both loaded and less than the tolerance apart in vertical dimension. As all ULDs
in our model use the same coordinate system, we do not need to care about the assigned
49
6 Air cargo palletization
From the overlaps we calculate the total supported area oj of each item j as follows. We
note that this formulation is non-linear, making this part of the problem intractable for
plain LP solving.
oxi,j ozi,j
X
oj = j∈I (6.32)
i∈I
We now model the transfer of weight from upper items j to lower item i. Even if the upper
item is not fully supported, our formulation ensures that all the weight of an upper item
is transferred to the items below it. We introduce an auxiliary variable wi representing
the total weight of item i, which is the sum of the weight of the lower item i plus the
weight transferred to it by items above.
X oxi,j ozi,j
wi = weightgrs
i + wj i∈I (6.33)
j∈I oj
Finally, we restrict the stress of an upper item j onto lower item i by the load-bearing
strength of the vertical orientation of item i. To detect the vertical orientation we reuse
auxiliary variables ri2∗ from the rotation matrix of the item orientation constraint. We
determine the stress at the contact area by the total weight and the total supported area
of the item above.
wj
oxi,j ozi,j > 0 ⇒ ri21 stackxi + ri22 stackyi + ri23 stackzi ≥ i, j ∈ I (6.34)
oj
50
6.2 The Air Cargo Palletization Model
Item sorting Besides the requirement to load only complete shipments, airlines also
want to spread a shipment with multiple items across as few ULDs as possible. This
decreases the risk of disruptions, e.g., if a ULD does not catch its flight, and reduces the
handling effort to consolidate the shipment again at the destination. In practice there
are even more reasons to reduce the spread of a set of items across ULDs. For example
items that arrive with the same inbound flight at the terminal, that have the same final
destination, or items that need special care during flight, like animals. Placing these items
on only a few ULDs saves a lot of handling effort.
Item sorting can also be seen from a ULD perspective. Air cargo is often offered with
different service levels, say standard and premium. As the premium shipments are sold
with the promise to be processed faster at the destination airport, they should not be
mixed with standard cargo. Another good reason for item sorting is to fill a ULD only
with items that have the same connecting flight after the current one. In this case, a
so called thru-unit can be built that can transit the next station without requiring any
handling effort.
While these are different requirements from a business view, they are technically equiv-
alent. Therefore, we formulate them all in the same way in our model. We identify two
vantage points on the sorting criteria. The first is item-bound: a group of items should
be split across as few ULDs as possible. The other is ULD-bound: inside one ULD there
should be as few different item groups as possible. We denote the corresponding criteria
sets as Quld and Qitem (Q = Quld ∪ Qitem ). For each sorting criterion q ∈ Q each item i
has a parameter sortq,i ∈ Qq indicating the group it belongs to with respect to criterion
q. We add auxiliary variables sort q,u,e for each constraint q indicating if the item group
e ∈ Qq is present in ULD u. This is the case if any item of this group is assigned to u:
To calculate the degree of sorting nq for each item-bound constraint q we count the number
of ULDs each group is present in. To better express the impact of bad sorting for each
constraint we add an exponential penalty parameter powq . We note that this non-linear
restriction can be reformulated into piecewise linear restrictions because the number of
ULDs a group is spread across will usually be small. We calculate the degree of sorting
as:
!powq
q ∈ Qitem
X X
nq = sort q,u,e (6.37)
e∈Qq u∈U
To calculate the degree of sorting for ULD-bound constraints, we sum up the same inci-
dence matrix as above just in the opposite order of dimensions:
powq
q ∈ Quld
X X
nq = sort q,u,e (6.38)
u∈U e∈Qq
Item compatibility Besides the soft item grouping constraints, there are also hard con-
straints on items, which must not be placed on the same ULD or in close proximity. These
constraints mostly stem from official dangerous goods regulations (DGR). These define
51
6 Air cargo palletization
a long list of items that have to be separated by a minimum distance. Examples are
food and perfumery items, animals and items containing sources of radiation, or items
with chemicals that could react with each other. There is only one paper by Eley (2003)
dealing with this kind of item separation constraint.
To split incompatible items onto different ULDs we introduce a constraint for all pairs
hi, ji of incompatible items A:
Item spacing For pairs of items that require a certain minimum distance we introduce
a parameter disti,j . Remember the coordinates of item i: the front bottom left corner
(xi , yi , zi ) end the rear top right corner (x0i , yi0 , zi0 ). For this constraint we consider hor-
izontal distance only, because vertical distance might not be sufficient for leakages. To
simplify the model we calculate the Manhattan distance instead of Euclidean distance √ be-
tween the items. Furthermore, multiplying a Euclidean distance by a factor of 2 yields
a valid upper bound for the distance in Manhattan distance. We define the minimum
distance constraint between two items i and j as:
√
max(0, xi − x0j , xj − x0i ) + max(0, zi − zj0 , zj − zi0 ) ≥ 2disti,j i, j ∈ I (6.40)
Item positioning For some items the allowed position inside the aircraft or inside the
assigned ULD needs to be restricted.
For example, if radioactive materials are loaded into a passenger aircraft they must have
a minimum distance to the passengers’ cabin, i.e., be loaded not above a certain absolute
height. To model a global positioning constraint of item i we introduce a bounding box
(xac ac ac ac ac ac
i , yi , zi ) to (xi , yi , zi ). The item’s position has to stay within this box:
xac
i ≤ xi i∈I (6.41)
x0i ≤ xac
i i∈I (6.42)
yac
i ≤ yi i∈I (6.43)
yi0 ≤ yac
i i∈I (6.44)
zac
i ≤ zi i∈I (6.45)
zi0 ≤ zac
i i∈I (6.46)
Similarly, the relative position of an item inside the ULD might need to be constrained.
This is usually the case for dangerous goods that need to be placed on the periphery of
the ULD to be inspected or accessed if necessary. The same applies to living animals that
need ventilation. On the other hand, items of high value should not be placed on the
periphery to prevent theft. To model this constraint of item i when assigned to ULD u we
introduce two more bounding boxes, one for the item start coordinates (← x uld
− y uld
u,i , ←
− z uld
u,i , ←
− u,i )
←− uld ←− uld ←− uld
to ( x u,i , y u,i , z u,i ) and another for the item end coordinates (→ uld
x u,i , → uld
y u,i , → uld
→
− − − −z u,i ) to
uld →− uld →− uld
( x u,i , y u,i , z u,i ). We apply the Big M method to relax this constraint if the item
is offloaded at all. The relative position is then limited as:
x uld
xi ≥ ←
− u,i + (assign u,i − 1)M u ∈ U; i ∈ I (6.47)
52
6.2 The Air Cargo Palletization Model
xi ≤ ←
−
x uld
u,i + (1 − assign u,i )M u ∈ U; i ∈ I (6.48)
yi ≥ y uld
←
− u,i + (assign u,i − 1)M u ∈ U; i ∈ I (6.49)
yi ≤ ←
−
y uld
u,i + (1 − assign u,i )M u ∈ U; i ∈ I (6.50)
z uld
zi ≥ ←
− u,i + (assign u,i − 1)M u ∈ U; i ∈ I (6.51)
zi ≤ ←
−
z uld
u,i + (1 − assign u,i )M u ∈ U; i ∈ I (6.52)
x0i ≥ →
x uld
− u,i + (assign u,i − 1)M u ∈ U; i ∈ I (6.53)
x0i ≤ →
−
x uld
u,i + (1 − assign u,i )M u ∈ U; i ∈ I (6.54)
yi0 ≥ y uld
→
−+ (assign u,i − 1)M
u,i u ∈ U; i ∈ I (6.55)
→
−
yi0 ≤ y uld
u,i + (1 − assign u,i )M u ∈ U; i ∈ I (6.56)
zi0 ≥ uld
−z u,i
→ + (assign u,i − 1)M u ∈ U; i ∈ I (6.57)
zi0 ≤ →
−z uld + (1 − assign )M
u,i u,i u ∈ U; i ∈ I (6.58)
Stability Load stability is required for all ULDs to prevent damage of the cargo and
movements inside the aircraft, which would endanger flight safety. We distinguish between
vertical and horizontal stability. Vertical stability prevents the items from falling down
or tipping. To enforce vertical stability we require that a minimum ratio suppi of item
i’s floor area is supported by other items or the item is placed directly on the ULD floor.
In many papers load stability is assured by requiring full support of all items. In an air
cargo setup this often not necessary and sometimes even not possible. For example, ULDs
on the lower deck only have a small floor area and reach their full width only at around
50 cm height. Accordingly, there must be overhanging items to fully utilize the loading
space.
In our formulation the minimum support ratio suppi is item dependent, because different
item geometries might require different supported areas. For a cardboard box with a flat
bottom a support of suppi = 0.75 might be sufficient. But, a pallet standing on four feet at
its corners only might require full support of suppi = 1.0. For items standing on the ULD
floor we assume full support. Therefore, we assume that items are placed directly on the
ULD floor if their vertical starting position yi is larger the vertical ULD starting position
startyu plus the stacking tolerance . Accordingly, we restrict the minimum supported area
by the following non-linear constraint:
yi > assign u,i startyu + ⇒ (oi ≥ suppi (x0i − xi )(zi0 − zi )) u ∈ U; i ∈ I (6.59)
Horizontal stability prevents the shifting of items when the ULD is moved or tilted. In air
cargo this is usually ensured by the usage of nets and straps after the ULD is build-up.
Therefore, we do not model horizontal stability explicitly.
6.2.4 Objective
The objective of the palletization is to load as much as possible while keeping the necessary
physical handling effort low. Therefore, we penalize all offloaded items, where assign off
i =
1, with their individual penalty offloadi .
53
6 Air cargo palletization
To simplify all handling operations we would also like the load plan to be as sorted as
possible. For each sorting criterion q ∈ Q the variable nq contains a measure how well the
items are sorted. We weight all measures by their individual penalty factors penaltyq .
Our objective minimizes the sum of penalties of the offloaded items and violated sorting
criteria:
subject to
1 = assign off
X
i + assign u,i i∈I (6.62)
u∈Ui
54
6.2 The Air Cargo Palletization Model
¬ assign off off
i ∨ assign j ∧ (0 ≤ yj − yi0 ≤ ) ⇒
i, j ∈ I (6.99)
oxi,j = max(0, min(x0i , x0j ) − max(xi , xj ))
¬ assign off off
i ∨ assign j ∧ (0 ≤ yj − yi0 ≤ ) ⇒
i, j ∈ I (6.100)
ozi,j = max(0, min(zi0 , zj0 ) − max(zi , zj ))
oxi,j ozi,j
X
oj = j∈I (6.101)
i∈I
X oxi,j ozi,j
wi = weightgrs
i + wj i∈I (6.102)
j∈I oj
wj
oxi,j ozi,j > 0 ⇒ ri21 stackxi + ri22 stackyi + ri23 stackzi ≥ i, j ∈ I (6.103)
oj
assign off off
i = assign cliquei i∈I (6.104)
assign u,i ≤ sort q,u,sortq,i q ∈ Q; u ∈ U ; i ∈ I (6.105)
55
6 Air cargo palletization
!powq
q ∈ Qitem
X X
nq = sort q,u,e (6.106)
e∈Qq u∈U
powq
q ∈ Quld
X X
nq = sort q,u,e (6.107)
u∈U e∈Qq
yi > assign u,i startyu + ⇒ (oi ≥ suppi (x0i − xi )(zi0 − zi )) u ∈ U; i ∈ I (6.128)
The objective, given in Equation (6.61), is to minimize the sum of the penalties of of-
floaded items and for violating the sorting constraints. Equation (6.62) models the ULD
assignment, Equations (6.63) to (6.73) the item rotation, Equations (6.74) to (6.87) the
item position inside the ULD, Equation (6.88) the item non-overlapping, Equation (6.89)
the item availability, Equations (6.90) and (6.91) the ULD weight limit, Equation (6.92)
the net weight limits, Equation (6.93) to (6.98) the ULD weight distribution, Equa-
tion (6.99) to (6.103) the stacking of items, Equation (6.104) the complete shipment of
items, Equations (6.105) to (6.107) the item sorting, Equation (6.108) the item compati-
bility on ULDs, Equation (6.109) the item spacing, Equations (6.110) to (6.127) the item
positioning constraints, and Equation (6.128) the item vertical stability.
56
6.3 Summary
6.3 Summary
In this chapter, we introduced the Air Cargo Palletization Problem (ACP) in detail, which
is to solve a three-dimensional container loading problem while respecting a multitude of
physical, regulatory, and organizational constraints. Furthermore, we analyzed the related
literature and presented a formal model, denoted as the Air Cargo Palletization Model
(APM), of the problem features.
There is a vast amount of literature regarding container loading problems and most of the
constraints present in air cargo have been mentioned in the literature. However, only few
works exist that deal with several of the practically relevant constraints simultaneously.
Of the twelve types of requirements described by Bischoff and Ratcliff (1995) eleven can
be found in our problem at hand and are built into our model.
The presented model is basically a three-dimensional multi-container loading problem,
also denoted as Multiple Heterogeneous Knapsack Problem (MHKP) in the literature. We
formally defined all of its constraints, which is especially interesting for the stackability
and stability constraints, because these are often only described verbally in literature.
Besides, our model introduces some new practically relevant features that have not yet
been presented in the literature. Most notably, we consider time, both of item arrivals
and bin due dates, and we add a small tolerance for the stacking constraint that allows
the stacked item to be supported by items of slightly different heights.
57
Aircraft configuration
Build-up scheduling
Palletization
7 Weight and balance Weight and balance
The final step of aircraft load planning is the weight and balance (FAA, 2016), often
abbreviated as WAB. Here, a set of packed and weighed ULDs has to be arranged on dis-
tinct loading positions inside the aircraft’s cargo compartments with respect to structural
and loading constraints. The weight and balance has to be calculated for each flight leg
individually. Cargo flights often contain multiple legs. After each leg some ULDs might
be loaded or unloaded while others continue onto the next flight leg. Rearranging the con-
tinuing ULDs between two flight legs is possible. Depending on the situation this might
save fuel or allow to load more weight. But, it also incurs cost for additional unloading
and loading operations. Therefore, we solve the weight and balance for all legs of a flight
within one model, to find a cost-optimal assignment for the whole flight.
The structural limitations of an aircraft include a total weight limit, weight limits for
individual loading positions as well as subsets of loading positions, and a defined range
for the aircraft’s CG. The loading restrictions consist of compatibility and assignment
constraints between the ULDs and the partially overlapping loading positions. Further-
more, loading positions must be accessible from the door during loading and unloading,
i.e., not be blocked by ULDs staying on board.
With regard to the weight and balance objective, the arrangement of ULDs influences the
flight in three ways. Firstly, it defines the CG of the aircraft. During flight there is an
optimal CG at which the aircraft consumes the least fuel. Therefore, a good arrangement
of ULDs puts the actual CG close to the optimum. Secondly, the assignment defines the
moment of inertia (MI) of the aircraft around the CG. A lower MI makes the aircraft easier
maneuverable as less force is necessary to change the direction of flight. Therefore, the
MI should be small. Finally, on multi-leg flights where only some ULDs are unloaded or
loaded at each stop, the arrangement of ULDs determines the number of ground handling
operations. Besides the cost, each ground handling operation takes time, increases the
wear and tear of the aircraft, and raises the risk of damaging the cargo. Therefore, the
number of operations should also be minimized. If the right ULDs are placed at the doors
no additional ULD movements are necessary.
We define the Weight and Balance Problem (WBP) as the subproblem of the ACLPP to
decide about the assignment of ULDs to loading positions on each leg of a multi-leg flight.
In the WBP we consider each flight independently, but successive legs must be handled
within one problem because handling operations take place between the legs.
In the next section, we discuss literature related to the WBP followed by a mathematical
formulation of the problem in Section 7.2.
7 Weight and balance
Overlapping positions
Cumulative weights
Moment of inertia
Optional loading
ULD separation
Number of legs
First author Year Objective
Brosh 1981 X - - - - 1 max load
Mongeau 2003 X - X - - 1 max load
Limbourg 2012 - X X X - 1 min moment of inertia
Vancroonenburg 2014 X X X - X 1 min center of gravity offset
Lurkin 2015 - X X - X 2 min cost
Dahmani 2016 X - - - - 1 max load, max priority
Table 7.1: Overview of recent literature on weight an balance problems with ULDs. The
columns show the considered features and objective. Technical constraints like
center of gravity limits, which are present in all the papers, are not shown.
The earliest notable work regarding the loading of ULDs into civilian aircraft was given
by Larsen and Mikkelsen (1980). The authors present an interactive loading procedure
that considers practical constraints like (combined) weight limits, bounds for loading
imbalance, and assignment restrictions between ULDs and loading positions.
An early LP formulation was given by Brosh (1981). The model deals with bulk loads, not
ULDs. The objective is to maximize the profit of the transported cargo while respecting
capacity and balance limits.
Mongeau and Bes (2003) consider the loading of ULDs into aircraft compartments, but
not to individual loading positions. The authors present a MIP model where each com-
partment’s capacity is limited by a maximum total weight and a set of linear sums on the
number of certain ULD types. Thus their model only calculates a rough estimation of
the center of gravity (CG) as the individual loading positions are not considered and the
compartments are rather large. Their single objective is to maximize the loaded weight.
Limbourg et al. (2012) present a MIP model for the assignment of ULDs to loading po-
sitions. They limit longitudinal and lateral imbalances, introduce load limits on subsets
of ULDs, and incorporate mutually excluding loading positions. The objective is to min-
imize the aircraft’s moment of inertia. They solved their model with CPLEX and report
runtimes of a few seconds for large cargo aircraft.
Vancroonenburg et al. (2014) extend the work above. Their model selects the most
profitable subset of ULDs and minimizes the deviation from the optimal CG. Furthermore,
60
7.2 The Weight and Balance Model
they add a set of balance restrictions that apply during different phases of the flight to
cater for changing fuel weights.
Lurkin and Schyns (2015) also extend the work of Limbourg et al. (2012). They introduce
multi-leg flights, however limiting themselves to only two legs, and model the accessibility
of loading positions at the stop-over airport. All given ULDs must be loaded. The
objective is to minimize the sum of additional fuel cost caused by a suboptimal CG and
the cost of reloading operations at the stop-over airport.
Dahmani and Krichen (2016) integrate weight and balance and palletization aspects in a
two-level problem. They assign items to bins and bins to loading positions while maximiz-
ing the total weight and priority of loaded cargo. They present a multi-objective particle
swarm optimization approach and compare their results to optimal MIP solutions for
small instances. However, their model lacks most of the features that are presented in
other recent papers. The item-to-bin assignment is solved as a one-dimensional packing
problem based on item weights. The bin-to-position assignment is unrestricted and allows
only a single aircraft configuration.
We give an overview of the mentioned papers, their covered features and objectives in
Table 7.1. The majority of features that are present in our problem at hand have already
been covered in the literature. However, none of the present papers simultaneously covers
all aspects of our problem at hand.
61
7 Weight and balance
We start by defining the problem parameters. In the following sections we introduce the
problem’s constraints and objective. At last, we present a short overview of the model.
7.2.1 Parameters
The WBM operates on three sets of entities: the legs of the considered flight L, the
loading positions of the aircraft P , and the transported ULDs U . In the following we use
the respective lower case indices to represent single entities: l ∈ L, p ∈ P , u ∈ U .
Aircraft parameters
• Bp ⊆ P : set of loading positions that block loading operations on position p
• BAac ∈ R: longitudinal balance arm of the aircraft at OEW
• BAlat
p ∈ R: lateral balance arm of loading position p
• BAlng
p ∈ R: longitudinal balance arm of loading position p
• distp ∈ R≥0 : distance between loading position p and the compartment door
• distp,p0 ∈ R≥0 : distance between loading positions p and p0
• fn,p ∈ R: weight factor of loading position p for constraint n
• limitn ∈ R: cumulative weight limit of constraint n
• N : set of cumulative weight constraints in the aircraft (n ∈ N )
• O ⊆ P × P : set of overlapping loading positions (hp, p0 i ∈ O)
• Rp ⊆ P : set of loading positions that position p depends on
• wOEW ∈ R≥0 : operating empty weight of the aircraft (OEW)
Flight parameters
• acg
l ∈ R: cost of additional fuel for deviations from the optimal CG on leg l
dist
• al ∈ R: cost of working time to move a ULD by one position after leg l
• ami
l ∈ R: cost of additional fuel depending on the MI on leg l
• aon
l ∈ R: cost of one ULD loading operation after leg l
un
• al ∈ R: cost of one ULD unloading operation after leg l
• BAfuel
l ∈ R: longitudinal balance arm of the fuel tanks on leg l
MAX
• BAl ∈ R≥0 : maximum allowed lateral CG imbalance on leg l
OPT
• BAl ∈ R: optimal longitudinal CG on leg l
• FWl ∈ R≥0 : total weight of loaded fuel before starting leg l
• MAXl ∈ R: maximum loadable total ULD weight on leg l
• MAXCGl ∈ R: aft limit of the longitudinal CG on leg l
• MINCGl ∈ R: forward limit of longitudinal CG on leg l
ULD parameters
• aoff
u ∈ R: penalty when offloading ULD u
62
7.2 The Weight and Balance Model
7.2.3 Constraints
In the following, we introduce the constraints that define a valid assignment of ULDs
to loading positions. Along with the upcoming constraints, we define further auxiliary
variables that are only relevant inside the defining constraint. We note that in practice
the xu,p,l variables only need to be defined for p ∈ loadableu and l ∈ legsu . To simplify
the notation in the following we assume that non-defined xu,p,l are generously handled as
zero values.
ULD assignment Each ULD u must be assigned to at most one loading position on
each of its flown legs legsu . Depending on the ULD type, weight, contour, or contained
dangerous goods it might not be loadable at certain loading positions. We denote the
feasible loading positions as loadableu and limit the positions u takes to this set. If u is
offloaded on one of its legs, indicated by xoff
u , it must be offloaded on any of its legs.
xu,p,l = 1 − xoff
X
u u ∈ U ; l ∈ legsu (7.1)
p∈loadableu
Loading position assignment On each flight leg l each loading position p can load at
most one ULD:
X
xu,p,l ≤ 1 p ∈ P;l ∈ L (7.2)
u∈U
63
7 Weight and balance
set of pairwise mutually excluding loading positions as O and prohibit the simultaneous
use of both on each leg l as:
hp, p0 i ∈ O; l ∈ L
X
(xu,p,l + xu,p0 ,l ) ≤ 1 (7.3)
u∈U
Total weight On each flight leg l the aircraft has a certain maximum payload weight
MAXl . The sum of weights weightu of all loaded ULDs must not exceed this limit.
The payload limit depends on the flight leg, because of the respective fuel weight and
airport parameters such as runway length or outside air temperature. Usually, an aircraft’s
maximum allowed takeoff weight is far lower then the sum of its individual empty weight,
maximum possible payload weight, and maximum possible fuel weight. Therefore, there
is a tradeoff between fuel and payload on each flight.
X X
MAXl ≥ weightu xu,p,l l∈L (7.4)
u∈U p∈P
Cumulative weights Besides the total weight limits, each aircraft has structural weight
limits for each loading position. Additional structural weight limits may apply for adjacent
loading positions, which are often strictly less than the sum of the individual limits. For
example, the two adjacent main deck positions DL and DR from Figure 2.8 might each be
able to carry a ULD with 4.1 tonnes weight but the combined weight on both positions
has to be less than 6.8 tonnes. Similar limits apply for groups of loading positions, for
all loading positions in the full upper and lower deck, as well as for subsets of loading
positions along the fuselage.
As a generalization, we introduce as set of cumulative weight constraints N on arbitrary
subsets of loading positions. For each constraint n ∈ N and its affected loading position p
we introduce a parameter fn,p representing the influence factor of the loading position. We
limit the weighted sum of ULD weights on these loading positions by parameter limitn .
X X
weightu fn,p xu,p,l ≤ limitn n ∈ N; l ∈ L (7.5)
u∈U p∈P
Center of gravity The distribution of weight of the aircraft itself, its payload, and fuel
influence the aircraft CG. To ensure the safety and maneuverability of the aircraft, its CG
always has to stay within a defined range. In practice this range varies with the different
phases of the flight. In our model we assume that the parameters are set in a way that
the resulting range is feasible for all phases of the flight.
According to basic engineering mechanics, see FAA (2016), the CG can be calculated
as the average rotational moment of all point masses weighted by their distances from
a reference datum. In Figure 7.1 we present a sketch of the main aircraft parameters
that influence the CG. The aircraft manufacturer usually defines a reference datum as
well as the longitudinal and lateral distances between this datum and the CG of each
relevant aircraft component. The distances are often referred to as balance arms. Relevant
components include the empty aircraft itself, the ULD loading positions, and the fuel
tanks.
64
7.2 The Weight and Balance Model
Reference datum
Fuel tank CG
BAac Empty aircraft CG
Centers of loading positions
BAfuel
l Feasible overall CG
p
lng
BAlng
p
MINCGl
MAXCGl
To determine the aircraft CG, we need to set the rotational moment in relation to the
total weight of the aircraft. We calculate the total weight at the beginning of each leg l
as:
wl = wOEW + FWl +
X X
weightu xu,p,l l∈L (7.7)
u∈U p∈P
The CG on leg l can now be calculated as ml /wl . On each leg the CG has a forward limit
MINCGl and aft limit MAXCGl . To avoid the division of variables we limit the rotational
moments and not the CG itself:
The lateral CG of the empty aircraft, the fuel weights, and the optimal lateral CG are
usually all at the center of the aircraft. Therefore, we only look at the payload for
65
7 Weight and balance
calculating the lateral CG, or rather the payload imbalance. Let BAlatp denote the lateral
balance arm of loading position p. We introduce the auxiliary variables mlat-l and mlat+
l
indicating a lateral moment to the left or right of the aircraft. We calculate the moment
of the lateral imbalance as:
BAlat lat+
− mlat-
X X
weightu p xu,p,l = ml l l∈L (7.9)
p∈P u∈U
The pilots may be able to adjust small lateral imbalances by pumping fuel between the
wing tanks. However, the imbalance should be small to maintain flexibility. Therefore,
we limit the imbalance on each leg l to BAMAX
l as:
mlat+
l + mlat-
l ≤ BAMAX
l wl l∈L (7.10)
Moment of inertia Weight limits and an ideal CG are not sufficient to describe a good
loading pattern. As an example, a good CG might be reached by placing one ULD on
the front and one at the back of the aircraft and nothing in between. While this might
be feasible with respect to weight and CG considerations, it would result in a higher than
necessary MI of the aircraft. With a higher MI the aircraft becomes less maneuverable
as more power is needed to raise or lower the aircraft’s pitch. Consequently, we want to
minimize the MI by placing heavier ULDs closer to the aircraft CG.
To simplify the formulation we use the optimal CG of the aircraft BAOPTl instead of the
actual CG, because the former is a constant while the latter is a decision variable. This
is reasonable because we expect the actual CG to be close to the optimum as this is part
of our objective function.
We introduce an auxiliary variable mmi
l to approximate the MI added by the loaded ULDs
on each leg l as:
ULD separation The same item incompatibility constraints that apply during palletiza-
tion also apply during flight. Therefore, two ULDs that contain incompatible items must
be loaded at positions that are a certain minimum distance apart.
66
7.2 The Weight and Balance Model
We introduce the set S of conflicting ULDs and a parameter minu,u0 representing the
minimum required distance between the pairs of ULDs. Furthermore, let distp,p0 denote
the distance in the aircraft between loading positions p and p0 . On each leg l we restrict
the applicable loading positions as:
hu, u0 i ∈ S; p ∈ P ; l ∈ L
X
xu,p,l + xu0 ,p0 ,l ≤ 1 (7.13)
p0 ∈P :
distp,p0 <minu,u0
Loading operations Cargo flights often contain multiple legs, at which only a part of
the ULDs are unloaded and others are loaded. As the loading positions are generally
only accessible in a first-in-last-out style, the assignment of ULDs to loading positions
influences the handling effort at each stop. ULDs can be reloaded between the legs, if
this is beneficial, i.e., it reduces the fuel consumption, or allows to load more cargo.
We consider two types of handling operations in the following: unloading a ULD and
loading a ULD. We introduce the auxiliary variable ql,p to indicate if the loading position
p needs to be cleared at the stop after leg l. A position needs to be cleared if a ULD is
removed from this position, a ULD is loaded at the position, or if the position is on the
path Bp of another position that needs to be cleared. For all legs but the last, denoted
as L0 , we add:
un on
Furthermore, we add auxiliary variables rl,p and rl,p to indicate if a real handling operation
takes place. These are set to one if a ULD at this position p is loaded or unloaded at the
stop after leg l.
un
X
rl,p ≥ ql,p + xu,p,l − 1 p ∈ P;l ∈ L (7.18)
u∈U
on
X
rl,p ≥ ql,p + xu,p,l+1 − 1 p ∈ P;l ∈ L (7.19)
u∈U
To sum up the overall loading effort after leg l we use three variables representing the total
number of offloaded ULDs rlun , the total number of loaded ULDs rlon , and the distance of
moving ULDs out of and into the aircraft rldist .
rlun = un
X
rl,p l∈L (7.20)
p∈P
rlon = on
X
rl,p l∈L (7.21)
p∈P
rldist = un on
X
distp (rl,p + rl,p ) l∈L (7.22)
p∈P
67
7 Weight and balance
7.2.4 Objective
There are four factors that make up a good weight and balance solution. First, all ULDs
should be loaded. Second, the longitudinal deviation from the optimal CG should be
minimized. Third, the MI of the payload should be small. And last, there should be
as few handling operations as possible at each stop-over airport. In our objective we
weight these factors by their induced cost. First, we describe how to determine the cost
parameters.
In some setups it might not be possible to load all ULDs. In these cases the least important
ULDs should be left behind. Let aoff u denote the penalty cost of offloading ULD u. In
practice this can be derived from the items loaded into the ULD and the respective
contracts with the shippers.
As mentioned before, the CG also influences the fuel consumption of the aircraft during
flight. Therefore, we estimate the additional fuel consumption attributed to the deviation
from the optional CG on each flight leg. Let BAOPT l denote the optimal point at which
the aircraft consumes the least fuel on leg l. The variable wl denotes the total weight of
the aircraft and ml its total rotational moment at the beginning of leg l. Let the variables
mlng-
l and mlng+
l denote the absolute deviation from the moment of the optimal CG to the
front and aft. We calculate them as:
BAOPT
l wl − ml = mlng+
l − mlng-
l ∀l ∈ L (7.23)
To transform this into cost, we add parameter acg l for each leg l representing the additional
fuel cost for each unit the moment deviates from the optimum. This cost factor mostly
depends on the aircraft type, the expected flight duration and the fuel price.
Nearly the same applies to the MI. A higher MI increases the necessary force to change the
aircraft’s direction of flight. This leads to higher drag and additional fuel consumption.
To transform the MI into cost, we weight it by a parameter ami l for each leg l.
To determine the cost of loading operations, we introduce parameters that represent
the cost at the destination airport of leg l for one unloading operation aun l , one loading
on
operation al , and the cost of working time when moving a ULD by one loading position
adist
l . These costs are usually well known to the airline and defined in the contracts with
the respective ground handling agents or airports.
To sum up, we define the total objective function for the WBM to minimize the sum of
costs stemming from offload penalties, additional fuel consumption on all flight legs, a
penalty for the MI, as well as the handling efforts for ULD unloading, loading, and moving
efforts at all visited airports along the flight:
X cg
aoff off
al (mlng- + mlng+
X
minimize u xu + l l )
u∈U l∈L (7.24)
+ami mi
l ml + aun
l rl
un
+ aon on
l rl + adist
l rl
dist
68
7.2 The Weight and Balance Model
X cg
aoff off
al (mlng- + mlng+
X
minimize u xu + l l )
u∈U l∈L (7.25)
+ami mi
l ml + aun un on on dist dist
l rl + al rl + al rl
subject to
xoff
X
u = 1− xu,p,l u ∈ U ; l ∈ legsu (7.26)
p∈loadableu
X
1≥ xu,p,l p ∈ P;l ∈ L (7.27)
u∈U
hp, p0 i ∈ O; l ∈ L
X
1≥ (xu,p,l + xu,p0 ,l ) (7.28)
u∈U
X X
MAXl ≥ weightu xu,p,l l∈L (7.29)
u∈U p∈P
X X
limitn ≥ weightu fn,p xu,p,l n ∈ N; l ∈ L (7.30)
u∈U p∈P
wl = wOEW + FWl +
X X
weightu xu,p,l l∈L (7.32)
u∈U p∈P
BAOPT
l wl = ml + mlng+
l − mlng-
l l∈L (7.33)
ml ≤ MAXCGl wl l∈L (7.34)
ml ≥ MINCGl wl l∈L (7.35)
mlat+ BAlat lat-
X X
l = weightu p xu,p,l + ml l∈L (7.36)
p∈P u∈U
BAMAX
l wl ≥ mlat+
l + mlat-
l l∈L (7.37)
mmi (BAOPT − BAlng 2
X X
l = weightu l p ) xu,p,l l∈L (7.38)
u∈U p∈P
X X X
xu,p,l ≤ xu,p0 ,l p ∈ P;l ∈ L (7.39)
u∈U p0 ∈R p u∈U
hu, u0 i ∈ S; p ∈ P ; l ∈ L
X
1≥ xu,p,l + xu0 ,p0 ,l (7.40)
p0 ∈P :
distp,p0 <minu,u0
rldist = un on
X
distp (rl,p + rl,p ) l∈L (7.47)
p∈P
69
7 Weight and balance
ml , mlat- lat+
l , ml , mlng-
l , mlng+
l , mmi
l , wl ∈ R≥0 l∈L (7.48)
rldist ∈ R≥0 l∈L (7.49)
un on
ql,p , rl,p , rl,p ∈ {0, 1} l ∈ L; p ∈ P (7.50)
xu,p,l ∈ {0, 1} u ∈ U; p ∈ P ; l ∈ L (7.51)
xoff
u ∈ {0, 1} u∈U (7.52)
The objective, given in Equation (7.25), is to minimize the sum of additional costs of the
flight. Equation (7.26) models the ULD assignment, Equation (7.27) the loading position
assignment, Equation (7.28) the overlapping positions, Equation (7.29) the total weight
limit of the aircraft, Equation (7.30) the cumulative weight limits of loading positions,
Equations (7.31) to (7.37) the center of gravity, Equation (7.38) the moment of iner-
tia, Equation (7.39) the loading dependencies, Equation (7.40) the ULD separation, and
Equations (7.41) to (7.47) the loading operations between the flight legs.
7.3 Summary
In this chapter, we introduced the Weight and Balance Problem (WBP) in detail, which is
to assign ULDs to loading positions in the aircraft for every leg of a flight while respecting
the aircraft’s structural limitations and reducing the costs of required fuel and reloading
operations. Furthermore, we analyzed the related literature and presented a formal model,
denoted as Weight and Balance Model (WBM), of the problem features.
There are a few works dealing with aircraft weight and balance in the literature. Most
of them focus solely on maximizing the load and consider flights with only a single leg.
The closest model we found, given by Lurkin and Schyns (2015), describes flights with
two legs and covers five of the eight requirements we identified in practice.
We combined all the features found in the literature into our model and extended it for
an arbitrary number of flight legs. Furthermore, we added a new practical constraint
that describes the conditional usage of loading positions, depending on the usage of other
loading positions. Furthermore, we standardized the way of specifying cumulative load
constraints.
70
8 Benchmark instances
To evaluate and compare solution approaches to the ACLPP one needs a set of benchmark
instances. Unfortunately, there are no suitable instances available yet, neither synthetic
ones nor instances stemming from practice. We mainly attribute this to the fact that
the ACLPP has not been considered as a whole in the past. But even in papers dealing
with parts of the problem, like Mongeau and Bes (2003), Rong and Grunow (2009), or
Lurkin and Schyns (2015), the authors did not publish any of the problem instances they
worked with. From the airline’s point of view, this is comprehensible as booking data are
seen as a trade secret. They would allow insights into the airline’s state of business in a
highly competitive market. Furthermore, the concrete shipment data could even allow to
identify the shippers and draw conclusions about their state of business. The same issues
apply in our case. For the development and evaluation of our approach, we work with
original datasets provided by our industrial partner, but we cannot publish them.
To make our results reproducible, we also create a set of publishable synthetic instances.
Simply creating random instances would not be of much use, as the ACLPP exhibits
a lot of structure that can be exploited by a solution approach. Hence, the instances
need to be carefully designed, to keep a maximum of the typical problem structure of the
ACLPP in practice. We do this by analyzing the provided real world data, we extract
their key characteristics and derive new synthetic instances from the given booking data
in a suitable way.
This chapter is structured as follows. First, we introduce the ACLPP data model in
Section 8.1. It combines the models and parameters described in Chapters 4 to 7. After-
wards, we present an analysis of the typical properties and problem structure of air cargo
bookings found at our industrial partner in Section 8.2. We present the actual datasets
used for our evaluation in Section 8.3. Finally, we describe a set of performance indicators
to compare solutions to the ACLPP and to relate our results to practice in Section 8.4.
Figure 8.1: Data model representing all master data (yellow, green), flight data (red),
booking data (violet) and decisions (blue) present in the ACLPP.
72
8.2 Analysis and insights into real world instances
shipment represents a single booking of a shipper with a certain origin, destination, prod-
uct, and the expected arrival time at the export terminal. A product defines the service
level of the shipment, typically standard or express. Shipments can contain multiple dif-
ferent items. Each item type is specified by its dimensions, weight, offload penalty, and
handling requirements. The latter contain information about the allowed item rotations,
load-bearing strength, and dangerous goods with their respective net weights. Often, a
booking contains multiple items of an item type. Until the airline gets hold of the items,
some parameters are still uncertain. The item dimensions and weight might slightly
change and it might turn out that items are not stackable or not rotatable although
stated differently by the shipper.
The model decisions correspond to the subproblems of the ACLPP. They contain the
set of used ULDs with their assigned build-up workstation, build-up time, and loading
position inside the aircraft on each flight leg. For each item of each shipment, the decisions
contain the information if the item is loaded or offloaded and, if loaded, the assigned ULD
as well as the placement position and rotation inside the ULD.
Flight legs A flight might consist of multiple successive legs. The larger the number of
legs the more complex the aircraft configuration and weight and balance decisions, because
ULDs with different origins or destinations must be arranged in the aircraft. Figure 8.2
presents the distribution of legs per flight in the typical flight plan of our partner. Less
than one third of the flights had only one leg. The majority needed to deal with multiple
legs and transport segments.
73
8 Benchmark instances
50
40
share of flights [in %]
30
20
10
0
1 2 3 4
20
15
10
5
0
5 15 25 35 45 55 65 75 85 95
Weight utilization According to practitioners, most flights are restricted by volume and
are not operated near the aircraft weight limit. The analyzed data match this statement.
Figure 8.3 presents the distribution of the weight utilization on flights in the analyzed
data. Consequently, weight limits need to be considered in practice but the total weight
of all items will most probably not make the problems hard to solve.
Volume utilization Although most cargo flights are characterized as restricted by vol-
ume the typical volume utilization is far away from 100 percent. Figure 8.4 presents the
respective distribution found in the analyzed data. On most flights the physical volume
capacity could only be filled up to 60 or 70 percent. We attribute this to the heterogeneity
of the cargo, stacking, stability, and other handling requirements. However, in retrospect,
it is hard to identify a single reason for unused capacity. There might not have been
74
8.2 Analysis and insights into real world instances
30
25
share of flights [in %]
20
15
10
5
0
5 15 25 35 45 55 65 75 85 95
10
5
0
enough bookings, bookings might have been canceled at short notice, some shipments
might have arrived too late, the cargo might have had adverse dimensions or stacking
properties, or it might have been packed in an inefficient way.
Items per segment As packing problems are known to be NP-complete, the number
of items to pack strongly influences the solution complexity. In Figure 8.4 we analyze
the distribution of items per transport segment found in the analyzed data. On average,
each segment contained 349 items. Around 3.8 percent of the segments had more than
1,000 individual items. The maximum number we found on any segment was close to
2,000 items.
75
8 Benchmark instances
70
60
50
share of flights [in %]
40
30
20
10
0
1 2 3 4 5 6 7 8 9 10 >10
Length ±5 cm 120 40 30 60 80
Share of items 19.3% 12.0% 11.9% 8.9% 8.0%
Item groups Air cargo shipments might contain different items. We denote all items
in a shipment with the same dimensions, weight, and handling requirements as an item
group. The empirical distribution of the number of distinct groups per shipment is given
in Figure 8.6. The majority of shipments, around 67 percent, contained one item group
only and shipments with more item types occurred less frequently.
Item frequency Shipments might also contain multiple identical items. In the analyzed
data only 11 percent of the items were unique in a shipment and around 90 percent
occurred less than 20 times. But, there have also been significant outliers with more
than 100 equal items. The distribution of item group sizes up to 20 items is given in
Figure 8.7. Generally, individual items appeared most often and higher multiples less
frequently. Interestingly, item groups with an even multiple occurred a little more often
than their odd neighbors. In total even multiples account for 52 percent of the items.
Item length and width In the following, we denote the longer horizontal edge as length
and the shorter as width of an item. Figures 8.8 and 8.9 show the empirical distribution
of item lengths and widths. In terms of the length, there was a peak at 120 cm, which
is the length of a standard EUR-pallet (see Section 2.2). This length alone accounted for
13.4 percent of all items. Further typical items lengths and their frequencies are shown
in Table 8.1. Multiples of these lengths also fit well on a standard EUR-pallet. A similar
effect shows with respect to the item width. Around 11.6 percent of all items are 80 cm
wide, which is the width of a standard EUR-pallet.
76
8.2 Analysis and insights into real world instances
12
10
share of items [in %]
8
6
4
2
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Figure 8.7: Distribution of item frequencies in all shipments (to be read as: around 9 per-
cent of all items belong to a group of 2 items)
20
15
share of items [in %]
10
5
0
0 20 40 60 80 100 120 140 160 180 200 220 240 260 280 300
77
8 Benchmark instances
20
15
share of items [in %]
10
5
0
10
5
0
Aspect ratio We define the aspect ratio by the ratio between the horizontal edges of the
items, i.e., the item width divided by the item length. Figure 8.10 shows the empirical
distribution of the aspect ratio. The most frequent ratio was 0.667, accounting for more
than 20 percent of all items. Further typical aspect ratios are shown in Table 8.2.
Not surprisingly the most frequent item length (120 cm) and width (80 cm) resemble the
most frequent aspect ratio (2:3). Around 10 percent of the items had this base size.
Item height Figure 8.11 shows the empirical distribution of the item heights. The most
frequent heights were 20 cm to 40 cm and the mean height was 57 cm. Comparing this
to a maximum height of up to 300 cm for main deck ULDs, some stacking seems to be
necessary, but there will hardly be more than 10 items on top of each other. In the
analyzed dataset, item heights tend to be higher for larger items. Therefore, we also
look at the length-to-height ratio of the items. Figure 8.12 shows the corresponding
78
8.2 Analysis and insights into real world instances
10
5
0
distribution. The most frequent ratio was 1.5, accounting for 8.6 percent of the items.
Furthermore, integer multiples occurred a bit more often than the fractional values close-
by. However, it is not clear if this is a real effect or just caused by shippers rounding item
dimensions.
Item weight In the analyzed booking data item weight correlates with item volume.
Therefore, we consider the item density in the following. The corresponding distribu-
tion is shown in Figure 8.13. The most frequent item densities were between 100 and
150 kg · m−3 . From Table 2.4 we know that typical cargo aircraft have a capacity ratio of
around 180 kg · m−3 . Therefore, we expect the loading problems to be more constrained
by volume than by weight and thus the related three-dimensional packing problems are
non-trivial to solve. This observation is in line with our findings regarding the weight
utilization above.
Transfer times Each shipment must be handled in the time between its arrival at the
airport and the scheduled departure time of its outgoing flight. We denote this interval as
transfer time. In general, a shorter transfer time provides less options to combine items
onto ULDs and thus makes it harder to find good packing solutions. In the following,
we analyze the transfer time of shipments that arrived via an inbound flight or RFS. In
our analysis, we omit shipments that started their journey at the terminal due to missing
arrival data. According to practitioners, these shipments typically arrive rather late, most
of them less than 12 hours before the flight departure.
79
8 Benchmark instances
10
8
share of items [in %]
6
4
2
0
10
5
0
80
8.2 Analysis and insights into real world instances
100
80
share of available volume [in %]
60
40
20
0
0−6 6−12 12−18 18−24 24−30 30−36 36−42 42−48 48−54 54−60 60−66 66−72
60
40
20
0
0−6 6−12 12−18 18−24 24−30 30−36 36−42 42−48 48−54 54−60 60−66 66−72
We consider standard and express shipments separately. Express shipments are sold at
a premium and allow the shipper to book connections with a shorter transfer time. For
both product types, the available cargo volume within a certain transfer time is shown
in Figures 8.14 and 8.15. As one would expect, express shipments generally exhibit a
shorter transfer time than standard shipments. Accordingly, around 42 percent of the
standard volume and 77 percent of the express volume arrives during the last 24 hours
before departure.
We note that the available time for the actual build-up of the cargo is significantly shorter
than the transfer time. First, the inbound ULDs must be unloaded from the aircraft,
transported to the terminal and broken down. The same applies to the aircraft loading
after the build-up. Accordingly, the handling time window especially for express shipments
can become really narrow at times.
81
8 Benchmark instances
8.3 Datasets
We present two datasets to evaluate our approach. The first is a set of 89 real historic
all-cargo flights (dataset A) provided by our industrial partner. The second set con-
tains 82 synthetic flights (dataset B) that we created based on real-world booking data.
Dataset B is publicly available under https://github.com/fbrandt/ACLPP. In both
datasets, the flights add up to a one-week flight schedule. All flights are performed by
an MD11F aircraft, whose characteristics we introduced in Section 2.4. Large all-cargo
aircraft like the MD11F are the most challenging to plan, because they can load much
more cargo than smaller or passenger aircraft and a lot more loading constraints must
be adhered. Accordingly, we expect results to these datasets to be easily transferable to
other aircraft types. For evaluation we use the same set of master data for both datasets.
We created a simplified model of the MD11F aircraft depicted in Figure 2.8. It has
53 loading positions and 24 pairs of positions are overlapping. We consider 16 partial
weight limits and one net weight constraint. The aircraft can load four different types of
ULDs. On the main deck, standard pallets (PMC) and double-sized pallets (PGE) can be
loaded. On the lower deck, standard pallets (PMC) and half-size containers (AKE) can
be loaded. Note that the PMC pallets built for the main and lower deck have different
contours and cannot be loaded into the other deck. All four ULD types have been intro-
duced in Section 2.3. Furthermore, we consider the 115 item incompatibility constraints
stemming from the original IATA dangerous goods regulations. We apply two sorting
criteria. The first is to split items of the same shipment across as few ULDs as possible.
The second is to avoid mixing standard and express shipments on the same ULD.
The basis for dataset B is the pool of real booking data analyzed in Section 8.2. Dataset A
is a one week slice of this pool.
The flights of the dataset B are taken from the public flight schedule of Lufthansa Cargo
AG during calendar week 48 of the year 2015. We selected all flights departing from
Frankfurt Airport that were performed by freighter aircraft.
For each flight b in B, we drew a random flight x from the pool that has the same number
of legs. From the flight x we took the total payload and the distribution of payloads among
its transport segments. Then, we iteratively drew random shipments from the flights in
the pool until their sum reached the total payload of flight x. Afterwards, we assigned
the drawn shipments to the transport segments of flight b with the same probability as
seen at flight x. Finally, we adjusted the arrival time of the drawn shipments to represent
the same transfer time as in their original flight.
82
8.3 Datasets
Datasets
A B
Flights 89 82
Source real-world synthetic Description
8.3.3 Scenarios
Because our datasets originate from booking lists of real historic flights, we do not ex-
pect them to contain many extreme features. During the booking period, sales staff is
continuously monitoring each flight and managing its capacity conservatively. Confirmed
bookings are extended by an expected stowage loss and buffers are added for special
handling requirements, like those of dangerous goods or living animals. Future bookings
must comply with the set safety margins or will only be accepted after a manual check
for compliance by the sales staff.
Nevertheless, a decision support system for the ACLPP should be able to find acceptable
solutions also for extreme cases. Furthermore, such a system could be used to automate
compliance checks and reduce the conservative safety margins of today to the individually
required level.
To evaluate solution approaches to the ACLPP also under difficult conditions, we intro-
duce two additional scenarios: one with a high load and one with shorter transfer times.
From a commercial view, these scenarios are very interesting. Higher loads mean more
shipments and thus more revenues. Shorter transfer times allow faster connections and
thus higher premiums can be charged.
We denote the original real-world and synthetic instances as base scenario in the following.
According to an IATA report (Tyler, 2015), the average weight load factor in the market
varies between 40 to 50 percent, which is also the case in our instances. Accordingly, load
maximization is not the prime challenge of many flights. Instead, the minimization of
handling efforts and at the same time streamlined aircraft operations are focused in the
base scenario.
The high load scenario on the other hand puts special focus on the load maximization.
In this case we extended the list of shipments for each flight until its volume capacity
is overbooked. We added shipments until the booking list contained either more than
100 tonnes of shipment weight or 600 m3 of volume. The respective norm capacities of
the considered aircraft are 93 tonnes and 535 m3 . The exact overbooking limits were
chosen arbitrary, but our intention is to put some stress on the palletization step without
83
8 Benchmark instances
Sales indicators The sales department aims at maximizing the utilization and revenue
of all flights. To measure the weight and volume utilizations, we use the average ratio
of loaded items to total capacity. In terms of weight we refer to the ratio as weight load
factor (WLF). Depending on the capacity definition, we distinguish two different load
factors with respect to volume. We denote them as gross load factor (GLF) and net load
factor (NLF). The GLF relates the loaded item volume to the full volume capacity of the
aircraft, while the NLF relates the loaded item volume to the volume capacity of the used
ULDs. If all loading positions in the aircraft are used, both GLF and NLF are equal.
But, on flights where the demand is lower than the capacity of the aircraft, the NLF is a
more meaningful measure of packing quality. The NLF is also interesting from a revenue
maximization perspective. For two solutions of a flight with the same GLF, a higher NLF
indicates that more loading positions in the aircraft remain available for highly profitable
last minute sales. As another measure for revenue maximization, we use the sum of offload
penalties (PEN). Each item that is offloaded incurs a certain cost, representing a customer
84
8.4 Performance indicators
Demand Demand
Crews
Crews
Figure 8.17: Sketch of an undesired schedule (left) with peaks and low periods compared
to a desired schedule with even workload (right). Both have the same total
workload, but the right requires less crews.
refund for late delivery or lost revenue, if an item cannot be transported due to capacity
restrictions. Solutions with a lower PEN are generally preferred by the sales department.
85
8 Benchmark instances
on the next flight leg needs to be temporarily unloaded or relocated to another loading
position at a stop-over airport. This might occur because the ULD is blocking another
ULD that needs to be unloaded or to reduce the aircraft’s imbalance on the next flight
leg.
To combine all the tangible costs of a flight, we further introduce a last indicator of the
total cost (TOTAL) that combines the penalties of offloaded shipments (PEN), the cost
of all used ULDs (UNITS), the cost of extra fuel (FUEL), and the cost of unnecessary
loading operations (OPS).
8.5 Summary
In this chapter, we took a look on the data of load planning problems in practice and
derived benchmark instances to evaluate our solution approaches.
We presented an extensive data model describing the required planning parameters. On
the one hand, there are a lot of required master data including the aircraft specifications,
considered ULD types, workstation setup, regulatory requirements like item incompati-
bilities and separation constraints, and commercial objectives. On the other hand, there
are the flight data describing the legs and booked shipments on the respective transport
segments.
To get an understanding of the planning challenges, we analyzed a large dataset of real
booking data. We found that flights are often not fully booked. Accordingly, dense packing
is not always the prime objective and planning results that lead to efficient handling as
well as aircraft operations are also highly important. Nevertheless, a significant part of
the items to load is quite large, often exceeding the size of a standard wooden pallet, such
that finding good three-dimensional packings is non-trivial. Overall, the items to load are
strongly heterogeneous by their dimensions, weight, and density. However, many items
appear multiple times in a shipment. Furthermore, the planning problems are significantly
86
8.5 Summary
larger than popular benchmark instances for container loading problems. This motivates
the creation of new benchmark instances of realistic size.
From the analyzed booking data, we derived two sets of benchmark instances. One
contains data of real flights, while the other contains synthesized flights mimicking the
real flights’ properties. The latter dataset is publicly available under https://github.
com/fbrandt/ACLPP. For each dataset we created three scenarios to examine interesting
variations from a practical point of view. The first scenario contains just the base data,
in the second all flights are overbooked, and in the third scenario the items have shorter
transfer times at the terminal. Altogether, we created 513 flights to evaluate our solution
approaches.
In preparation of the evaluation, we discussed suitable performance indicators for load
planning results from a practical point of view. Fitting to the identified stakeholders
and general objectives, we introduced twelve measures for aircraft utilization, physical
handling effort, and aircraft operations efficiency.
87
9 A sequential planning approach
In this chapter, we present our first approach to solve the Air Cargo Load Planning Prob-
lem (ACLPP). To integrate well with the current manual planning processes of our indus-
trial partner introduced in Section 3.3, i.e., the aircraft configuration, build-up scheduling,
palletization, and weight and balance, we present a sequential approach that solves these
steps one by one. The whole process is denoted as SeqACLPP in the following. The main
goal of the SeqACLPP is to automate the manual planning steps of today. Our objective
is to find a good overall load plan, with respect to all constraints and performance indi-
cators presented in Section 8.4. Furthermore, this approach should provide a benchmark
for process changes.
Since the ACLPP cannot be solved independently for each flight and the degree of inter-
connection depends on the planning step, we consider three scopes in our solution: the
flight plan, flights, and segments. The flight plan usually contains multiple flights, which
compete for the same resources in the air cargo terminal. A flight potentially consists
of multiple transport segments, which compete for the same resources in the aircraft. In
Table 9.1 we give an overview of the planing steps and which scopes are considered in each
individual run of the respective step. The aircraft configuration is run for each flight. The
build-up scheduling is run for the full flight plan at once and considering all the transport
segments. The palletization is run individually for each transport segment. Finally, the
weight and balance is solved for each flight.
This chapter is organized as follows. In Section 9.1 we present a volume and weight
based approach (VWAC) to solve the Aircraft Configuration Problem (ACP). It decides
what ULDs should be built for each transport segment of a flight. In Section 9.2 we
present a rolling horizon planning approach (RHBS) to solve the Build-up Scheduling
Problem (BSP). It decides when to build the selected ULDs. After that, we present
our approach to assign and pack items onto the selected and scheduled ULDs (BDAP)
by a Logic-based Benders Decomposition (LBBD) solving the Air Cargo Palletization
Problem (APP). Finally, in Section 9.4 we present our solution step (UWAB) to solve the
Weight and Balance Problem (WBP). In this step, the built ULDs are assigned to loading
positions in the aircraft.
9.1.1 Preprocessing
The booking data introduced in Section 8.1 contain all the information about the individ-
ual shipments. But, as our model operates on aggregated data of each transport segment,
we need to derive some model parameters from the input booking data.
Offload penalties Each item to load has a specific penalty offloadi that applies if it is
offloaded. This penalty indicates the lost profit or the refund to the customer. During
aircraft configuration we only consider the total demand with respect to volume and
weight for each transport segment, not the individual items. To do that, we need to
derive suitable offload penalties for each segment. In our preprocessing we determine the
penalties as the average penalty across all items Ik on the segment k, weighted by the
item weight and volume respectively:
X X
offloadi offloadi
i∈Ik i∈Ik
offloadvol
k = X offloadwgt
k = X k∈K (9.1)
volumei weightgrs
i
i∈Ik i∈Ik
Estimated bin capacity In practice it is unlikely that we are able to fill a ULD up to
its physical volume capacity. Often the combinatorics between the items and the curved
shape of the ULD will result in some unused space. Therefore, in the following we use
the average achievable volume utilization of each ULD type instead of the real geometric
90
9.1 Volume-and-weight-based aircraft configuration
volume capacity. In practice this utilization can be derived from the built ULDs seen on
historic flights or earlier iterations of this solution process. We will discuss the impact of
the estimated capacity on the constructed solutions and the choice of suitable parameters
in Section 10.2.1.
Minimum number of required bins The third preprocessing step is to determine the
minimum number of ULDs required for certain ULD types. Here, we check for each item
if it would fit into each ULD type. For example, very long items might only fit into PGE
ULDs and high items that are not rotatable must be placed into the upper deck, thus
requiring a main deck PMC ULD. See Figure 2.3 for an overview of the used ULD types.
The geometric volumes of items requiring a special ULD type are summed up and divided
by the average achievable volume utilization for this ULD type. Rounding the result up
to the next integer gives us the minimum required number of ULDs of each type.
!
1 1
xk,v costv + ykwgt offloadwgt + ykvol offloadvol
X X
minimize k k (9.2)
k∈K v∈V 2 2
subject to
The objective, given in Equation (9.2), is to minimize the total cost from the used ULDs
and offloaded cargo. Because offloaded items will appear twice, as offloaded volume and
91
9 A sequential planning approach
Set/Parameter Description
F set of ULD combination restrictions in the aircraft
K set of transport segments on the considered flight
L set of legs of the considered flight
V set of available ULD types
availl,v ∈ N available units at departure airport of leg l
capvol
v ∈ R≥0 volume capacity per ULD of type v
wgt
capv ∈ R≥0 weight capacity per ULD of type v
costv ∈ R handling cost (preparation, loading) per ULD of type v
demvol
k ∈ R≥0 volume of the shipments on segment k
demwgt
k ∈ R≥0 weight of all shipments on segment k
limitf ∈ R total ULD limit in restriction f
mf,v ∈ R factor of ULD type v in restriction f
mink,v ∈ N minimum required number of ULDs of type v
startl ⊆ K set of transport segments starting with flight leg l
offloadvol
k ∈ R≥0 penalty for offloaded shipment volume
offloadwgt
k ∈ R≥0 penalty for offloaded shipment weight
onk ⊆ L set of flight legs of transport segment k
Variable Description
bl,f ∈ {0, 1} 1 if on leg l combination restriction f holds
xk,v ∈ N number of ULDs to built on segment k of type v
ykvol ∈ R≥0 volume offloaded on segment k
ykwgt ∈ R≥0 weight offloaded on segment k
92
9.2 Rolling horizon build-up scheduling
weight, we multiply the penalties by 12 . In the following we briefly describe the restrictions.
A detailed explanation of the constraints is given in Section 4.2.3.
Equations (9.3) and (9.4) make sure that enough weight and volume capacity is reserved
or that the cargo is marked as offloaded. Equations (9.5) and (9.6) limit the selected set
of ULDs to a valid aircraft configuration. The minimum number of required ULDs per
type on each transport segment are modeled with Equation (9.7). Finally, Equation (9.8)
ensures that no more than the available number of ULDs are used at each airport.
For simplicity we assume that the handling cost and available ULD types are the same for
all visited airports. We note that the model can be easily extended to support different
parameters for each airport.
9.2.1 Preprocessing
Most parameters of the BSP are defined in the booking lists of the flights or are determined
during the aircraft configuration, see Table 9.3. In this section, we discuss how the
remaining parameters, see Section 5.2.1, can be derived from these input data.
Offload penalties Each item to load has a specific offload penalty offloadi . This penalty
indicates the lost profit or the refund to the customer. Due to workstation or worker
capacity restrictions we might not be able to schedule all ULDs or we have to schedule
them too early, at a period where not enough cargo is available. In both cases we loose
volume capacity and will have to offload items later. Analog to the offload penalties in
93
9 A sequential planning approach
the aircraft configuration, we estimate the loss by the volume-weighted average offload
penalty across all items Ik on segment k as:
X
offloadi
i∈Ik
offloadvol
k := X k∈K (9.12)
volumei
i∈Ik
We only consider volume, and not weight, here because flights are usually volume-bound
and thus we expect that the cargo weight can be redistributed onto other ULDs.
Cargo availability In our model we use the available cargo volume during each period.
The booking lists contain the arrival period of each item. Therefore, we calculate the
available cargo volume per segment k and period t as:
availvol
X
k,t := volumei k ∈ K; t ∈ T (9.13)
i∈Ik :
availi ≤t
Parallel build-ups In practice we only want to build a limited number of ULDs for the
same segment at the same time. This leaves more options and time to react to operational
problems during build-up and allows to build the ULDs on close-by workstations. Let
splitmax denote the maximum desired number of parallel build-ups of a segment. Enforcing
a hard limit in practice might lead to offloads for segments where the cargo arrives rather
late such that the limit is too low to build all ULDs on time. In these cases we want to
set a less restrictive limit.
As a suitable limit we choose the maximum required parallel build-ups, between any
build-up period and the scheduled departure period of the flight, for which all cargo can
be packed. For each period t, we determine the cargo volume arriving in the future
(demvol vol
k − availk,t ) and the volume that could be packed in the remaining time, if no
parallel build-ups are allowed. Note that the number of ULDs of type j v that kcan be built
k −t−1
sequentially in the time between t and duek can be determined as duedur v
. The ratio
of both gives us the required parallelism and its maximum over the periods the sought
limit. If the required parallelism is less than the desired splitmax , we allow splitmax to be
built in parallel.
demvol vol
k − availk,t
splitk := max splitmax ; max j
duek −t−1
k k ∈ K; v ∈ V (9.14)
t∈T :
t<duek −durv durv
capvol
v
94
9.2 Rolling horizon build-up scheduling
Set/Parameter Description
K set of transport segments to build ULDs for
S set of crew shifts
T set of time periods
V set of available ULD types
availvol
k,t ∈ R≥0 demand volume for segment k available at period t
vol
capv ∈ R≥0 volume capacity per ULD of type v
costs ∈ R≥0 cost of one build-up crew in shift s
demvol
k ∈ R≥0 total volume of the shipments on segment k
duek ∈ T build-up due date of segment k
durv ∈ N number of periods to build-up a ULD of type v
ends ∈ T last period after shift s
maxs ∈ N max build-up crews in shift s
offloadvol
k ∈ R≥0 offload penalty per volume unit for segment k
openv,t ∈ N open workstations for ULD type v at period t
packk ∈ R≥0 already packed demand volume for segment k at period 0
splitk ∈ N max simultaneous build-ups for segment k
starts ∈ T first period of shift s
uldk,v ∈ N number of ULDs of type v to schedule for segment k
δ(v, t) ⊆ T periods when build-ups in progress during period t pot. started
δ(v, t) = {t0 | t0 ∈ T : t − durv < t0 ≤ t}
φ(k) ⊆ T periods when ULD build-ups for segment k can be started
φ(k) = {t | t ∈ T : 0 < t ≤ duek }
θ(s) ⊆ T periods when workers of shift s can perform build-ups
θ(s) = {t | t ∈ T : starts ≤ t < ends }
the number of required crews crews s during each shift. Furthermore, it tracks the already
built volume pack k,t for each segment and period. By comparing this with the available
cargo volume in each period, we can derive the lost space inside planned ULDs dead k,t
and if necessary the not scheduled ULDs offload k,v . For completeness, we repeat the BSM
with minor adjustments for this step:
!
offloadvol capvol
X X X X
minimize k dead k,t + v offload k,v + costs crews s (9.15)
k∈K t∈T v∈V s∈S
95
9 A sequential planning approach
Variable Description
crews s ∈ N number of crews required during shift s
dead k,t ∈ R≥0 unusable volume capacity during build-ups for segment k in period t
offload k,v ∈ N number of selected but not scheduled ULDs for segment k of type v
pack k,t ∈ R≥0 already packed demand volume for segment k prior to period t
start k,v,t ∈ N number of ULDs build-ups started for segment k of type v at period t
subject to
X
uldk,v = offload k,v + start k,v,t k ∈ K; v ∈ V (9.16)
t∈T :
t≤duek −durv
The objective, given in Equation (9.15), is to minimize the sum of the cost of the lost
profit due to early build-ups or unscheduled ULDs and the cost of the deployed crews. In
the following we briefly describe the restrictions. A detailed explanation of the constraints
is given in Section 5.2.3.
Equation (9.16) makes sure that all requested ULDs are built on time or are marked as
offload. Equations (9.17) and (9.18) calculate the already built cargo volume at each
period and Equation (9.19) enforces that during each period not more than the already
available cargo is packed. The number of parallel build-ups for a segment is limited with
Equation (9.20). Similar checks make sure that the number of available workstations is
respected in Equation (9.21) and that during each period enough crews are on duty in
Equation (9.22).
96
9.2 Rolling horizon build-up scheduling
Shift
i-1 i i+1 i+2 i+3 i+4 i+5
Iteration i
i+1
i+2
Figure 9.1: Rolling horizon planning of build-up schedules. During the i-th iteration,
build-ups during shifts i to i + k (k = 2 is this example) are planned. Of this
result only ULDs built during shift i are fixed and the procedure is repeated
for the next shift.
97
9 A sequential planning approach
In this section, we present our solution approach to the Air Cargo Palletization Prob-
lem (APP). The APP decides which items are placed into which ULD and how they have
to be arranged in the three-dimensional space to fulfill all physical, regulatory, and orga-
nizational constraints. In the earlier steps we already selected a suitable superset of ULDs
for each transport segment and assigned a build-up period for each ULD. It is possible
to solve the APP for each transport segment independently, because items for different
segments must be placed in different ULDs. Therefore, we only consider problems with a
single transport segment in the following.
As the three-dimensional packing problem is NP-complete and large real world instances
are typically computationally very hard to solve, we decompose the problem and solve
it heuristically. Our approach is known as Logic-based Benders Decomposition (LBBD),
which was introduced by Hooker (2007). Its basic idea is to split an optimization problem
into a linear master problem and an arbitrary subproblem. For a given solution to the
master, the subproblem is solved heuristically. If the subproblem turns out to be infeasible,
problem-specific heuristic cuts are derived from the subproblem and added to the master.
Then the master is solved again and the process is repeated until the subproblem can be
solved.
In our case, the master problem is a vector container loading problem, denoted as BinAs-
sign in the following. It decides, which ULDs to use and how to assign items to them.
In the master problem all non-geometric constraints are handled. Our subproblem is a
three-dimensional knapsack problem, denoted as CPPack in the following. It needs to be
solved for each individual ULD and deals with all the geometric and physical aspects of
the placement of items inside the ULD. For cases, in which not all boxes can be packed
in the subproblem, we derive valid inequalities from the packable subset of items and add
them to the master problem before resolving it. We repeat this process until all ULDs
can be successfully packed in the subproblem. On top of the LBBD, we reduce the search
space heuristically to make the problem solvable within an acceptable time limit. We
denote this process as BDAP in the following.
Our approach implements all but two features of the APP introduced in Section 6.2. We
only omit item spacing restrictions between ULDs and item positioning restrictions within
the aircraft, because the ULDs do not have an assigned loading position yet and thus no
absolute coordinates within the aircraft are given. Nevertheless, both restrictions will be
modeled and thus be respected as ULD spacing constraints in the final weight and balance
step. We give an overview which constraints are handled by which part of our solution in
Table 9.6.
The remainder of this section is structured as follows. In Section 9.3.1 we introduce
the MIP formulation of the BinAssign master problem. In Section 9.3.2 we present the
constraint program of the CPPack subproblem. In Section 9.3.3 we describe the cut
generation and LBBD. Afterwards, we present two methods to reduce the search space
and to speed up our approach. In Sections 9.3.4 we introduce a decomposition by item
volume and in Section 9.3.5 the estimation of stowage loss for the items. At last, we recap
the overall procedure in Section 9.3.6.
98
9.3 Air cargo palletization
Table 9.6: Overview which constraints are handled in the master and subproblem
subject to
assign u,i ≤ amounti in u,i u ∈ U; i ∈ I (9.29)
load u ≥ in u,i u ∈ U; i ∈ I (9.30)
amounti = assign off
X
i + assign u,i i∈I (9.31)
u∈Ui
grs
X
limitu ≥ weighti assign u,i u∈U (9.32)
i∈I
X
volumeu ≥ volumei assign u,i u∈U (9.33)
i∈I
99
9 A sequential planning approach
Set/Parameter Description
Dg set of net weight limits applying to subsets of ULDs (d ∈ Dg )
G set of considered net weight categories (g ∈ G)
I set of item types to load (i ∈ I)
Q set of sorting criteria (q ∈ Q)
Qq value domain of sorting criterion q
U set of available ULDs (u ∈ U )
A⊆I ×I pairs of item types not allowed within one ULD (hi, ji ∈ A)
amounti number of items of type i
cliquei ∈ I item type that must be loaded completely to also load type i
costu ∈ R≥0 cost when using ULD u
limitnet
d ∈ R≥0 net weight limit for all items placed in uldsd for weight limit d
limitu ∈ R≥0 gross weight limit of ULD u
offloadi ∈ R≥0 penalty for each item of type i that is offloaded
penaltyq ∈ R≥0 linear penalty for sorting errors of criterion q
powq ∈ N exponential penalty for sorting errors of criterion q
sortq,i ∈ Qq group of item type i w.r.t. sorting criterion q
item
Q ⊆Q set of sorting criteria to group items by
Quld ⊆ Q set of sorting criteria to separate items by
Ui ⊆ U ULDs that item type i can be packed into
uldsd ⊆ U ULDs considered for net weight limit d
volumei ∈ R≥0 volume of each item of type i
volumeu ∈ R≥0 maximum usable volume of ULD u
weightgrs
i ∈ R≥0 gross weight of each item of type i
weightnet
g,i ∈ R≥0 weight of each item of type i w.r.t. weight category g
100
9.3 Air cargo palletization
Variable Description
assign u,i ∈ N number of items of type i loaded into ULD u
assign off
i ∈ N number of items of type i that are offloaded
in u,i ∈ {0, 1} is item i present in ULD u
load u ∈ {0, 1} 1 if ULD u is loaded
nq ∈ N number of penalties w.r.t. sorting criterion q
none i ∈ {0, 1} 1 if item i is completely loaded
sort q,u,e ∈ {0, 1} 1 if sorting value nq is present in ULD u
limitnet weightnet
X X
d ≥ g,i assign u,i g ∈ G; d ∈ Dg (9.34)
u∈uldsd i∈I
assign off
i = amounti none i i∈I (9.35)
none i = none cliquei i∈I (9.36)
in u,i ≤ sort q,u,sortq,i q ∈ Q; u ∈ U ; i ∈ I (9.37)
!powq
q ∈ Qitem
X X
nq = sort q,u,e (9.38)
e∈Qq u∈U
powq
q ∈ Quld
X X
nq = sort q,u,e (9.39)
u∈U e∈Qq
The objective, given in Equation (9.28), is to minimize the sum of cost of the used ULDs,
the penalties of offloaded items, and the penalties for violating the sorting constraints. In
the following we briefly describe the restrictions. A detailed explanation of the constraints
is given in Section 6.2.3.
Equation (9.29) tracks what item types are present in a ULD. According to Equa-
tion (9.30) items can only be assigned to a loaded ULD. Equation (9.31) models the
assignment of items to ULDs. Equations (9.32) and (9.33) ensure that the ULD’s weight
and volume capacity is respected. Complete shipment constraints are enforced by Equa-
tions (9.35) and (9.36). Equations (9.37) to (9.39) calculate the penalties with respect to
the different item and bin sorting criteria. Finally, Equation (9.40) models incompatibility
constraints between items that must not be placed in the same ULD.
101
9 A sequential planning approach
Set/Parameter Description
Cu set of contour planes of ULD u (hx, y, z, ai ∈ Cu )
I the items to pack (i ∈ I)
dimxi , dimyi , dimzi ∈ R≥0 dimensions of item i
disti,j ∈ R≥0 minimum required distance between items i and j
offloadi ∈ R≥0 penalty when item i is offloaded
roti ⊆ R allowed rotations of item i
rotationsi ⊆ R4≥0 rotated dimensions and load-bearing strength of item i
stackxi , stackyi , stackzi ∈ R≥0 maximum load-bearing strength of item i
startxu , startyu , startzu ∈ R start coordinate of ULD u
suppi ∈ R≥0 minimum supported area of item i (ratio)
udimzu , udimyu , udimxu ∈ R≥0 dimensions of ULD u
weightgrs
i ∈ R≥0 gross weight of item i
(xcg cg cg
u , yu , zu ) ∈ R
3
lower bound of the valid CG of ULD u
(xcg cg cg
u , yu , zu ) ∈ R
3
upper bound of the valid CG of ULD u
x uld
(←
− u,i , ←y uld
− u,i , ←z uld
− u,i ) ∈R 3
lower bound of item i start position inside ULD u
(←
−
x uld ←−uld ← −uld
u,i , y u,i , z u,i ) ∈ R3 upper bound of item i start position inside ULD u
x uld
(→
− u,i , →
−y uld uld
−z u,i )
u,i , → ∈R 3
lower bound of item i end position in ULD u
(→
−
x uld − uld →
→ − uld
u,i , y u,i , z u,i ) ∈R 3
upper bound of item i end position in ULD u
packing height tolerance
In the master problem we assigned items to bins with respect to the total volume, weight,
and further domain specific constraints. In this section, we present a constraint program-
ming model to determine the three-dimensional positions of the items inside the bin with
respect to the geometric and physical constraints. The model considers only one bin, i.e.,
it must be run for each bin from the solution of the master problem. We derive our model
from the mathematical formulation of the APM in Section 6.2.
Table 9.9 introduces the sets and parameters of the model and Table 9.10 presents its
decision variables. The model decides which of the items assigned to the bin are actually
packed pack i , at which position (xi , yi , zi ), and orientation (size xi , size yi , size zi ). Auxiliary
variables track the mechanical relations, like the actual load-bearing strength of the item
stack i , how much an item weighs including items stacked on top of it wi , if an item is
placed on the floor floor i , or if it supports another item base i,j . For the calculation of
the contact areas between two items we track the overlap along the x-axis oxi,j and z-axis
ozi,j as well as the total supported area of an item oi . Finally, to limit the bin’s center of
102
9.3 Air cargo palletization
103
9 A sequential planning approach
gravity (CG), we keep the total bin weight wu as well as the moment of force of all packed
items (mx , my , mz ).
Data: item dimensions dim∗i , load-bearing strength stack∗i , allowed rotations roti
Result: set of tuples of possible item dimensions and load-bearing strength
rotationsi
1 rotationsi ← ∅;
2 if XYZ ∈ roti then
3 add (dimxi , dimyi , dimzi , stackyi ) to rotationsi ;
4 end
5 if XZY ∈ roti then
6 add (dimxi , dimzi , dimyi , stackzi ) to rotationsi ;
7 end
8 if YXZ ∈ roti then
9 add (dimyi , dimxi , dimzi , stackxi ) to rotationsi ;
10 end
11 if YZX ∈ roti then
12 add (dimyi , dimzi , dimxi , stackzi ) to rotationsi ;
13 end
14 if ZYX ∈ roti then
15 add (dimzi , dimyi , dimxi , stackyi ) to rotationsi ;
16 end
17 if ZXY ∈ roti then
18 add (dimzi , dimxi , dimyi , stackxi ) to rotationsi ;
19 end
Algorithm 2: Preprocessing for generating all allowed dimensions and the corre-
sponding load-bearing strength of the vertical axis for an item
To simplify the modeling of item rotations, we use a preprocessing step to create a set of
tuples (x, y, z, s) containing all valid rotations of the item with its respective dimensions
(x, y, z) and the corresponding load-bearing strength (s) of the vertical dimension. To
assemble the set we iterate over all possible rotations. See Algorithm 2 for a pseudo-code
description of the preprocessing.
We define the CPPack constraint optimization model as follows:
X
minimize (1 − pack i )offloadi (9.48)
i∈I
subject to
104
9.3 Air cargo palletization
weightgrs 0
X
my = i (yi + yi ) pack i (9.63)
i∈I
weightgrs 0
X
mz = i (zi + zi ) pack i (9.64)
i∈I
weightgrs
X
wu = i pack i (9.65)
i∈I
2wu xcg
u ≤ mx ≤ 2wu xcgu (9.66)
2wu ycg
u ≤ my ≤ 2wu ycgu (9.67)
2wu zcg
u ≤ mz ≤ 2wu zucg
(9.68)
base i,j ⇔ pack i ∧ pack j ∧ (0 ≤ yj − yi0 ≤ ) i, j ∈ I (9.69)
oxi,j = base i,j max(0, min(x0i , x0j ) − max(xi , xj )) i, j ∈ I (9.70)
ozi,j = base i,j max(0, min(zi0 , zj0 ) − max(zi , zj )) i, j ∈ I (9.71)
oxi,j ozi,j
X
oj = j ∈ I (9.72)
i∈I
grs
X oxi,j ozi,j
wi = weighti + wj i ∈ I (9.73)
j∈I oj
oxi,j ozi,j > 0 ⇒ stack i oj ≥ wj i, j ∈ I (9.74)
max(0, xi − x0j , xj − x0i )2
(pack i ∧ pack j ) ⇒ dist2i,j ≤ i, j ∈ I (9.75)
+ max(0, zi − zj0 , zj − zi0 )2
x uld
(←
− u,i ≤ xi ≤ ←
−
x uld
u,i )∧
uld
y u,i ≤ ←
− uld
yi ≤ y u,i )∧
pack i ⇒ (←
− u ∈ U ; i ∈ I (9.76)
z uld
(←
− u,i ≤ zi ≤ ←
−
z uld
u,i )
x uld 0 →
− uld
(→
− u,i ≤ xi ≤ x u,i )∧
y uld 0 →
− uld
pack i ⇒ (→
− u,i ≤ yi ≤ y u,i )∧ u ∈ U ; i ∈ I (9.77)
uld 0 →
− uld
−z u,i ≤ zi ≤ z u,i )
(→
floor i ⇔ pack i ∧ (yi ≥ startyu + ) i ∈ I (9.78)
¬floor i ⇒ oi ≥ suppi size xi size zi i ∈ I (9.79)
base i,j ∈ {0, 1} i, j ∈ I (9.80)
105
9 A sequential planning approach
The objective, given in Equation (9.48), is to minimize the penalty from offloaded items.
As soon as a solution without offloaded items is found the subproblem is solved successfully
and the search can be stopped. In the following we briefly describe the constraint groups.
A detailed explanation of the constraints is given in Section 6.2.3.
Equation (9.49) selects a valid rotation and the corresponding load-bearing strength for
each item. It is implemented as a table constraint. Equations (9.50) to (9.52) set the
item start and end coordinates in relation to the item size. Equations (9.53) to (9.60)
ensure that the item is fully inside the bins contour shape, see the explanation along
Equation (6.20) and Figure 6.1. Furthermore, Equation (9.61) checks that packed items
do not overlap.
Equations (9.62) to (9.68) take care of a valid CG of the packed bin. Therefore, Equa-
tions (9.62) to (9.64) calculate the combined moment of force of all packed items for each
axis, Equation (9.65) calculates the weight of the packed bin, and Equations (9.66) to
(9.68) check that the CG, which is defined as the moment of force divided by the weight,
is within the allowed limits for each axis.
Equations (9.69) to (9.74) model the load-bearing of the stacked items. Equation (9.69)
detects if two items have suitable vertical positions to form a stack and Equations (9.70)
and (9.71) calculate the horizontal overlap along the x and z-axis. Equation (9.72) sums up
the overlaps to calculate the total supported area of an item. Equation (9.73) determines
the effective weight of an item, i.e., including the weight stacked on top of it. Finally,
Equation (9.74) ensures that the load-bearing strengths of all items are respected.
Beyond that, Equation (9.75) enforces the minimum spacing between two packed items,
if the items must not be placed in close proximity. Equations (9.76) to (9.77) check that
the items are placed within their positioning limits. Finally, Equation (9.78) and (9.79)
assure a minimum supported area for each item that is not placed on the floor of the
ULD.
Solution search To find valid packings we apply a depth first search on the constraint
model. Our branching strategy fixes the items in descending order of their volume. For
each item we first fix the variable pack i followed by the coordinates y, x, z and finally
select a rotation. In the left (right) branch pack i is set to 1 (0). For each axis the
branching decision is chosen in the same way. We create a set of points of interest (POI),
which contains promising coordinates for placing the considered item. The set contains
the end coordinates of the already placed items along the given axis plus the lower and
upper bounds to place the current item. See Figure 9.2 for an illustration. Crainic et
al. (2008) introduced a similar concept called Extreme Points. They show that placing
items at these points provides an efficient way to utilize the bin volume. However, in our
106
9.3 Air cargo palletization
points of interest: lb P1 P2 P3 ub
item to pack 2
1
3
bin size
Figure 9.2: Points of interest (POI) along a given axis. Positions considered for branching
are the end coordinates of all placed items (P1, P2, P3) as well as the lower (lb)
and upper bound (lb) to place the item into the bin.
case we refrain from just placing items at the chosen points because the irregular shaped
ULDs and the weight distribution constraints might allow or require different coordinates.
Instead, we will use the POI for branching.
Let p denote the integer domain variable of the starting coordinate the considered item
should be placed on an axis and P the set of POI along the same axis. In the left branch
we set p to its domain minimum:
p = min(p) (9.87)
If a solution is found that packs all items, the search is finished. For each found solution
that does not pack all items, we restrict the remaining search to solutions that strictly
pack more volume than the current solution.
If the search did not finish after a given time limit, we stop it and return the best solution
found so far. Furthermore, to save time during future iterations we cache all successfully
packed ULDs. Preliminary experiments have shown that a significant part of the BinAs-
sign solution does not change between the iterations of the master problem and thus a
lot of time in the subproblem can be saved by caching its results.
107
9 A sequential planning approach
search space. The assignment and the packing phase are then repeated. It can be easily
shown that this process will lead to a feasible packing after a finite number of iterations.
We note that this procedure has no optimality guarantee, because the constraint program
generating the cuts is a heuristic. The overall procedure is known as logic-based Benders
Decomposition (LBBD) and was first described by Hooker (2007).
In a setup similar to ours Pisinger and Sigurd (2007) applied LBBD to a two-dimensional
knapsack problem. They introduced a valid inequality to their one-dimensional knapsack
master problem if a set of items I 0 assigned to a bin could not be fully loaded in the
subproblem, which was a constraint satisfaction problem for two-dimensional packing.
Denoting xi as indicator that item type i is loaded, they add the inequality
|I 0 | − 1 ≥
X
xi (9.89)
i∈I 0
to the master problem and solve it again. In their setup each item type represents a single
item. Therefore, the inequality forbids the current unsuccessful solution in the next run
and forces the master problem to assign at least one item less into the bin. Repeating
this procedure leads to a feasible solution of the master problem and subproblem in
the end. However, this approach would be highly ineffective in our case, because our
problems at hand typically contain multiple items of the same type and the inequality
in Equation (9.89) does not cut off symmetric solutions. Furthermore, we deal with
heterogeneous bins, i.e., each inequality is only valid for one ULD type.
Therefore, we propose an adapted inequality. The underlying idea is the same: if only a
subset of the assigned items I 0 can be packed in a CPPack solution, we add cuts to the
BinAssign model, which forbid solutions dominating the packable subset. Let assign u,i
denote the number of items of type i assigned to a bin u in a BinAssign solution and
actual u,i denote the number of items that could be packed in the CPPack solution.
Technically, we forbid solutions dominating the set of actual u,i for item types where
actual u,i < assign u,i in the next LBBD iteration. Therefore, we add one cut for each
item type i where actual u,i < assign u,i . This cut allows to assign a number of actual u,i
items of type i to the bin. More than actual u,i items can only be packed, if at least one
of the other item types in I 0 is assigned strictly less than in the current solution. An
illustration of the generated cuts and how they interact is given in Figure 9.3. For item
types that could be packed completely, i.e., where actual u,i = assign u,i , no cut is added,
because packing more items of this type might be possible.
Next, we describe how to model the cut for an item type i that could not be packed
completely. Let cutj denote the allowed number of items of type j ∈ I 0 in the cut. For
the item type i we set cuti = actual u,i + 1 and for all other item types j ∈ I 0 we set
cutj = actual u,j . Let U 0 be the set of ULDs of the type that I 0 could not be packed into.
For each ULD u ∈ U 0 and item type j ∈ I 0 we introduce a new variable facet u,j indicating
that the item type j is packed with a number complying with the cut. Finally, we need to
make sure that at least one facet u,j holds for each ULD u. Formally, we add the following
heuristic cut to the BinAssign model:
assign u,j ≤ cutj − 1 + (1 − facet u,j )amountj j ∈ I 0; u ∈ U 0 (9.90)
u ∈ U0
X
1≤ facet u,j (9.91)
j∈I 0
108
9.3 Air cargo palletization
0 i 0 i 0 i
actual u,i assign u,i actual u,i assign u,i actual u,i assign u,i
Figure 9.3: Illustration of the created cuts: Two item types i and j are assigned to a bin
assign u,∗ times by the master problem, but can only be packed actual u,∗ times
by the subproblem. For each item we add a cut (left and center sketch) with
two facets (one for i and another for j). Thereby, the crossed out solutions
are cut off. The solution space for the BinAssign (right sketch) is reduced to
the current packable solution or to solutions where at least one item is strictly
less often packed into the bin.
On average our instances contain more than 700 items compared to a maximum of
100 items used by Pisinger and Sigurd (2007). Due to the large problem sizes, the runs
of the LBBD with the cut generation presented in the last section did often not termi-
nate in our preliminary experiments. To reach acceptable runtimes, we therefore further
decompose the problem to reduce the search space of each LBBD run.
The idea is to run multiple successive LBBD, which consider only a subset of the items. In
the beginning, we consider only large items and move to smaller items after valid packings
for the larger items have been found. Therefore, we introduce a sliding window of the item
volume starting with the largest present item volume. Items below the window volume
are considered in the master problem but not in the subproblems. As soon as a valid
packing of the larger items is found the window is moved towards smaller items and all
items larger than the window are fixed to their current bins. This way, we care for the
hardest to pack items first, which is also the usual approach in practice.
For the width of the window we introduce a parameter wsize. Let ub denote the upper
bound of the volume window, which is initialized to the largest volume of any item type
in I. The lower bound of the window is set to ub/wsize, which also becomes the upper
bound after moving the window. The general procedure of the sliding window is depicted
in Figure 9.4. We analyze suitable values for the wsize in our evaluation in Section 10.2.3.
One technical remark: For items larger than ub, we set the variable pack i in the CPPack
model to 1. Otherwise, the subproblem might offload an item already fixed to the ULD
in the BinAssign model.
109
9 A sequential planning approach
ub ub/wsize ub/wsize 2
item volume
3 move window
Figure 9.4: Search space reduction by sliding window. In the BinAssign (1) model only
items below the volume ub are free to be assigned. During the CPPack (2)
search only items larger than ub/wsize are considered. If the packing succeeds
for all ULDs, the window is moved (3) to the next smaller items.
110
9.4 Weight and balance
The question remains how to choose a suitable stowage loss for a given item. For items
outside the sliding window we assume no stowage loss. The larger items have already been
successfully packed to their assigned bin and smaller items are not considered for packing
yet, i.e., we have no information about their packing behavior. We estimate the stowage
loss of an item within the sliding window based on the frequency the item appears in the
cuts for a specific ULD type. Starting with the original item volume, we multiply the
parameter stowagev,i by a constant factor each time the item is part of a generated cut.
Hence, the more often an item occurs in an unpackable bin, the higher its stowage loss
gets. We reset the stowage loss of each item when the sliding window is moved forward,
i.e., when a packable assignment for all currently considered items is found. We analyze
suitable values for the stowage loss factor in our evaluation in Section 10.2.3.
9.4.1 Preprocessing
Before introducing the model itself, we present two preprocessing steps. These steps
derive required model parameters from the solution of the previous air cargo palletization
step.
111
9 A sequential planning approach
112
9.4 Weight and balance
Offload penalties Each item to load has a specific penalty that applies if it is offloaded.
As we only deal with ULDs during weight and balance, we sum up the penalties of the
items packed into each ULD to determine the offload penalty of the ULD.
Minimum spacing of ULDs During air cargo palletization we already dealt with in-
compatible items that have to be placed into separate ULDs. Some goods also require
not to be loaded into adjacent ULDs or to have a minimum spacing within the aircraft.
Accordingly, we calculate a minimum spacing between two ULDs as the maximum of all
pairwise minimum distances of items in the considered ULDs.
aoff off
fuel + ami mi
X X X X
minimize u xu + l + ops l + l ml (9.93)
u∈U l∈L l∈L l∈L
subject to
xoff
X
u = 1− xu,p,l u ∈ U ; l ∈ legsu (9.94)
p∈loadableu
X
1≥ xu,p,l p ∈ P;l ∈ L (9.95)
u∈U
hp, p0 i ∈ O; l ∈ L
X
1≥ (xu,p,l + xu,p0 ,l ) (9.96)
u∈U
X X
MAXl ≥ weightu xu,p,l l∈L (9.97)
u∈U p∈P
X X
limitn ≥ weightu fn,p xu,p,l n ∈ N; l ∈ L (9.98)
u∈U p∈P
wl = wOEW + FWl +
X X
weightu xu,p,l l ∈ L (9.100)
u∈U p∈P
BAOPT
l wl = ml + mlng+
l − mlng-
l l ∈ L (9.101)
f uel− lng-
fuel +
l = costl ml + costfl uel+ mlng+
l l ∈ L (9.102)
113
9 A sequential planning approach
Set/Parameter Description
L flight legs
N set of cumulative weight constraints in the aircraft (n ∈ N )
P loading positions in aircraft
U ULDs to load
adist
l ∈R cost of working time to move a ULD by one position after leg l
ami
l ∈R cost of additional fuel depending on the MI on leg l
aoff
u ∈R penalty when offloading ULD u
aon
l ∈R cost of one ULD loading operation after leg l
aun
l ∈R cost of one ULD unloading operation after leg l
Bp ⊆ P blocking positions when (un)loading a ULD at position p
ac
BA ∈ R longitudinal balance arm of the empty aircraft (OEW)
BAfuel
l ∈ R≥0 longitudinal balance arm of the aircraft’s fuel tanks
lat
BAp ∈ R lateral balance arm of loading position p
BAlng
p ∈ R longitudinal balance arm of loading position p
BAMAX
l ∈ R≥0 maximum allowed lateral CG imbalance on leg l
OPT
BAl ∈R optimal longitudinal CG on leg l
f uel−
costl ∈ R≥0 cost of extra fuel for forward CG deviations on leg l
costfl uel+ ∈ R≥0 cost of extra fuel for aft CG deviations on leg l
distp ∈ R≥0 distance between position and door
distp,p0 ∈ R≥0 distance between loading positions
fn,p ∈ R factor of loading position p for constraint n
FWl ∈ R≥0 fuel weight loaded on leg l
legsu ⊆ L legs the ULD will be on board
limitn ∈ R cumulative weight limit of constraint n
loadableu ⊆ P loading positions available for ULD u
MAXl ∈ R maximum loadable ULD weight on leg l
MAXCGl ∈ R aft limit of the longitudinal CG on leg l
minu,u0 ∈ R≥0 minimum distance of separation constraint
MINCGl ∈ R forward limit of longitudinal CG on leg l
O⊆P ×P set of overlapping loading positions (hp, p0 i ∈ O)
Rp ⊆ P set of loading positions that position p depends on
S⊆U ×U set of ULDs to separate (hu, u0 i ∈ S)
wOEW ∈ R≥0 operating empty weight (OEW) of the aircraft
weightu ∈ R≥0 total weight of ULD u
114
9.4 Weight and balance
Variable Description
fuel +
l ∈ R≥0 cost of required extra fuel on leg l
ml ∈ R≥0 longitudinal rotational moment of loaded aircraft on leg l
mlat-
l ∈ R≥0 left lateral imbalance from aircraft center on leg l
mlat+
l ∈ R≥0 right lateral imbalance from aircraft center on leg l
mlng-
l ∈ R≥0 forward deviation of rotational moment from optimal CG on leg l
lng+
ml ∈ R≥0 aft deviation of rotational moment from optimal CG on leg l
mi
ml ∈ R≥0 moment of inertia of the loaded ULDs on leg l
ops l ∈ R≥0 extra handling cost after leg l
ql,p ∈ {0, 1} 1 if loading position p needs to be cleared after leg l
un
rl,p ∈ {0, 1} 1 if a ULD is unloaded from position p after leg l
on
rl,p ∈ {0, 1} 1 if a ULD is loaded on position p after leg l
dist
rl ∈ R≥0 total ULD move distance after leg l
wl ∈ R≥0 total weight of loaded aircraft of leg l
xu,p,l ∈ {0, 1} 1 if ULD u is loaded at position p on leg l
xoff
u ∈ {0, 1} 1 if ULD u is not transported
ml ≤ MAXCGl wl l ∈ L (9.103)
ml ≥ MINCGl wl l ∈ L (9.104)
mlat+ BAlat lat-
X X
l = weightu p xu,p,l + ml l ∈ L (9.105)
p∈P u∈U
BAMAX
l wl ≥ mlat+
l + mlat-
l l ∈ L (9.106)
mmi (BAOPT BAlng 2
X X
l = weightu l − p ) xu,p,l l ∈ L (9.107)
u∈U p∈P
X X X
xu,p,l ≤ xu,p0 ,l p ∈ P ; l ∈ L (9.108)
u∈U p0 ∈Rp u∈U
hu, u0 i ∈ S; p ∈ P ; l ∈ L (9.109)
X
1≥ xu,p,l + xu0 ,p0 ,l
p0 ∈P :
distp,p0 <minu,u0
115
9 A sequential planning approach
rldist = un on
X
distp (rl,p + rl,p ) l ∈ L (9.116)
p∈P
ops l = aun un
+ aon on
+ adist dist
X X
l rl,p l rl,p l rl l ∈ L (9.117)
p∈P p∈P
fuel + dist
l , ops l , rl ∈ R≥0 l ∈ L (9.118)
ml , mlat-
l , ml
lat+
, mlng-
l , mlng+
l , mmi
l , wl ∈ R≥0 l ∈ L (9.119)
un on
ql,p , rl,p , rl,p ∈ {0, 1} l ∈ L; p ∈ P (9.120)
xu,p,l ∈ {0, 1} u ∈ U ; p ∈ P ; l ∈ L (9.121)
xoff
u ∈ {0, 1} u∈U (9.122)
The objective, given in Equation (9.93), is to minimize the sum of additional costs of
the flight. These costs may arise from offloaded ULDs, the extra fuel consumed due to
imbalance, extra handling operations to reload ULDs inside the aircraft between legs, and
a penalty proportional to the moment of inertia of the aircraft. In the following we briefly
describe the restrictions. For an in depth explanation and motivation of the constraints
we refer to Section 7.2.3.
The unique assignment of each ULD is modeled in Equations (9.94) and (9.95). The
mutual exclusion of overlapping loading positions is enforced by Equation (9.96). Equa-
tions (9.97) and (9.98) track the total and cumulative weights of loaded ULDs. Equa-
tions (9.99) to (9.104) model the extra fuel required due to the position of the longitu-
dinal CG of the aircraft. The lateral imbalance of the aircraft is restricted with Equa-
tions (9.105) and (9.106). Equation (9.107) models the moment of inertia of the aircraft.
Interdependent loading positions are enforced by Equation (9.108). Minimum required
distances of ULDs are handled within Equation (9.109). Finally, Equations (9.110) to
(9.117) model the required handling operations to load and unload the ULDs between the
respective legs of the flight.
9.5 Summary
In this chapter, we introduced a first solution approach for the Air Cargo Load Planning
Problem (ACLPP) denoted as SeqACLPP. It consists of a sequential four-step planning
pipeline that follows the current manual processes in operational practice.
For the first step, dealing with the aircraft configuration, denoted as VWAC, we presented
a MIP model that selects the number of ULDs of each type to build for each transport
segment of a flight based on aggregated booking data. The selected ULDs together with
the arrival times of the cargo and departure time of the flights build the input for the
next step.
To solve the second step, dealing with the build-up scheduling, denoted as RHBS, we
introduced a rolling horizon planning approach that determines the ULD build-up start
times for all flights departing during the planning horizon. In each round we apply a MIP
model solving one shift while also taking the demand of the next n shifts into account.
For the third step, dealing with the air cargo palletization, denoted as BDAP, we realized
a Logic-based Benders Decomposition approach. The LBBD master problem is a MIP
116
9.5 Summary
containing a vector container loading problem that assigns items to ULDs. In the master
problem all non-geometric aspects like weights, time, sorting and compatibilities are han-
dled. The LBBD subproblem, which is solved for each ULD individually, is implemented
as a constraint program and solves the three-dimensional knapsack problem. In it we
deal with all the geometric aspects as well as stacking and stability issues. If some items
cannot be packed into the ULD in a subproblem, we heuristically derive cuts, add them
to the master problem, and solve it again. To make the solution process come to an end
within a reasonable amount of time we introduced two extensions. The first reduces the
search space by considering only a part of the items during each iteration. The second
increases the virtual volume of items that repeatedly cause problems during the packing.
For the forth step, dealing with the weight and balance, denoted as UWAB, we presented
a MIP model that assigns the weighed ULDs to loading positions of the aircraft. The
model can handle flights with an arbitrary number of legs at once and minimizes the total
cost caused by additional fuel required due to aircraft imbalances and necessary reloading
operations at stop-over airports to access ULDs.
117
10 Evaluation
In this chapter, we describe our experimental setup and the achieved results. We im-
plemented the SeqACLPP approach introduced in Chapter 9 and evaluated it on the
benchmark instances described in Chapter 8. To evaluate its applicability for operational
practice, we compare the achieved solution quality to real-world solutions. Furthermore,
we survey the achieved solution quality for the introduced scenarios and discuss the re-
quired runtimes. Before we ran our experiments, we performed an extensive parameter
tuning to choose suitable configuration settings for the SeqACLPP approach.
This chapter is organized as follows: First, we describe our implementation and testing
environment in Section 10.1. Afterwards, we introduce our preliminary tests to determine
suitable parameter settings values for the SeqACLPP approach in Section 10.2. Finally,
we describe the results achieved with the SeqACLPP approach in Section 10.3.
We implemented all presented models in C++ using the Visual Studio 2012 compiler
with standard Release mode settings. All executables were built in 32-bit mode. As MIP
solver we employed Gurobi in version 7.0.1. Gurobi was set to use only a single thread,
to stop at a 1 percent MIP gap, and to spend 95 percent of the time with heuristics. All
other parameters remained at their default values. For the constraint program introduced
in Section 9.3.2 we used Gecode, an open-source constraint programming framework, in
version 4.4.0 with its standard branch and bound search.
We performed our experiments on two types of machines. The smaller machines had one
Intel Core i5-760 processor with 4 cores clocked at 2.8 GHz and equipped with 8 MB
cache. Each machine had 8 GB main memory and was running on a 64-bit Windows 7
Professional. The bigger machine had two Intel Xeon E5-2650 v2 processors each with
8 cores clocked at 2.6 GHz and equipped with 20 MB cache. The machine had 128 GB
main memory and was running on a 64-bit Windows Server 2012. In total we employed
six machines of the smaller and one of the bigger type. All machines were simultane-
ously executing as many solution processes as they had cores, i.e., all experiments were
performed under full load. Accordingly, the presented runtimes can be seen as a con-
servative benchmark originating from adverse conditions. The differences of the average
runtimes seen across all the used machines were less than 15 percent. Therefore, we omit
a breakdown of the runtimes by machines in the following.
10 Evaluation
Option Value
Aircraft configuration (VWAC)
estimated achievable volume utilization in percent 66
Build-up scheduling (RHBS)
planning horizon in shifts 3
MIP time limit in seconds 900
Palletization (BDAP)
size of the sliding window of item sizes 1.1
stowage loss increment factor 1.02
BinAssign initial time limit in seconds 300
BinAssign warm start time limit in seconds 60
CPPack time limit in seconds 1
Weight and balance (UWAB)
MIP time limit in seconds 300
Table 10.1: Parameters of the SeqACLPP and their values chosen for evaluation
120
10.2 Preliminary parameter tuning
2000
AKE
PMC
PGE
1500
# selected ULDs
1000
500
0
the observation that larger containers are easier to pack with a high utilization, because
they provide more options to arrange the items. To keep things simple, we assume the
same utilization for all ULD types in the following. Thereby, we slightly overestimate the
capacity of small ULD types and underestimate it for large ULD types.
Setting the utilization parameter to 55 percent in the SeqACLPP would not be a good
choice, because the utilization achieved by our palletization step (BDAP) introduced in
Section 9.3 is probably different from the one seen in practice. Therefore, we ran a second
test to survey the average achievable volume utilization of the BDAP. We ran this test on
the individual segments of the A-base flights without limiting the number of usable ULDs.
During these experiments an NLF of around 66 percent could be achieved. Therefore, in
the remainder of this work, we set the volume capacities of all ULD types to 66 percent
of their geometric volume, when running the VWAC.
The model solves for almost all instances in well under a second. Therefore, we set no
time limit for the MIP solver.
121
10 Evaluation
night
late
124.8%
early
costs relative to best solution
182
150
runtime per iteration [sec]
100
68
46.3
50
22.5
0 2.5
0
planning horizon
Figure 10.3: Runtimes per shift for different planning horizons
horizon of 0 is not useful. In this case it would not be possible to build ULDs of flights
departing early in a shift during the previous shift, which is necessary in practice.
As it is common practice we use three shifts per day: an early (06:00 to 14:00), late (14:00
to 22:00), and night (22:00 to 06:00) shift. For our experiments, we expect the cost of a
night shift to be 20 percent above the cost of the other shifts. An overview of the costs
of the selected crews per shift for different planning horizons is given in Figure 10.2. All
numbers are given relative to the best found solution, which had a planning horizon of
four shifts (32 hours).
As expected, shorter planning horizons give worse results, but from three shifts on the
quality is nearly constant. Interestingly, the number of late shifts for a planning horizon
of one shift is almost twice as high as for all others. We attribute this to two effects. First,
instead of the more expensive night shifts the model selects more late shifts. Accordingly,
a planning horizon of 1 shift shows the lowest number of night shifts. The second effect is
that, with a planning horizon of one shift, flights departing during the late shifts cannot
be built during the night shift before, although a significant amount of their cargo has
122
10.2 Preliminary parameter tuning
already arrived. But, during the night there are only a few departing flights in the schedule
of the A-base scenario and thus the selected crews often cannot be fully utilized.
Besides the solution quality, we are interested in the runtime of the RHBS to decide
about a suitable planning horizon. Remember from Figure 9.1, that we solve the Build-
up Scheduling Model (BSM) in a rolling horizon approach, i.e., we execute it successively
for each shift with a lookahead of a planning horizon of n shifts. Figure 10.3 shows the
average runtime required for one BSM run for different planning horizons. We stopped
the search after 900 seconds or when the MIP gap became smaller than 1 percent. As
one would expect the runtime grows exponentially for larger planning horizons. We note
that for planning the shifts of one week we must run 21 iterations, i.e., planning with a
48 hours horizon takes more than 1 hour.
Given the above insights into solution quality and runtime we select a planning horizon
of 3 shifts, or 24 hours respectively, for the remainder of this work.
10.2.3 Palletization
The Logic-based Benders Decomposition (LBBD) solving the palletization (BDAP), which
we presented in Section 9.3.3, has five parameters for which we need to identify suitable
values. First, there is the size of the sliding window of item volume. During each iteration,
only items within the window are considered for assignment and packing. Larger items
have a fixed assignment while smaller items are not considered during packing.
The second parameter is the stowage loss factor. After each failed ULD packing, i.e.,
where some items could not be placed into the assigned ULD, we multiply the virtual
volume of all items assigned to this ULD by an expected stowage loss factor. Accordingly,
in upcoming BinAssign iterations, less of these items will be assigned to the ULD and
thus it should become easier to find a feasible packing.
The other parameters limit the runtime: a cold start and warm start time limit for the
BinAssign MIP model and a time limit for the CPPack search.
To find suitable parameter settings with tolerable effort we randomly selected 30 flights
from our datasets, 5 of each scenario, and solved those flights for different parameter
values. We repeated the experiments three times and show the average values in the
following. In the remainder of this section we present the achieved results and justify our
choice of parameters.
First, we analyze the effects of different sizes of the sliding window of item volume. As
introduced in Algorithm 3, the window size determines the number of successive runs of
the LBBD to process all items, starting with the biggest items in the first run and then
moving to smaller items. The window during an LBBD run is defined as (ub/wsize, ub]
for a window size wsize and upper bound ub. As stated above, only items with a volume
within the window are considered for the bin assignment and packing. Thus, the window
size determines the number of items handled during each iteration. A larger window size
leads to larger subproblems in each iteration, but also fewer shifts of the window are
123
10 Evaluation
12000
10356 10391
10000 9692 9905
9563 9721
9119
avg. penalty per instance
8000
6000
4000
2000
0
necessary until all items have been covered. On our sample instances we evaluated the
SeqACLPP approach for varying values of wsize ranging between 1.05 and 2.5. In the
following, we discuss the impact of the different values on solution quality and required
effort.
The first thing we note is that there is no clear relationship between the window size and
solution quality. Figure 10.4 shows the average offload penalty of our sample instances
for the different sizes. All values are within a range of 12 percent. One explanation of
this effect might be the large number of items in the instances. Even if only a part of the
items is considered at each sliding window position, the remaining solution space seems
to contain many alternative solutions of similar quality.
As one would expect, the required number of total LBBD iterations, i.e., the sum of iter-
ations of all LBBD runs, of Algorithm 3 decreases with a larger window size. Figure 10.5
shows the average total LBBD iterations it takes to solve the sample instances for dif-
ferent window sizes. However, this decrease is not linear. Larger window sizes require
less LBBD runs with different volume windows, but lead to more infeasible packings and
thus more LBBD iterations in each run for adding cuts before a feasible packing is found.
Figure 10.6 presents the average number of iterations the LBBD takes for a run before
the packings can be solved successfully.
Furthermore, there is a tradeoff between window size and solution runtime, with a window
size of 1.25 showing the shortest runtimes. Figure 10.7 shows the respective average
runtimes. At small window sizes, the high number of total LBBD iterations lead to high
runtimes. Larger window sizes also increase runtimes, because more items have to be
considered in the BinAssign model and thus each iteration takes longer. Given the results
above, we choose a value of 1.1 as the size of the sliding window in the remainder of this
work. This setting showed the lowest penalty and the second best runtimes.
Next, we analyze the impact of different settings for the stowage loss factor on solution
quality and effort. As introduced in Section 9.3.1, in the LBBD master problem, the
124
10.2 Preliminary parameter tuning
350
309
300
avg. iterations per instance
250
193
200
150
118
95
100
86 86 83
50
0
5.67
avg. iterations per window position
4.76
5
3.97
4
3.27
3
2.3
2
1.58
1.29
1
0
Figure 10.6: Average LBBD iterations per run for different window sizes
2000
1976
avg. runtime per instance [sec]
1680
1616
1554
1500
1351
1303
1198
1000
500
0
125
10 Evaluation
12000
10060
10000
9823 9756 9594
9510 9566
9119
avg. penalty per instance
8000
6000
4000
2000
0
BinAssign model, we solve a vector container loading problem with respect to item volume
and weight. If the assignment result cannot be packed by the CPPack subproblem, we
assume that the assigned items incur some stowage loss. To overcome this in the next
LBBD iteration, we increase the item volume considered in the master problem by a factor
stow. The more often an item occurs in unpackable bins, the higher its stowage loss gets.
Accordingly, larger factors should result in less required iterations before a feasible three-
dimensional packing can be found. On our sample instances we evaluated the SeqACLPP
approach for varying values of stow between 1.0 and 1.5, representing a volume increment
between 0 and 50 percent for each failed packing attempt.
As the first result we note, similar to the window size, that there is no clear relationship
between the stowage loss factor and solution quality. Figure 10.8 shows the average offload
penalty of our sample instances for different factors. As for the window size, we assume
that this effect stems from the large number of items in the instances. Even if an increased
stowage loss cuts of promising solutions, the remaining solution space seems to contain
many alternative solutions of similar quality.
The required number of total LBBD iterations, i.e., the sum of iterations of all LBBD
runs, of Algorithm 3 decreases slightly for higher stowage loss factors. Figure 10.9 shows
the average number of total iterations it takes to solve the sample instances. For small
values between 1.01 and 1.05 the number of required iterations does not change at all.
The same picture shows for the average number of iterations the LBBD takes for a run,
i.e., before the packings can be solved successfully, which is shown in Figure 10.10. Again,
higher values lead to less iterations, because the stowage loss rises faster.
Regarding the total solution runtime, we see a clear drop from more than 1,600 seconds to
around 1,300 seconds when the stowage loss factor is used. For larger factors the runtime
decreases slowly in the same way as the number of required iterations. Figure 10.11 shows
the respective average runtimes. According to the found results, we choose a value of 1.02
for the stowage loss factor in the remainder of this work.
126
10.2 Preliminary parameter tuning
201
200
193 193 193
184
177
167
avg. iterations per instance
150
100
50
0
Figure 10.9: Total LBBD iterations for different stowage loss factors
1.67
1.58 1.58 1.6
1.51
avg. iterations per window position
1.5
1.44
1.35
1.0
0.5
0.0
Figure 10.10: Average LBBD iterations per run for different stowage loss factors
1656
1500
avg. runtime per instance [sec]
1344
1288 1303
1249 1254
1132
1000
500
0
127
10 Evaluation
80
share of instances [in %]
60
40
20
0
10 20 30 40 50 60 >60
Time limits
We introduce three time limits to restrict the runtime of the BDAP step. The first is the
runtime of the initial cold start run of the BinAssign model for a transport segment. As
the MIP is started without an initial solution, it typically takes longer to reach a small
MIP gap. Therefore, we set a time limit of 300 seconds for this first run. The following
warm start iterations use the previous solution and reach small MIP gaps much faster.
The distribution of runtimes seen in the experiments above is shown in Figure 10.12. We
set the time limit of successive runs of the BinAssign model to 60 seconds.
Furthermore, we need to limit the runtime of the CPPack search. In our experiments
above, the CPPack model showed to be extremely fast for most bins. However, sometimes
the search gets stuck and does not return any solution. As the model is run very often,
we set a short time limit of 1 second for the branch and bound search. Figure 10.13 shows
the distribution of unsolvable bins within a 1 second time limit across the instances. In
almost all instances less than 10 percent of the bins were unsolvable within the time limit.
From our point of view this is acceptable, especially because the unsolvable bins will add
a cut to the BinAssign and might be tested again in the next iteration with a similar but
smaller set of items. Thus, we expect to lose not much solution quality by a short time
limit.
128
10.3 Results of the sequential approach
25
20
share of instances [in %]
15
10
5
0
1 2 3 4 5 6 7 8 9 10 >10
Figure 10.13: Distribution of the share of unsolvable bins per instance for CPPack with a
time limit of 1 second (in %)). To be read as: in 24 percent of all instances
between 1 and 2 percent of the bins could not be solved within 1 second.
60
50
share of instances [in %]
40
30
20
10
0
Figure 10.14: Distribution of runtimes of the weight and balance step (in sec)
small MIP gaps, see Figure 10.15. Around 70 percent of them have a gap smaller than
10 percent. Therefore, in our evaluation we keep the initial time limit of 300 seconds.
We evaluated our approach on the two datasets introduced in Section 8.3. First, we relate
our results to actual load plans seen in practice to check the plausibility of our solutions.
Afterwards, we discuss the results achieved for the different scenarios.
129
10 Evaluation
70
60
share of instances [in %]
50
40
30
20
10
0
10 20 30 40 50 60 70 80 90 100
Figure 10.15: Distribution of the remaining MIP gap of flights reaching a time limit of
300 seconds for the weight and balance step (in %)
Real-world SeqACLPP ∆
solutions approach
WLF 0.495 0.493 -0.4%
GLF 0.327 0.322 -1.5%
NLF 0.546 0.662 +21.2%
UNITS 23.000 15.685 -31.8%
SPLIT 0.283 0.201 -29.0%
DISP 3.100 2.585 -16.6%
MIX 0.173 0.116 -32.9%
CREWS n/a 211 n/a
Table 10.2: Performance of the SeqACLPP approach compared to results seen in practice
Comparison to practice
We compare our results of the real world dataset base scenario (A-base) with the actual
solutions created by load planners and palletization workers in practice. Table 10.2 gives
an overview of the respective performance indicators.
With regard to the aircraft utilization indicators, the weight load factor (WLF) and
volume gross load factor (GLF) cannot be further improved, because the given flight
instances contained only the transported items of the real flights. Some items, representing
around 0.4 percent of the weight and 1.5 percent of the volume, that were loaded in
practice were offloaded by our approach. For these cases we identify three reasons. First,
the workers in practice are more flexible than the SeqACLPP approach. For example,
they can postpone a ULD to wait for a late item or add dunnage material to provide an
even surface for a large and light item. Second, there might be errors in the booking data
that made the real packing easier. Maybe, some items in reality were smaller than in the
booking data or one large booked item turned out to be a set of smaller items. Third,
130
10.3 Results of the sequential approach
(a) Main deck PMC pallet (NLF: 77%) (b) Lower deck PMC pallet (NLF: 72%)
(c) Main deck PGE pallet (NLF: 68%) (d) Lower deck AKE container (NLF: 80%)
some items loaded in practice were offloaded by our approach in favor of saving another
ULD position.
However, in our solutions the average volume net load factor (NLF) of the ULDs could be
improved from 54.6 percent seen in practice to 66.2 percent. This represents an increase in
the achieved packing density of more than 21 percent. Example packing patterns for the
considered types of ULDs and the related volume utilization are shown in Figure 10.16.
In the same manner the average number of built ULDs for each flight (UNITS) decreased
by more than 31 percent. Part of this can be attributed to the higher packing density.
The remainder results from choosing larger ULDs, especially the use of standard PMC
pallets instead of half-sized AKE containers on the lower deck. The latter shows that
the SeqACLPP approach is able to tailor its solutions to the assembly cost of the ULDs.
For the benchmark instances these cost were only roughly estimated and thus the results
differ from practice.
The indicators representing handling effort could all be improved considerably. The ratio
of shipments that are split onto multiple ULDs (SPLIT) could be reduced from 28.3 per-
cent to 20.1 percent. Furthermore, the average number of ULDs a splitted shipment was
distributed across (DISP) could be reduced from 3.1 ULDs to 2.6 ULDs. To grasp the
total effect of the SPLIT and DISP changes on the transport effort within the air cargo
terminal, we calculate the total number of transports between the warehouse and the
131
10 Evaluation
It represents the average number of warehouse to ULD workstation transports for splitted
shipments and a single transport for non-splitted shipments. Compared to the current
practice, our results realize a reduction of transports of more than 17 percent.
The ratio of ULDs that contain both standard and premium shipments (MIX) could
be reduced from 17.3 percent to 11.6 percent. Together with the reduction of handled
UNITS, this results in around 2 ULDs less per flight that would need preferred express
handling and thus incur higher cost.
With respect to the required crews, we cannot make any statement. In practice, the
build-up crews are also used for other tasks, for example, in the break-down of incoming
ULDs, and thus no specific number of build-up crews was available to us.
Besides the numbers, we also discussed individual load plans with the respective experts
of our industrial partner who found the results to be reasonable. In general, we can say
that the SeqACLPP approach works and provides solutions showing better performance
values than the current practice.
Scenario evaluation
As the second step of our evaluation, we analyze the results of the SeqACLPP approach
for the respective scenarios defined in Section 8.3.3. Table 10.3 shows the achieved per-
formance values.
In the base and fast scenarios of both datasets the achieved utilization with respect to
the aircraft weight (WLF) and volume (GLF and NLF) capacity is pretty stable. Almost
all items are loaded and an NLF between 66.1 percent and 66.8 percent is achieved. In
the high-load scenarios much more cargo has to be offloaded, because all the flights are
overbooked. Nevertheless, our approach utilizes more than 96 percent of the aircraft
weight capacity (WLF) and fills on average 69.5 percent and 70.9 percent of the physical
volume of the ULDs (NLF), which is slightly better than in the base and fast scenarios.
According to practitioners, utilizing 70 percent of the volume of a single ULD is already
a very good result.
132
10.3 Results of the sequential approach
The aircraft type used in our experiments had a standard configuration of 3 PGE, 20 main
deck PMC, and 10 lower deck PMC ULDs, totaling 33 units. Accordingly, almost all load-
ing positions are used in the high-load flights. Therefore, we conclude that the SeqACLPP
approach is able to find good solutions, which are also well-balanced with respect to the
weight and volume capacities of the aircraft.
The indicators representing handling effort, namely SPLIT, DISP, and MIX, are simi-
lar across all scenarios, indicating that these objectives can also be robustly improved
compared to the current manual practice.
The number of crews employed in the scenarios correlates with the built ULDs. Crew
productivity for all scenarios ranges between 5.0 and 6.9 ULDs per crew and shift. The
fast scenarios show the lowest productivity with 6.1 and 5.0 ULDs per crew and shift.
The reason here clearly is the unleveled workload stemming from the short transfer times
of the cargo. During rush hours a high number of crews is needed, but before and after
the crews are idling.
Next, we look at the total costs achieved by the SeqACLPP approach. Table 10.4 shows
the respective average values for each scenario. A significant part of the costs stems from
the penalties of offloaded items (PEN). While this is reasonable for the overbooked high-
load scenarios, this result is not satisfactory for the base and fast scenarios. Analyzing
the results in detail, we identified two primary reasons for offloaded items.
First, during aircraft configuration the capacity to accommodate large items is overes-
timated. We only consider the item volume and weight here, neglecting the real item
dimensions. Thereby, the model is too optimistic when selecting ULDs for large items.
Later, during palletization these items cannot be combined on ULDs and some of them
must be offloaded. In the fast scenarios, we see less offloads, because the ULDs are
generally built later and therefore more combinations of items are possible.
The second reason causing significant offloads in our solutions are too heavy ULDs created
by the palletization step for which no loading position in the aircraft can be found during
the weight and balance step. While the individual weight limit of a ULD type is quite
high, for example, a main deck PMC pallet can weight up to 6,800 kg, the possible loading
positions for heavy ULDs are very limited. Only four of the 26 positions on the main
deck of our sample MD11F aircraft can handle this weight. Furthermore, the cumulative
load limits of adjacent positions reduce the solution space significantly. For example,
only two of the four positions mentioned above can be used simultaneously for such
heavy ULDs without violating the maximum running load along the aircraft fuselage. On
some positions the combined weight limit of two adjacent ULDs is less than 125 percent
133
10 Evaluation
Figure 10.17: Example weight distribution on a freighter main deck. The pink bars at
both sides indicate the admissible range and the actual the center of gravity.
Lighter ULDs are colored green, heavier ones red. For example, the ULD to
the right only weights 2,485 kg but is close to the weight limit at its position
of 2,700 kg.
of the individual weight limit of each position. Therefore, it is hard to come up with
general weight limits for individual ULDs. This observation coincides with the current
planning practice. Experienced load planners have a loading position in mind for each
planned ULD and partly take cumulative weight limits into account to reduce the risk
of ULD offloads later. However, this is a mostly manual approach, heavily depending
on the individual experience of the load planner, and other aspects adding additional
complexity like weight distribution or the relocation of ULDs between the flight legs are
not systematically considered.
Besides the high offload penalties, the achieved load plans of the SeqACLPP approach
are already very good. The additional fuel cost due to aircraft imbalances (FUEL) for the
base and fast scenarios is almost negligible for practical setups. In the high-load scenarios
some extra fuel burn seems to be inevitable. As the optimal center of gravity (CG) of our
sample MD11F aircraft is closer to the aft of the aircraft, there are 14 loading positions
in front of and only 10 behind the point of the optimal CG. As we operate close to the
aircraft weight limit in the high-load scenarios, most loading positions carry significant
weight. Consequently, this leads to a forward CG increasing the fuel burn. An example of
the weight distribution and aircraft CG on a highly booked flight is given in Figure 10.17.
Similarly, the amount of conducted reloading operations (OPS) in the presented results
is significantly lower than in current practice. We give an overview of the distribution of
reloading operations in Table 10.5 and describe the actual reloading operations of a sample
134
10.3 Results of the sequential approach
(a) After leg 1/3: Four ULDs (white) need to be unloaded. Therefore, three additional ULDs
must be temporarily removed.
(b) After leg 2/3: Eight ULDs (light blue) need to be unloaded. One ULD must be temporarily
removed and is reloaded at another loading position to reduce lateral imbalance.
Figure 10.18: Loading patterns on a freighter main deck over a three-leg flight. Colors
indicate the port of unloading of the ULD: after the first leg (white), the
second (light blue), or third (dark blue). The large arrows show the position
of the cargo door. The pink bars at both sides indicate the admissible range
and the actual the center of gravity.
135
10 Evaluation
Handling Legs
operations 1 2 3 4
0 100% 67% 31% 0%
1 0% 19% 15% 0%
2 0% 8% 33% 0%
3 0% 4% 18% 0%
4 0% 1% 3% 33%
≥5 0% 1% 0% 67%
flight in Figure 10.18. On most flights with two or three legs, up to two reloaded ULDs
were sufficient. Instances with four legs, always exhibited reloading operations. During
these flights, it is hardly possible to place ULDs destined for the last stop without blocking
ULDs that need to be unloaded at earlier stops. Even if it would be possible, the caused
shifts of aircraft CG at each stop might already justify the cost of the reloading operations
to save fuel. The highest number of reloading operations we found on any resulting flight
was 13. Therefore, we argue that the model finds a good tradeoff between the extra fuel
burned due to aircraft imbalances and the effort to establish a lower imbalance between
two legs. This poses a significant improvement to the current practice, where sometimes
the complete aircraft is unloaded and reloaded again at a stop-over airport.
At last we give an overview of the computational effort required to solve the instances in
the different scenarios, see Table 10.6. Solving a flight of the base or fast scenario takes on
average 14 minutes (806 seconds). Assuming that load planning starts around 24 hours
before a flight, this amount of time is acceptable in practice to create good initial load
plans. However, the shown runtimes are too long to be used in an interactive process with
the load planner. Therefore, our solution is not yet suitable for handling frequent updates
due to changed booking data or manual interventions by the load planner. Runtimes for
the high-load scenarios are even longer and take on average 37 minutes (2,222 seconds)
per flight. The main cause is that the generated cuts cannot effectively reduce the search
space of the overbooked flights as there are a lot of alternative items and thus many
LBBD iterations are necessary until a feasible packing is found. An easy way to start
speeding up the solution approach is to introduce parallelization. All our experiments
were performed with a single thread. Nevertheless, our BDAP approach can easily be
parallelized at multiple points. For example, the branch-and-bound part of the BinAssign
136
10.4 Summary
MIP can be multi-threaded with current MIP solvers. Also, the CPPack search can be
run independently for each ULD.
10.4 Summary
In this chapter, we evaluated the SeqACLPP approach with respect to solution quality
and runtime by solving the benchmark instances from Chapter 8.
To find suitable parameter settings for the planning steps, we described a set of preliminary
experiments. We ran those experiments on a subset of the benchmark instances, showed
how different settings impact solution performance, and chose suitable values for our
general evaluation. Nevertheless, we expect that in other setups, i.e., with respect to the
structure of the shipments, aircraft, or flight plans, different parameters might produce
better results and the presented experiments should be rerun to identify them.
In our main evaluation we compared the benchmark results to actual load plans seen in
practice. We found that the SeqACLPP approach performs well and is able to improve
most performance indicators. The average packing density of the ULDs (NLF) can be
improved by more than 21 percent compared to current practice. In parallel, the item
sorting (SPLIT and MIX) can be improved by around 30 percent, which results in less
and cheaper handling operations. In our results, the absolute cost for extra fuel due to
aircraft imbalance and reloading operations is very low for most flights.
On many flights of the high-load scenarios the aircraft capacity can be fully utilized.
However, in the base and fast scenarios sometimes items are offloaded, although there is
enough aircraft capacity. We identified two causes. In the first case not enough ULDs
were selected during the aircraft configuration. At this step the items are not individually
considered and therefore the capacity is overestimated. In the second case a set of heavy
ULDs, which were created at the palletization step, cannot be placed together in the
aircraft during the weight and balance step. Although the individual weights of the
ULDs are fine, no combination can be found that meets all the cumulative structural load
limits of the aircraft. We address these issues in the next chapter.
The average solution runtimes range between 13 and 38 minutes per flight. In practice this
is acceptable to provide non-interactive initial solutions for the load planners. However,
it is too slow for interactive usage and a further speed up, for example by parallelization
would be necessary.
137
11 Coordinated planning approaches
In the evaluation of the SeqACLPP approach, see Section 10.3, we discovered an unsatis-
factory high amount of offloaded cargo although loading positions in the aircraft remained
free. During the SeqACLPP approach, we executed each of the four planning steps aircraft
configuration (VWAC), build-up scheduling (RHBS), palletization (BDAP), and weight
and balance (UWAB) individually. In each step we solely considered the constraints and
objective of the respective step. Thereby, we aimed for a local optimum of each step at
the risk of producing results that do not fit well with the successive planning steps. We
identified two typical cases.
First, there were not enough ULDs selected during the VWAC step to accommodate large
items. Second, the ULDs built during the BDAP step had a weight distribution that often
did not fit into the aircraft in the UWAB step. In effect some of the ULDs and items
could not be transported.
In this chapter, we introduce and evaluate two methods to avoid such local optimization
by introducing coordination between the planning steps. The basic idea is to already
respect constraints of later planning steps during the solution of an earlier step, here the
aircraft configuration.
At first, we examine the integration of palletization aspects into the aircraft configuration
in Section 11.1. After that, we incorporate weight and balance aspects into the aircraft
configuration in Section 11.2.
and the BinAssign model presented in Section 9.3.1. The objective stays the same as in the
original aircraft configuration step, but the added constraints of the bin assignment must
be fulfilled. By doing this we still do not create three-dimensional load plans during the
SAC. The items are only assigned to a ULD considering the ULD capacity, required ULD
types, and item incompatibilities. Thereby, we expect to get a more realistic estimate of
the number of required ULDs.
Besides the aircraft configuration step, all other steps remain the same as in the SeqA-
CLPP approach, presented in Chapter 9. In particular, during palletization items must
not be packed into the same ULD to which they were assigned by the SAC model. In the
following we denote the SeqACLPP approach with the new SAC aircraft configuration
step as SeqACLPP-SAC.
Evaluation
To evaluate the SeqACLPP-SAC approach, we repeated the experiments introduced in
Section 10.3. We give an overview of the absolute performance indicators achieved in
Table 11.1 and their relative deviation compared to the SeqACLPP approach in Table 11.2.
There are only minor variations in the utilization indicators. Most notably, the number of
built ULDs (UNITS) increased by 2.5 percent across all scenarios. However, this does not
mean that the ULD capacity increased. More often, PMC ULDs were replaced by multiple
140
11.1 Shipment-based aircraft configuration
smaller AKE ULDs to better meet the demand for item sorting and incompatibilities. By
using these additional ULDs, around 0.4 percent more of the shipment weight (WLF)
and 0.5 percent more of the shipment volume (GLF) can be loaded. The ratio of ULDs
containing both standard and express items (MIX) can be reduced significantly in most
scenarios. We attribute this to the item sorting constraints, which are now respected
during the aircraft configuration. Ideally, they affect any solution to contain enough
selected ULDs for both sets of standard and express shipments.
With respect to the cost, the SeqACLPP-SAC approach performs better than the SeqA-
CLPP approach and can reduce the total cost by 5.7 percent. We give an overview of the
absolute cost values achieved by the SeqACLPP-SAC approach in Table 11.3 and their
relative deviation compared to the SeqACLPP approach in Table 11.4.
The increase of the load factors seen above leads to 13.5 percent less offload penalties
(PEN). Interestingly, for the scenarios with the highest improvements (A-base, A-fast,
B-base) the cost of the chosen ULDs (UNITS) could also be reduced. Here, the SAC
model produces a better fit of ULDs for the items than the VWAC model. The changes
of costs for extra fuel (FUEL) and handling operations (OPS) fluctuate from scenario to
scenario. As the absolute values of these costs are rather small, the impact of the relative
changes appears larger than it is. Most of the changes were caused by a single flight
in the respective scenario. Altogether, the SeqACLPP-SAC approach could significantly
improve the cost of 3 of the 6 scenarios. However, the overbooked scenarios (A-high,
B-high) could not be improved as the utilization here is already very high.
At last, we analyze the computational effort of the SeqACLPP-SAC approach. We distin-
guish two separate parts: the runtime of the SAC model itself and the change of runtime
of all the planning steps. We give an overview of the runtimes for each step and scenario,
as well as the change compared to the SeqACLPP approach in Table 11.5.
141
11 Coordinated planning approaches
50
46.3
40
share of instances [in %]
31.1
30
20
13.4
10
4.7
3.2
0.3 0.9
0
Figure 11.1: SAC MIP gap distribution after 30 seconds runtime (rounded up)
142
11.2 Weight-and-balance-based aircraft configuration
The runtime of the VWAC model, which we presented in Section 9.1, was negligible. For
almost all flights, the model solved in well under a second. The SAC model on the other
hand takes much longer to be solved to optimality. Therefore, we stop the MIP search
after 30 seconds. Around 10 percent of the instances can be solved down to a 1 percent
MIP gap until the time limit is reached. The distribution of the resulting MIP gaps of
the remaining flights is shown in Figure 11.1. Of those flights about 90 percent can be
solved with a MIP gap of less than 15 percent.
The computational effort required to solve the palletization (BDAP) and weight and
balance (UWAB) steps does not change substantially. The number of LBBD iterations
during palletization slightly changes for each scenario but on average it stays the same.
The average runtime across all scenarios increases by 0.8 percent, a deviation well within
measuring tolerance.
Accordingly, we can say that the incorporation of palletization aspects into the aircraft
configuration step works and can be done with acceptable computational effort, albeit its
effects on solution quality are limited.
143
11 Coordinated planning approaches
Set/Parameter Description
capwgt
p ∈ R≥0 weight capacity at loading position p
capvol
p ∈ R≥0 volume capacity at loading position p
costp ∈ R handling cost for a ULD on loading position p
subject to
wl = wOEW + FWl +
X
wp (11.12)
p∈P
The objective, given in Equation (11.1), minimizes the total cost from the penalties of
offloaded cargo weight and volume, the used ULDs, and the extra fuel cost caused by
144
11.2 Weight-and-balance-based aircraft configuration
a suboptimal center of gravity (CG) of the aircraft. Equations (11.2) and (11.3) make
sure that the segment demand weight and volume is distributed onto the loading posi-
tions or is marked as offloaded. Equation (11.4) marks a loading position if it is used for
any transport segment. Mutual exclusions of overlapping loading positions are enforced
by Equation (11.5). The usage order of interdependent loading positions is respected
by Equation (11.6). Equation (11.7) enforces that weight is only placed on used load-
ing positions and that the individual weight limit of each loading position is respected.
Equation (11.8) collects the weight on each loading position irrespective of the allot-
ted transport segment. Equation (11.9) limits the total weight loaded into the aircraft.
Equation (11.10) ensures that the cumulative weight limits of the loading positions hold.
Equations (11.11) and (11.12) calculate the longitudinal balance arm and the total weight
of the loaded aircraft. Both values are input variables for Equations (9.101) to (9.107) to
calculate the extra fuel required due to a suboptimal CG of the loaded aircraft.
After the aircraft configuration step, we insert the chosen ULD weights as target weights
for the ULDs to build during the palletization step. Therefore, we add a target weight
parameter targetu for each selected ULD u. Given this parameter, we add the following
constraint to the BinAssign model from Section 9.3.1 to calculate the excess weight dev u
for each ULD u:
weightgrs
X
targetu ≥ i assign u,i − dev u u∈U (11.16)
i∈I
We do not consider negative deviations, i.e., when the ULD is too light. First, because
it would generally not limit the loadability of the ULD. Second, these cases already lead
to penalties at other parts of the model. If a ULD weight is lower than the target weight
but the same amount of total weight is transported on all ULDs, then another ULD will
be heavier than its target weight and incur penalty cost. Or, if a ULD weight is lower
than the target weight because some items are offloaded, this also leads to offload penalty
cost.
At last, we add the deviation from the target weight as cost to the objective of the bin
assignment model:
dev 2u
X
Equation (9.28) + α (11.17)
u∈U
145
11 Coordinated planning approaches
Evaluation
To evaluate the SeqACLPP-WAC approach, we repeated the experiments introduced in
Section 10.3. We follow the same evaluation scheme as used in Section 11.1 for the
Shipment-based Aircraft Configuration. We give an overview of the absolute performance
indicators achieved in Table 11.7 and their relative deviation compared to the SeqACLPP
approach in Table 11.8.
With respect to the solution quality, we get a heavily diverging picture for the base and
fast scenarios on one side and the high scenarios on the other. The weight load factor
(WLF) can be improved in all base and fast scenarios, on average by more than 3 percent.
However, the WLF decreases in the high scenarios by 4.2 percent. For these overbooked
flights, the WAC seems to be too conservative, when assigning weight to the ULDs. The
aim of the WAC is the creation of loadable ULD target weights that result in a well
balanced aircraft, but in these cases balancing should not the prime concern. Also the
volume net load factor (NLF) reduces across all scenarios by around 1.5 percent while
4.5 percent more ULDs are built (UNITS). However, this is reasonable, as the chosen
target weights are often significantly below the weight limit of a ULD type and thus the
load needs to be split across more ULDs. This also has a negative impact on the handling
indicators. The share of shipments that are split (SPLIT) increases significantly in all
scenarios, on average by 28 percent. The increase of dispersion of splitted shipments
146
11.2 Weight-and-balance-based aircraft configuration
(DISP) by 3.4 percent and share of ULDs with both standard and express shipments
(MIX) by 8.6 percent is also noticeable albeit less drastic.
In the base and fast scenarios the disadvantage of a higher handling effort is compensated
by a significant reduction of most cost components. On average the penalties for offloaded
items can be reduced by more than 76 percent in those scenarios. The bad performance
of the WAC for the high scenarios also shows in the penalty cost, which are 27.9 percent
higher than in the SeqACLPP approach. The cost for built ULDs increases across all
scenarios. This effect is in line with the rise in the number of used ULDs. The cost
for extra fuel due to imbalances (FUEL) can be reduced by 39.9 percent and handling
operations (OPS) by 16.7 percent from their already low absolute levels. Thus, in the base
and fast scenario an almost ideal balance can be achieved for most of the flights, while
the number of performed reloading operations is less than one ULD per flight on average.
Altogether, the total cost for flights in the base and fast scenarios could be reduced by
more than 29 percent compared to the SeqACLPP approach. But, for highly booked
flights the total cost is around 22.6 percent higher than in the SeqACLPP approach, due
to the increased offloads. Therefore, it seems beneficial to choose the concrete solution
approach on a flight-per-flight basis, depending on the respective utilization.
At last, we analyze the runtime of the WAC approach. As in the last section, we first
look at the runtime of the WAC model itself. After that, we discuss the impact on the
runtime of the other planning steps.
Similar to the SAC model, the WAC model takes a noticeable amount of time to be solved
to optimality for most flights. Therefore, we also set a time limit of 30 seconds for the
aircraft configuration step. Around 50 percent of the flights can be solved down to a
1 percent MIP gap until this time limit is reached. The distribution of the resulting MIP
gaps of the remaining flights is shown in Figure 11.2. Almost all of those flights show a
MIP gap of less than 10 percent.
147
11 Coordinated planning approaches
25.2
25
20
18.8
share of instances [in %]
18
15.2
15
10
6.6
5.5
4.7
5
3
1.7
0.6 0.6
0
1% 2% 3% 4% 5% 6% 7% 8% 9% 10% >10%
Figure 11.2: WAC MIP gap distribution after 30 seconds runtime (rounded to 5%)
An overview of the computational effort required for the planning steps is given in Ta-
ble 11.11. The runtime of the palletization step (BDAP+) increases by 18.8 percent
compared to the original BDAP. We attribute this to the additional target weight con-
straint and the calculation of the related deviation penalty. Also, the weight and balance
step (UWAB) takes longer, about 60.6 percent. Part of this can be explained by the larger
number of ULDs to load, as was the case at the SeqACLPP-SAC approach. Furthermore,
the better weight distribution across the ULDs creates a larger search space for the model,
because lighter ULDs can be placed at a higher number of loading positions.
Altogether, we can say that the incorporation of weight and balance aspects into the air-
craft configuration step works very well for flights that are not fully booked. However, on
overbooked flights the solutions are worse than in the SeqACLPP approach. Fortunately,
as the booked weight and volume of a flight is known at the time of load planning, the
better suiting approach can be chosen for each flight individually.
11.3 Summary
In this chapter, we presented two extensions of the SeqACLPP approach with the aim to
reduce the penalty of offloaded items as seen in Chapter 10.
148
11.3 Summary
149
12 Conclusion
In this chapter, we summarize the main contributions and results of this thesis. We
discuss our findings regarding the stated research questions and conclude with an outlook
on promising future research.
12.1 Summary
The goal of this work was to understand the load planning problem faced by cargo airlines
and develop suitable solution approaches by using operations research methods to create
a decision support system. Along this way, we generated several contributions to the
state of research, which we introduce in the following in the order of their appearance in
this thesis. Besides, we give a graphical overview of the developed models and solution
approaches in Figure 12.1.
In Chapter 2, we presented a brief introduction into the air cargo business as well as
the operational handling processes of airlines that transport cargo. After that, we gave
a comprehensive overview of the Air Cargo Load Planning Problem (ACLPP) and its
four subproblems: the Aircraft Configuration Problem (ACP), the Build-up Scheduling
Problem (BSP), the Air Cargo Palletization Problem (APP), and the Weight and Balance
Problem (WBP) in Chapter 3. We identified the three main stakeholders of load planning:
sales, handling, and aircraft operations. Their respective objectives on the problem are
maximizing revenue, minimizing physical handling effort, and minimizing operational
cost of the flight. Furthermore, we discussed the challenges of current manual planning
approaches.
In the next four Chapters 4 to 7 we introduced the ACLPP subproblems one by one in
detail. For each subproblem, we reviewed the existing literature and formally specified an
optimization model (ACM, BSM, APM, WBM). The ACM and BSM are the first models
tackling the respective problems. For the APP and WBP only models partially covering
the aspects of our problem at hand could be found. The APM especially introduces the
following features that have not yet been dealt with in the literature:
• It considers time as a new dimension of the packing problem. Only items that are
available before the assembly time of a ULD can be assigned to it.
• The stacking and stability constraints track the statics between the items and allow
for partial support as well as placement on uneven surfaces.
• To cover item allocation restrictions, a soft item sorting constraint is added. It
allows for groups of items to be packed preferably together or onto separate ULDs.
In the WBM we consider the union of constraints found in the literature. Besides, we
added the following practical aspects:
12 Conclusion
SAC
SeqACLPP-SAC (11.1)
Aircraft configuration
VWAC (9.1) RHBS
ACP / ACM (4.2)
BDAP
SeqACLPP (9)
Build-up scheduling
RHBS (9.2) UWAB
BSP / BSM (5.2)
ACLPP
SeqACLPP-WAC (11.2)
BDAP (9.3) WAC
APP / APM (6.2)
RHBS
Weight and balance BDAP+
UWAB (9.4)
WBP / WBM (7.2)
UWAB
Figure 12.1: Components presented in this work, along with the sections they are intro-
duced in.
152
12.2 Research questions
of a sequential four-step planning pipeline that follows the current manual processes in
practice. The ACP is solved for each flight by a MIP model implementing a Weight-
and-Volume-based Aircraft Configuration (VWAC). For the BSP we presented a rolling
horizon approach (RHBS) considering all flights in the planning horizon. It solves one shift
per iteration by also employing a MIP model. We realized the APP with a Logic-based
Benders Decomposition approach, denoted as BDAP, which is solved for each transport
segment of a flight. It consists of a MIP master problem and subproblems solved via a
constraint program. The master problem, denoted as BinAssign, distributes the items
among the ULDs and covers all non-geometric aspects of the problem. The subproblem,
denoted as CPPack, captures all the three-dimensional packing aspects. Finally, the WBP
is solved for each flight by a MIP model, denoted as ULD-based Weight and Balance
(UWAB).
We successfully evaluated the SeqACLPP approach on the introduced benchmark in-
stances and reported the results in Chapter 10. As the approach contains a number of
parameters, we introduced a set of methods to determine suitable settings. Furthermore,
we discussed the achieved results with respect to solution quality and effort and identified
areas for improvement.
Based on identified weaknesses of the SeqACLPP approach, we introduced and evaluated
two coordinated planning approaches in Chapter 11. In the SeqACLPP-SAC approach
we incorporate aspects of the APP into the ACP by replacing the VWAC with a new
Shipment-based Aircraft Configuration (SAC). In the same way, in the SeqACLPP-WAC
approach we replace the VWAC with a Weight-and-balance-based Aircraft Configuration
(WAC) to consider WBP aspects within the ACP step. Finally, we analyzed the effects
of both approaches on the solution quality and runtimes. Both approaches can further
improve the solutions.
1) What are the requirements and drivers of air cargo load planning in practice?
The ACLPP affects three airline departments: sales, handling, and aircraft operations.
All three have partially conflicting objectives on the subject. We identified four parts of
the problem: aircraft configuration, build-up scheduling, palletization, and weight and
balance. After introducing the general planning process in Chapter 3, we described the
four parts in detail and formally in Chapters 4 to 7.
2) Can valid and competitive load plans be generated with reasonable effort? From
the identified parts of the problem, we derived the four-step planning approach SeqA-
CLPP. We implemented it and evaluated its performance on real and synthetic benchmark
instances. Compared to real load plans seen in practice, the average packing density could
153
12 Conclusion
be improved by more than 20 percent and the performance with respect to the required
handling effort and aircraft operations could be significantly improved. The required run-
times range between 13 and 38 minutes per flight, which is acceptable for non-interactive
planning. We described our solution approach in Chapter 9 and its evaluation in Chap-
ter 10.
3) Does splitting the problem lead to adverse effects and what can we do about
it? During the evaluation of the SeqACLPP approach we found that considering each
solution step independently leads to a higher than necessary amount of offloaded items.
The reason typically is an overestimation of the capabilities of later steps. For example,
the volume capacity of a single ULD is easily overestimated if only the volume of the
items to be loaded is considered. Furthermore, the aircraft capacity for heavy ULDs is
overestimated if only a subset of the ULDs to load is considered. To overcome those
effects, we incorporated constraints of later planning steps into the aircraft configuration
step. Thereby, we could improve the solution quality for four out of six scenarios. These
coordinated planning approaches are presented in detail in Chapter 11.
154
12.4 Outlook
12.4 Outlook
Our evaluation showed that the presented approaches are suitable to automatically gen-
erate load plans for cargo flights. The generated load plans are significantly better than
plans manually created by load planning experts. Compared to the current operational
practice, we could, for example, achieve a 20 percent higher packing density and reduce
the required warehouse to workstation transports in the air cargo terminal by more than
17 percent due to better item sorting. The costs of additional fuel burn due to aircraft
imbalances or ULD reloading operations at stop-over airports in our solutions are almost
negligible.
This shows that cargo airlines can significantly profit from employing the presented ap-
proaches in their operational practice. More and especially the profitable last-minute
cargo can be transported. Furthermore, the costs of load planning, handling effort, and
aircraft operations can be significantly reduced. In the highly competitive air cargo busi-
ness this can provide airlines with a competitive edge to operate profitably.
Besides the operational load planning, further use cases of the presented approaches are
imaginable. They could be used throughout the booking process to estimate the actual
aircraft utilization of a flight or to calculate the effective space required by a new booking.
On a tactical level new products or routes could be evaluated by exemplary load plan-
ning. Even the aircraft can be optimized by simulating the effects of added or removed
equipment, like floor locks or additional fuel tanks, on the load plans in practice. These
changes modify the aircraft configuration space and hence its loading capabilities, but
they also alter the weight of the unloaded aircraft and thus its fuel consumption on any
flight.
155
Bibliography
Amadeus (2015). Amadeus Flight Management. Technical report, Amadeus IT Group
SA. Available online from: www.amadeus.com, last accessed: 18.05.2017.
Boeing (2011). MD-11 airplane characteristics for airport planning. Technical report,
Boeing Commercial Airplanes. Available online from: www.boeing.com, last accessed:
18.05.2017.
Brandt, F., J.-N. Popratnjak and E. Schulz (2014, 3). Packing with Item Availability and
Bin Due Dates. Presentation at the 11th Meeting of the EURO Special Interest Group
on Cutting and Packing.
Brosh, I. (1981). Optimal cargo allocation on board a plane: a sequential linear program-
ming approach. European Journal of Operational Research 8 (1), p. 40 – 46.
Burnson, P. (2013). Top 25 Freight Forwarders: Top 25 prevail despite market divergence.
Logistics Management. Available online from: www.logisticsmgmt.com, last accessed:
18.05.2017.
Ceschia, S. and A. Schaerf (2013). Local search for a multi-drop multi-container loading
problem. Journal of Heuristics 19 (2), p. 275–294.
Crabtree, T., T. Hoang, J. Edgar and R. Tom (2014). Boeing World Air Cargo Forecast
2014-2015. Technical report, Boeing Commercial Airplanes. Available online from:
www.boeing.com, last accessed: 18.05.2017.
Crabtree, T., T. Hoang, R. Tom and G. Gildemann (2016). Boeing World Air Cargo
Forecast 2016-2017. Technical report, Boeing Commercial Airplanes. Available online
from: www.boeing.com, last accessed: 18.05.2017.
Crainic, T. G., G. Perboli and R. Tadei (2008). Extreme Point-Based Heuristics for
Three-Dimensional Bin Packing. INFORMS Journal on Computing 20 (3), p. 368–384.
157
Bibliography
Dahmani, N. and S. Krichen (2016). Solving a load balancing problem with a multi-
objective particle swarm optimisation approach: application to aircraft cargo trans-
portation. International Journal of Operational Research 27 (1-2), p. 62–84.
de Cleyn, S., K. de Vos, T. Kallstenius, E. van Bruystegem, W. van Daele and S. Ver-
meulen (2014). Optimization takes flight with weight and balance software for airlines.
Technical report, iMinds insights. Available online from: www.iminds.be, last accessed:
24.04.2017.
Egeblad, J., C. Garavelli, S. Lisi and D. Pisinger (2010). Heuristics for container loading
of furniture. European Journal of Operational Research 200 (3), p. 881 – 892.
FAA (2016). Aircraft Weight and Balance Handbook. Technical report, Federal Aviation
Administration. Available online from: www.faa.gov, last accessed: 18.05.17.
Feng, B., Y. Li and Z.-J. M. Shen (2015). Air cargo operations: Literature review and
comparison with practices. Transportation Research Part C: Emerging Technologies 56,
p. 263 – 280.
Fuellerer, G., K. F. Doerner, R. F. Hartl and M. Iori (2010). Metaheuristics for vehi-
cle routing problems with three-dimensional loading constraints. European Journal of
Operational Research 201 (3), p. 751 – 759.
Grandjot, H., I. Roessler and A. Roland (2007). Air Cargo Guide: An Introduction to the
Air Cargo Industry. Huss.
Guéret, C., N. Jussien, O. Lhomme, C. Pavageau and C. Prins (2003). Loading Aircraft
for Military Operations. The Journal of the Operational Research Society 54 (5), p.
458–465.
Heidelberg, K. R., G. S. Parnell and J. E. Ames (1998). Automated air load planning.
Naval Research Logistics (NRL) 45 (8), p. 751–768.
Hong Ha, H. T. and N. Nananukul (2016). Air Cargo Loading Management System
for Logistics Forwarders. In: Proceedings of 2016 International Conference on Urban
Planning, Transport and Construction Engineering, Pattaya, p. 51–58.
158
Bibliography
ISO (2003). ISO 6780:2003: Flat pallets for intercontinental materials handling – Principal
dimensions and tolerances. Technical report, International Organization for Standard-
ization.
Larsen, O. and G. Mikkelsen (1980). An interactive system for the loading of cargo
aircraft. European Journal of Operational Research 4 (6), p. 367 – 373.
Limbourg, S., M. Schyns and G. Laporte (2012). Automatic aircraft cargo load planning.
Journal of the Operational Research Society 63 (9), p. 1271–1283.
Lin, J. L., C. H. Chang and J. Y. Yang (2006). A study of optimal system for
multiple-constraint multiple-container packing problems. Lecture Notes in Computer
Science 4031 LNAI, p. 1200–1210.
Lurkin, V. and M. Schyns (2015). The Airline Container Loading Problem with pickup
and delivery. European Journal of Operational Research 244 (3), p. 955 – 965.
Murray, G. (2016). Load factors at historic lows, says IATA. Air Cargo News. Available
online from: www.aircargonews.net, last accessed: 18.05.2017.
Nance, R., A. Roesener and J. Moore (2011). An advanced tabu search for solving
the mixed payload airlift loading problem. The Journal of the Operational Research
Society 62 (2), p. 337–347.
Nobert, Y. and J. Roy (1998). Freight Handling Personnel Scheduling at Air Cargo
Terminals. Transportation Science 32 (3), p. 295–301.
Paquay, C., M. Schyns and S. Limbourg (2016). A mixed integer programming formulation
for the three-dimensional bin packing problem deriving from an air cargo application.
International Transactions in Operational Research 23 (2), p. 187–213.
Pisinger, D. and M. Sigurd (2007). Using decomposition techniques and constraint pro-
gramming for solving the two-dimensional bin-packing problem. INFORMS Journal on
Computing 19 (1), p. 36–51.
159
Bibliography
Rong, A. and M. Grunow (2009). Shift designs for freight handling personnel at air cargo
terminals. Transportation Research Part E: Logistics and Transportation Review 45 (5),
p. 725 – 739.
The Economist (2016). Too little freight, too much space. The Economist. Available
online from: www.economist.com, last accessed: 24.04.2017.
Tyler, T. (2015). IATA Annual Review 2015. Technical report, International Air Trans-
port Association. Available online from: www.iata.org, last accessed: 18.05.2017.
Wikipedia (2016). Pallet — Wikipedia, The Free Encyclopedia. Available online at:
http://en.wikipedia.org/wiki/Pallet, last accessed 31.10.2016.
Yan, S., C.-H. Chen and C.-K. Chen (2006a). Long-term manpower supply planning for
air cargo terminals. Journal of Air Transport Management 12 (4), p. 175–181.
Yan, S., C.-H. Chen and C.-K. Chen (2008a). Short-term shift setting and manpower
supplying under stochastic demands for air cargo terminals. Transportation 35 (3), p.
425–444.
Yan, S., C.-H. Chen and M. Chen (2008b). Stochastic models for air cargo terminal man-
power supply planning in long-term operations. Applied Stochastic Models in Business
and Industry 24, p. 261–275.
Yan, S., C. K. Chen and C. H. Chen (2006b). Cargo terminal shift setting and manpower
supplying in short-term operations. Journal of Marine Science and Technology 14 (2),
p. 109–118.
Yan, S., C.-T. Lo and Y.-L. Shih (2006). Cargo Container Loading Plan Model and
Solution Method for International Air Express Carriers. Transportation Planning and
Technology 29 (6), p. 445–470.
160
List of Figures
2.1 Illustration of flights, legs, and segments . . . . . . . . . . . . . . . . . . . 8
2.2 Images of packed ULDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Examples of ULD types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Air cargo modes of transport . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5 Material flow in an air cargo terminal . . . . . . . . . . . . . . . . . . . . . 13
2.6 Build-up workstations in a cargo terminal . . . . . . . . . . . . . . . . . . 14
2.7 Images of aircraft loading . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.8 Deck layout of an MD11F aircraft . . . . . . . . . . . . . . . . . . . . . . . 16
161
List of Figures
162
List of Tables
2.1 Main differences between the passenger airline and air cargo business . . . 6
2.2 Specifications of common ULD container types . . . . . . . . . . . . . . . . 10
2.3 Specifications of common ULD pallet types . . . . . . . . . . . . . . . . . . 11
2.4 Common aircraft types and their cargo capacities . . . . . . . . . . . . . . 12
163
List of Tables
164
Glossary
ACLPP Air Cargo Load Planning Problem
ACM Aircraft Configuration Model (see Section 4.2.5)
ACP Aircraft Configuration Problem
AKE standard half-width ULD container with dimensions 200.7x153.4 cm (79x60.4 in)
APM Air Cargo Palletization Model (see Section 6.2.5)
APP Air Cargo Palletization Problem
BDAP LBBD for air cargo palletization step (see Section 9.3)
BinAssign Bin Assignment Model (see Section 9.3.1)
BSM Build-up Scheduling Model (see Section 5.2.5)
BSP Build-up Scheduling Problem
CG center of gravity
CPPack Constraint Program 3D Packing Model (see Section 9.3.2)
CREWS sum of required build-up crews (perf. indicator, see Section 8.4)
GLF volume gross load factor (perf. indicator, see Section 8.4)
165
Glossary
MIX share of ULDs with multiple products (perf. indicator, see Section 8.4)
NLF volume net load factor (perf. indicator, see Section 8.4)
166