Location-Routing for Distribution Centers
Site: | Saylor Academy |
Course: | BUS606: Operations and Supply Chain Management |
Book: | Location-Routing for Distribution Centers |
Printed by: | Guest user |
Date: | Saturday, November 2, 2024, 9:10 PM |
Description
Read this article. One objective of this paper is to determine distribution center locations. Compare and contrast the two cases presented.
Abstract
Nowadays, organizations have to compete with different competitors in regional, national and international levels, so they have to improve their competition capabilities to survive against competitors. Undertaking activities on a global scale requires a proper distribution system which could take advantages of different transportation modes. Accordingly, the present paper addresses a location-routing problem on multimodal transportation network. The introduced problem follows four objectives simultaneously which form main contribution of the paper; determining multimodal routes between supplier and distribution centers, locating mode changing facilities, locating distribution centers, and determining product delivery tours from the distribution centers to retailers. An integer linear programming is presented for the problem, and a genetic algorithm with a new chromosome structure proposed to solve the problem. Proposed chromosome structure consists of two different parts for multimodal transportation and location-routing parts of the model. Based on published data in the literature, two numerical cases with different sizes generated and solved. Also, different cost scenarios designed to better analyze model and algorithm performance. Results show that algorithm can effectively solve large-size problems within a reasonable time which GAMS software failed to reach an optimal solution even within much longer times.
Source: Saeed Fazayeli, Alireza Eydi, and Isa Nakhai Kamalabadi, https://link.springer.com/article/10.1007/s40092-017-0218-6
This work is licensed under a Creative Commons Attribution 4.0 License.
Literature review
This study integrates multimodal transportation
and LRP. Both of them are apparently independent fields of research and
will be discussed separately. Also a few papers jointly discussing the
two concepts are also cited. Different researchers used combination of
problems to define their model. Shen et al. presented location
and inventory problems together. Azadeh et al. considered vehicle
routing and inventory decisions simultaneously. Beginning of LRP
development can be traced back to 70 and 80s when Laporte and Nobert presented a single-depot model which was subsequently used by
other researchers. Loperte et al. considered multi-depot LRP to
further develop the problem. Thereafter, various authors has introduced
different approaches to the problem which can be classified based on
problem structure (single-echelon or multi-echelon), type of data
(deterministic, probabilistic, or fuzzy), number of product types
(single-product or multi-product), number and capacity of facilities
(single-facility or multi-facility, capacitated or incapacitated), type
and capacity of vehicles (homogenous or heterogeneous, capacitated or
incapacitated), time window and problem type (soft or hard), number of
objective functions (single-objective or multi-objective), and solving
methods (exact, heuristic, meta-heuristic, and combinational). In this
regard, some researchers present review
papers.
Wu et al. designed a three echelon LRP. They also
considered tight time windows and time deadlines to create services for
high-speed trains. Albareda-Sambola et al. proposed a
multi-period LRP model and a stable model against time. An approximation
based on replacing vehicle routes by spanning trees is proposed, and
its capability for providing good quality solutions is assessed in a
series of computational experiments Karaoglan et al. used goods
pick and delivery planning in LRP. The authors proposed two
polynomial-size mixed integer linear programming formulations for the
problem and a family of valid inequalities to strengthen their
formulation. Rodriguez-Martin and Salzar-Gonzalez considered
locations of and routing through hub facilities. Proposed model decide
on the location of hubs, the allocation of nodes to hubs, and the
routing among the nodes allocated to the same hubs, with the aim of
minimizing the total transportation cost. Ahmadi-Javid and Seddighi set probabilistic facility capacity and disruption risk in the
problem. The goal is to determine the location, allocation and routing
decisions that minimize the annual cost of location, routing and
disruption. Tavakkoli-Moghaddam and Raziei took demands as fuzzy
numbers. They present a bi-objective location-routing-inventory problem
with heterogeneous fleets in a two-echelon distribution network and
fuzzy demands. Ghezavati and Beigi proposed a bi-objective
mathematical model for location-routing problem in a multi-echelon
reverse logistic network. Their proposed network consists of hybrid
collection/inspection centers, recovery centers and disposal centers.
They considered total cost minimization and minimizing the maximum time
of completion of the collecting return products as objective functions.
Hiassat et al. also considered location-routing-inventory problem
for perishable products distribution. Samanlioglu developed a
LRP for dangerous materials handling. In this paper, a new
multi-objective location-routing model is developed, and implemented in
the Marmara region of Turkey. Shahabi et al. added inventory
management to three levels LRP. They also assumed that demand across the
retailers is to be correlated as Najjartabar et al. which
considered correlated demands in location-inventory problem in a three
level supply chain. Aghighi and Malmir used location-routing
inventory problem on perishable product distribution system design. In
this paper, authors considered stochastic demands and travel times and
solved problem in two phases. And Fazel Zarandi et al. considered
time window, fuzzy demand, and fuzzy travel times at the same time.
Moreover these papers, Govindan et al. proposed LRP in a
sustainable network. Sustainable networks have a growing trend in supply
chain problems. Afshar-Bakeshloo et al. developed a model, named
Satisfactory-Green Vehicle Routing Problem. It consists of routing a
heterogeneous fleet of vehicles to serve a set of customers within
predefined time windows. Also, Najjartabar-Bisheh et al. analyzed
the role of third-party companies in a sustainable supply chain design.
As
LRPs, multimodal transportation papers can be classified based on their
planning time horizon (strategic, tactical, or operational). More
recently, Crainic and Steadie Seifi et al. classified the
researches on multimodal transportation in two review papers and can be
referred for more studies.
Following studies are joint papers for
both LRP and multimodal transportation. Li et al. introduced
location of terminals problem on a multimodal transportation network.
The proposed model simultaneously considers choices of travelers on
route, parking location and mode between auto and transit. Chiadamrong
and Kawtummachai designed a methodology to support decision
making on sugar industry. This aim of this paper is to suggest the best
inventory position and transportation route in the distribution system
considering different transportation options. Tiwari et al. considered route selection on a multimodal transportation network with
several objectives: minimization of travel time and travel cost, later
schedules and delivery times of every service provider in each pair of
location, and lastly variable cost must be included in every location.
Alumur et al. considered hub location problem and hub network
design and assumed the hub and non-hub nodes are linked via multimodal
transportation. Also, Moccia et al. considered hub facilities on
multimodal network, but they proposed and solved a routing problem. Xie
et al. considered mode changing facility location and multimodal
route selection problem on a multimodal network for dangerous materials
transportation. They considered different origin/destination pairs and
selected the best multimodal route with determining mode changing
points. Hajibabai and Ouyang presented a location and routing
problem for biofuel transformation facilities on a multimodal network.
In this study, first, some locations were selected for biofuel
transformation facilities which were to be located between supplier and
customers; then, multimodal routes were determined connecting suppliers
to the facilities and then the facilities to customers. However, they
presumed the routes to be of multimodal nature, neglecting to consider
different modes and mode changing issues. Tuzkaya et al. presented distribution facilities location problem in a multimodal
transportation network. In their approach, in the first phase, using
analytic network process (ANP), a decision was made on the best
transportation mode and the best potential sites to establish
facilities; in the second phase, distribution facilities location
problem was solved. Finally, Ayar and Yamaded time windows to
multimodal routing problems.
Even though location-routing
problem has experienced various developments during recent past, yet few
papers are reported, wherein multimodal transportation is accounted for
in such problems. To the best of our knowledge, no paper in the
literature considered products delivery tours from DCs to customers
while determining routs from supplier to DCs on multimodal network at
the same time. Using multimodal logistics is an indispensable option for
world class organizations, so the present paper is an attempt to
fill-in this gap in the research field of location-routing.
Introduction
Effective
and efficient transportation of materials and products through the
chain of suppliers, manufacturers, assemblers, distribution centers
(DCs), retail stores, and customers is crucial in the competitive world
of today. In other words, transportation is a key part of a supply chain
which ensures on-time delivery of raw materials and finished products. Decisions made regarding a supply chain transportation
system can be classified into three different levels. The first level
refers to strategic decisions with long-term (several years) effects on
the supply chain. These are mainly the decisions made on the
transportation system design and supplying resources (facility location,
size and capacity of facilities, facility and plant layout,
transportation fleet). The next level is tactical decisions which has
mid-term effects (several months or quarters) and include production and
distribution planning and resource allocation issues (facility space,
fleet size and shipments packaging strategies). Third level is
operational decisions which are made on a daily or weekly basis. Orders
aggregation, shipments, and vehicle fleet dispatch are examples of these
decisions. For the last four decades, researchers
have studied combination of these decisions with a combinational view to
supply chain and transportation problems. In this regard,
location-routing problem (LRP) considers both location (strategic level)
and routing (tactical level) problems. LRP represents a relatively new
form of location problems addressing locating facilities such as
distribution centers and depots, where routing aspects are
simultaneously considered. Reflecting interactions between facility
location and fleet routing, LRP can provide a better view for logistics
analysts and managers, preventing poor and local optimizations. LRP had
growing trends especially in recent years. Govindan et al. used LRP in perishable products distribution system design.
Riquelme-Rodríguez et al. present and compare two methods for
locating water depots along the road network and used arc routing in
their problem. And Gao et al. introduced ant colony optimization
with clustering for solving the dynamic location-routing problem.
Seyedhosseini et al. reviewed dynamic location problems based on
their models, solution, methods and applicability and analyzed gaps for
future research. It can also be used for dynamic LRPs.
In
general, because of geographical distances between producers and
consumers demand for goods transportation has raised. Transportation, especially in long distances, is a world class
business which cannot be accomplished through roads only due to
availability and cost concerns. So there is a need for other
transportation modes or a combination of them (i.e., multimodal
transportation). European Conference of Ministers of Transport in 2001
defined multimodal transportation as "movement of goods in one and the
same loading unit or vehicle, which uses successively two or more modes
of transport without handling the goods themselves in changing modes".
Multimodal transportation has experienced an increased importance during
recent years and now multimodal transportation is competing with
single-mode transportation. In this regard, many transportation
companies have established multimodal transportation services. The
second point is that, multimodal transportation is becoming an important
policy for organizations because of its advantages in terms of cost and
coordination between modes in large-scale cargoes. The
third point is that, in references and handbooks of transportation,
multimodal transportation is treated as an independent and
well-separated transportation mode. Last but not least,
since 1990, the number of papers on multimodal transportation follows a
growing trend. Some researchers have reviewed
the related literatures. To sum up,
multimodal transportation is a relatively new field of research, with
its increasing importance during recent years.
The objective of
this study is to help designing a distribution system with two
transportation network types. First network transfers products from
supplier (with determined location) to DCs via a multimodal
transportation system. On second network, products are distributed among
customers via routing tours started from DCs on a single-mode network.
In this problem, different questions will be answered: which multimodal
route should be used to transfer products to DCs? Is there need to
change mode in determined multimodal routes? And if yes, mode changing
facilities should locate on which multimodal terminals? Each routing
tour generated from open DCs, meet which customers and in what order? In
fact, this study considers LRP and multimodal route selection problem
simultaneously.
Research methodology is consists of the following
sections. First, introduced problem modeled as a linear programming
with a cost minimizing objective. Then mathematical model solved with
GAMS optimizing software and CPLEX solver for two different numerical
instances. Also, a genetic algorithm generated for the problem and its
results compared with CPLEX results.
The following section gives a
review on related literatures on multimodal logistics and
location-routing problem. Then, the subsequent section gives an
explanation of the proposed problem, followed by the section introducing
the corresponding mathematical model. In the following section, the
used solving approach is introduced before demonstrating and solving two
different numerical cases, where the cases are further analytical
discussed. The final section concludes the paper.
Literature review
This study integrates multimodal transportation
and LRP. Both of them are apparently independent fields of research and
will be discussed separately. Also a few papers jointly discussing the
two concepts are also cited. Different researchers used combination of
problems to define their model. Shen et al. presented location
and inventory problems together. Azadeh et al. considered vehicle
routing and inventory decisions simultaneously. Beginning of LRP
development can be traced back to 70 and 80s when Laporte and Nobert presented a single-depot model which was subsequently used by
other researchers. Loperte et al. considered multi-depot LRP to
further develop the problem. Thereafter, various authors has introduced
different approaches to the problem which can be classified based on
problem structure (single-echelon or multi-echelon), type of data
(deterministic, probabilistic, or fuzzy), number of product types
(single-product or multi-product), number and capacity of facilities
(single-facility or multi-facility, capacitated or incapacitated), type
and capacity of vehicles (homogenous or heterogeneous, capacitated or
incapacitated), time window and problem type (soft or hard), number of
objective functions (single-objective or multi-objective), and solving
methods (exact, heuristic, meta-heuristic, and combinational). In this
regard, some researchers present review
papers.
Wu et al. designed a three echelon LRP. They also
considered tight time windows and time deadlines to create services for
high-speed trains. Albareda-Sambola et al. proposed a
multi-period LRP model and a stable model against time. An approximation
based on replacing vehicle routes by spanning trees is proposed, and
its capability for providing good quality solutions is assessed in a
series of computational experiments Karaoglan et al. used goods
pick and delivery planning in LRP. The authors proposed two
polynomial-size mixed integer linear programming formulations for the
problem and a family of valid inequalities to strengthen their
formulation. Rodriguez-Martin and Salzar-Gonzalez considered
locations of and routing through hub facilities. Proposed model decide
on the location of hubs, the allocation of nodes to hubs, and the
routing among the nodes allocated to the same hubs, with the aim of
minimizing the total transportation cost. Ahmadi-Javid and Seddighi set probabilistic facility capacity and disruption risk in the
problem. The goal is to determine the location, allocation and routing
decisions that minimize the annual cost of location, routing and
disruption. Tavakkoli-Moghaddam and Raziei took demands as fuzzy
numbers. They present a bi-objective location-routing-inventory problem
with heterogeneous fleets in a two-echelon distribution network and
fuzzy demands. Ghezavati and Beigi proposed a bi-objective
mathematical model for location-routing problem in a multi-echelon
reverse logistic network. Their proposed network consists of hybrid
collection/inspection centers, recovery centers and disposal centers.
They considered total cost minimization and minimizing the maximum time
of completion of the collecting return products as objective functions.
Hiassat et al. also considered location-routing-inventory problem
for perishable products distribution. Samanlioglu developed a
LRP for dangerous materials handling. In this paper, a new
multi-objective location-routing model is developed, and implemented in
the Marmara region of Turkey. Shahabi et al. added inventory
management to three levels LRP. They also assumed that demand across the
retailers is to be correlated as Najjartabar et al. which
considered correlated demands in location-inventory problem in a three
level supply chain. Aghighi and Malmir used location-routing
inventory problem on perishable product distribution system design. In
this paper, authors considered stochastic demands and travel times and
solved problem in two phases. And Fazel Zarandi et al. considered
time window, fuzzy demand, and fuzzy travel times at the same time.
Moreover these papers, Govindan et al. proposed LRP in a
sustainable network. Sustainable networks have a growing trend in supply
chain problems. Afshar-Bakeshloo et al. developed a model, named
Satisfactory-Green Vehicle Routing Problem. It consists of routing a
heterogeneous fleet of vehicles to serve a set of customers within
predefined time windows. Also, Najjartabar-Bisheh et al. analyzed
the role of third-party companies in a sustainable supply chain design.
As
LRPs, multimodal transportation papers can be classified based on their
planning time horizon (strategic, tactical, or operational). More
recently, Crainic and Steadie Seifi et al. classified the
researches on multimodal transportation in two review papers and can be
referred for more studies.
Following studies are joint papers for
both LRP and multimodal transportation. Li et al. introduced
location of terminals problem on a multimodal transportation network.
The proposed model simultaneously considers choices of travelers on
route, parking location and mode between auto and transit. Chiadamrong
and Kawtummachai designed a methodology to support decision
making on sugar industry. This aim of this paper is to suggest the best
inventory position and transportation route in the distribution system
considering different transportation options. Tiwari et al. considered route selection on a multimodal transportation network with
several objectives: minimization of travel time and travel cost, later
schedules and delivery times of every service provider in each pair of
location, and lastly variable cost must be included in every location.
Alumur et al. considered hub location problem and hub network
design and assumed the hub and non-hub nodes are linked via multimodal
transportation. Also, Moccia et al. considered hub facilities on
multimodal network, but they proposed and solved a routing problem. Xie
et al. considered mode changing facility location and multimodal
route selection problem on a multimodal network for dangerous materials
transportation. They considered different origin/destination pairs and
selected the best multimodal route with determining mode changing
points. Hajibabai and Ouyang presented a location and routing
problem for biofuel transformation facilities on a multimodal network.
In this study, first, some locations were selected for biofuel
transformation facilities which were to be located between supplier and
customers; then, multimodal routes were determined connecting suppliers
to the facilities and then the facilities to customers. However, they
presumed the routes to be of multimodal nature, neglecting to consider
different modes and mode changing issues. Tuzkaya et al. presented distribution facilities location problem in a multimodal
transportation network. In their approach, in the first phase, using
analytic network process (ANP), a decision was made on the best
transportation mode and the best potential sites to establish
facilities; in the second phase, distribution facilities location
problem was solved. Finally, Ayar and Yaman added time windows to
multimodal routing problems.
Even though location-routing
problem has experienced various developments during recent past, yet few
papers are reported, wherein multimodal transportation is accounted for
in such problems. To the best of our knowledge, no paper in the
literature considered products delivery tours from DCs to customers
while determining routs from supplier to DCs on multimodal network at
the same time. Using multimodal logistics is an indispensable option for
world class organizations, so the present paper is an attempt to
fill-in this gap in the research field of location-routing.
Problem description
In a location-routing problem, a supplier of a
product seeks to satisfy demands raised by some retailers in different
locations. To do this, the supplier has to establish a number of DCs.
The problem is defined as the determination of locations for DCs. The
transportation network connecting supplier to potential DCs supposed to
be a multimodal network including three transportation modes (road,
railways and seaways); and transportation from DCs to retailers is
performed via a road network (one mode). On road network products pass
through routing tours to be moved from DCs to retailers. Figure 1
demonstrates the problem schematically. The multimodal links on the
figure can represent either of a road, a railway, a seaway, or a
combination of these transportation modes with multimodal terminals to
change modes.
Fig. 1 Schematic of the proposed problem
This problem is based on the following assumptions:
- Each transportation mode has a specific and determined cost.
- During the transportation operation, transportation mode may be changed at some nodes along the multimodal network.
- Transportation mode can be changed at multimodal terminals where at least two different transportation modes start/end. Providing mode change facilities imposes a fixed cost to the system.
- Product unit does not change when transportation mode changes.
- DCs need a fixed cost to establish.
- Capacities of DCs are constrained by the capacities of the allocated vehicles.
- Retailers' demands are determined and satisfied through routing tours starting from established DCs. The tours return back to the DC after meeting a number of retailers.
- For each DC, one vehicle is allocated with one tour determined for each vehicle.
- Each retailer is assigned to a pair of vehicle and DC.
- Total allocated retailers' demand cannot exceed the vehicle capacity.
Problem formulation
The following notations are used to describe the problem.
Sets
: Transportation modes,
: Set of intermediate nodes (between supplier and DCs) crossed by only one transportation mode
: Set of intermediate nodes (between supplier and DCs) crossed by road and railway transportation modes only
: Set of intermediate nodes (between supplier and DCs) crossed by road and seaway transportation modes only
: Set of intermediate nodes (between supplier and DCs) crossed by railway and seaway transportation modes only
: Set of intermediate nodes (between supplier and DCs) crossed by more than one transportation modes,
: Set of nodes including supplier node as well as the nodes between supplier and potential
: Set of arcs for each transportation mode from supplier to DCs,
: Set of potential DCs
: Set of potential DCs and retailers
: Set of vehicles to be used to deliver products from DCs to retailers
Parameters
: Distance between nodes and
: Distance between nodes and
: Raised demand by retailer
: Unit product distribution cost per unit distance from DCs to retailers by vehicle
: Unit product transportation cost per unit distance for each mode
: Fixed cost of providing a mode changing facility at node ,
: Fixed cost of establishing a DC at node
Decision variables
: Amount of products passing, on the transportation mode m, through link to
Moreover, is
a slack variable used in sub-tour elimination constraint, and is
large enough constant parameter. Note that, if three different modes
cross over one another a node, a combination of the modes is accounted
for and the node will be taken as a member of all three sets, namely
.
The problem formulation is as follows:
(1)
(2)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
Objective
function (1) seeks to minimize costs including multimodal
transportation costs and location-routing costs. First and second
sentences are about location-routing costs which calculate cost of
routing from DCs to retailers and DCs establishment fixed cost,
respectively. Third and fourth sentences, respectively, calculate cost
of transportation from supplier to DC on multimodal network, and cost of
providing mode changing facilities as multimodal transportation costs.
Constraint set (2) defines flow conservation on multimodal network and
states that product flow inters to a node should be to equal product
flow exits it. Mode changing can be happened only on multimodal
terminals (nodes that more than one mode inters or exits the node). For
each transportation mode, if products inter to a multimodal network and
leave it with the same mode, mode changing will not happen and the
corresponding variable will be zero. Same logic uses for
changing modes. Constraint set (3) illustrate this for each node .
As accounted for by constraint set (4), sum of products arriving at a
DC should be equal to total demands raised by the assigned retailers to
that DC. Based on the constraint set (5), each retailer is assigned to
exactly one DC. Constraint set (6) ensures that no product can be
dispatched to a non-established DC and if DC establishment variable
takes zero, all the product flows ending to that DC take zero as well.
Constraint set (7) assigns each retailer to exactly one vehicle, while
the constraint set (8) limits the capacity of the vehicles and ensures
that summation of assigned customers demand does not pass vehicle
capacity. In each product delivery tour on road network, every vehicle
once entered a node will definitely exit that node and constraint set
(9) guarantees that. Constraint set (10) is to ensure that each and
every vehicle is allocated to at most one DC. The absence of common
links between DCs is promised by constraint set (11). The constraint set
(12) assures that a retailer is assigned to a DC if and only if there
is a route from the DC to that retailer. Constraint sets (13) and (14)
state that vehicles can be dispatched only from established DCs.
Constraint set (15) relates to sub-tour elimination, and constraints
(16), (17), and (18) define variables. The last three constraints
determine model variables signs.
Solving approach
To validate mathematical model, two different
numerical cases are solved by optimization software GAMS. Also, due to
linear nature of the model, CPLEX solver was further used. The numerical
cases were run under different scenarios using a personal laptop
equipped with an Intel® Core™ i3 CPU at 2.4 GHz and 6 GB of RAM.
A
location-routing problem combines location and routing problems which
both of them are NP-hard class problems, so LRP is NP-hard as well. To solve a NP-hard problem, a proper solving
algorithm and method is required because as the size of the problem
increases, processing time increases exponentially, as is obviously seen
in the second numerical case.
In this study, a genetic algorithm
with a new chromosome structure is presented to solve problems with
different sizes. The proposed algorithm is composed of the following
components.
Chromosome presentation
Proposed chromosome consists of two separate parts. The first part refers to the multimodal routes from supplier to DCs (on multimodal network), and the second part refers to DCs location and tours routing from DCs to retailers (location-routing problem).
(a) In the first part, a matrix is developed to represent the multimodal route. The matrix dimensions are determined by the number of potential DC and intermediate nodes (between supplier and potential DCs). Number of potential DCs is taken as the number of matrix rows and each row represents a multimodal route for the corresponding potential DC. Regarding the number of columns, for each intermediate node two columns added to the matrix, i.e., each node is represented by two elements in each row (multimodal route). The first element has a binary (0 or 1) value showing if the intended node is used in the route or not. The second element distinguishes the transportation mode via which the product travels from the current node to the next one (one for road transportation, two for rail transportation, and three for sea transportation). Also, an extra first column is inserted to show the transportation mode via which products travel from the supplier to the first intermediate node along the route. Here the subject is clarified by a numerical example. Suppose a multimodal network with one supplier, six intermediate nodes, and four potential DCs. The following matrix expresses typical routes from the supplier to DCs.
The first row represents a route from the supplier to potential DC number one (DC 1). The first element along the row is 1, that is, the transportation starts from the supplier on road mode. The second element along the row is 1, which indicates the first intermediate node along the route. The third element shows that the transportation proceeds from the node 1 via road transportation. Being zero, the next pair of elements reveals that the intermediate node 2 is not used in the route. The sixth and seventh elements along the row show that the route enters the intermediate node 3 and leaves the rout via road transportation. And finally the last two elements determine that the intermediate node 6 presents along the route, and the route continues towards potential DC 1 by rail transportation with a mode change happening at node 6. Applying this process to the next DCs, row 2 shows that route to DC number two (DC 2) is on rail network and crosses the intermediate nodes 2, 4 and 5. Furthermore, row 3 presents the route to DC number three (DC 3). Nodes 3 and 4 uses in this route and transportation mode change at node 3 from road to seaway. Lastly, row 4 corresponds to the route to potential DC number four (DC 4); it indicates that intermediate nodes 1, 3 and 6 are used in the route and mode changing happened from railway to road on node 1 and 6 and from road to railway on node 3.
(b) The second part of the chromosome is a string of numbers representing established DCs and sequence of retailers along routing tours. The string length is equal to total number of retailers plus potential DCs minus one. To demonstrate the string, a sample string with nine retailers and four potential DCs is presented as follows:
The numbers 1–9 present 9 retailers, and the numbers 10, 11, and 12
refer to the DCs. Retailers are assigned to DCs via the following
process. From the start of the string to one of the numbers 10, 11, or
12 (the one appeared first) will be assigned to DC 1. Obviously, if the
string was started with one of the corresponding numbers to DCs, no
retailer would be assigned to DC 1. In this case, retailers 1, 2, and 4
will be assigned to DC 1, with the same sequence. The retailers falling
between the first and second corresponding numbers to DCs (10, 11 and
12) will be assigned to DC 2. In this example, as number 11 comes right
after number 12, no retailer is assigned to DC 2, i.e., DC2 is not going
to be established. Similarly, the retailers falling between the second
and third corresponding numbers to DCs (10, 11 and 12) will be assigned
to DC 3. In this case, retailers 8, 9, 7, and 6 are assigned to DC 3,
with the same sequence of meeting the retailers. And lastly, retailers
falling within the third corresponding number to DCs (10, 11 and 12) to
the end of the string (retailers 3 and 5, respectively, in this example)
are assigned to DC 4.
Generation of initial population
Two
different populations with equal numbers should be generated for the
two different parts of the chromosome. Each member of the matrix part of
the chromosome shows a possible route from supplier to potential DCs.
To generate an initial population for this part, the algorithm is fed by
all inbound links into intermediate nodes along with their types. The
algorithm starts from potential DC 1 and selects a random inbound link
from the set of corresponding inbound links. Then starting node of the
selected link is determined before a random inbound link is assigned to
the nodes. This process continues until the node 0 (supplier) is
reached. The obtained route is then transformed into the corresponding
chromosome representation as described above. Repeating the process for
other potential DCs, matrix rows and columns are formed.
The
initial population for the string part of chromosome is created by a
routine called "randperm" in MATLAB. For each matrix part of the
chromosome, a string part is generated and their costs are summed up
into a single response.
Parents selection mechanism
Parent selection mechanism is an important part of the genetic algorithm. In the present research, roulette wheel selection mechanism was used.
Crossover operator
In crossover operation, for the matrix part, in selected parents rows are replaced with each other, as follows:
For
the string part of the chromosome, a random number is selected between 2
and length of string minus 1. This number divides selected parents into
two parts. Combination of these parts generates two offspring. First
part of first parent along with second part of second parent make
offspring one and second part of first parent along with first part of
second parent make offspring two. Following with the operation,
modifications are done and repetitive members replace missing ones. An
example is presented below to clarify the operation.
Note that, for both crossover operations, the operator works only in 50% of the time. So, under this condition, offspring with changes in just one part of the chromosome are possible.
Mutation operator
In the
matrix part of the chromosome, mutation operator performs as follows.
Based on mutation rate, number of rows is selected randomly and for each
selected row, a new route generates using of same process in initiating
the population. In the next step, selected and primary routes (rows)
distances are computed and compared together. If the new route has less
distance, it replaces in the related row, otherwise primary row
reserves.
For the string part of the chromosome, mutation
operator is randomly selected from a set of five different mutation
functions. In the first function, two different members of the string
are randomly selected to be replaced with each other.
In second function, in addition to replacing the members, the order of members between them is reversed.
In third function, two members are random taken and the first member is moved after the second member.
In the fourth function, the assigned retailers for each tour are determined. Then, their order is reversed in the routes.
In
the fifth function, after determining the retailer tours, two tours are
selected randomly and a random member of each selected tour is
exchanged.
Similar to crossover operator, mutation operators apply at a probability of 50%. As mentioned, this allows for the generation of offspring wherein only one part of the chromosome is changed.
Fitness function
The model's objective function is
used as the fitness function. For each matrix part of the chromosome, a
string part is generated; coupled together, both parts are used as a
single chromosome in fitness function. For each chromosome, four cost
functions and one penalty function are developed. The first cost
function addresses the cost of routing tours from DCs to retailers. As
explained before, open DCs and their allocated tours are determined
based on the string part of the chromosome. Then, DC numbers are added
to the beginning and end of each related tour before determining the
distance between each pair of nodes along the tour. Lastly, overall tour
cost can obtain by summing up the calculated distances and multiplying
the result by the product's unit transportation cost.
In second
cost function, established DCs are distinguished using string part of
the chromosome and summation of their establishment costs is calculated.
To
determine transportation cost on the multimodal network (from supplier
to potential DCs), the following process is applied. As a first step,
the matrix part of the chromosome is decomposed into its rows and in
each row the intermediate nodes used along the route are identified. In
the second step, transportation mode between nodes is distinguished. In
third step, distances between nodes are determined and multiplied by the
corresponding transportation cost; sum of the results gives total cost
for each link. Finally, total demand for each DC is calculated and
multiplied by link costs. Sum of these costs form the multimodal network
transportation cost. Last cost function is the cost of providing mode
changing facilities at multimodal terminals. To have the cost
calculated, nodes which mode changes are happened should be identified.
For this mean, inbound and outbound modes are determined for each node
along multimodal links. If the modes are identical, then node may host
no mode change; otherwise mode changing facilities need to be
established on that location. Fixed cost of providing mode changing
facilities is aggregated to form the fourth cost function.
For
this fitness function, a penalty is considered for violating vehicle
capacity along the routing tours. If sum of assigned retailers' demands
to a potential DC violated corresponding vehicle capacity, the penalty
is applied.
Forming the next population
To form the next generation, first population along with offsprings generated by crossover operator and mutants are sorted on the basis of their costs. New population with the same size as first population is selected from the first members of the set (fewer costs are selected).
Stop condition
The algorithm is set to stop once a predefined maximum number of iterations is achieved.
Algorithm parameter setting
Parameter setting is an important part of coding the algorithm where different parameter configurations contribute to the quality of answers. In this study, running the algorithm with different parameter configuration arrived to following optimum values of GA parameters (Table 1).
Table 1 Genetic algorithm parameters
Parameter name | Value | Parameter name | Value |
---|---|---|---|
Population size | 400 | Roulette wheel selection pressure | 20 |
Mutation rate | 0.8 | Mutation implementation rate | 0.8 |
Crossover rate | 0.8 |
Numerical cases and analysis of the results
In this section, two numerical cases were generated and solved. Proposed genetic algorithm and CPLEX solver were used to solve the cases. GA coded in MATLAB software and GAMS software was used to run CPLEX software and obtained results compared. A personal laptop equipped with an Intel® Core™ i3 CPU at 2.4 GHz and 6 GB of RAM was used to process the data. Also, different cost scenarios were designed to analyze model and algorithm sensitivity.
Case 1: description
Each numerical case have two parts; a multimodal network along with a single-mode network of DCs and retailers. In case 1, the multimodal network is generated by random data. It consists of 1 supplier, 8 intermediate nodes, 2 potential DCs, 15 road links, 19 railway links and 14 seaway links. The distances between nodes along the road network were uniformly generated in [0, 400] interval (First x and y coordination generated for each node, then Euclidean distances calculated). To generate railway network distances, another uniform distribution over interval [0, 20] is used, and results added to the Euclidean distances. Adding another random number to railway network distances from interval [0, 20], generates seaway network distances. Table 2 shows the defined links and their distances along the three transportation networks.
Table 2 Multimodal network for the three numerical examples
Node number | Exiting arc | Road | Rail | Sea | Node number | Exiting arc | Road | Rail | Sea |
---|---|---|---|---|---|---|---|---|---|
1 | (1,2) | 23 | 27 | – | 4 | (4,6) | 184 | – | 204 |
1 | (1,3) | – | 87 | – | 4 | (4,7) | – | 136 | 146 |
1 | (1,4) | – | 197 | – | 4 | (4,8) | – | 373 | 390 |
1 | (1,5) | 331 | – | – | 5 | (5,7) | 170 | 179 | 188 |
2 | (2,3) | 60 | – | 70 | 5 | (5,8) | 304 | 315 | 360 |
2 | (2,4) | – | 179 | – | 6 | (6,8) | 214 | 220 | 227 |
2 | (2,5) | – | 300 | 313 | 6 | (6, DC1) | 287 | 300 | 315 |
2 | (2,7) | 350 | 383 | – | 7 | (7,8) | 190 | 197 | 310 |
3 | (3,4) | 100 | 111 | – | 7 | (7, DC1) | 259 | 260 | 268 |
3 | (3,6) | – | 275 | 282 | 7 | (7, DC2) | 332 | 343 | 357 |
3 | (3,7) | – | 320 | – | 8 | (8,DC2) | 155 | 164 | 177 |
4 | (4,5) | 134 | – | – |
For second part of the numerical case 1, five retailers were considered. Table 3 shows their x and y coordination and demands. This part of the numerical case extracted from LRP instances with 20 customers and 5 DCs reported by Prodhon (2010). Establishment costs of DC 1 and DC 2 were 10,841 and 11,961, respectively, with a unit on-vehicle transportation cost of 20.
Coordinates | DC 1 | DC 2 | Retailer 1 | Retailer 2 | Retailer 3 | Retailer 4 | Retailer 5 |
---|---|---|---|---|---|---|---|
X | 6 | 19 | 20 | 8 | 29 | 18 | 19 |
Y | 7 | 44 | 35 | 31 | 43 | 39 | 47 |
Demand | – | – | 18 | 13 | 19 | 12 | 18 |
Scenario number | Shipment cost for each mode | Transfer cost between modes | Vehicle capacity | GAMS value | GAMS solution time (s) | GA values | Best multimodal path | Best route | ||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Road | Rail | Sea | Worst | Medium | Best | |||||||
1 | 3 | 2 | 1 | 100 | 100 | 64,061 | 1.06 | 64,061 | 64,061 | 64,061 | 1-R-2-S-3-S-4-S-7-S-DC1a | DC1-2-1-4-5-3-DC1b |
2 | 3 | 2 | 1 | 10,000 | 100 | 73,961 | 0.59 | 73,961 | 73,961 | 73,961 | 1-R-2-S-3-S-6-S-8-S-DC1 | DC1-2-1-4-5-3-DC1 |
3 | 3 | 2 | 1 | 50,000 | 100 | 107,801 | 0.64 | 107,801 | 107,801 | 107,801 | 1-R-4-R-7-R-DC1 | DC1-2-1-4-5-3-DC1 |
4 | 3 | 2 | 1 | 10,000 | 70 | 87,270 | 1.08 | 87,270 | 87,270 | 87,270 | 1-R-2-S-3-S-4-S-7-S-DC1 | DC1-2-1-5-3-DC1 |
1-R-2-S-3-S-4-S-7-S-DC2 | DC2-4-DC2 | |||||||||||
5 | 23 | 22 | 21 | 10,000 | 70 | 1,073,830 | 1.42 | 1,073,830 | 1,073,830 | 1,073,830 | 1-H-2-H-3-S-4-S-7-S-DC1 | DC1-2-1-5-3-DC1 |
1-H-2-H-3-S-4-S-7-S-DC2 | DC2-4-DC2 | |||||||||||
6 | 23 | 22 | 21 | 50,000 | 70 | 1,090,753 | 1.13 | 1,090,753 | 1,090,753 | 1,090,753 | 1-R-4-R-7-R-DC1 | DC1-2-1-5-3-DC1 |
1-R-4-R-7-R-DC2 | DC2-4-DC2 |
aMultimodal route starts from supplier (node 1) and paths nodes number 2, 3, 4, 7 and end to DC1. Transportation links between supplier and node number 2 is a railway (R) and other transportation links are seaway (S)
All best multimodal paths start from node 1 (supplier) and pass intermediate nodes to reach DCs. Notations H, R, and S between the nodes refer to road, railway, and seaway modes. Best routes start from DCs and pass through retailers (retailers numbers are different from multimodal path numbers) and eventually returning back to the original DC.
Under scenario 1, mode changing cost (cost of providing mode changing facilities at multimodal terminals) is much lower than DC establishment cost (about one hundredth). Furthermore, transportation cost on road and railway networks, compare to seaway network, are triple and twice, respectively; and considered capacity for each DC is adequate to satisfy all retailers' demands. Result show that under this scenario, only DC1 (with lower establishment cost) established. Because of high DC establishment cost, when one DC can answer to all the retailers demand (high vehicle capacity), just one DC establishes. In this scenario, seaway has the lowest cost and mode changing cost is negligible. So multimodal route is consists of four seaway and one railway links and multimodal terminal established at node 2. Under scenario 2, mode changing cost is raised to 10,000 (close to that of DC establishment cost). However, no change is seen in the results, i.e., seaway transportation still presents a costly justifiable approach, and similar to scenario 1, a multimodal terminal established at node 2. In scenario 3, mode changing cost is about five times larger than DC establishment cost. The results show that change in transportation mode is no longer economic, and multimodal route products transported from supplier to potential DC 1 along the railway network. With sufficient vehicle capacity for all the demands, only one DC is established. Under scenario 4, mode changing cost set to 10,000 and vehicle capacity decreased to 70, so that a single DC cannot answer all the demands. In this scenario, both of DCs established with a different multimodal route and delivery tour for each DC. In scenario 5, differences between transportation costs for three modes are lower than previous scenarios. Again, mode changing cost and vehicle capacity are set to 10,000 and 70, respectively. Results show that in the multimodal network, products are transport along road (due to lower distance) and seaway (due to lower cost) networks. Since DC capacity has not changed, retailer routes are the same. Sixth scenario is similar to previous scenario with raise in mode changing cost. In this scenario model, choose a multimodal route with no changing in modes, so railway network (due to its continuity from the supplier to DCs) is preferred over road network (with lower transportation distances) and seaway network (with lower costs). The results show that a change in vehicle capacity can change the number of established DCs and affect routs to retailers.
Case 2
Example generated by Xiong and Wang (2012) used in case 2, for multimodal part of the problem. The authors defined a multimodal network with 35 nodes and three modes including truck, rail and barges transportation. Five ending nodes (nodes 31–35) considered as potential DCs and node 1 defined as supplier location.Some modifications did on multimodal network. According to the problem assumptions, all links between potential DCs deleted. As a result, node 34 (potential DC 4) lose all of its communications to other nodes. To modify that three truck, rail and barge links from node 27–34 added to multimodal network. Also, every defined distance for multimodal network is multiplied by 10 to provide more consistency with DCs and retailers distances. For LRP part of the problem, Prodhon instance with 5 potential DCs and 20 customers used (Prodhon 2010).
Software and algorithm results for case 2 under different cost and capacity scenarios are presented in Table 5. Also, for this case, the parameter B is set to the same value (100,000).
Same scenarios defined and solved for case 2. However, in contrary to the case 1, cost of a change in transportation mode had lower impact on changing multimodal routes. This is because of significant differences between distances of transportation modes. Compared to other modes, road network has lower distances, so under these cost scenarios, using a road network is costly justifiable, even with higher transportation cost.
In the first three scenarios capacity of DCs was set to 300; so two DCs could adequately answer all of the demands. The results show that under all three scenarios, DCs 3 and 4 which had lower establishment cost, selected to establish. Under scenarios 1 and 3, mode changing cost is low, so the node 17 selected for multimodal terminal. Under scenario 2, mode changing cost is raised to 10,000; such a high cost caused a change in multimodal route to avoid mode change; however, route structure changes very slightly.
Under scenarios 4, 5 and 6, DCs' capacity was 70; as a result, all the DCs should be established to fulfill all the demands. In scenario 5, transportation costs were all close together compared to scenario 4, however, such a change had no impact on multimodal route. So in this case, transportation distance is more important than transportation cost and road transportation is the popular mode due to its lower distances. Under scenario 6, mode changing cost was 10, but yet no change was evident on multimodal route. Comparing results with scenario 3 reveals that with the same mode changing cost, a different route was attained for DC 3. In fact, when rail and road modes costs were 2 and 3, respectively, transportation mode was likely to change at node 17, but when the costs were 22 and 23, respectively, this was not the case and transportation continued along the road network.
For the same established DCs, different tours from DC to retailers were attained under different scenarios. For example, under scenarios 1 and 2, different tours were attained for DC 3 and DC 4. However, according to the same transportation cost and identical distances between retailers and DC, such a difference was not expected (similar to case 1). The situation was attributed to sub-optimality of the solutions given by the software under different scenarios. GAMS reported a feasible solution within limited run time. GA reported an equal or even better solution with lower run times, but the optimality of the answers is yet to be proved.
Although the case 2 was considered as a medium-size problem, because of high complexity of the model and NP-hard nature of the problem (Shen et al. 2003), GAMS failed to find an optimal solution within the limited run time. Existing gap within the solutions are reported in Table 5.
Scenario number | Shipment cost for each mode | Transfer cost between modes | Vehicle capacity | GAMS value | GAMS solution time (s) | Gap (%) | GA Values | GA solution time | Best multimodal path | Best route | ||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Road | Rail | Sea | Worst | Medium | Best | |||||||||
1 | 3 | 2 | 1 | 100 | 300 | 253,997 | 7200 | 4 | 254,837 | 254,255 | 253,997 | 565 | 1-H-2-H-7-H-11-H-15-H-17-R-22-H-26-H-29-H-DC3 | DC3-10-DC3 |
1-H-4-H-5-H-12-H-16-H-21-H-27-H-DC4 | DC4-18-1-17-3-8-19-20-7-15-16-4-11-14-5-13-12-9-2-6-DC4 | |||||||||||||
2 | 3 | 2 | 1 | 10,000 | 300 | 265,947 | 7200 | 24 | 267,397 | 265,471 | 264,517 | 581 | 1-H-2-H-7-H-10-H-14-H-18-H-20-H-22-H-26-H-29-H-DC3 | DC3-15-DC3 |
1-H-4-H-5-H-12-H-16-H-21-H-27-H-DC4 | DC4-6-2-9-12-13-5-14-11-4-10-16-7-20-19-8-3-17-1-18-DC4 | |||||||||||||
3 | 3 | 2 | 1 | 10 | 300 | 253,817 | 7200 | 4 | 254,297 | 254,070 | 253,817 | 531 | 1-H-2-H-7-H-11-H-15-H-17-R-22-H-26-H-29-H-DC3 | DC3-10-DC3 |
1-H-4-H-5-H-12-H-16-H-21-H-27-H-DC4 | DC4-18-6-2-9-12-13-5-14-11-4-16-15-7-20-8-19-3-17-1-DC4 | |||||||||||||
4 | 3 | 2 | 1 | 10,000 | 70 | 387,904 | 7200 | 35 | 416,594 | 403,294 | 387,904 | 605 | 1-H-2-H-8-H-9-H-13-H-24-H-30-H-DC1 | DC1-3-17-4-15-DC1 |
1-H-2-H-7-H-10-H-14-H-18-H-20-H -22-H-26-H-29-H-DC2 | DC2-18-2-8-19-DC2 | |||||||||||||
1-H-2-H-7-H-10-H-14-H-18-H-20-H -22-H-26-H-29-H-DC3 | DC3-1-11-10-14-16-DC3 | |||||||||||||
1-H-4-H-5-H-12-H-16-H-21-H-27-H-DC4 | DC4-12-13-5-9-6-DC4 | |||||||||||||
1-H-4-H-5-H-12-H-16-H-21-H-27-H-28-H-DC5 | DC5-20-7-DC5 | |||||||||||||
5 | 23 | 22 | 21 | 10,000 | 70 | 2,499,884 | 7200 | 28 | 2,502,704 | 2,497,490 | 2,489,884 | 560 | 1-H-2-H-8-H-9-H-13-H-24-H-30-H-DC1 | DC1-19-1-18-17-DC1 |
1-H-2-H-7-H-10-H-14-H-18-H-20-H -22-H-26-H-29-H-DC2 | DC2-9-5-14-7-DC2 | |||||||||||||
1-H-2-H-7-H-10-H-14-H-18-H-20-H -22-H-26-H-29-H-DC2 | DC3-3-10-12-16-20-DC3 | |||||||||||||
1-H-4-H-5-H-12-H-16-H-21-H-27-H-DC4 | DC4-2-4-11-13-6-DC4 | |||||||||||||
1-H-4-H-5-H-12-H-16-H-21-H-27-H-28-H-DC5 | DC5-15-8-DC5 | |||||||||||||
6 | 23 | 22 | 21 | 10 | 70 | 2,492,234 | 7200 | 29 | 2,492,714 | 2,491,766 | 2,489,894 | 621 | 1-H-2-H-8-H-9-H-13-H-24-H-30-H-DC1 | DC1-1-9-11-10-20-DC1 |
1-H-2-H-7-H-10-H-14-H-18-H-20-H -22-H-26-H-29-H-DC2 | DC2-6-4-16-15-8-DC2 | |||||||||||||
1-H-2-H-7-H-10-H-14-H-18-H-20-H -22-H-26-H-29-H-DC2 | DC3-17-2-18-3-DC3 | |||||||||||||
1-H-4-H-5-H-12-H-16-H-21-H-27-H-DC4 | DC4-12-5-14-7-DC4 | |||||||||||||
1-H-4-H-5-H-12-H-16-H-21-H-27-H-28-H-DC5 | DC5-13-19-DC5 |
Relative gap percentage is reported by GAMS software
GA solution time is for '100 iterations
Conclusions
As a new branch of location problems,
location-routing problem is still under development by various
researchers. Present paper considered a location-routing problem on
multimodal network. This paper aims to model and solve two problems at
the same time. First problem is to select multimodal routes from
supplier to potential DCs along with locating multimodal terminals.
Second problem is DC location with routing tours from located DCs to
retailers. An integer linear programming proposed and a genetic
algorithm developed to capture the problem structure. To validate
mathematical model, analyze sensitivity and demonstrate algorithm
performance, two small and large size numerical instances generated
based on previous papers, and different cost scenarios applied to these
instances. Scenarios were different in vehicle capacity, transportation
modes' costs, and mode changing cost. According to the results, for
different scenarios, different multimodal routes selected. Changing mode
change cost affects on establishing multimodal terminals. High mode
changing cost caused products to be transported on just one
transportation mode; decreasing the cost, however, led to changes in
modes, requiring multimodal terminals to be established. Changing
vehicle capacity cause a change in number of established DCs and
retailers orders on delivery tours. Also, by changing transportation
cost on multimodal network, model makes a trade-off between distance and
transportation cost and selects a multimodal route with lowest cost. In
large numerical instance, due to high complexity of the model, GAMS
software failed to find an optimum solution within a reasonable time. In
this case, genetic algorithm run under different scenarios and ended up
returning solutions equal to or better than GAMS results, revealing
good performance of the algorithm.
For future researches, first
suggestion is to develop other solving algorithms including exact
algorithms and comparing results. Other developments to LRP can be other
suggestion for future research; mathematical model can be further
developed considering uncertainties within data and dynamic programming
issues, for example. Applying model for real cases and reporting real
results can be another validation for model.