# A Personalized Urban Multicriteria Shortest Path Stochastic Optimization Algorithm

Authors: Gong Bowen; Lin Ciyun
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Drivers’ route choice behavior is usually personalized and multicriteria in practice. Therefore, the urban shortest path problem is the personalized urban multicriteria shortest path (PUMSP) problem. However, the solutions of the PUMSP problem are difficult to meet the drivers’ travel habits in the state of the art. To solve this problem, first, a new stochastic optimization algorithm based on the iterative calculation of a valid route set is proposed in this paper. The effective and reasonable path searching mechanism is designed based on drivers’ route choice habits. Then, the evaluation method of calculation results is given. The comparative experimental results with the genetic algorithm show that the proposed algorithm has reached better results in the evaluation parameters and computing time. The experimental results also demonstrate that it is meaningful to consider drivers’ travel law in the personalized urban multicriteria shortest path algorithm design for avoiding obtaining impractical routes solutions.


---

## Body

## 1. Introduction

The personalized urban multicriteria shortest path (PUMSP) problem is classified as a NP-hard problem and a significant branch of the urban multicriteria shortest path (UMSP) problem, in which two or more criteria and other constraints are considered, and finding the optimum path based on the importance-value of each criterion from the driver’s opinion in the route choice is the main goal. For example, given an origin-destination, help a driver to find the optimum path with the minimum weighted sum of travel time, travel length, and road grade whose weights separately are 0.4, 0.3, and 0.3. Because of the wide application prospect of the PUMSP, it has generated great interest among researches and lots of solution algorithms exist in the literatures [1, 2].The personalized urban multicriteria shortest path optimization is a complex problem. The multicriteria shortest path optimization is the core. The existing algorithms are mainly deterministic and stochastic. Early on, some classic deterministic algorithms of the single-criterion shortest path (SSP) problem are used to solve the multicriteria shortest path (MSP) problem. One representative idea is presented by Sadeghi, Kim, and Nadi. In their research, the MSP problem is transformed into the SSP problem by constructing an integrated impedance function regarding the multicriteria for each arc in the network [3, 4]. And based on this processing, all the deterministic algorithms for the SSP problem can be used to solve the MSP problem. However, it is unreasonable as pointed by Mooney and Liu [5, 6]. In the MSP problem, the statistical unit of all the criteria should be the route, and not the arc.Martins and Guerriero analyzed the distinction and relation between the SSP problem and the MSP problem in detail [7, 8]. And the MSP problem is regarded as an extension of the SSP problem in their research. And the traditional label algorithm is improved. In the improved label algorithm, the label and its update mechanism had been redesigned. For example, instead of one state label, a vector is used to label the states of all the criteria. But the time complexity of the improved label algorithm is rather high. Set N to be the number of all the nodes in the network; the label’s setting number of one node is up to ∑
k
=
0
N
-
2
N
-
2
!
/
N
-
2
-
k
! [9, 10]. And in recent years, these algorithms are usually used to compare with other algorithms in experiments. Caramia and Kang proposed some approximation approaches to find the optimum solutions by cyclically constructing the set of k shortest paths based on each criterion and Dijkstra algorithm. The approximate optimum solutions are obtained by intersecting the sets. And the experiment showed that it is efficient for less criteria and small networks.Recently, with the rapid development of intelligent optimization algorithms, lots of stochastic optimization algorithms for solving the MSP problem have emerged. Especially for the flexible form of the optimization function, lots of the intelligent optimization algorithms are improved to solve the MSP problem. Keivan and Fang improved the ant colony algorithm to solve the MSP problem and compared with the label algorithm by simulation tests [11, 12]. Bezerra et al. compared the properties of the single-ant-colony algorithm and multi-ant-colony algorithm in different networks through a series of experiment tests [13]. Chiang and Siddiqi improved the evolutionary algorithm to solve the MSP problem with time window and random demand [14, 15]. Osman and Ji improved the genetic algorithm to solve the MSP problem in the general network and the stochastic network [16, 17].The strong robustness, flexibility, and adaptation of stochastic optimization algorithms attract an extensive attention from researchers. However, existing algorithms still have a number of limitations, such as the lack of effective strategies for generating all the valid routes, determining the best compromising solution from the driver’s point of view when more than one possible solution simultaneously exists, which seriously affect their performance. The newer and better algorithms are required in reality.The main aim of this paper is to report a new stochastic optimization algorithm for solving the PUMSP problem and to assess its performance. Unlike most of existing algorithms for the PUMSP problem, the proposed algorithm uses drivers’ daily travel routes as the initial routes instead of the random routes used in most of the stochastic optimization algorithms. In addition, the proposed algorithm iteratively updates the initial routes with the consideration of the common law of drivers’ route adjusting in travel which is little considered in existing algorithms.The rest of the paper is arranged as follows. In Section2, some notations and definitions about an urban road network, the driver’s travel preferences, and the valid route are defined, based on which the personalized urban multicriteria shortest path is determined, and the personalized urban multicriteria shortest path optimization model is provided. In Section 3, a new stochastic optimization algorithm for the PUMSP problem and its evaluation parameter is proposed, in which the effective and reasonable operators on the initialization and iterative update of the valid route set are designed combining with three criteria chosen by a driver. In Section 4, the comparative experiment between the proposed algorithm and the genetic algorithm for solving the PUMSP problem is carried out, and the experimental results are analyzed and discussed. In Section 5, conclusion is considered.


