Sage Journals: Discover world-class research

Abstract

Introduction:

In large-scale events such as concerts and sports competitions, participants often leave the venue at the same time to return to their respective destinations. Improper traffic planning and traffic light operation usually lead to traffic congestion and road chaos near the sites. Rapid evacuation of participants has become an important issue.

Objectives:

In this work, a one-way road orientation planning problem with multiple venues is studied in which all roads near the venues are to be scheduled into a one-way orientation with strong connectivity to increase the evacuation efficiency of participants.

Methods:

In accordance with Robbins’ theorem and a random sequence of integers, an encoding scheme based on module operator is presented to construct a strongly connected graph and plan a one-way orientation for all roads. The proposed encoding scheme is further embedded into four artificial intelligence approaches, namely, grey wolf optimization, immune algorithm, genetic algorithm, and particle swarm optimization, to solve the one-way road orientation planning problem such that the total distance of all vehicles from venues to their destinations is minimized.

Results:

Numerical results of test problems with multiple venues in Taiwan are provided and analyzed. As shown, all four algorithms can obtain the best solution for the test problems.

Conclusions:

The new presented encoding scheme with four algorithms can be used to effectively solve the one-way road orientation planning problem for the evacuation of participants. Moreover, grey wolf optimization is superior to the other three algorithms and particle swarm optimization is faster than the other three algorithms.

Keywords

Road orientation planning problem grey wolf optimization immune algorithm genetic algorithm particle swarm optimization

Introduction

During large-scale activities, participants frequently leave the venue simultaneously and return to their respective communities, typically resulting in traffic congestion and road chaos near the site due to improper traffic planning and traffic light operation. Thus, an appropriate direction scheduling of vehicles can effectively evacuate all participants.

Several methods have been used to quickly evacuate all vehicles of the participants within a short time. Among these methods, the one-way road system is a popular technology used in traffic operation management. The advantages of implementing a one-way traffic system are as follows (Homburger and Kell¹):

Effective use of existing roads;

Improves road capacity;

Increases vehicle speed;

Improves road traffic safety;

Shortens the cycle time of signal lights and increases the efficiency of intersections;

Reduces the intensity of traffic management and improves the effectiveness of management measures;

Eliminate traffic accidents, such as frontal and side collisions with oncoming vehicles.

Many evacuation planning problems have been modeled and studied in the past. For example, Barbarosoğlu and Arda² proposed a two-stage stochastic programming model to plan the transportation of essential first-aid commodities to disaster-affected areas during emergency response. Han et al.³ devised a framework for simultaneously optimizing evacuation traffic destination and route assignment. On the basis of this framework, they can determine the optimal evacuation destination and route assignment using a one-step optimization procedure. Lindell and Prater⁴ considered an evacuation problem for a hurricane emergency. They proposed a system called evacuation management decision support system to display information about the minimum, most, and maximum probable evacuation time estimates compared with the earliest, most, and latest probable estimated times of arrival under stormy conditions. Lindell⁵ presented a fast method for calculating evacuation time, and the estimate made is compatible with the research findings about evacuees’ behavior during hurricanes. Stepanov and Smith⁶ investigated the optimal design and analysis of evacuation routes in transportation networks. They also surveyed several evacuation models and various solutions based on the type of route assignment (simple, static, and dynamic) and the scale of the problem (micro, meso and macro). The other references of evacuation planning are referred to Campos et al.⁷ and Han et al.³ Additionally, El-Hamied et al.⁸ surveyed evacuation planning process by using Geographical Information System and Dhamala⁹ surveyed models and algorithms for evacuation planning network problems.

As indicated in the above literature, several evacuation planning problems have been modeled and studied. However, their major subject focuses on the evacuation of people or vehicles directly to shelters without considering the connectivity of all roads in their studied network. The connectivity of all roads is important for vehicles because it can provide flexibility and reduce congestion for vehicles once vehicles drive into wrong roads.

