Caputo 2006
Caputo 2006
Caputo 2006
Access to this document was granted through an Emerald subscription provided by 549148 []
For Authors
If you would like to write for this, or any other Emerald publication, then please use our Emerald for
Authors service information about how to choose which publication to write for and submission guidelines
are available for all. Please visit www.emeraldinsight.com/authors for more information.
About Emerald www.emeraldinsight.com
Emerald is a global publisher linking research and practice to the benefit of society. The company
manages a portfolio of more than 290 journals and over 2,350 books and book series volumes, as well as
providing an extensive range of online products and additional customer resources and services.
Emerald is both COUNTER 4 and TRANSFER compliant. The organization is a partner of the Committee
on Publication Ethics (COPE) and also works with Portico and the LOCKSS initiative for digital archive
preservation.
Freight
A genetic approach for freight transportation
transportation planning planning
A.C. Caputo, L. Fratocchi and P.M. Pelagagge
Faculty of Engineering, University of L’Aquila, L’Aquila, Italy 719
Abstract
Purpose – This purpose of this paper is to present a methodology for optimally planning long-haul
road transport activities through proper aggregation of customer orders in separate full-truckload or
less-than-truckload shipments in order to minimize total transportation costs.
Design/methodology/approach – The model is applied to a specific Italian multi-plant firm
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
operating in the plastic film for packaging sector. The method, given the order quantities to be shipped
and the location of customers, aggregates shipments in subgroups of compatible orders resorting to a
heuristic procedure and successively consolidates them in optimized full truck load and less than truck
load shipments resorting to a Genetic Algorithm in order to minimize total shipping costs respecting
delivery due dates and proper geographical and truck capacity constraints.
Findings – The paper demonstrates that evolutionary computation techniques may be effective in
tactical planning of transportation activities. The model shows that substantial savings on overall
transportation cost may be achieved adopting the proposed methodology in a real life scenario.
Research limitations/implications – The main limitation of this optimisation methodology is that
an heuristic procedure is utilized instead of an enumerative approach in order to at first aggregate
shipments in compatible sets before the optimisation algorithm carries out the assignments of
customer orders to separate truckloads. Even if this implies that the solution could be sub-optimal, it
has demonstrated a very satisfactory performance and enables the problem to become manageable in
real life settings.
Practical implications – The proposed methodology enables to rapidly choose if a customer order
should be shipped via a FTL or a LTL transport and performs the aggregation of different orders in
separate shipments in order to minimize total transportation costs. As a consequence, the task of
logistics managers is greatly simplified and consistently better performances respect manual planning
can be obtained.
Originality/value – The described methodology is original in both the kind of approach adopted to
solve the problem of optimising orders shipping in long-haul direct shipping distribution logistics, and
in the solution technique adopted which integrates heuristic algorithm and an original formulation of a
GA optimisation problem. Moreover, the methodology solves both the truckload assignment problem
and the choice of LTL vs FTL shipment thus representing an useful tool for logistics managers.
Keywords Transportation, Freight forwarding, Distribution management, Optimization techniques,
Italy
Paper type Research paper
Nomenclature
A ¼ constant FZ ¼ fixed charge characteristic of a
B ¼ constant geographical zone (e)
C ¼ cost (e) GA ¼ genetic algorithm
COG ¼ compatible orders groups K ¼ fitness function parameter Industrial Management & Data
Systems
DSS ¼ decision support system L ¼ string length (bits) Vol. 106 No. 5, 2006
ECL ¼ economic compatibility limit (e) LC ¼ local transport cost (e) pp. 719-738
q Emerald Group Publishing Limited
F ¼ specific fee (e/kg) LTL ¼ less than truck load 0263-5577
FTL ¼ full truck load m ¼ number of trucks DOI 10.1108/02635570610666467
IMDS n ¼ number of customer orders Subscripts
NS ¼ number of customers FTL ¼ full truck load
106,5 OVTB ¼ order visibility time bucket (days) LTL ¼ less than truck load
q ¼ transported quantity (kg) i ¼ index
T ¼ truck number variable j ¼ index
UEC ¼ unitary extra cost, fixed cost per k ¼ index
additional stop (e/stop) ind ¼ individual
720 W ¼ weight (kg)
WR ¼ weight range Greek symbols
Z ¼ geographical zone d ¼ auxiliary binary variable
Introduction
Distribution logistics has always been a key factor for the competitiveness of industrial
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
companies, but recently, its importance has grown significantly, due to the evolution of
both markets and production systems (Zografos and Ginnouli, 2002). In fact, in a context
of growing globalisation, firms have to supply markets distant from their own
warehouses and plants. Moreover, the diffusion of information and communication
technologies has introduced new ways to market products, like e-commerce paradigms,
that increase goods mobility (Caputo et al., 2004; Soliman and Youssef, 2003; Trappey
et al., 2004). This is also enhanced by the progressive shift from a make-to-stock
production to a just-in-time and quick response paradigm implying a continuous flow of
materials through the supply chain. Another phenomenon which increases mobility of
goods is the de-localization of manufacturing activities in countries with low labour cost.
Furthermore, customers’ expectations in terms of delivery service level are constantly
growing. Such factors make the distributive logistic system, and the related costs,
increasingly important and often critical for competitiveness of companies.
Road transport is by far the main mode of goods transportation in continental
industrialised countries. As an example, in the period from 1970 to 2000 road transport
has grown in the European Union countries from 52 to 74 per cent of the total quantity
of tonne kilometres hauled reaching a value of 1; 348 £ 109 t km (European
Communities, 2003).
To supply customers by road transport, logistics managers can usually choose
between two different shipping modes: full truck loads (FTLs) and less than truck
loads (LTLs) (Crainic, 1999). In FTL shipping, the manager hires an entire truck to
carry goods directly to customers’ locations. This kind of shipment is used if the
quantity of goods to be delivered is near to the truck capacity. In this case, the shipping
cost depends from the final destination and the number of intermediate stops and,
provided that the full truck capacity is actually saturated, this results in the lowest cost
per transported tonne. In LTL shippings, instead, only a fraction of the entire truck
capacity is hired and the cost is proportional to the transported amount with specific
fees depending on weight ranges (WRs) and the destination zone. This means that the
carrier dependent fees, the customer locations and the amount of goods to be shipped
define the actual convenience of one shipping mode respect the other one.
In the literature, a wide range of planning models for supply chain management
(Ma and Davidrajuh, 2005; Narasihman and Santosh, 2004) and specifically freight
transportation were developed (Brown and Ronen, 1997; Crainic, 2000; Crainic and
Laporte, 1997; Roy and Delorme, 1989) although they found limited practical application.
However, in real practice, it often happens that logistics managers rely entirely on Freight
their personal judgement and experience to choose among LTL and FTL mode and to transportation
select the carrier. Thus, sub-optimal choices may result (Allen and Liu, 1995; Kuo and
Soflarsky, 2003). planning
In this scenario, the adoption of a decision support system (DSS) to help logistics
managers to perform the correct selection of carrier and shipping mode minimizing
transportation costs proves to be highly beneficial, owing to the complexity of the 721
problem, the large number of variables involved and the number of possible options to
be compared (Helo and Szekely, 2005; Lursen and Yang, 1996; Powell and Sheffi, 1989).
Specific approaches aimed at selecting the optimal carriers for a predefined set of
shippings were also developed in the literature (Caputo et al., 2005; Kuo and Soflarsky,
2003) and proved to be either effective and easy to use in practice. However, although
the proper choice of carrier may significantly reduce shipping costs, even greater
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
Problem statement
As previously stated, it is assumed that an order can be delivered by two kind of road
transport modes, LTL shipment or FTL. The transportation mode is, therefore, the
main decision variable. Although motor carrier cost functions may be developed
according to different criteria (Christensen and Huston, 1987; Harmatuck, 1992), the
typical cost for a LTL shipment of weight W to a geographical zone Zj is:
C LTL ðZ j ; W Þ ¼ LC þ W £ FðZ j ; WRk Þ ð1Þ
The cost CLTL is the sum of two terms: the first is the local transport cost, LC, that is the
cost to carry goods from the manufacturer’s site to the carrier consolidation centre.
IMDS The second term is a product of the shipped weight W multiplied by the fee F (e/kg),
which is a function of the destination zone Zj and of the weight range WRk to which the
106,5 goods amount W belongs.
The cost for a FTL shipping of a truck which reaches NS different customers
located in different geographical zones Z j ð j ¼ 1; 2; . . .Þ is:
The cost is composed of two terms: the first is given by a fixed charge (e) depending on
the geographical zone to be reached. In case that multiple zones are visited in a single
shipping route, the highest value charge is applied among the fixed charges FZj
corresponding to the visited zones. The second term is the product of the unitary extra
cost UEC (e/stop) times the number of additional stops ðNS 2 1Þ: Therefore, the
shipment cost is independent of the carried quantity. A comparison of these cost
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
functions is shown in Figure 1 which refers to the case of a single zone – single
customer shipment (i.e. NS ¼ 1 and j ¼ 1).
Observing Figure 1, it is evident that a break even quantity exist and that for a
single order, it is immediate to decide whether to ship it through a LTL or through a
FTL. For a quantity smaller than 19 ton, in this case, it is cheaper to adopt a LTL
shipment. However, for a group of orders, the choice is more difficult, in fact to consider
each order singularly may result in a higher total cost that considering the same orders
as a whole group. For example, suppose that the maximum quantity transportable by a
truck is 26 ton and that there are three orders of 8 ton each, coming from customers
located in the same geographical zone, with a break even between FTL and LTL of
19 ton and a UEC value of 70 e/stop. As the single order is lower than the break even
value the LTL mode would be chosen for each order, with a total cost of 3,000e
according to Figure 1. However, it would be preferable to ship a FTL of 24 ton with a
total cost of 2,240e resulting from a fixed cost of 2,100e for the considered delivery zone
and including the charge for two additional stops. Obviously, the cost formulas (1) and
(2) are strictly related to the chosen carrier: each carrier applies in fact a different rate
for each zone it reaches, and the decision maker must also choose, for each shipping,
the best carrier to guarantee that the shipping expenses are minimized.
1600
1400
Transportation cost (Euro)
FTL
1200
1000
800
LTL
600
200
Figure 1.
Example of FTL and LTL 0
0 5 10 15 20
cost functions
Shipped cargo weigth (t)
It follows that while for a LTL shipping, the only decision variable is the carrier; on the Freight
contrary, for a FTL transport, the actual cost depends from the set of orders transportation
aggregated into that single FTL shipment, and from the choice of the carrier.
Therefore, the choice of the delivery mode for each order is very important to minimize planning
the total cost as for a given set of orders supplied by both LTLs and FTLs, the total
cost is obviously the sum of LTLs cost and FTL shipments cost.
In this problem, there are two kinds of constraints: time constraints and quantity 723
constraints. The first kind is the due date agreed between customer and supplier.
The first quantity constraint specifies instead that the quantity of goods delivered to a
customer must exactly match the quantity required by the customer; the second
quantity constraint specifies that the quantity carried by a truck cannot exceed the
maximum quantity allowed by the road law of the nation in which the truck will pass
through as well as the truck capacity.
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
Finally, the objective function to be minimized is the total cost function, i.e. the sum
of the LTL and the FTL shippings cost.
Methodology
In this work, a method for optimally selecting and aggregating a given set of shipping
orders in FTL and/or LTL shipments is presented, with the aim of minimizing total
shipping costs defined as the sum of LTLs and FTLs cost. Here, it is assumed that cost
is the only relevant performance measure and that all carriers offer the same
performance level in terms of on-time delivery and service quality.
In order to solve this problem, an optimisation method has been proposed in which
the overall problem is decomposed in simpler sub-problems. The entire procedure
includes the following main phases:
.
carrier database creation;
.
decomposition of orders list in compatible orders groups (COG);
. optimisation of shipping modes for each COG; and
.
output of optimal shippings list.
communication routes between them, so that it is possible, for a truck, to visit both
zones along the same route. Then, two zones are economically compatible if the
difference between their fixed charge FZj is less than a user defined fixed threshold.
The COGs are created by choosing and order to start from (which also implies a
starting zone), and grouping in the same COG all other orders coming from customers
located in zones geographically and economically compatible with the first one. While
the geographic compatibility constraint ensures that orders of the same COG may be
shipped through a single route, the concept of economical compatibility, given the
structure of the FTL cost function, limits the penalty imposed by the delivery in
the zone having the highest FZ. In fact, if deliveries have to be made to several
customers in two zones whose FZ values are 2.100 and 2.500e, respectively, the cost is
computed as if assuming that the truck would deliver its whole load to the most
expensive zone. The fixed threshold is used to prevent this extra cost, and varying its
value the COGs change and so the possible savings change too.
In the orders reduction step, a check is made on the order size to verify if orders for
quantity higher that the truck capacity exist so that it is possible to send one full
truck to those customers, and to treat the remaining quantity as separate orders.
Therefore, the orders reduction block directly creates, from the examined COG, a list
optimal single customer – single zone FTL shippings to which the optimal carrier is
directly associated. Such optimal shippings are then stored for subsequent
utilization.
In the following step of COG partitioning, the remaining orders are subdivided in Freight
two distinct subgroups, namely the orders to be shipped in LTL mode and those to be transportation
shipped in FTL mode. Given a COG partition, a very high number of possible set of
FTL shipments will result from all possible combination of orders in FTL trucks planning
among which the optimal one can be chosen. Therefore, the cost of a partition is not
known a priori because this will be the result of the actual aggregation of the orders
belonging to the two subgroups in a number of separate shipments. Obviously, many 725
different partitions can be obtained from a single COG, each one giving rise to an
optimal set of FTL shippings, the best partition being the one giving rise to the lowest
value of the sum of LTL and FTL shipping costs. It follows that all possible partitions
should be investigated and the cost from the optimal shippings from all partitions
should be compared to define the lowest cost shipping strategy.
However, it is not feasible to enumerate all partitions and search for the
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
optimal shipping list from each one. Therefore, it has been chosen to restrict the
search for optimal shippings only among heuristically defined “good” partitions.
Good partitions are created as follows.
At first, the basic partition is created including all orders into the FTL subgroup
and leaving the LTL subgroup void. The rationale behind this choice is the fact that
generally speaking the FTL shipping has a lower specific cost (e/tonne) that the LTL,
thus it would be preferable to exploit FTL shipping at the maximum extent possible.
However, in this case, full saturation of trucks capacity may not be reached. To avoid
this drawback, some orders are transferred from the FTL subgroup to the LTL
subgroup, thus creating alternative partitions, in order to reduce the number of FTL
and increase their saturation level. Orders to be transferred to the LTL subgroup are
chosen prioritarily among those to be delivered to zones having the highest absolute
difference between the corresponding fixed charges FZj and the average value of the
FZ charge for the FTL subgroup. In fact, eliminating from the FTL subgroup, those
orders having the highest FZ charge reduces the cost penalty on the remaining FTL
orders, while eliminating orders having the lowest value of FZ reduces the cost penalty
they would suffer if they were shipped together with orders assigned to more
expensive zones. Generation of alternative partitions is stopped when the number of
FTL is reduced from the original value N to N 2 2:
In the subsequent step, the optimal FTL and LTL shipping between the two
subgroups of any generated partition are determined. In the case of LTL shipments,
this simply consist in assigning to each LTL order its optimal carrier as indicated by
the carrier database.
Referring instead to FTL orders, the system will make their optimal aggregation in
a certain number of FTL shipments and will associate them to their optimal carrier.
This activity is rather complex and will be discussed in greater detail in the next
section. As a result of this optimisation step, the list of FTL and LTL shippings
together with their total costs, as resulting from their association with the optimal
carrier, are computed for each partition. The total shipping costs of each partition are
compared and the partition giving rise to the lowest total cost is selected.
Optimisation model
The core of the optimisation process is the optimal aggregation of orders on FTL
726 shippings starting from the FTL subgroup of any given partition. As a matter of fact,
for a partition LTL/FTL, the overall cost of LTLs is fixed and cannot be reduce further,
because for each LTL order, the system chooses the carrier with the lowest rates. On
the contrary, as far as FTLs are concerned, the optimisation process is not limited to
the choice of the best carrier; but it is also very important to aggregate the orders in an
appropriate manner on trucks, to obtain the lowest total cost. This optimisation
process is carried out as follows. Given a set of n customer orders, the first step is to
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
calculate the number m of trucks needed to deliver the whole quantity. In this
application, the number of trucks is simply computed as the ratio of total quantity to
the capacity of a single truck and rounding to the next integer. In this work, it is
assumed that an order can be even split into partial orders assigned to different
shipments if this can contribute to a cost saving or to increase the carrier saturation.
The problem of optimally aggregating n orders on m trucks can be viewed as the
problem of choosing, for each truck jth and for each order ith, the quantity qij of the ith
order which must be carried by the jth truck minimizing total transportation costs.
COG 1
Shipping
Optimization Optimal
orders Creation of COGs
of COGs shipping list
list
COG k
Optimization of
COGs
Computation of
Partition 1 LTL and FTL
shippings costs
optimization
and data storage
Figure 2. Computation of
LTL and FTL
Optimisation process Partition l
optimization
shippings costs
and data storage
Therefore, for the given set of n orders and m trucks, one needs to specify n £ m Freight
decision variables values qij, that are the quantities carried by each truck jth to each ith transportation
customer. The choice of the qij values must satisfy the following quantity constraints:
the sum of all quantities carried to a customer must be equal to the quantity the planning
customer has requested, and the sum of all quantities carried by a single truck cannot
exceed the maximum quantity that a truck is allowed to carry. In a mathematical form,
this is stated as: 727
8X m
>
>
>
> qij ¼ q_requestedi
>
< j¼1
Xn ð3Þ
>
>
>
> qij # q_max
>
: i¼1
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
where q_requestedi is the quantity ordered by customer ith, and q_max is the
maximum quantity that a truck is allowed to carry. Time constraint (i.e. respect of
due dates) have been neglected as they have been already satisfied when creating
the COGs.
Finally, the objective function to minimize is the sum (total_c) of the costs of each
truckload ðci Þ :
Xm
Total_c ¼ ci ci ¼ max FZj j¼1;2;... þUEC £ ðNS 2 1Þ ð4Þ
i¼1
The problem, as formulated, is difficult to solve, because it requires to determine m £ n
variables qij which can assume a value between 0 and q_max. In order to simplify the
solution, the problem has been then reformulated introducing a binary formalization
and decomposed in the following three steps:
(1) transformation of the real problem into a binary problem;
(2) search for the best binary combination of m £ n bits which complies with the
transformed constraints and which has the lowest cost; and
(3) transformation of the best binary combination of m £ n bits to a real
combination of m £ n real values, i.e. the desired quantities qij.
The first step is the transformation of the real problem into a binary problem. To each
real variable qij is thus associated a binary variable dij according to the following rules:
(
qij . 0 , dij ¼ 1
ð5Þ
qij ¼ 0 , dij ¼ 0
The previous formulas mean that if the quantity carried to the customer ith by the
truck jth is zero (or, in other words, if the truck jth does not reach the customer ith), the
variable dij is 0 and vice versa. Otherwise, if the quantity carried to the customer ith by
the truck jth is positive (the truck reaches the customer), the variable dij is 1 and vice
versa. Then it is possible to associate to each truck a binary string of n bits (as many as
the number of customers), in which if the ith bit of the string related to the truck jth is
“1” it means that the jth trucks reaches the ith customer, if the bit is “0” it means that
the truck does not reach the customer, as shown in Figure 3.
IMDS Since, the constraint equations cannot be directly translated in binary formulation,
106,5 the check that a given string satisfies the constraints is carried out resorting the
following algorithm which verifies that the sum of quantities ordered by the customers
visited by any subset of trucks is lower than the total capacity of all trucks visiting
such customers.
For T ¼ 1 to m 2 1
728 (1) create all partitions of the overall set of m trucks in two subgroups: FTL1 and
FTL2 (with FTL1 > FTL2 ¼ Ø), constituted of T trucks the first one and
(m 2 T) the second one; and
(2) for each partition, verify if the T trucks satisfy the quantity constraints by
applying the subsequent formula:
n
X
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
next T.
As far as the objective function (equation (4)) is concerned, there is no need of
transformation in binary form because it is independent from the actual quantities
transported and depends only on the visited customers which are specified by the
values of dij variables. This enables to directly calculate the cost of the real shipment
combination corresponding to the binary combination examined.
After the transformation is complete, it is possible to search the binary combination
which complies with the transformed constraints and which allows for minimum cost.
This task has been devoted to a GA. GA is a stochastic global search method that
mimics the process of natural biological evolution (Goldberg, 1989). It operates on a
population of individuals representing candidate solutions to the problem and applies
the principle of survival of the fittest to produce better performing individuals in
subsequent evolutionary generations of the examined population. At each generation,
individuals are selected according to their level of fitness and then they are bred
together. This process leads to the creation of individuals better suited to their
environment than their parents.
GAs show a number of advantages respect other optimisation techniques making
this method suitable for combinatorial optimisation problems even of large size as in
this case. They examine a population of solutions in parallel instead of evaluating a
single solution at a time. GAs do not require any information on the derivative of the
objective function (as happens in gradient methods) and the sole value of the objective
function influences the direction of the search. Finally, GAs can give a certain number
of potentially optimal solutions, and the final choice can be demanded to the user. This
characteristic can be important when a problem has a group of optimal solutions, as
happens in multi-objective optimisation.
Figure 3. TRUCK j-th 0 1 0... 0101 bit i-th =0: truck j-th does not reach
Binary coding of truckload customer j-th
shipping
n
A flow chart of the adopted GA method is shown in Figure 4. Freight
In this problem, the population is a group of individuals, and an individual is a transportation
string of n £ m bits which complies with the transformed constraints. It is important to
highlight that in the developed GA, the check on constraints satisfaction is performed planning
any time a new individual joins the population. Moreover, at each generation, only new
individuals different from the already existing ones are accepted to join the population.
If, in fact, in the creation of the new generation an individual is produced who is equal 729
to an already existing one it is rejected and tries to further generate a new individual.
The first step of the GA is the creation of an initial population: a certain number of
individuals are randomly created so as to start the optimisation process. Then, for each
individual its cost is computed, and subsequently the calculation of the fitness function
is performed. The fitness function (equation (7)) indicates the quality of the single
individual with respect to the entire population according to the chosen performance
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
measure. In this case, an individual whose cost is less than the average cost has a
fitness function higher than the average:
average_cost K
fitness ðindividualÞ ¼ ð7Þ
individual_cost
The parameter K is a convergence parameter, and in the present problem, it is used to
change the importance given to the best individuals: a very high K parameter makes
the best individuals very favoured, making the search more rapid, but also causes the
decrease of the genetic variety. So it is important, for each kind of problem, the
determination of the most appropriate K parameter.
Subsequent step is the selection process which consists in creating couples of
individuals who will generate offsprings once the desired number of offsprings per
generation has been fixed. This implies at first determining for each individual a
probability of reproducing which is proportional to the value of its fitness function, and
subsequently picking the couples of individuals for reproduction, also known as
sampling, in a number able to produce the required number of offsprings. This is
carried out resorting to proper selection algorithms. In this work, the stochastic
universal sampling method is adopted.
The successive phase is the creation of the new generation of individuals. The new
generation is composed by:
.
the best individual copied from the previous generation;
.
new individuals randomly generated;
.
new individuals obtained by crossover recombination of the selected individuals
of the previous generation; and
.
mutant individuals.
Copy of the previous generation best individual enables to maintain the best result
reached so far. Random generation of new individuals enables to maintain the genetic
NO
CREATION OF
INITIAL
COST
FITNESS
FUNCTION
SELECTION
CREATION OF
THE NEXT
NUMBER OF
GENERATION =
YES CHOICE OF
OPTIMAL
Figure 4.
CALCULATION PROCESS
POPULATION CALCULATION GENERATION N_MAX? INDIVIDUAL Generic GA flow chart
IMDS variety, because such individuals are absolutely independent from the best individual
106,5 of the present generation, and this enables to overcome local minima. Recombination of
individuals to create offspring enables to reproduce the best features of existing
individuals into new individuals. According to the uniform crossover process adopted
in this work, given a couple of parents individuals, a crossover mask of k bits (the same
length as the parent individuals) is randomly generated, which determines from which
730 parent each bit is copied (Figure 5).
In greater detail, as shown in Figure 5, if the ith bit of the mask is “1” the
corresponding bit of the offspring 1 is the same of first parent, otherwise if the ith bit of
the mask is “0” the corresponding bit of the offspring 1 is the same of the second parent.
The last option is the mutation of some individuals. Mutation is the process which
changes a part of an individual to create a new individual, different from the original.
The purpose of the mutation process is to examine a wider range of solutions in order
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
to maintain the genetic variety. In the developed method, it has been chosen a dynamic
approach to the mutation process. Particularly, the higher the persistence of the same
best individual in a population, meaning that a local minimum has been reached, the
higher is the mutation frequency. More specifically, the number of individuals to
mutate and the maximum number of bits to mutate are growing functions with the
growth of the persistence of the same best individual. This approach enables to
overcome local minima with a reduced number of generations respect the adoption of a
fixed percentage of mutations.
When the number of generations reaches the limiting value N_MAX, the iterative
process is terminated and the resulting best individual is picked to represents the
desired solution, i.e. the combination of m £ n bits which complies with the constraints
at the lowest cost.
As known, GA does not allow to know if it reached the optimal solution or simply a
sub-optimal, although very good, solution. Therefore, it is very important that the GA
parameters are set at values allowing the system to perform satisfactorily while
containing the computation time. In particular, two parameters must be fixed: the
number of individuals and the number of generations N_MAX. Both are growing
functions of the size of the problem which is defined by the length of the individual,
m £ n: In the adopted approach, the relation between the length of the individual and
the number of individuals in a population is linear, and so is the relation between the
length of individuals and N_MAX:
PARENT 1 O1
1 0 1 0 1 1
1 1 1 0 0 1
PARENT 2 O2
1 1 0 1 0 1
1 0 0 1 1 1
Figure 5. MASK
Uniform crossover method
1 0 1 1 0 1
(
num_ind ¼ A1 þ B1 £ Lind Freight
ð8Þ transportation
N _MAX ¼ A2 þ B2 £ Lind
planning
in which A1, B1, A2, B2 are constants and Lind ¼ m £ n:
Adoption of linear relations guarantees that the search’s dimension grows with the
growth of the problem’s dimension, but while the complexity of the problem grows as 731
2m£n ; the time complexity of the related GA grows as OðL3ind Þ:
At the conclusion of the GA execution, it is necessary to transform the obtained
binary string in a real string of m £ n quantities, in order to create the physical
shipments, and this is the third step of FTLs optimisation procedure. As the best
binary string already complies with the constraints, it will certainly exist a real string
of m £ n quantities, related to the binary string, that satisfies the real constraints. So
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
In this work, this system has been solved by the application of the Fourier-Motzkin
method, which is based on the transformation of the original system into an equivalent
one much simpler to solve. As a result, the quantities each truck has to deliver to the
customers are computed, and the system can create the best FTL shippings list.
Merging such result with the optimal LTL shipments list previously created, enables to
generate the overall optimal shipping list.
Application example
To empirically validate this DSS, it was applied to the case of an Italian firm,
producing plastic film for packaging and having about 200 million euros annual
revenues. The firm has two plants in the central and southern Italy, and supplies the
European, North African and Asian markets. European customers are supplied by
road transport, both FTL and LTL shipments, while the remaining markets are mainly
supplied by sea transport. The analysis considered the 4,254 orders delivered in the
period January-March 2002 towards 224 different customers located in the continental
Europe. Such orders were shipped in 837 truckloads on the basis of a manual planning
operated by the logistics manager. Overall shipping cost was about 1.2 million euros.
At first, relying on aggregate historical data, a statistical analysis about the
FTL/LTL shippings partition was carried out, concerning number of loads, delivered
quantities and costs, obtaining the percentage values shown in Figure 6.
As a result 79 per cent of loads were composed of LTLs, while the remaining 21 per
cent were FTL shippings. About 32 per cent of the total 12,290.725 ton delivered were
IMDS shipped as LTLs while 68 per cent as FTLs. The total cost for the considered period
106,5 was 1,197.179e composed as 46.5 per cent of LTLs costs and 53.5 per cent of FTLs
costs. The average costs per quantity was 85 e/t for FTL shippings and 155 e/t for LTL
shippings. Average truck filling percentage was about 69 per cent for FTLs.
Such data indicated a non optimal shipping policy as LTL shipments were the
majority but accounted for only a third of transported freight while being still
732 responsible for nearly half of total costs. On the contrary, FTL shipments appeared
much more efficient and effective. In fact with a limited number of shipments about
two-thirds of goods were transported with only slightly more than 50 per cent of total
costs.
Subsequently, the proposed optimisation model was applied on a subset of orders in
the January-March 2002 period in order to generate alternative optimal shippings lists
for sake of comparison. Owing to incomplete historical data, only a subset of the total
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
4,254 orders for which complete shipping data were available was utilized in the
optimisation phase. However, in the following analysis, per cent savings are shown
respect the actual historical cost of the same subset of orders. In order to utilize the
proposed approach, at first the values of the following three optimisation parameters
had to be set: the maximum weight per truck, the economic compatibility limit (ECL),
and the order visibility time bucket (OVTB), i.e. the time horizon over which orders are
visible and can be aggregated. As far as the first parameter is concerned, European
countries limit, in fact, the maximum total weight of the truck, which includes the
weight of the empty truck and the weight of carried goods. This weight limit is not the
same for all countries: France and Austria have a stricter limit than other countries.
As a consequence, two different values were considered, a first constraint of 25 ton
for all shipments involving crossing of Austria or France, and a limit of 26 ton relating
to all remaining shippings. The ECL, that is the maximum difference between FZ rates
for zones which may form a COG, was varied parametrically from 0 to 350e. Finally,
the OVTB was changed in the 1-13 weeks range. To evaluate effects of ECL variations,
OVTB was set at four weeks, while ECL was set at 150e when OVTB was changed.
Effects of ECL change are shown in Figures 7-10.
It appears immediately evident that the computer-aided system was able to generate
a significantly greater percentage of FTL shipments respect the manual planning
operated by the transportation manager. Figure 7, referring to the changes in the
LTL/FTL ratio, also shows that when the ECL grew the number of shipment
decreased, due to the progressive shift from LTL to FTL. The transfer of orders from
LTLs to FTLs was evident also when considering the quantities carried and costs paid
100
90
80
70
Percent(%)
60
50
40
30
Figure 6. 20
LTL
Firm data – LTLs vs 10
FTL
FTLs 0
Number Tons Costs
350
FTL
Freight
transportation
Number of shipments
300 LTL
250 planning
200
150
100 733
50
Figure 7.
0 Number of shipments as
0 12 25 50 80 100 120 150 200 250 300 350 function of ECL
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
6000
FTL
LTL
5000
Quantity (t)
4000
3000
2000
1000
Figure 8.
0 Quantity shipped as
0 12 25 50 80 100 120 150 200 250 300 350 function of ECL
400000 FTL
350000 LTL
300000
250000
200000
150000
100000
50000 Figure 9.
0 Shipments cost as function
0 12 25 50 80 100 120 150 200 250 300 350
of ECL
(Figures 8 and 9). The per cent savings obtained as ECL increased are shown instead in
Figure 10. In the analysed case study, the trend of savings showed an initial growth,
then it reached a maximum (about 37.4 per cent of saving), followed by a gradual
decrease, and a final stabilization. As a matter of fact, a low ECL guarantees that the
cost of FTLs is low because all zones to be reached have a similar rate, but also
prevents the creation of suitable aggregations of orders, owing to the strict constraints
it fixes, and then it leads to increased utilization of LTLs. On the other side, a high ECL
allows the creation of suitable aggregation of orders, but the costs of FTLs are higher.
IMDS 38.00
106,5 37.80
37.60
500
450
Number of shipments
400 FTL
350 LTL
300
250
200
150
100
50
Figure 11.
Number of shipments as 0
1 2 4 13
function of OVTB
OVTB (weeks)
horizon of orders visibility, and this also had beneficial effects on the quantities carried Freight
and on the shippings costs (Figures 12 and 13). transportation
Figure 14 shows the resulting percentage savings, making it clear that if the OVTB
increased, the savings grew too, although with a progressively reduced relative planning
increment. The greatest savings increment was obtained passing from one to two
weeks of OVTB. However, even if Figure 13 shows that the highest savings were
obtained for 13 weeks of OVTB, it should be remarked that for many firms often it is 735
almost impossible to know customers orders more than two or four weeks in advance.
6000
5000
4000
Quantity(t)
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
3000
2000
1000
FTL
LTL
Figure 12.
0 Quantity as function of
1 2 4 13
OVTB
OVTB (weeks)
450000
FTL
400000
LTL
350000
300000
250000
200000
150000
100000
50000 Figure 13.
0 Shipment cost as function
1 2 4 13 of OVTB
OVTB (weeks)
45
40
Percent savings (%)
35
30
25
20
15
10
5 Figure 14.
0 Percentage savings as
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 function of OVTB
OVTB (weeks)
IMDS Nevertheless, this is not a major drawback as the system offered the best incremental
106,5 performance passing from one to two weeks, and this is a useful result because it is not
so difficult to obtain a two weeks OVTB, while for such order of magnitude the value of
percentage savings were about 34 per cent, a substantial result.
However, while such results are strictly applicable to the examined case only, they
have a more general validity. As a concluding remark, this analysis showed two
736 categories of problems in the analysed firm. At first, the chosen carrier was not the
optimal one in 55 per cent of shipments because the best carrier was often actually
unknown given the large number of shipping zones to be considered. Moreover, the
analysis showed an excessive use of LTL shipments which ultimately penalized the
overall logistic performances. The main cause was the presence of marginal customers
requiring small quantities of goods and/or the high number of customers in
geographically/commercially marginal areas. In this cases, the application of the
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
Managerial implications
In this work, an optimisation methodology for optimally planning long-haul road
transport shipments through proper aggregation of customer orders into separate FTL
or LTL shipments was presented. The method has relevant practical applications in
that it enables to rapidly choose whether a customer order should be shipped via a FTL
or a LTL transport, and performs the aggregation of different orders into separate
shipments in order to minimize total transportation costs. As a consequence, the task of
logistics managers is greatly simplified and consistently better performances respect
manual planning can be obtained.
Therefore, the described transportation planning method may help solving one of
the typical problems affecting logistics managers decisions, i.e. the excessive use of
LTL shipment which, being much less cost-effective that FTL shipments, ultimately
penalize the overall logistic performances.
In fact, if an excess use of FTL is motivated by the presence of marginal customers
requiring small quantities of goods and/or a high number of customers in
geographically/commercially marginal areas, the utilization of the model can help in
improving orders aggregation so that an increase of the percentage of FTL shipments
is obtained respect a manual planning.
Moreover, the utilization of the associated DSS in a what-if manner by changing the
settings of the model parameters enables also to gain significant managerial insights
about the trade-offs involved in transportation planning decisions. This knowledge
may help to improve the overall effectiveness and efficiency of the logistics
department. As an example, the DSS utilization helps to point out the important
opportunity offered by LTL shipments in minimizing total transportation expenses, so
that they can be still considered an important leverage to be acted upon instead of a
merely residual choice.
Furthermore, the model enables to assess the effect of changing the ECL limit, so
that in any given scenario, the manager can choose the right value for this important
parameter which affects the orders aggregation choices and ultimately defines the Freight
balance among FTL and LTL shipments. Finally, the model utilization also enables to transportation
evaluate the effects of changing the time bucket over which prospective order may be
aggregated. The possibility of knowing how much the savings would grow by planning
increasing the OVTB is a very important result for business managers who can assess
the advantage of an extended OVTB, and can evaluate the opportunity of changing the
sales policies to obtain a longer OVTB value. 737
Conclusions
This work focused on the development of a DSS which generates optimal truck
shipments from a transportation orders list. After a statement of the problem and its
mathematical formulation, an optimisation approach was presented based on the
application of a GA which creates compatible groups of orders and optimizes each one
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
of them separately in order to minimize total shipment costs using either LTL and FTL
shipping modes.
The method, through a decomposition of the list of delivery orders into compatible
groups, their further association to LTL or FTL shipments, and the aggregations of
FTL transports into optimal shipments, enables to minimize the total transportation
cost yielding potential savings even higher than 35 per cent respect traditional manual
planning as demonstrated in the analysed case study.
Owing to the adoption of GAs and some simplifying assumptions, the method is
fast enough to enable its use in a day-to-day industrial context. The application of the
method to an industrial case study also showed how the system may exploit the
economies of scale of FTL better than a traffic manager could do through manual
planning, but also that LTL may be a useful leverage for reducing total costs and
should be considered as an additional resource when planning a shipment strategy
rather than a residual choice. As future research objectives, refined heuristic
procedures will be searched to more effectively aggregate shipments into compatible
sets before the optimisation algorithm carries out the assignments of customer orders
to separate truckloads. Furthermore, new cost functions will be made available to
model different shipment scenarios, and the effects of more strictly integrating the
shipment planning problem with production planning and marketing management
will be explored.
References
Allen, W.B. and Liu, D. (1995), “Service quality and motor carrier costs: an empirical analysis”,
The Review of Economics and Statistics, Vol. 77 No. 3, pp. 499-509.
Brown, G.G. and Ronen, D. (1997), “Consolidation of customer orders into truckloads at a large
manufacturer”, Journal of the Operational Research Society, Vol. 48 No. 8, pp. 779-85.
Caputo, A.C., Cucchiella, F., Fratocchi, L., Pelagagge, P.M. and Scacchia, F. (2004), “Analysis and
evaluation of e-supply chain performances”, Industrial Management & Data Systems,
Vol. 104 No. 7, pp. 546-57.
Caputo, A.C., Fratocchi, L. and Pelagagge, P.M. (2005), “A framework for analysing long-range
direct shipping logistics”, Industrial Management & Data Systems, Vol. 105 No. 7,
pp. 876-99.
Christensen, L.R. and Huston, J.H. (1987), “A re-examination of the cost structure for specialized
motor carriers”, Logistics and Transportation Review, Vol. 23 No. 4, pp. 339-51.
IMDS Crainic, T.G. (1999), “Long-haul freight transportation”, in Hall, R.W. (Ed.), Handbook of
Transportation Science, Kluwer Academic Publishers, Dordrecht, pp. 433-91.
106,5 Crainic, T.G. (2000), “Service network design in freight transportation”, European Journal of
Operational Research, Vol. 122, pp. 272-88.
Crainic, T.G. and Laporte, G. (1997), “Planning models for freight transportation”, European
Journal of Operational Research, Vol. 97, pp. 409-38.
738 European Communities (2003), Panorama of Transport: Statistical Overview of Transport in the
European Union, Office for Official Publications of the European Communities,
Luxembourg, ISBN 92-894-4993-4.
Goldberg, D.E. (1989), Genetic Algorithms in Search, Optimization, and Machine Learning,
Addison-Wesley, Reading, MA.
Harmatuck, D.J. (1992), “Motor carrier cost function comparison”, Transportation Journal, Vol. 31
No. 4, pp. 31-46.
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
Helo, P. and Szekely, B. (2005), “Logistics information systems: an analysis of software solutions
for supply chain co-ordination”, Industrial Management & Data Systems, Vol. 105 No. 1,
pp. 5-18.
Kuo, C. and Soflarsky, F. (2003), “An automated system for motor carrier selection”, Industrial
Management & Data Systems, Vol. 103 No. 7, pp. 533-9.
Lursen, S. and Yang, J. (1996), “Application of DSS in truck dispatching”, Proceedings of 27th
Annual Meeting of the Decision Sciences Institute, 24-26 November, Orlando, FL, Vol. 2,
pp. 556-8.
Ma, H. and Davidrajuh, R. (2005), “An iterative approach for distribution chain design in agile
virtual environment”, Industrial Management & Data Systems, Vol. 105 No. 6, pp. 815-34.
Narasihman, M. and Santosh, M. (2004), “Decision models in global supply chain management”,
Industrial Marketing Management, Vol. 33 No. 1, pp. 21-7.
Powell, W.B. and Sheffi, Y. (1989), “Design and implementation of an interactive optimization
system for the network design in the motor carrier industry”, Operations Research, Vol. 37
No. 1, pp. 12-29.
Roy, J. and Delorme, L. (1989), “NETPLAN: a network optimization model for tactical planning in
the less-than-truckload motor carrier industry”, INFOR Journal, Vol. 27 No. 1, pp. 22-35.
Soliman, F. and Youssef, M.A. (2003), “Internet-based e-commerce and its impact on
manufacturing and business operations”, Industrial Management & Data Systems, Vol. 103
No. 8, pp. 546-52.
Trappey, A.J.C., Trappey, C.V., Hou, J.L. and Chen, B.J.G. (2004), “Mobile agent technology and
application for online global logistic service”, Industrial Management & Data Systems,
Vol. 104 No. 2, pp. 169-83.
Zografos, K.G. and Ginnouli, I.M. (2002), “Emerging trends in logistics and their impact on
freight transportation systems: a European perspective”, Transportation Research Record,
No. 1790, 02-4177, pp. 36-44.
Corresponding author
P.M. Pelagagge can be contacted at: [email protected]
1. Henry C. W. Lau. 2015. Computational Intelligence Approach for Process Parameter Settings Using
Knowledge Representation. Lecture Notes on Software Engineering 3, 49-52. [CrossRef]
2. A. Azadeh, M. Taghipour, S.M. Asadzadeh, M. Abdollahi. 2014. Artificial immune simulation for
improved forecasting of electricity consumption with random variations. International Journal of Electrical
Power & Energy Systems 55, 205-224. [CrossRef]
3. Uroš Klanšek. 2014. Solving the nonlinear discrete transportation problem by MINLP optimization.
Transport 29, 1-11. [CrossRef]
4. Mark Ko, Ashutosh Tiwari, Jörn Mehnen. 2010. A review of soft computing applications in supply chain
management. Applied Soft Computing 10:3, 661-674. [CrossRef]
5. Hans-Otto Günther, Thorben Seiler. 2009. Operative transportation planning in consumer goods supply
chains. Flexible Services and Manufacturing Journal 21:1-2, 51-74. [CrossRef]
Downloaded by SELCUK UNIVERSITY At 09:45 29 January 2015 (PT)
6. H.C.W. Lau, C.X.H. Tang, G.T.S. Ho, T.M. Chan. 2009. A fuzzy genetic algorithm for the discovery
of process parameter settings using knowledge representation. Expert Systems with Applications 36:4,
7964-7974. [CrossRef]
7. Harry K.H. Chow, K.L. Choy, W.B. Lee. 2007. Knowledge management approach in build‐to‐order
supply chains. Industrial Management & Data Systems 107:6, 882-919. [Abstract] [Full Text] [PDF]