## 2. Personalized Urban Multicriteria Shortest Path Optimization Model

According to the graph theory, if the intersection is abstracted as a node and one driving direction of the road between the adjacent intersections is abstracted as a directed arc, then an urban road network can be abstracted as a directed graphG
=
V
,
E, in which V is the set of nodes with N
=
V and E is the set of arcs with M
=
E. Each arc
e
∈
E is corresponding with an ordered pair of nodes, in the form from the node ξ to the node ζ. And the arc e simultaneously has an associated set X
e of its criteria-costs with C
=
X
e, in which C is the total number of the criteria chosen by the driver. And each route R in G has an associated set B
R of the criteria values with C
=
B
R. Set w
c
c
=
1,2
,
…
,
C is the importance-value of the cth criterion, and ∑
c
=
1
C
w
c
=
1. Obviously, there is b
c
,
R
=
∑
η
∈
R
,
x
c
,
η
∈
X
R
x
c
,
η, in which b
c
,
R is the value of the cth criterion of the route R and x
c
,
η is the cth criterion-cost of the arc
η.Definition 1.
InG, a connection route l between a given origin-destination O
,
D
∈
V without any loops or repeated arcs and conforming to the urban traffic regulations is a valid route.Definition 2.
The routel
∗ which has the minimum linear-weighted sum of all the criteria chosen by the driver among all the valid routes between O and D in G is the personalized urban multicriteria shortest path between O and D.Based on Definitions1 and 2, the personalized urban multicriteria shortest path optimization model can be described as the following. In (1), L
O
,
D is the set of all the valid routes between O and D in G:(1)
f
l
∗
=
min
l
∈
L
O
,
D
⁡
f
l
,
(2)
f
l
=
∑
c
=
1
C
w
c
∑
g
∈
l
,
x
c
,
g
∈
X
g
x
c
,
g
,
(3)
∑
c
=
1
C
w
c
=
1
.


## 3. The Stochastic Optimization Algorithm for Solving the PUMSP Problem

The survey and analysis about vehicles’ trajectories in urban road networks done by the authors’ team showed that some common laws exist in drivers’ daily travel. For each pair of nodes in urban road network, there are one or more fixed routes which are chosen by experienced drivers. When poor travel condition emerges in parts of the preselected routes in travel which may be caused by many factors like congestion caused by traffic accident or water gathered on the road after raining, drivers will replace the parts using other routes within certain distance range once found by them before arriving there. And the ultimately chosen routes are nearly all around the preselected routes within certain distant range. Based on these laws, a stochastic optimization algorithm is designed and proposed to solve the PUMSP problem, in which the optimum path is obtained by iteratively updating a valid route setQ including certain number of valid routes between O and D. The calculating process is as shown in Figure 1.Figure 1
The calculating process of the proposed algorithm.


### 3.1. Urban Road Network Data Preparation

