# Optimizing Route for Hazardous Materials Logistics Based on Hybrid Ant Colony Algorithm

Authors: Haixing Wang; Guiping Xiao; Zhen Wei
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

Optimizing Route for Hazardous Materials Logistics (ORHML) belongs to a class of problems referred to as NP-Hard, and a strict constraint of it makes it harder to solve. In order to dealing with ORHML, an improved hybrid ant colony algorithm (HACA) was devised. To achieve the purpose of balancing risk and cost for route based on the principle of ACA that used to solve TSP, the improved HACA was designed. Considering the capacity of road network and the maximum expected risk limits, a route optimization model to minimize the total cost is established based on network flow theory. Improvement on route construction rule and pheromone updating rule was adopted on the basis of the former algorithm. An example was analyzed to demonstrate the correctness of the application. It is proved that improved HACA is efficient and feasible in solving ORHML.


---

## Body

## 1. Introduction

Hazardous materials, which have different physical and chemical properties, have high risk during transportation, as a series of problems may arise in this process. Route optimization is a complex combinatorial optimization problem, which is a typical NP-complete problem and difficult to come up with a direct answer. It is a practical problem in urgent need of solution in which we can find the optimal plan under the restrictions quickly, accurately, safely, and economically.Optimizing Route for Hazardous Materials Logistics (ORHML) can be described as follows. Given a set of hazardous materials and an underlying network consisting of a number of nodes and capacitated arcs, we wish to find an optimal routing plan to ship the hazardous materials through the network at lowest cost without violating the capacity limits. ORHML models also appear as subproblems in more complicated models, such as distribution system design and capacitated network design.ORHML has attracted the attention of many OR researchers. Kara et al. [1] presented several route planning models of road. Verma and Verter [2] gave a number of route planning models of rail. Iakovou [3] provided route planning models of water. Miller-Hooks [4] modeled ORHML as a path selection problem in a stochastic time-varying network. Dell’Olmo et al. [5] finding a number of spatially dissimilar paths between an origin and a destination can also be considered in this area. Jin and Batta [6] presented a risk model that took into account the dependency to the impedances of preceding road segments. Erkut and Verter [7] proposed a collection of edges in place of an origin-destination route for a hazmat shipment, where travel on this path can be viewed as a probabilistic experiment. It considered minimizing for a given OD pair in a hazmat transport network is a shortest path problem which is solved easily for even large networks. Their work also pointed out that this approximation is likely to result in a very small error in measuring the incidence probability along a hazmat transport route [8].In general, in spite of their more realistic assumption, most of the exact versions of risk models have some puzzling properties and these models may not be suitable for hazmat transportation planning. We suggest that researchers and practitioners consider the properties of the risk models carefully.Successful ant colony algorithms have been developed for several combinatorial optimization problems, such as Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP).Based on the successful application of ant colony algorithm to TSP, a new ACA was adopted in solving ORHML. A collaborative metaheuristic approach is inspired by the foraging behavior of real colonies of ants. The basic ACA application is a large number of simple artificial agents that are able to build good solutions for hard combinatorial optimization problems through low-level based communications. Real ants cooperate in their search for food by depositing chemical traces (pheromones) on the floor.


## 2. Model Analysis