The primary objective of this study is to plan the orientation of roads in one way such that all nodes in the roads are strongly connected and all vehicles from multiple venues can return quickly to their destinations. To achieve connectivity of all nodes in the roads, a strongly connected graph must be constructed. However, for a given network, there are numerous such strongly connected graphs for one-way road orientation planning problem (hereinafter referred to as ROPP). To our knowledge, past research focused on the emergency evacuation planning and ignored the connectivity of network which is concerned in this paper.

In the paper, an encoding scheme for converting any random integer into its corresponding depth-first-search spanning tree is presented and then Robbins’ theorem is used to construct a strongly connected graph for ROPP. Then, the encoding scheme is embedded into four artificial evolutionary intelligence approaches, namely, grey wolf optimization (GWO), immune algorithm (IA), genetic algorithm (GA), and particle swarm optimization (PSO), to solve ROPP. The numerical results of two test problems with multiple venues in Tainan, Taiwan are provided to demonstrate the performance of the four adopted algorithms for ROPP problem.

ROPP, notations, and assumptions

Notations

N number of nodes in a network, 1 ≤ i ≤ N

n number of destinations in a network, 1 ≤ j ≤ n

e number of venues in the network, 1 ≤ k ≤ e

v_kj number of vehicles from venue k to destination j, 1 ≤ k ≤ e, 1 ≤ j ≤ n

d_kj shortest distance from venue k to destination j, 1 ≤ k ≤ e, 1 ≤ j ≤ n

z_kj total distance of vehicles from venue k to destination j, 1 ≤ k ≤ e, 1 ≤ j ≤ n

z(•) = , the total routing distance of vehicles from all venues to their respective destinations

The objective of ROPP is to schedule the orientation of all roads in a one-way direction such that all nodes in the networks are strongly connected and the total routing distance of vehicles from all venues to their destinations is minimized, that is, min z(•).

Assumptions

The network with N nodes contains e venues and n destinations.

All vehicles in the venues have to return to their destinations simultaneously. Assume that the total of v_kj vehicles have to return to destination j from venue k, 1 ≤ k ≤ e, 1 ≤ j ≤ n.

All the vehicles will take the shortest path to return to their destinations. Assume that the shortest distance is d_kj from venue k to destination j, 1 ≤ k ≤ e, 1 ≤ j ≤ n.

To avoid traffic chaos, all roads are scheduled in a one-way direction and strongly connected; that is, every node in the network can visit each other.

The objective of ROPP is to minimize the total routing distance of vehicles from all the venues to their destinations.

Figure 1(a) illustrates an example of the ROPP network with 3 venues and 10 destinations and Figure 1(b) is a feasible solution of the example. However, Figure 1(c) is an infeasible solution for the example since it is not a strongly connected graph. More specifically, the nodes on the right hand side of the dotted line in Figure 1(c) cannot reach the nodes on the left hand side. This means that the connectivity of any two nodes is not maintained.

Figure 1.

The example of one-way ROPP network with 3 venues and 10 destinations.

Difference between ROPP and other routing problems

The considered ROPP differs from other typical routing problems. The following briefly summarizes the major differences.

(1) ROPP differs from the evacuation routing problem (ERP)

ERP (Lindell and Prater;⁴ Stepanov and Smith⁶) aims to efficiently evacuate residents or vehicles to refuge or shelters during emergency events. ERP must schedule the evacuation paths for residents such that evacuation time is minimized. ROPP differs from ERP because the former is required to plan the orientation for all roads such that all roads can connect to one another. By contrast, ERP must only schedule the evacuation paths for residents without considering the connectivity of roads.

(2) ROPP differs from the transshipment routing problem (TRP)

TRP (Baldacci et al.;¹⁰ Peres et al.¹¹) aims to deliver goods efficiently from some nodes to certain specific nodes. TRP must schedule the delivery paths for vehicles such that the total delivery distance of a vehicle is minimized. ROPP differs from TRP because the former is required to plan the orientation for all roads such that all roads can connect to one another. Conversely, based on the given roads, TRP must only schedule the delivery paths for vehicles without considering the connectivity of roads.

(3) ROPP differs from the shortest path problem (SPP)