Urban road network data including criteria-costs data of each arc in the road network and the road network topology data are required in the calculation process. The method of [18] is applied to organize and store the road network data. The statistic section of the arc criteria-costs is between the center points of the adjacent intersections in the traditional methods. The differences of different turning directions in the intersection are usually neglected and errors are easily produced. In this paper, the sections between the exits of adjacent intersections are determined as the statistic sections of the arc criteria-costs, just as showed in Figure 2, the arc criteria-costs of the arcs AB, AD, and AC between the exits of intersection o
1, and the intersection o
2 should be separately counted.Figure 2
The sketch of the arc criteria-costs statistic sections.In order to describe the algorithm, three criteria chosen by a driver are considered including “travel length,” “travel time,” and “effect from other travel factors.” The “travel length” value (b
1) of the route l is the sum of the arc-distance values of the route l. The “travel time” value (b
2) of the route l is the sum of the arc passing-time of the route l. The “effect from other travel factors” value (b
3) of the route l is the sum of the arc-effect values of the route l. According to the driver’s opinion, the “effect from other travel factors” value of an arc is the sum of the effect values of four travel factors including waiting time before red light, road grade, road around marketplaces, and vehicles parking in the roadside (4), in which δ
ι is the effect value of the travel factor ι. The effect values of the four travel factors are given in Table 1, which are obtained from travel survey done by the authors.Table 1
The effect values of different travel factors.
Number
Travel factor
δ
ι
1
Waiting time before red light
1 second~10 seconds
0.10
11 seconds~30 seconds
0.30
31 seconds~60 seconds
0.40
61 seconds~90 seconds
0.60
>90 s
0.90
2
Road grade
Expressway
0.05
Major arterial
0.40
Minor arterial
0.60
Local street
0.80
3
Road around marketplaces
0.60
4
Vehicles parking in the roadside
One side
0.30
Double sides
0.60The corresponding criteria-costsx
1, x
2, and x
3 for each arc in G are normalized using (5)~(6). In (5), x
-
c is the average value of the cth criterion-cost x
c of all arcs in G and x
-
τ is the maximum of x
-
c  (c
=
1,2
,
3); y
c is the transition value. In (6), y
ς
,
c and y
τ
,
c separately are the minimum and maximum of y
c of all the arcs, and z
c is the normalization value of x
c. The values of the three criteria can be calculated using (7), in which b
c
,
l is the value of thecth criterion of the route l; z
c
,
h is the normalization value of the cth criterion-cost of the arc h:(4)
x
3
=
∑
ι
=
1
4
δ
ι
,
(5)
y
c
=
x
c
x
-
τ
x
-
c
c
=
1,2
,
3
,
(6)
z
c
=
y
c
-
y
ς
,
c
y
τ
,
c
-
y
ς
,
c
c
=
1,2
,
3
,
(7)
b
c
,
l
=
∑
h
∈
l
,
h
∈
E
z
c
,
h
c
=
1,2
,
3
.


### 3.2. Route Encoding

An unfixed-length decimal encoding method is applied for encoding the routes, by which a route is encoded using a positive integer sequence consisting of the IDs of nodes fromO to D in the route. For example, in a route as showed in Figure 3, the route encoding is {
1
5
4
2
3
8
6
9
}.Figure 3
The example of a route.


### 3.3. Comprehensive Evaluation Function Value Calculation

According to (2), a comprehensive evaluation function is defined using (8), in which z
c
,
υ is the normalization value of the cth criterion-cost x
c of the arc v in the route l: (8)
f
l
=
∑
c
=
1
3
w
c
∑
υ
∈
l
z
c
,
υ
.


### 3.4. The Valid Route Set Initialization Operator

In the proposed algorithm, the optimum path is obtained by iteratively updating a valid route setQ consisting of certain number of valid routes. The initialization of the valid route set Q directly affects the performance of the proposed algorithm. Unlike the existing stochastic optimization algorithms, the proposed algorithm does not use a stochastic method to generate the initial routes. Instead, with the consideration of the law of drivers’ initial route choice in daily travel, all the daily travel routes are encoded and used to initialize Q, which can be obtained from the taxi monitoring system or the survey about the vehicle trajectories between O and D.


### 3.5. The Valid Route Set Update Operator