ORHML optimization model can be demonstrated as follows:(1)Minimize∑1≤k≤K(λCk+(1-λ)R)xksubjectto∑1≤k≤Kxijk≤u∀(i,j)∈Αℕxk=bk∀k∈Kxijk≥0∀(i,j)∈A,k∈K0≤λ≤1,
where  G=(N,A) represents the actual road network, in which the set of nodes N represents a road intersection, and arc set A indicates the connection between the intersection of sections. If (i,j) denotes the sections, then obviously i,j∈N and (i,j)∈A. K represent a different flow of hazardous materials set k∈K; k represents the hazardous materials k. xijk represents hazardous materials k using the arc (i,j); Cijk represents the unit cost when hazardous materials k use arc (i,j); Rijk represents the unit risk when hazardous materials k use arc (i,j). u represents the capacity constraints of the road. N represents the node-arc incidence matrix λ as the parameter [9].b
k
(
i
) represents the supply amount or demand amount in point i of hazardous materials k, bk(i)>0 means that the supply, bk(i)<0 which means that the demand.Based on the risk analysis theory, the risk of hazardous materialsk in (i,j) can be calculated by the following formula [10]:
(2)Rijk=∑s=16p(Aijk,Mk,Dk)*Rij(dsk),p(Aijk,Mk,Dk)=p(Dk∣Aijk,Mk)*p(Mk∣Aijk)*p(Aijk),
where Aijk represents the traffic accident of hazardous materials k in (i,j); Mk represents the leak accident of hazardous materials k in (i,j); Dk represents the accident loss of hazardous materials k in (i,j). Dk= {casualties along the road, casualties in the vehicle, property damage, traffic interruption, evacuation, environmental damage}. Rij(dsk) represents the risk of loss caused by the harm s.(1) Casualties along the roadRij(d1k):
(3)Rij(d1k)=lij*rk*ρij*HLV,
where lij represents the length of the road; rk represents the radius of the influence area for the accident disaster; ρij represents the population density along the road;  HLV represents the value of the loss of life.(2) Casualties in the vehicleRij(d2k):
(4)Rij(d2k)=(Qij1*N1+Qij2*N2)*HLV,
where Qij1 represents the traffic flow of bus; Qij2 represents the traffic flow of car; N1 represents the patronage of bus; N2 represents the patronage of car.(3) Property damageRij(d3k):
(5)Rij(d3k)=Qij1*CLV1+Qij2*CLV2,
where CLV1 represents the loss value of bus; CLV2 represents  the loss value of car.(4) Traffic interruptionRij(d4k):
(6)Rij(d4k)=T1T0*(Qij1*N1+Qij2*N2)*TLV,
where T1 represents the traffic disruption time; T0 represents per unit time;  TLV represents the value of loss time.(5) EvacuationRij(d5k):
(7)Rij(d5k)=lij*rk*ρij*AEC,
where  AEC represents average evacuation costs.(6) Environmental damageRij(d6k):
(8)Rij(d6k)=lij*rk*ELVij,
where ELVij represents value of environmental damage of unit area.


## 3. Solving Strategies