SPP (Llanos et al.¹²) aims to find the shortest path for a vehicle such that the total delivery distance is minimized. ROPP differs from SPP because the former must plan the orientation for all roads such that all roads can connect to one another. By contrast, SPP is only required to schedule the delivery path for vehicles without considering the connectivity of roads.

(4) ROPP differs from k-SPP

k-SPP (Brander and Sinclair¹³) aims to find the k feasible shortest paths for a vehicle such that the total delivery distance is minimized. k-SPP is an extension of SPP, and SPP is a special case of k-SPP if k = 1. ROPP differs from k-SPP because the former must plan the orientation for all roads such that all roads can connect to one another. Conversely, k-SPP is only required to schedule the top k delivery paths for a vehicle without considering the connectivity of roads.

As shown in the preceding sections, the major difference between ROPP and other typical routing problems is that ROPP maintains the connectivity of all roads, which is disregarded in other typical routing problems. However, the connectivity of all roads is important for drivers once they drive into wrong roads in actual practice. To maintain the connectivity of all roads, one has to construct a strongly connected graph for ROPP. Since there exist numerous feasible strongly connected graphs for ROPP, in this study, a novel encoding scheme is presented and embedded into four algorithms to solve ROPP without exploring all feasible strongly connected graphs. In addition to ROPP, strongly connected graphs have other applications. For example, Daugulis¹⁴ presented an interesting application in practice: if vertices are at intersections and edges are (possibly one-way) roads, then how many one-way roads or intersections can be closed such that the remaining road network is still strongly connected.

Approaches

Approaches for constructing a strongly connected graph

ROPP is related to ERP, TRP, and SPP. Given that each road has to be scheduled into a one-way orientation, the total number of possible plans for all roads is 2 ^m , where m is the number of roads. Thus, the complexity for ROPP is O(2 ^m ) and it is NP-hard. This finding implies that the solving time of the optimal solution for the mathematical model of ROPP is exponential rather than polynomial. Therefore, in this paper, we intend to present efficient approaches for solving ROPP within a feasible time. In this study, a new encoding scheme is presented to convert any sequence of random integers into its corresponding depth-first-search spanning tree and Robbins’ theorem is then applied to construct a strongly connected graph for ROPP. Finally, the encoding scheme is embedded into four artificial intelligence (AI) approaches, namely, GWO, IA, GA, and PSO, to solve ROPP and then compare the numerical results of the four adopted algorithms.

Depth-first-search spanning tree

The primary steps for finding a depth-first-search spanning tree are as follows.

Step 0. Select any vertex and label it with 1, i ← j ← 1.

Step 1. Select any vertex that is connected by a single edge to the vertex labeled i. If no such vertex exists, then skip to Step 4; otherwise, proceed to Step 2.

Step 2. Label the selected vertex j + 1.

Step 3. Let i ← j ← j + 1.

Step 4. Let i ← i-1. If i = 0, then stop; otherwise, return to Step 1.

Notably, Step 1 for finding the depth-first-search spanning tree has to select one vertex from all feasible vertices. Typically, it is “random” selected. However, our encoding scheme is designed to find a “specific” vertex based on a random sequence.

Robbins’ theorem

The major steps for Robbins’ theorem (Bang-Jensen and Gutin¹⁵) are as follows.

Step 1. Find a depth-first-search spanning tree.

Step 2. Orient all edges on the spanning tree from the vertex with a smaller label to the vertex with a larger label.

Step 3. Orient all edges not on the spanning tree from the vertex with a larger label to the vertex with a smaller label.

New encoding scheme and example

For the ROPP, a new encoding scheme is presented to convert a random permutation of {1, 2,…, N} with a module operator into its corresponding feasible solution for the problem, where N is the total number of nodes in the network. That is, the “mod” operator is used in the new encoding scheme to select the next vertex to connect in Step 1 of constructing the depth-first-search spanning tree.

There are three main phases for the method presented in this paper to construct the strongly connected graph for the ROPP.

Phase 1: Given a random sequence of integers, R, and construct its “corresponding” depth-first-search spanning tree based on “module operator.”

Phase 2: Based on the depth-first-search spanning tree obtained in Phase 1, apply Robbins’ theorem for constructing the strongly connected graph.