In reality, the preselected routes are often adjusted based on drivers’ experiences, and the replaced routes are not always the best. And sometimes, the preselected routes have not been adjusted when travel condition goes bad in parts of the routes because of the lack of information. A personalized travel often has not been satisfied. So, in the updating ofQ, the parts with poor travel conditions in each route in Q should be timely identified and adjusted. And as the increase of iteration times, the routes in Q should converge to the optimum path gradually and the adjusted nodes in each route in Q are fewer and fewer.With the consideration of the above, for each iteration, some new routes will be generated by adjusting parts of each route inQ. In order to increase the search for the routes around the routes with the smaller comprehensive evaluation function value, for each iteration, the number of routes generated by each route q (q
∈
Q) is calculated using (9), in which s
τ and s
ς separately are the maximum and minimum of routes generated by a route in Q in each iteration; f
τ
,
k and f
ς
,
k separately are the maximum and minimum of the comprehensive evaluation function values of all the routes in Q in the kth iteration. f
q and S
q
,
k separately are the comprehensive evaluation function value and the number of new routes generated by the route q in the kth iteration. As shown in Figure 4, there is a linear relation between S
q
,
k and f
q. From (9) and Figure 4, it can be seen that the larger the comprehensive evaluation function value, the fewer the number of the generated new routes:(9)
S
q
,
k
=
s
ς
+
s
τ
-
s
ς
f
τ
,
k
-
f
q
f
τ
,
k
-
f
ς
,
k
.Figure 4
The linear relation betweenS
q
,
k and f
q.Assume that the number of the replaced nodesm
k
,
q in the route q is the same for generating each new route and is a function of k (10), in which H
q is the number of nodes in the route q, and λ is a real number, λ
∈
0,1, and K is the total number of iterations: (10)
m
k
,
q
=
1
+
H
q
-
3
1
-
k
K
λ
.Based on all the above, a new routeq
1 can be generated by replacing m
k
,
q nodes in the route q. Set u and v separately to be the start node and the end node of the replaced part in the route q,  μ to be a real number, and μ
=
m
k
,
q
+
2. Then, the places of u and v can be determined according to the following method.In order to make the replaced part incline to the part with poor travel condition, a costρ is calculated for each arc in the route q using (11) firstly, in which z
d is the normalization value of the vertical distance from the end node of an arc to the straight connecting line between O and D just as shown in Figure 5, z
2
∗ is the normalization value of the expected travel time of the arc, and ε  (ε
3
~
N
0,1) is the random item which is different for each arc in the route q:(11)
ρ
=
w
1
z
d
+
w
1
z
2
-
z
2
∗
z
2
∗
+
w
3
z
3
-
ε
.Figure 5
The vertical distancez
d from the end node of an arc to the straight connecting line between O and D.Subsequently, find out the nodeϑ from all the nodes excepting D in the route q which is the end node of the arc with the maximum value of the arc cost ρ. Set p
1 to be the number of nodes between O and ϑ and p
2 to be the number of nodes between ϑ and D. Set r to be position of the node u in the route q; then the node u is the r
+
μ
-
1th node in the route q. And r is determined based on the following rules:(1)
Ifμ
≥
p
1
+
3 and μ
≤
p
2
+
3 are true, then 1
≤
r
≤
p
1
+
1. And r should be, respectively, selected from the range for generating each new route. As shown in Figure 6(a), when node 2 is the node ϑ and μ
=
6, then the node u can be any node from node 1 to node 4 in the route, and the node v is a node from node 8 to node 9 in the route.
(2)
Ifμ
≥
p
1
+
3 and μ
>
p
2
+
3 are true, then 1
≤
r
≤
p
1
+
p
2
+
4
-
μ. As shown in Figure 6(b), when node 2 is the node ϑ and μ
=
7, then the node u can be any node from node 1 to node 5 in the route, and the node v is a node from node 6 to node 9 in the route.
(3)
Ifμ
<
p
1
+
3 and μ
≤
p
2
+
3 are true, then p
1
+
4
-
μ
≤
r
≤
p
1
+
1. As shown in Figure 6(c), when node 2 is the node ϑ and μ
=
4, then the node u can be any node from node 5 to node 4 in the route, and the node v is a node from node 3 to node 8 in the route.
(4)
Ifμ
<
p
1
+
3 and μ
>
p
2
+
3 are true, then p
1
+
4
-
μ
≤
r
≤
p
1
+
p
2
+
4
-
μ. As shown in Figure 6(d), when node 8 is the node ϑ and μ
=
6, then the node u can be any node from node 5 to node 4 in the route, and the node v is a node from node 6 to node 9 in the route.Figure 6
The nodesu,  v determination: (a) μ
≥
p
1
+
3 and μ
≤
p
2
+
3; (b) μ
≥
p
1
+
3 and μ
>
p
2
+
3; (c) μ
<
p
1
+
3 and μ
≤
p
2
+
3; (d) μ
<
p
1
+
3 and μ
>
p
2
+
3.
(a)
(b)
(c)
(d)In reality, drivers prefer to select the replacing routes around the preselected routes within certain distant range. The replacing route between the nodesu,  v is generated based on Dijkstra algorithm and the arc cost as shown in (12), in which δ
δ
3
~
N
0,1 is the random item which is different for each arc in G and in generating each new route: (12)
λ
=
z
1
+
δ
.All the new routes can be generated based on the above method. When all the new routes have been generated, delete the new routes which are repeated with routes inQ. In addition, count the total number of routes in Q and the remaining new routes, from which the routes with the largest comprehensive evaluation function value are deleted until the number of the remaining routes equals the maximum number of routes allowed in Q. And then, update Q using all the remaining routes.