HACA goal is to find the shortest tour. In HACAm ants build tours in parallel, where m is a parameter. Each ant is randomly assigned to a starting node and has to build a solution, that is, a complete tour. A tour is built node by node: each ant iteratively adds new nodes until all nodes have been visited. Improvement process of solution strategy is present in the algorithm; this strategy can transform solution of the problem to a single ant path. Given multiple source points, ink points, and the corresponding flow, construct an ant colony; in the initial state, the ants are randomly distributed in each source point; the ants’ next point is selected at random. Updated according to the flow from the source point to sink point as weight. When the ant went to the source point and the corresponding sink point, place the ants to another source point, begin the next search process until all sources and sinks were finished, and then complete a cycle of the ant. As can be seen in Figure 1 [11].Figure 1
Improvement process of solution strategy.When antk is located in node i, it chooses the next node j probabilistically in the set of feasible nodes according to pijk(t).In the HACA, original version formula forpijk(t) is
(9)pijk(t)={[τij(t)]α[ηij]β∑l∈Nik[τil(t)]α[ηil]βj∈Nik0else.The number of next nodes which antk in node i could select is represented by  wink(i). In basic ant colony algorithm,  wink(i)=cnt(allowedk),  cnt(allowedk) denotes the number of nodes in set allowedk. The value of  wink(i) should be adjusted dynamically:
(10)wink(i)={cnt(allowedk)if(1-V(i))*cnt(allowedk)=cnt(allowedk)⌊(1-V(i))*cnt(allowedk)⌋+1else.The sum of ants is represented byM; there are r trails from node i; the number of ants that pass node i is Yi, and Yi is distributing in r trails with number a1,a2,…ar:
(11)V(i)={YiM(1-1Yir∑i=1r(Yi/r-ai)2r-1)ifYi≠00else.Using for reference the idea of ant-Q algorithm of Dorigo, the meliorative route construction rule can be expressed as follows (12)j={AccordingPijselectj,Pij=[τij]α[ηij]β[μij]γ[κij]λ∑h∈allowedk[τij]α[ηij]β[μij]γ[κij]λj∈allowedk,P≤r0Accordingmaxj∈allowedk{[τij]α[ηij]β[μij]γ[κij]λ}selectj,P≥r1AccordingPij′selectj,Pij′=[τij]α[ηij]β[μij]γ[κij]λ∑h∈allowedk′[τij]α[ηij]β[μij]γ[κij]λj∈allowedk′,r0≤P≤r1μij=di0+d0j-dij, called saving; κij=(Qi+qi)/Q. Variable induced considering the time constraint.The algorithm constructs two ant colonies to realize the goal of optimization: minimize the cost and risk of the hazardous materials transportation. These two ant colonies are the HACA-RISK and HACA-COST, which are used to determine the optimal route. In consideration of the two together, we may find better solutions to the problem. After getting the improved solution, the overall pheromone update would be used to get the exchange of information concerning the advantages and disadvantages of the solution [12].The HACA-RISK optimization process is to get the feasible solution which uses one less risk thanψgb. HACA-RISK process is used to determine a shorter path under the circumstances. Once a new better feasible solution has been figured out, ψgb should be updated. These two processes will come to an end if a solution with the use of fewer cost comes up. At the same time, a new ant colony can be built on the basis of this new solution, which restarts a new interactive optimization process.If the least cost has been figured out by this algorithm, the HACA-RISK optimization process can be stopped, and then we shift to the HACA-COST optimization process.In the HACA-COST we introduce an integer vectorIN; INi means the times that the point has not been covered by the solution. This parameter should be updated correspondingly with the optimal solution. Whenever a new solution has been found, the overall pheromone update should be applied to reset ψgb.The HACA-COST optimization process is similar to the traditional HACA optimization process which is to optimize the utilization of the load capacity and volume of RISKs.The optimizing process can be divided into two parts: first, the ants move between the various points in search of the optimal solution; second, decompose the optimal solution intoVmin subsets according to the location of the original node, then allocate goods to the RISKs.The movement of ants in the HACA-COST and HACA-RISK is similar to each other. At the beginning of the algorithm, ants are randomly distributed among all the nodes. From the initial node, the ants determine the next move within the scope of available points, on the basis of the probability and the restrictions on RISK load capacity and volume. The time and cost of all nodes to the virtual origin node are 0, and no direct connection between the virtual origin nodes is allowed. Once the ants arrive the terminal node, thus begins the construction of the next subset. After traversing all the nodes, the ants return to the initial node to form a loop, that is, feasible solution.In the HACA-COST optimization process, a feasible solutionψ1,…,ψm is formed through the collaboration of all the ant colonies. Compare ψ1,…,ψm with ψgb, if better, update ψgb with the value of ψ1,…,ψm.When the above process was being completed, the obtained solution may still be incomplete (and may have missed points), so the insertion process is needed as further optimization. Insertion process is mainly to deal with the point that has not been included in the existing solution. The process determines the optimal feasible insertion position (the shortest path) for each point until the plug cannot find a viable location [13].


## 4. Example and Analysis

As can be seen in Figure2, there are two kinds of hazardous materials X (flammable liquid) and Y (poisonous gas) : X, from note A to note H, flow is 60 units; Y, from note B to note G, flow is 20 units. That is, b(A) = 60, b(H) = −60, b(B) = 20, and b(G) = −20. The related data values are shown in Table 1.Table 1
Parameter value.
l
i
j (km)
ρ
i
j (person/km2)
Q
i
j
1
Q
i
j
2
ELV
i
j
p
(
A
i
j
x
)
p
(
A
i
j
y
)
AB
80
500
16
400
19000
0.0000018
0.000002
AC
35
1000
20
730
6000
0.0000055
0.0000069
AD
60
700
34
500
12000
0.0000035
0.0000044
BA
70
400
40
250
18000
0.0000015
0.0000019
BD
50
800
52
670
14000
0.0000035
0.0000044
BE
70
700
18
370
15000
0.0000025
0.0000031
CF
15
800
42
850
5000
0.0000065
0.0000081
CG
30
1200
68
680
9000
0.0000045
0.0000056
DF
20
2000
48
970
0
0.0000075
0.0000094
EF
25
1800
36
750
6000
0.0000055
0.0000069
EH
65
800
44
350
18000
0.0000015
0.0000019
FG
40
900
24
500
12000
0.0000035
0.0000044
FH
50
700
18
380
16000
0.0000025
0.0000031
GH
35
400
16
250
12000
0.0000015
0.0000019
HG
65
300
12
250
18000
0.0000015
0.0000019Figure 2
Road network.Set freight = 0.5 yuan/km/unit,HLV=1000000 yuan/person, N1=50 persons/vehicle, N2=3 persons/vehicle, CLV1=500000 yuan, CLV2=100000 yuan, T0=24 h, T1=16 h, AEC=10000 yuan, and TLV=20 yuan/h.p
(
M
x
∣
A
i
j
x
)
=
0
.
6, rx=0.3 km; p(My∣Aijy)=0.3, ry=2 km. The probabilities of hazard losses p(Dk∣Aijk,Mk) can be seen in Table 2.Table 2
The probabilities of hazard losses.
p
(
D
k
∣
A
i
j
k
,
M
k
)
R
i
j
(
d
1
k
)
R
i
j
(
d
2
k
)
R
i
j
(
d
3
k
)
R
i
j
(
d
4
k
)
R
i
j
(
d
5
k
)
R
i
j
(
d
6
k
)
X
0.4
0.8
0.6
0.4
0.1
0.2
Y
0.7
0.6
0.3
0.4
0.7
0.7Total expected riskRijk is shown in Table 3.Table 3
Total expected risk.
R
i
j
k
AB
AC
AD
BA
BD
BE
CF
CG
X
1495.61
2527.264
2448.515
847.7595
2496.6
2256.487
978.3397
2412.688
Y
744.24
1408.428
1373.803
480.7152
1402.368
1250.897
540.918
1337.213
DF
EF
EH
FG
FH
GH
HG
X
2880.29
3249.342
1574.389
2098.725
1663.237
349.7931
590.3967
Y
1590.48
1810.836
892.7568
1177.546
922.467
197.7444
334.7838Set Fright = 0.5 yuan/km/unit. The costCij  can be shown in Table 4.Table 4
The cost.
AB
AC
AD
BA
BD
BE
CF
CG
DF
EF
EH
FG
FH
GH
HG
C
i
j
40
17.5
30
35
25
35
7.5
15
10
12.5
32.5
20
25
17.5
32.5In view of complexity of this problem, the whole level optimization solutions are obtained based on the random searching and evolution process of the improved ant colony algorithm. The solution can be seen in Figure3.Figure 3
Solution.


## 5. Summary

Solving the ORHML is to determine route plans that can make a minimum of risk and safety under the premise of restrictions of the placements. That is, to seek a safe routing plan that could obtain the lowest cost with the conditions has been known.A new ant colony optimization based approach to solve ORHML was introduced. In particular, the algorithm has been designed to solve ORHML with a balance between the safe and the cost. Pinpointing the characteristics of this problem, our algorithm introduces a new methodology for optimizing multiple objective functions. We consider the optimization of the safe and the cost at the same time. This paper analyzes the differences of the ant colony algorithms in solving the restricted ORHML. In order to deal with ORHML, an improved HACA was devised. Pinpointing the characteristics of this problem, we consider the optimization of cost and risk together. The basic idea is to coordinate the activity of different ant colonies, each of them optimizing a different objective. These colonies work by using independent pheromone trails but they collaborate by exchanging information. Furthermore, the integrated use of HACA-SAFE and HACA-COST has been applied as the improvement of the solving strategy.Finally, the feasibility and effectiveness of this method has been scrutinized with practical examples. From the result on the test problem, we can conclude that the model and the heuristic procedures are quite successful in solving ORHML.



---

*Source: 752830-2013-12-04.xml*