Phase 3: Based on the strongly connected graph obtained in Phase 2, we compute the distance matrix among nodes, including venues and destinations, and compute the objective value for the random sequence R.

The following example is to illustrate the new encoding scheme.

Example

The network has 16 nodes, 24 roads, and 1 venue.

The distance between any two consecutive nodes is 1.

Suppose that all destinations are in the nodes in Figure 2(a) and the venue is at Node 1 in Figure 2(a).

ROPP aims to schedule a one-way direction for all roads such that the total routing distance of all vehicles from the venue to the destinations is minimized.

Encoding scheme

A total of 16 nodes can be seen in Figure 2(a), and a random sequence of 1–16 is used to provide a feasible solution for ROPP. Suppose that the random sequence is R1 = {9,4,6,13,2, 12,16,8,11,14, 15,3,10,75,1}.

R1(1) = 9; thus, start the depth-first-search spanning tree from Node 9 in Figure 2(a).

Three unconnected nodes, namely, Nodes 5, 10, and 13, are found at Node 9. Since [R1(1) mod 3] + 1 = (9 mod 3) + 1 = 1, an arc from Node 9 to Node 5 is assigned.

Two unconnected nodes, namely, Nodes 1 and 6, are found at Node 5. Since [R1(2) mod 2] + 1 = (4 mod 2) + 1 = 1, an arc from Node 5 to Node 1 is assigned.

In accordance with the similar steps used for a depth-first-search spanning tree, black arcs are obtained, such as those shown in Figure 2(b) based on R1.

Lastly, following the major steps for Robbins’ theorem, the red arcs in Figure 2(c) are added. Figure 2(c) shows a strongly connected graph.

Accordingly, the total distance can be computed for all vehicles from the venue to their respective communities on the basis of Figure 2(d).

Similarly, in accordance with the proposed encoding scheme, if the random sequence of 1–16 is R2 = {13,2,7,15,3,1,14,8,9,6,12,11,16,10,4,5}, then a strongly connected graph is achieved, as shown in Figure 2(d). Thus, if there are only two destinations at nodes 7 and 13, respectively, then the solution of R1 is superior to R2 since d_1,7 = 3 and d_1,13 = 11 in Figure 2(c) and d_1,7 = 3 and d_1,13 = 5 in Figure 2(d).

Figure 2.

The strongly connected graph for the example.

Note that depth-first-search spanning tree and Robbins’ theorem are typical approaches for constructing a strongly connected graph. However, as mentioned in this paper, there are numerous strongly connected graphs for a given network. The considered ROPP aims to minimize the total routing distance of vehicles based the “optimal strongly connected graph.” In other words, for a given network, how to find the “optimal strongly connected graph” among numerous feasible strongly connected graphs is the main issue of this paper.

In this paper, for a given random sequence of integers, say R, we adopt “module operator” to find R’s corresponding depth-first-search spanning tree and R’s corresponding strongly connected graph. That is, different random sequences of integers will lead to different strongly connected graphs and different strongly connected graphs will lead to different feasible solutions of ROPP. Consequently, as shown below in this paper, we adopt four evolutionary algorithms, namely, GWO, IA, GA, and PSO to find the “optimal strongly connected graph,” that is, the optimal one-way orientation of all roads for the ROPP such that the total routing distance of vehicles from venues to destinations is minimized.

Four algorithms

In the past, researchers focused on deriving the global optimal solution for various types of complicated optimization problems. Therefore, many mathematical models and solutions, for example, the branch-and-bound technique (Francis et al.¹⁶), have been proposed to solve complicated optimization problems. However, exact methods for NP-hard problems are extremely time-consuming and they are impractical to use when the problem is large. With the advent of AI algorithms in recent years, several evolutionary algorithms and meta-heuristics based on nature or animal behavior have been developed to solve numerous complicated optimization problems in various fields, such as engineering, management, and computer science. Yazdani and Jolai¹⁷ presented a lion optimization algorithm based on the behavior of lions. They also mentioned more than 30 novel AI algorithms and their various applications. Particularly, meta-heuristics are suitable for solving real-life engineering design problems, for example, Meng et al.,¹⁸ Gupta et al.,¹⁹ Yıldız et al.,²⁰ Champasak et al.,²¹ Yıldız et al.,²² Yıldız et al.,²³ Dhiman et al.,²⁴ Yıldız et al.,²⁵ Panagant et al..²⁶