### 3.6. The Optimum Path Determination and Evaluation

The route with the minimum comprehensive evaluation function value inQ is the optimum path obtained by K times iteration. In this paper, we also measure another parameter β to evaluate the calculation results (equation (13)), in which q
∧ is the optimum path by K times iteration and q
j
∗ is the single-criterion shortest path based on the jth arc criterion-cost. β represents the average of the relative differences of the three criteria of the route q
∧ and their respective minimum values:(13)
β
=
1
3
∑
c
=
1
3
w
3
∑
i
∈
q
∧
x
c
,
i
-
∑
j
∈
q
j
∗
x
c
,
j
∑
j
∈
q
j
∗
x
c
,
j
2
.


## 3.1. Urban Road Network Data Preparation

Urban road network data including criteria-costs data of each arc in the road network and the road network topology data are required in the calculation process. The method of [18] is applied to organize and store the road network data. The statistic section of the arc criteria-costs is between the center points of the adjacent intersections in the traditional methods. The differences of different turning directions in the intersection are usually neglected and errors are easily produced. In this paper, the sections between the exits of adjacent intersections are determined as the statistic sections of the arc criteria-costs, just as showed in Figure 2, the arc criteria-costs of the arcs AB, AD, and AC between the exits of intersection o
1, and the intersection o
2 should be separately counted.Figure 2
The sketch of the arc criteria-costs statistic sections.In order to describe the algorithm, three criteria chosen by a driver are considered including “travel length,” “travel time,” and “effect from other travel factors.” The “travel length” value (b
1) of the route l is the sum of the arc-distance values of the route l. The “travel time” value (b
2) of the route l is the sum of the arc passing-time of the route l. The “effect from other travel factors” value (b
3) of the route l is the sum of the arc-effect values of the route l. According to the driver’s opinion, the “effect from other travel factors” value of an arc is the sum of the effect values of four travel factors including waiting time before red light, road grade, road around marketplaces, and vehicles parking in the roadside (4), in which δ
ι is the effect value of the travel factor ι. The effect values of the four travel factors are given in Table 1, which are obtained from travel survey done by the authors.Table 1
The effect values of different travel factors.
Number
Travel factor
δ
ι
1
Waiting time before red light
1 second~10 seconds
0.10
11 seconds~30 seconds
0.30
31 seconds~60 seconds
0.40
61 seconds~90 seconds
0.60
>90 s
0.90
2
Road grade
Expressway
0.05
Major arterial
0.40
Minor arterial
0.60
Local street
0.80
3
Road around marketplaces
0.60
4
Vehicles parking in the roadside
One side
0.30
Double sides
0.60The corresponding criteria-costsx
1, x
2, and x
3 for each arc in G are normalized using (5)~(6). In (5), x
-
c is the average value of the cth criterion-cost x
c of all arcs in G and x
-
τ is the maximum of x
-
c  (c
=
1,2
,
3); y
c is the transition value. In (6), y
ς
,
c and y
τ
,
c separately are the minimum and maximum of y
c of all the arcs, and z
c is the normalization value of x
c. The values of the three criteria can be calculated using (7), in which b
c
,
l is the value of thecth criterion of the route l; z
c
,
h is the normalization value of the cth criterion-cost of the arc h:(4)
x
3
=
∑
ι
=
1
4
δ
ι
,
(5)
y
c
=
x
c
x
-
τ
x
-
c
c
=
1,2
,
3
,
(6)
z
c
=
y
c
-
y
ς
,
c
y
τ
,
c
-
y
ς
,
c
c
=
1,2
,
3
,
(7)
b
c
,
l
=
∑
h
∈
l
,
h
∈
E
z
c
,
h
c
=
1,2
,
3
.


## 3.2. Route Encoding

An unfixed-length decimal encoding method is applied for encoding the routes, by which a route is encoded using a positive integer sequence consisting of the IDs of nodes fromO to D in the route. For example, in a route as showed in Figure 3, the route encoding is {
1
5
4
2
3
8
6
9
}.Figure 3
The example of a route.


