A heuristic algorithm for the Air Transport Unit Consolidation Problem Lorenzo Peirano1Enrico Angelelli1Claudia Archetti2 1University of Brescia Department of Economics and Management Brescia Italy

2025-04-27 0 0 2.71MB 35 页 10玖币
侵权投诉
A heuristic algorithm for the Air Transport Unit Consolidation Problem
Lorenzo Peirano(1) Enrico Angelelli(1) Claudia Archetti(2)
(1) University of Brescia, Department of Economics and Management, Brescia, Italy
lorenzo.peirano@unibs.it,enrico.angelelli@unibs.it
(2) ESSEC Business School in Paris, Department of Information Systems, Decision Sciences and Statistics, Cergy, France
archetti@essec.edu
Abstract
Consolidation of loose packages into transport units is a fundamental activity offered by logistics service
providers. Moving the transport units instead of loose packages is faster (with one movement only, multiple packages
are loaded instead of having one load operation for each package), safer (chances of damage and loss is reduced)
and cheaper. One of the typical objective of consolidation problems is the minimization of the number of transport
units used, e.g. containers. In air transportation, however, transport units have multiple aspects which concur
in the calculation of the cost and thus optimization in the number and characteristics of the transport units is
required. In this paper, we present the air transport unit consolidation problem where the aim is to determine how
to consolidate loose packages in transport units with the goal of minimizing the corresponding cost. The problem
is a variant of the three-dimensional bin packing problem where the objective function is formulated according to
the way costs are calculated in the air transport business. In addition, side constraints are included to take into
account specific requirements. We propose a heuristic algorithm which construct an initial feasible solution and
then improves it through a local search algorithm. Computational tests on randomly generated instances show that
the algorithm provides high quality solutions in a reasonable computing time. In addition, tests on real data show
that it improves solutions found in practice by the company providing the data.
Keywords: air transport; three-dimensional bin packing; consolidation; heuristics.
1 Introduction
Freight forwarders handle international shipments for their customers and focus their activity on offering the most
complete logistic service from origin to destination. This involves not only the management of documents and the
physical transfer of goods, but includes other logistic operations (packaging and labelling are just some examples).
One of the activities carried out is the consolidation of loose packages into transport units (TU). For air shipments
TUs are usually pallets of various dimensions, and crates. Since most of the times shipper companies are not able to
consolidate themselves the goods of which the shipment is composed, freight forwarders spend a high amount of time
in performing this operation. The most evident reason behind consolidation in TU is that the movement of a TU
is not only faster, more efficient and cheaper than handling a higher number of packages, it also increases the safety
of the shipment since it is more difficult to loose or damage packages. Moreover, since the information included in
the documentation must be aligned to the characteristics of the shipment, controls by any monitoring organization
(customs, FDA, police, etc.) are easier, and, thus, faster. However, choosing the number and quality of TU to be used
is not a simple task and it requires the consideration of different aspects. Indeed, the way in which loose packages are
consolidated impacts in the shipment cost. In fact, TUs can have different dimensions and weight capacities, which
generates different costs. In the following, we assume the measures are expressed in centimeters and in the width ×
length ×height format, with the latter sometimes not reported. The most common TU used is pallets. EUR and
EUR1 pallets are the standard European 120x80x15 pallets, EUR2 are 120x100 while EUR6 are 80x60. Height is the
same for every pallet and from now on it will not be reported anymore. American standards are slightly different
(40x48 inches) while in Japan the standard measure is 110x110.
1
arXiv:2210.06004v1 [math.OC] 12 Oct 2022
Air transportation services apply a unitary freight on the taxable weight, which is the higher between the real weight
of the shipment and the weight equivalent conversion of its volume. Every cubic meter is equal to approximately 167
kilograms of weight. When the TU is stackable, the volumetric weight is converted on the actual volume of the TU.
On the other side, when the TU is not stackable, it effectively occupy the volume generated by the projection of the
base dimensions to the maximum height of the vehicle.
Each airplane model has different sizes of the cargo hull and thus its limitations and characteristics must be considered.
Air transportation is carried out by two main families of aircraft: Passengers and Freighter. Passenger aircrafts (PAX)
transport passengers on the upper deck and cargo on the lower section of the aircraft. Higher priority is given to
passenger’s luggages and the remaining slots are allocated to cargo shipments. Depending on the model of the aircraft,
different kind of Load Unit (LU) can fit inside the lower deck, defining the constraints in loading the cargo into the
plane. The most common internal heights for LU for passenger airplane are 130 and 160 cm for medium and long range
flights, respectively, while short range flight usually requires smaller airplanes with maximum height on the lower deck
of 110 cm. Very small aircrafts do not use LUs or any kind of consolidated shipment and only accept loose packages
with very limited weight and dimensions.
LUs shape and size defines the maximum dimensions allowed for each TU to be accepted on a given airplane. The
TU is limited in every dimension by the physical boundaries of the LU. However, when using standardized TU like
pallets, their base is always loadable within any LU and the only dimension which is limited is the height.
Freighter (Cargo Aircraft Only, or CAO) aircraft do not transport passengers and thus can make use of the upper
section deck to transport cargo. The upper section deck exploits the circular shape of the aircraft to allow the trans-
portation of bigger packages. Most of the times the upper deck do not use LUs and directly load the consolidated TU.
One strict condition imposed by air companies is that the material to be loaded on the upper deck must be forkliftable
and movable with handling vehicles.
Figure 1: Cross-section of a CAO
In Figure 1 a cross-section of a CAO aircraft is shown. The lower part is the lower deck and it is loaded with LU
only. Upper deck is loaded with both LU and loose packages, especially if their dimensions are out of the gauge for
the LU. The upper deck height limit depend on the base dimension of the package: with a small base it can be placed
near the center where the shape of the aircraft allows for a higher height, otherwise, the wider the base, the lower is
2
the maximum height allowed. For aircrafts with a side door the height of the door is usually considered as maximum
height allowed for transport. CAO aircrafts have a maximum loading height for cargo of 290 cm for medium sized
aircraft and 310-320 for large sized aircraft. Even bigger CAO aircraft exists but do not operate with a line service
and rely purely on chartering and thus are not considered in this work.
Figure 2: Boxes, transport units and load units
In this paper we study the problem of consolidating loose packages (boxes) in TU to be transported through air
transportation services. As shown in Figure 2, we want to consolidate boxes into pallets, pallets are themself then
loaded into LUs by the air company (or by a third party logistics company appointed by the air company). We focus
on the first part of the problem, i.e., consolidating loose packages in TUs and we refer to Paquay et al. (2018) for a
reference on the problem of loading already palletized items or loose packages into LU suitable for air transportation.
The problem tackled in Paquay et al. (2018) focuses on loading loose packages and palletized packages into LUs. This
operation is carried out by air companies (or, on their behalf, by airport handling operators) and happens after the
problem we want to tackle in this work. Here, we focus on the first step where a freight forwarder (or a shipper)
need to consolidate multiple packages into TU of multiple and varied dimensions in order to minimize the costs that
will be paid for the transportation by air means. This is a separate and distinct operation carried out by shippers
/ freight forwarders on a previous time before delivering the shipment to the airport. While the procedure can be
considered as a whole singular operation when shippers/freight forwarder have the availability of LUs, this is not a
very common scenario. Most of the time they deliver loose packages or packages consolidated in TUs, and therefore
the first operation illustrated in Figure 2 need to be tackled separately.
The Air Transport Unit Consolidation Problem (ATUCP) is thus the problem where, given a set of loose packages,
the best packing into TUs has to be determined in order to minimize the total cost. Based on the definition given
in Bortfeldt and W¨ascher (2013), the ATUCP can be considered as a Multiple Bin-Size Bin Packing Problem (MBS-
BPP) since the boxes to be packed are extremely heterogeneous, while pallets are weakly heterogeneous. We want to
consolidate a set of boxes into the optimal heterogeneous mix of TUs of any given type that seeks the minimization
of an objective function considering the value of the TUs (i.e. their taxable weight) and the position of the center of
gravity. As explained later, the latter term measures the stability of the TU: we want a TU as stable as possible to
avoid damages during transportation. The taxable weight is the unit of measure to which the unitary freight is applied
by air companies. Clearly, it cannot be lower than the sum of the weights of the boxes. When weight is low, though,
the volumetric weight conversion is usually higher and thus a proper consolidating technique is needed to effectively
reduce the cost of the shipment.
Boxes can be stackable or non stackable. In the following we treat the case where TU are always non-stackable, i.e.,
no TU can be loaded on top of another TU. Whenever a TU is non stackable, the volume is calculated applying the
maximum height of the airplane deck. Usually this maximum is considered using a standard height of 160 cm for
lower deck cargo and 290 cm for upper deck cargo. Moreover, boxes can or cannot be turnable, i.e. two dimensions
can be swapped. It is assumed that base dimensions are always swappable, the length can become the width and
vice versa. This is not always the case if other means of transportation are considered (for instance, if we consider
the consolidation of goods to be shipped through containerization, a package can have extraordinary dimensions that
3
allow it to be forkliftable on one side only, and thus it can be loaded only with the dimensions derived by the given
rotation).
One aspect to be taken into account when planning the load layout of a TU is the position of the center of gravity
of the load. The center of gravity is the unique point where the weighted relative position of the distributed mass
sums up to zero. This is the point to which a force may be applied to cause a linear acceleration without an angular
acceleration. Assuming that the weight is always equally distributed, every box have its center of gravity equal in
geometrical center, and the center of gravity of the TU is the weighted average point of the boxes’ centers of gravity.
A well balanced TU with a center of gravity placed near the central point of the base is easier to transport when lifted
with forklifts or cranes, is more stable due to a better balance and, especially when pallets are considered, is more
resistant and less subject to damages to the base. Usually it is better to keep heavy items at the bottom of the TU
in order to avoid damages to other boxes and improve the balance of the cargo when subject to horizontal movement.
Therefore, one of the objective we seek is to place the center of gravity as near as possible to the center of the base
and in the lowest position possible. Thus, the objective of the ATUCP combines the minimization of total costs and
the optimization of the center of gravity. A numerical example of cost calculation is shown in Section 1.1 while the
calculation of the center of gravity is explained in Section 2.2.
The contribution of this paper can be summarized as follows:
1. We introduced the Air Transport Unit Consolidation Problem (ATUCP) which is a problem finding relevant
practical applications in airline freight transportation.
2. We consider an objective function including solution cost, measured on the basis of the TUs used to consolidate
packages, and stability, measured by the center of gravity which depends on the disposition of packages in each
TU.
3. We present a heuristic algorithm which first construct a feasible solution and then improves it through a local
search based on different neighbourhoods.
4. We propose a procedure for generating ATUCP instances which enables a comparison between the solution
provided by the heuristic algorithm and an optimal solution determined analytically.
5. We perform exhaustive tests on randomly generated instances and on real data. The results show that the
heuristic algorithm provides high-quality solutions and largely outperforms solutions generated by the operators
of the company providing the real data.
The paper in organized as follows. Section 1.1 presents a numerical example of how solution cost is calculated. The
relevant literature is reviewed in Section 1.2 while the problem is formally defined in Section 2. Section 3 is devoted
to the description of the algorithm while computational results are presented in Section 5. Finally, some conclusions
are drawn in Section 6.
1.1 Example of cost calculation
Consider the following simple example: we need to transport 12 boxes with dimensions 60x40x60 and we have avail-
ability of pallets with base 120x80. Assume that the weight of boxes is very limited and therefore only the volume is
considered. We can choose to consolidate the boxes in one single pallet 120x80x195 (solution 1) or two pallets where
one has dimensions 120x80x135 and the other has dimensions 120x80x75 (solution 2).
The following table report the volumetric weight for the two possible consolidations.
Table 1: Weights
Volume Conversion
Solution 1 465 kg
Solution 2 513 kg
4
Consolidating in one pallet generates less volume (120 ·80 ·290 = 2.784 CBM·167 = 465 kg ), but forces to fly
with a freighter aircraft since its height is greater than the maximum height of the LU (160 cm). Pallets with lower
height on the other side generates more taxable weight (120 ·80 ·160 ·2 = 3.072 CBM ·167 = 513 kg). Cargo flights
are typically less frequent and more expensive. For instance, if a passenger airline (PAX) company offers a freight of
e2.00/kg and a cargo airline (CAO) company offers a freight of e2.30/kg, the total freight paid is as per table 2
below.
Table 2: Costs
Total Cost
Solution 1 e1,069.50
Solution 2 e1,026.00
In this case, creating two pallets is the cheapest option, since it reduces the total cost of the air shipment. Fur-
thermore, if we consider the availability of pallets with base 120x120 we can consolidate all the boxes on a single
pallet 120x120x135 with a volume weight conversion equal to 384 kg. Considering the freight of PAX flight e2.00
the cost is e768.00. Consolidating the boxes in a single pallet with base 120x120 is then the best option. In our
work it is assumed that there always is a wide choice of flights and aircraft, thus the need for optimization. While
during the COVID-19 crisis the number of passenger’s flight reduced significantly (even though many of them were
used to transport cargo nontheless), the situation returned to pre-pandemic levels, where multiple companies offer
their services for the transportation of cargo, using both passenger’s and Cargo Aircraft Only options. The effective
availability of space on aircrafts impacts the time needed to transport goods and the cost of it, but it is not depending
on the consolidation layout and is not directly handled by shippers/forwarders and thus, it is not considered in this
study.
1.2 Related literature
The ATUCP is a three dimensional bin packing problem (3D-BPP) where the objective is finding the optimal way
to allocate loose packages to TUs in order to seek the minimization of TU’s cost function and optimize the center of
gravity. Martello et al. (2000) give a description of the 3D-BPP and propose an exact branch and bound algorithm for
the solution of large instances. A MILP formulation with different valid inequalities is presented by Hifi et al. (2010b).
3D-BPPs are often very difficult to solve with exact methods. Henceforth, a wide range of heuristics approaches has
been introduced in the literature. Tabu search techniques are presented in Lodi et al. (2002) and Crainic et al. (2009)
with good results. Gendreau et al. (2006) propose a tabu search algorithm capable of solving a combined capacitated
vehicle routing and loading problem. Crainic et al. (2009) propose a two level tabu-search heuristic. The first level
heuristic is meant to deal with the optimality of the bin packing problem, while the second level of the heuristic finds
feasible layouts for the packing of the items in the bins. Neighborhoods are explored using a k-chain-moves procedure
involving chains of kchanges in the solution, which proves to be effective in exploring large neighborhoods in contained
computational times. This is clear in the computational results where the method proposed result particularly effective
in finding good solution when the time available is limited. Similarly, the three-dimensional single bin-size bin packing
problem is studied in Hifi et al. (2010a) where the authors present a MILP formulation of the problem. Moreover,
they propose valid inequalities usefull to improve the relaxed lower bound of the formulation proposed. Final solutions
are found through an heuristic approach. Mack and Bortfeldt (2012) present a straightforward heuristic capable of
solving two-dimensional and three-dimensional bin packing problems. In the same work the authors introduce a set of
1,800 benchmark instances with on average 1,500 items each, which are useful in order to test bin pacing algorithms
on very large instances. de Almeida and Figueiredo (2010) present an heuristic for a particular case of the container
loading problem where special constraints on the position of the boxes are implemented. The heuristic approach
proposed by the author is designed to be easy to implement for warehouse workers during the loading operation
and the results of the computational campaign shows that the methodology is capable of generating good solutions,
especially when real-world data is used as input. Alvarez-Vald´es et al. (2013) present a two phase algorithm useful for
5
摘要：

AheuristicalgorithmfortheAirTransportUnitConsolidationProblemLorenzoPeirano(1)EnricoAngelelli(1)ClaudiaArchetti(2)(1)UniversityofBrescia,DepartmentofEconomicsandManagement,Brescia,Italylorenzo.peirano@unibs.it,enrico.angelelli@unibs.it(2)ESSECBusinessSchoolinParis,DepartmentofInformationSystems,Deci...

展开>> 收起<<
A heuristic algorithm for the Air Transport Unit Consolidation Problem Lorenzo Peirano1Enrico Angelelli1Claudia Archetti2 1University of Brescia Department of Economics and Management Brescia Italy.pdf

共35页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：35 页 大小：2.71MB 格式：PDF 时间：2025-04-27

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 35
评分 收藏
分享
立即下载
客服
关注