From the literature, GA and PSO may be the most popular algorithms due to their numerous successes in various problems. In addition, GWO and IA have attracted much attention due to their successful applications. The former, GWO, was proposed by Mirjalili et al.²⁷ in 2014 and its main steps are constructed by the social hierarchy, encircling prey, hunting and attacking prey (exploitation) of grey wolves. In the GWO, four types of grey wolves are involved, namely, alpha, beta, delta and omega. For each iteration of GWO, the position of each grey wolf in the population will update and its fitness will be evaluated. Then the best grey wolf (alpha), the second grey wolf (beta) and the third grey wolf (delta) will be updated. To shorten this paper, we illustrate the flowchart of GWO in Figure 3 and refer to Mirjalili et al.²⁷ and Nadimi-Shahraki et al.²⁸ for the detailed description of GWO.

Figure 3.

Main steps of GWO (Mirjalili et al.²⁷).

In addition to GWO, IA has elicited attention due to its unique memory mechanism. As demonstrated by Hsieh and You,²⁹ IA is similar to GA in terms of crossover and mutation operations, except for its unique memory mechanism that can be used to increase the variety of solutions. Thus, in the study, IA is also adopted to solve the considered ROPP. The major steps of IA are illustrated in Figure 4.

Figure 4.

Main steps of IA (Hsieh and You²⁹).

To evaluate the performance of GWO and IA for solving ROPP, we also provide the numerical results of GA and PSO for comparison. The primary steps of GA and PSO are referred to those of Holland³⁰ and Kennedy and Eberhart,³¹ respectively.

Test problem

The test problems are examples from Tainan, Taiwan. Figure 5(a) and (b) shows the networks of the two problems with two and three venues, respectively. Assume that various numbers of vehicles have to return from different venues into four major destinations. Table 1 provides the data for the two test problems. For example, Test Problem 1 shows that two venues are located at nodes 5 and 25, respectively, and participants from the two venues have to return to their communities. That is, 100 vehicles of participants have to return from venue at node 5 to community at node 4; 80 vehicles of participants have to return from venue at node 25 to community at node 4; 230 vehicles of participants have to return from venue at node 5 to community at node 11; 225 vehicles of participants have to return from venue at node 25 to community at node 11, and so on. In the two test problems, we have to find the optimal one-way orientation of all roads such that the total routing distance of all vehicles from venues to their destinations is minimized.

Figure 5.

Two test problems in Tainan, Taiwan.

Table 1.

Test problems.

Test problem	Venue	Destination(vehicles)
1	5	4(100)	11(230)	15(200)	17(70)
1	25	4(80)	11(225)	15(190)	17(170)
2	5	4(100)	11(230)	15(200)	17(70)
	10	4(100)	11(75)	15(50)	17(150)
	25	4(80)	11(225)	15(190)	17(170)

The preliminary tests are conducted to set the parameters for GWO, IA, GA and PSO. In GWO, population = 50, maximum iteration = 1000, parameter a is decreased by using 2-iter*((2)/Max_iter). In IA and GA, population = 50, affinity = 0.25, crossover = 0.99, mutation = 0.03, maximum generations = 1000. For PSO, the parameters are set as follows: (C1, C2) = (1.2, 1.49618), population = 50, and maximum generations = 1000. Then 20 trials via GWO, IA, GA, and PSO are performed on the two test problems. The optimal solution for the two test problems is shown in Figure 6. The best and average of solutions, CPU times, and convergence iteration of 20 trials are summarized in Table 2 and Figures 7 to 9.

Figure 6.

The optimal solution for the two test problems in Taiwan, Taiwan.

Figure 7.

Numerical results of objective for various algorithms

Figure 8.

Numerical results of CPU time for various algorithms.