## 3.3. Comprehensive Evaluation Function Value Calculation

According to (2), a comprehensive evaluation function is defined using (8), in which z
c
,
υ is the normalization value of the cth criterion-cost x
c of the arc v in the route l: (8)
f
l
=
∑
c
=
1
3
w
c
∑
υ
∈
l
z
c
,
υ
.


## 3.4. The Valid Route Set Initialization Operator

In the proposed algorithm, the optimum path is obtained by iteratively updating a valid route setQ consisting of certain number of valid routes. The initialization of the valid route set Q directly affects the performance of the proposed algorithm. Unlike the existing stochastic optimization algorithms, the proposed algorithm does not use a stochastic method to generate the initial routes. Instead, with the consideration of the law of drivers’ initial route choice in daily travel, all the daily travel routes are encoded and used to initialize Q, which can be obtained from the taxi monitoring system or the survey about the vehicle trajectories between O and D.


## 3.5. The Valid Route Set Update Operator

In reality, the preselected routes are often adjusted based on drivers’ experiences, and the replaced routes are not always the best. And sometimes, the preselected routes have not been adjusted when travel condition goes bad in parts of the routes because of the lack of information. A personalized travel often has not been satisfied. So, in the updating ofQ, the parts with poor travel conditions in each route in Q should be timely identified and adjusted. And as the increase of iteration times, the routes in Q should converge to the optimum path gradually and the adjusted nodes in each route in Q are fewer and fewer.With the consideration of the above, for each iteration, some new routes will be generated by adjusting parts of each route inQ. In order to increase the search for the routes around the routes with the smaller comprehensive evaluation function value, for each iteration, the number of routes generated by each route q (q
∈
Q) is calculated using (9), in which s
τ and s
ς separately are the maximum and minimum of routes generated by a route in Q in each iteration; f
τ
,
k and f
ς
,
k separately are the maximum and minimum of the comprehensive evaluation function values of all the routes in Q in the kth iteration. f
q and S
q
,
k separately are the comprehensive evaluation function value and the number of new routes generated by the route q in the kth iteration. As shown in Figure 4, there is a linear relation between S
q
,
k and f
q. From (9) and Figure 4, it can be seen that the larger the comprehensive evaluation function value, the fewer the number of the generated new routes:(9)
S
q
,
k
=
s
ς
+
s
τ
-
s
ς
f
τ
,
k
-
f
q
f
τ
,
k
-
f
ς
,
k
.Figure 4
The linear relation betweenS
q
,
k and f
q.Assume that the number of the replaced nodesm
k
,
q in the route q is the same for generating each new route and is a function of k (10), in which H
q is the number of nodes in the route q, and λ is a real number, λ
∈
0,1, and K is the total number of iterations: (10)
m
k
,
q
=
1
+
H
q
-
3
1
-
k
K
λ
.Based on all the above, a new routeq
1 can be generated by replacing m
k
,
q nodes in the route q. Set u and v separately to be the start node and the end node of the replaced part in the route q,  μ to be a real number, and μ
=
m
k
,
q
+
2. Then, the places of u and v can be determined according to the following method.In order to make the replaced part incline to the part with poor travel condition, a costρ is calculated for each arc in the route q using (11) firstly, in which z
d is the normalization value of the vertical distance from the end node of an arc to the straight connecting line between O and D just as shown in Figure 5, z
2
∗ is the normalization value of the expected travel time of the arc, and ε  (ε
3
~
N
0,1) is the random item which is different for each arc in the route q:(11)
ρ
=
w
1
z
d
+
w
1
z
2
-
z
2
∗
z
2
∗
+
w
3
z
3
-
ε
.Figure 5
The vertical distancez
d from the end node of an arc to the straight connecting line between O and D.Subsequently, find out the nodeϑ from all the nodes excepting D in the route q which is the end node of the arc with the maximum value of the arc cost ρ. Set p
1 to be the number of nodes between O and ϑ and p
2 to be the number of nodes between ϑ and D. Set r to be position of the node u in the route q; then the node u is the r
+
μ
-
1th node in the route q. And r is determined based on the following rules:(1)
Ifμ
≥
p
1
+
3 and μ
≤
p
2
+
3 are true, then 1
≤
r
≤
p
1
+
1. And r should be, respectively, selected from the range for generating each new route. As shown in Figure 6(a), when node 2 is the node ϑ and μ
=
6, then the node u can be any node from node 1 to node 4 in the route, and the node v is a node from node 8 to node 9 in the route.
(2)
Ifμ
≥
p
1
+
3 and μ
>
p
2
+
3 are true, then 1
≤
r
≤
p
1
+
p
2
+
4
-
μ. As shown in Figure 6(b), when node 2 is the node ϑ and μ
=
7, then the node u can be any node from node 1 to node 5 in the route, and the node v is a node from node 6 to node 9 in the route.
(3)
Ifμ
<
p
1
+
3 and μ
≤
p
2
+
3 are true, then p
1
+
4
-
μ
≤
r
≤
p
1
+
1. As shown in Figure 6(c), when node 2 is the node ϑ and μ
=
4, then the node u can be any node from node 5 to node 4 in the route, and the node v is a node from node 3 to node 8 in the route.
(4)
Ifμ
<
p
1
+
3 and μ
>
p
2
+
3 are true, then p
1
+
4
-
μ
≤
r
≤
p
1
+
p
2
+
4
-
μ. As shown in Figure 6(d), when node 8 is the node ϑ and μ
=
6, then the node u can be any node from node 5 to node 4 in the route, and the node v is a node from node 6 to node 9 in the route.Figure 6
The nodesu,  v determination: (a) μ
≥
p
1
+
3 and μ
≤
p
2
+
3; (b) μ
≥
p
1
+
3 and μ
>
p
2
+
3; (c) μ
<
p
1
+
3 and μ
≤
p
2
+
3; (d) μ
<
p
1
+
3 and μ
>
p
2
+
3.
(a)
(b)
(c)
(d)In reality, drivers prefer to select the replacing routes around the preselected routes within certain distant range. The replacing route between the nodesu,  v is generated based on Dijkstra algorithm and the arc cost as shown in (12), in which δ
δ
3
~
N
0,1 is the random item which is different for each arc in G and in generating each new route: (12)
λ
=
z
1
+
δ
.All the new routes can be generated based on the above method. When all the new routes have been generated, delete the new routes which are repeated with routes inQ. In addition, count the total number of routes in Q and the remaining new routes, from which the routes with the largest comprehensive evaluation function value are deleted until the number of the remaining routes equals the maximum number of routes allowed in Q. And then, update Q using all the remaining routes.


