Location-Routing for Distribution Centers
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.
![\left[ {\begin{array}{*{20}c} 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 2 \\ 2 & 0 & 0 & 1 & 2 & 0 & 0 & 1 & 2 & 1 & 2 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 3 & 1 & 3 & 0 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 1 & 2 & 0 & 0 & 0 & 0 & 1 & 1 \\ \end{array} } \right].](https://learn.saylor.org/filter/tex/pix.php/efb2c2467ab96c7261ea4bdfbe7daac3.svg "\left[ {\begin{array}{*{20}c} 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 2 \\ 2 & 0 & 0 & 1 & 2 & 0 & 0 & 1 & 2 & 1 & 2 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 3 & 1 & 3 & 0 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 1 & 2 & 0 & 0 & 0 & 0 & 1 & 1 \\ \end{array} } \right].")
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 |