Figure 9.

Numerical results of convergence iteration for various algorithms.

Table 2.

Numerical results of four algorithms for test problems.

Problem			GWO	IA	GA	PSO
		Min	8055	8055	8055	8055
	Obj	Avg	8055	8091.9	8162.05	8060.3
		Max	8055	8272	8462	8161
		Std	0.00	75.12	154.86	23.70
		Min	18.00	1	1	1
1	Iter	Avg	103.15	83.2	219.55	96.9
		Max	326.00	559	685	275
		Std	88.75	153.42	221.39	79.65
		Min	76.52	147.02	124.38	18.53
	CPU	Avg	77.13	172.96	128.39	22.322
		Max	79.02	296.06	133.56	29.08
		Std	0.64	40.49	2.40	3.00
		Min	11134	11134	11134	11134
	Obj	Avg	11161.9	11663.3	11731.68	11310.55
		Max	11244	13074	13303	11934
		Std	36.42	539.44	666.02	214.45
		Min	44	3	2	7
2	Iter	Avg	447.1	66.3	305.55	173.90
		Max	821	407	915	687
		Std	246.31	112.72	293.79	200.28
		Min	75.53	151.41	121.31	19.09
	CPU	Avg	77.89	170.91	128.34	24.60
		Max	83.64	280.67	132.52	37.56
		Std	1.57	34.40	2.68	6.15

Discussions

From Table 2 and Figures 7 to 9, one observes that:

The objective value increases with an increase in the number of venues. For example, the best objective value is 8055 for case with two venues and 11134 for the case with three venues. This observation implies that more venues will increase the total routing distance of vehicles.

The standard deviation of the objective value increases with an increase in number of venues. For example, through GWO, the standard deviation of the objective value is 0.00 for the case with two venues and 36.42 for case with three venues. Similar findings for IA, GA and PSO can be obtained. This observation indicates that more venues will increase the complexity of the problem and increase the difficulty in solving for the four algorithms.

The average convergence iteration is stable with an increase in the number of venues. However, the standard deviation of the convergence iteration slightly increases with an increase in number of venues. For example, through GWO, the average convergence iteration is 103.15 for the case with two venues and 447.1 for case with three venues. Similar findings for GA and PSO can be obtained. This observation also suggests that more venues will increase the complexity of the problem and increase the difficulty in solving for the four algorithms.

The CPU time of an algorithm for the two test problems is stable for all four algorithms. For example, through GWO, the average CPU time is 77.13 for the case with two venues and 77.89 for the case with three venues. This observation implies that the adopted four algorithms are stable for more venues.

Among the four AI algorithms, GWO outperforms IA, GA and PSO. For example, the average of the objective value for the case with three venues is 11161.9 via GWO, 11663.3 via IA, via 11731.68 GA, and 11310.55 via PSO.

Among the four AI algorithms, PSO is faster than GWO, GWO is faster than GA, and GA is faster than IA. For example, the average CPU time for the case with three venues is 77.89 via GWO, 170.91 via IA, 128.34 via GA, and 24.60 via PSO.

To further analyze the performance of the adopted four algorithms in this paper, the following hypothesis is tested by using the numerical results of 20 trials.

H₀: Avg(A) = Avg(B),

H₁: Avg(A)≠Avg(B),

where Avg(A) and Avg(B) denote the average objective, that is, the total routinh distance of vehicle, by using algorithms A and B, where A, B∈{GWO, IA, GA, PSO}, A≠B. Based on numerical results of 20 trials in objective value, the corresponding p-values of the statistical hypothesis are summarized in Table 3, which shows the following:

For Test problem 1, GWO is superior to IA and GA significantly with p-values 0.0204, 0.0030, respectively. PSO is superior to IA and GA significantly with p-values 0.0432 and 0.0044, respectively. IA is superior to GA significantly with p-values 0.0396. But there is no significant difference between GWO and PSO.

For Test problem 2, GWO is superior to IA, GA, and PSO significantly with p-values 0.0003, 0.0006, and 0.0031, respectively. PSO is superior to IA and GA significantly with p-values 0.0059 and 0.0065, respectively. But there is no significant difference between IA and GA.