## 3.6. The Optimum Path Determination and Evaluation

The route with the minimum comprehensive evaluation function value inQ is the optimum path obtained by K times iteration. In this paper, we also measure another parameter β to evaluate the calculation results (equation (13)), in which q
∧ is the optimum path by K times iteration and q
j
∗ is the single-criterion shortest path based on the jth arc criterion-cost. β represents the average of the relative differences of the three criteria of the route q
∧ and their respective minimum values:(13)
β
=
1
3
∑
c
=
1
3
w
3
∑
i
∈
q
∧
x
c
,
i
-
∑
j
∈
q
j
∗
x
c
,
j
∑
j
∈
q
j
∗
x
c
,
j
2
.


## 4. Experiments and Discussion

An urban road network including 2000 nodes and 7014 arcs is used to evaluate the performance of the proposed algorithm. The referred data in the algorithm are obtained by simulation. The performance of the proposed algorithm is compared with those of the genetic algorithm proposed in [19] by calculating the optimum paths between two nodes (IDs: 1 and 1259) in the road network under five groups of w
c
s in Table 2. The minimum of the three criteria separately are 7847.60 meters, 811.71 seconds, and 31.67. And in order to keep the comparability, the genetic algorithm in [19] is improved in four aspects: (1) the comprehensive evaluation function defined in Section 3.3 is defined as the fitness of the generic algorithm, (2) all the daily travel routes between the origin node and the destination node are used to initialize the population, (3) the node ϑ defined in Section 3.5 is defined as the gene variation node in each route, and (4) the replacing routes are generated based on Dijkstra algorithm and the arc cost λ defined in (12). Table 3 gives the basic parameters’ values of the two algorithms.Table 2
Five groups ofw
c
s in (8).
Group
Each criterion importance-value
w
1
w
2
w
3
1
0.5
0
0.5
2
0.4
0.2
0.4
3
0.3
0.4
0.3
4
0.2
0.6
0.2
5
0.1
0.8
0.1Table 3
The basic parameters’ values.
Algorithm
Basic parameter
Value
The proposed algorithm
Maximum number of routes in the valid route set
20
Maximum number of iterations
100
Maximum number of routes generated by a route in each iteration
5
Minimum number of routes generated by a route in each iteration
2
The genetic algorithm
Maximum number of chromosomes in the population
20
Maximum number of iterations
100
Crossover probability
0.9Each algorithm is tested for 50 times under each group ofw
c
s. The iterative calculation results of the two algorithms are given in Figure 7, in which f
-
k is the average of the minimum comprehensive evaluation function values (or the minimum fitness function values) achieved by each algorithm for k times iteration during 50 times’ test. Table 4 gives the average of the minimum comprehensive evaluation function values (or the minimum fitness function values) achieved by each algorithm by 100 times’ iteration during 50 times’ test. As shown in Figure 7 and Table 4, the proposed algorithm has achieved smaller values of f
-
100. The average computing time of the proposed algorithm during 50 times’ test is 31.33 seconds, and that of the genetic algorithm is 43.65 seconds. Table 5 gives the values of the three criteria and the evaluation parameter β of the optimum paths achieved during 50 times’ test under each group of w
c
s. It can be seen that the proposed algorithm has reached a smaller value of β than the genetic algorithm under each group of w
c
s. It is obvious that the performance of the proposed algorithm is better than the genetic algorithm in solving the PUMSP problem. Figure 8 shows the daily travel routes and the optimum paths obtained by the two algorithms under each group of w
c
s. The optimum paths obtained by the two algorithms are all around the daily travel routes, which matches the reality. All of these calculation results indicate that the proposed algorithm can be used to solve the PUMSP problem.Table 4
f
-
100 achieved by the two algorithms under each group of w
c
s during 50 times’ test.
Each criterion importance-value
f
-
100
w
1
w
2
w
3
The proposed algorithm
The geneticalgorithm
0.5
0
0.5
15.58
16.39
0.4
0.2
0.4
15.20
15,87
0.3
0.4
0.3
14.57
15.45
0.2
0.6
0.2
13.77
15.2
0.1
0.8
0.1
12.58
14.67Table 5
The values of the three criteria andβ of the optimum paths achieved during 50 times’ test under each group of w
c
s.
Each criterion importance-value
The proposed algorithm
The genetic algorithm
w
1
w
2
w
3
x
1/meter
x
2/second
x
3
β
x
1/meter
x
2/second
x
3
β
0.5
0
0.5
9343.15
1277.71
40.08
0.1634
10930.65
1094.36
34.56
0.2016
0.4
0.2
0.4
8936.59
945.06
44.07
0.1693
10901.61
1083.48
34.79
0.1740
0.3
0.4
0.3
8970.47
911.00
45.11
0.1429
9018.87
826.20
59.81
0.2704
0.2
0.6
0.2
9067.27
869.69
48.16
0.1168
10795.14
1025.51
38.54
0.1803
0.1
0.8
0.1
8834.95
819.68
58.94
0.0874
10766.10
1021.16
40.92
0.2118Figure 7
The changing off
-
k achieved by the two algorithms with the increasing of iteration times under each group of w
c
s: (a) the proposed algorithm; (b) the genetic algorithm.
(a)
(b)Figure 8
The daily travel routes and the optimum paths obtained by the two algorithms under each group ofw
c
s: (a) the daily travel routes, (b) the optimum paths obtained by the proposed algorithm, and (c) the optimum paths obtained by the genetic algorithm.
(a)
(b)
(c)


## 5. Conclusions

The personalized urban multicriteria shortest path optimization is a complex problem. The stochastic algorithms are proved to be superior to the deterministic algorithms. But existing stochastic algorithms still have some limitations like the lack of the strategies about avoiding the impractical routes and the long computing time which largely affect the performance in practice application. In this paper, a new stochastic optimization algorithm is proposed to solve the PUMSP problem. Unlike most of the existing stochastic optimization algorithms based on the random strategies in the initial routes generation and update, the key operators of the proposed algorithm are designed based on drivers’ travel route choice law on the initial routes choice and adjustment in daily travel. The experiment results showed that the proposed algorithm reached better results in the evaluation parameters and computing time in comparison with those of the genetic algorithm. And the experiment results also indicated that the proposed algorithm has the ability of avoiding the impractical solutions.It should be noted that the proposed algorithm is universal for more criteria. But (11) should be adjusted when more criteria are considered. In addition, the computing time can be further reduced by using a better shortest path algorithm to generate the replacing routes.



---

*Source: 987358-2015-11-30.xml*