Conclusions

In this study,

A ROPP is presented in which each road has to be scheduled into a one-way orientation and all roads are strongly connected such that all vehicles can be quickly evacuated from the venues to their respective destinations.

A new encoding scheme is presented to convert any integer sequence into its corresponding feasible depth-first-search spanning tree and then Robbins’ theorem is used to construct a strongly connected graph for ROPP.

The encoding scheme is embedded into four AI approaches, namely, GWO, IA, GA, and PSO, to solve ROPP.

The numerical results of test examples from Tainan, Taiwan are presented to demonstrate and compare the performance of the four algorithms. Numerical results show that GWO is superior to the other three algorithms for solving ROPP.

Table 3.

P-values of the statistical hypothesis for four algorithms.

Problem	Algorithm	GWO	IA	GA	PSO
1	GWO	–	0.0204*	0.0030*	0.1649
	IA	–	–	0.0396*	0.0432*
	GA	–	–	–	0.0044*
	PSO	–	–	–	–
	GWO	–	0.0003*	0.0006*	0.0031*
2	IA	–	–	0.3616	0.0059*
	GA	–	–	–	0.0065*
	PSO	–	–	–	–

*Significant difference with α = 0.05.

In the future, a more flexible ROPP may be considered. One example is ROPP with maximal arrival time for vehicles and capacity of flow for roads. Moreover, several other algorithms for solving ROPP can be investigated and experimented.

Footnotes

Acknowledgments

The authors appreciate Mr T.Y. Tsai for the preliminary test of setting parameters. This research was partially supported by Ministry of Science and Technology, Taiwan, under Grant No. MOST 107-2221-E-150-026 and MOST 108-2221-E-150-002.

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The authors received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Yi-Chih Hsieh

Author biographies

Yi-Chih Hsieh received a PhD degree in Industrial Engineering from University of Iowa, USA, and his research interests include optimization, operations research and applications of artificial intelligence. He is now a professor of Department of Industrial Management, National Formosa University, TAIWAN.

Peng-Sheng You received a PhD degree in Management Science and Engineering from University of Tsukuba, Japan, and his research interests include inventory management, supply chain management and applications of artificial intelligence. He is now a professor of Department of Business Administration, National Chiayi University, TAIWAN.

References

Homburger

Kell

. Fundamentals of traffic engineering, (book) institute of transportation studies, University of California, Berkeley, 1988. https://trid.trb.org/view/1184555

Barbarosoğlu

Arda

. Two-Stage stochastic programming framework for transportation planning in disaster response. J Oper Res Soc 2004; 55: 43–53.

Han

Yuan

Chin

, et al. Global optimization of emergency evacuation assignments. Interfaces 2006; 36: 502–513.

Lindell

Prater

. A hurricane evacuation management decision support system (EMDSS). Nat Hazards 2007; 40: 627–634.

Lindell

. EMBLEM2: an empirically based large scale evacuation time estimate model. Transport Res A-Pol 2008; 42: 140–154.

Stepanov

Smith

. Multi-objective evacuation routing in transportation networks. Eur J Oper Res 2009; 198: 435–446.

Campos

Bandeira

. A method for evacuation route planning in disaster situations. Procedia Soc Behav Sci 2012; 54: 503–512.

El-Hamied

SSA

Saleh

AAE

Asem

. Survey on using GIS in evacuation planning process. Int J Comput Sci Inf Technol Secur 2012; 10: 40–43.

Dhamala

. A survey on models and algorithms for discrete evacuation planning network problems. J Ind Manag Optim 2015; 11: 265–289.

10.

Baldacci

Ngueveu

Calvo

. The vehicle routing problem with transhipment facilities. Transport Sci 2017; 51: 395–789.

11.

Peres

Repolhoa

Martinelli

, et al. Optimization in inventory-routing problem with planned transshipment: a case study in the retail industry. Int J Prod Econ 2017; 193: 748–756.

12.

Llanos

Gonzalez-Escribano

Arranz

. The shortest-path problem: analysis and comparison of methods (synthesis lectures on theoretical computer science). Morgan & Claypool, 2018: 1–87.

13.

Brander

Sinclair

. A comparative study of k-shortest path algorithms. In: Merabti

Carew

Ball

(eds) Performance engineering of computer and telecommunications systems (pp. 370–379). London: Springer, 1996.

14.

Daugulis

. Strong connectivity and its applications, working paper: https://arxiv.org/pdf/1609.07355.pdf, 2016.

15.

Bang-Jensen

Gutin

. Digraphs: theory, algorithms and applications. Heidelberg, Germany: Springer Science & Business Media, 2013.

16.

Francis

Smilowitz

Tzur

. The period vehicle routing problem and its extensions. The vehicle routing problem: latest advances and New challenges, in Operations research/computer science interfaces series, Boston, USA: Springer, 2008; 73–102.

17.

Yazdani

Jolai

. Lion optimization algorithm (LOA): a nature-inspired metaheuristic algorithm. J Comput Des Eng 2016; 3: 24–36.

18.

Meng

Wang

, et al. A comparative study of metaheuristic algorithms for reliability-based design optimization problems. Arch Comput Methods Eng 2021; 28; 183: 1853–1869.

19.

Gupta

Abderazek

Yıldız

, et al. Comparison of metaheuristic optimization algorithms for solving constrained mechanical design optimization problems. Expert Syst Appl 2021: 115351.

20.

Yıldız

Pholdee

, et al. The Henry gas solubility optimization algorithm for optimum structural design of automobile brake components. Mater Test 2020; 62: 261–264.

21.

Champasak

Panagant

Pholdee

, et al. Self-adaptive many objective meta-heuristic based on decomposition for many-objective conceptual design of a fixed wing unmanned aerial vehicle. Aerosp Sci Technol 2020; 100: 105783.

22.

Yıldız

Albak

, et al. Butterfly optimization algorithm for optimum shape design of automobile suspension components. Mater Test 2020; 62: 365–370.

23.

Yıldız

Özkaya

Yıldız

, et al. The equilibrium optimization algorithm and the response surface-based metamodel for optimal structural design of vehicle components. Mater Test 2020; 62: 492–496.

24.

Dhiman

Singh

Slowik

, et al. EMoSOA: a new evolutionary multi-objective seagull optimization algorithm for global optimization. Int J Mach Learn Cybern 2021; 12: 571–596.

25.

Yıldız

ABS

Pholdee

Bureerat

, et al. Sine-cosine optimization algorithm for the conceptual design of automobile components. Mater Test 2020; 62: 744–748.

26.

Panagant

Pholdee

Bureerat

, et al. Seagull optimization algorithm for solving real-world design optimization problems. Mater Test 2020; 62: 640–644.

27.

Mirjalili

Lewis

. Grey wolf optimizer. Adv Eng Soft 2014; 69: 46–61.

28.

Nadimi-Shahraki

Taghian

Mirjalili

. An improved grey wolf optimizer for solving engineering problems. Expert Syst Appl 2021; 166: 113917.

29.

Hsieh

You

. A generalized museum visitor routing problem considering the preferences and congestion for multiple groups :an example in Taiwan. Intell Autom Soft Comput 2020; 26: 693–703.

30.

Holland

. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Cambridge, MA, USA: MIT press, 1975.

31.

Kennedy

Eberhart

. Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks IV, 1995; 1942–1948.

Evolutionary artificial intelligence algorithms for the one-way road orientation planning problem with multiple venues: An example of evacuation planning in Taiwan

Abstract

Introduction:

Objectives:

Methods:

Results:

Conclusions:

Keywords

Introduction

ROPP, notations, and assumptions

Notations

Assumptions

Difference between ROPP and other routing problems

Approaches

Approaches for constructing a strongly connected graph

Depth-first-search spanning tree

Robbins’ theorem

New encoding scheme and example

Example

Encoding scheme

Four algorithms

Test problem

Discussions

Conclusions

Footnotes

Acknowledgments

Declaration of conflicting interests

Funding

ORCID iD

Author biographies

References