Communications and Network, 2013, 5, 606-610
http://dx.doi.org/10.4236/cn.2013.53B2109 Published Online September 2013 (http://www.scirp.org/journal/cn)
Research on Traveling Routes Problems Based on
Improved Ant Colony Algorithm
Zhanchang Yu, Sijia Zhang, Siyong Chen, Bingxing Liu, Shiqi Ye
Department of Information Science and Technology, Jinan University, Guangzhou, China
Received May 2013
ABSTRACT
This paper studies how to obtain a reasonable traveling route among given attractions. Toward this purpose, we propose
an objective optimization model of routes choosing, which is based on the improved Ant Colony Algorithm. Further-
more, we make some adjustment in parameters in order to improve the precision of this algorithm. For example, the
inspired factor has been changed to get better results. Also, the ways of searching hav e been adjusted so that the travel-
ing routes will be well designed to achieve optimal effects. At last, we select a series of attractions in Beijing as data to
do an experimental analysis, which comes out with an optimum route arrangement for the travelers; that is to say, the
models we propose and the algorithm we improved are reasonable and effective.
Keywords: Traveling Routes; Ant Colony Algorithm; Parameter Adjustment; Searching Ways
1. Introduction
To effectively manage the traveling route problem, many
researchers have devoted themselves to this area. How to
establish a reasonable traveling route has caused hot dis-
cussion. Travelers are willing to expect a high quality
and reasonable price traveling experience, that is to say,
they want to visit attractions as much as possible in a
limited time. Only in this way can they obtain the satis-
faction of traveling. As a result, for the travelers, one of
the most important factors they value is the route de-
signed fo r them.
Traveling route setting is a optimization problem. Many
researchers at home and abroad have studied this issue.
Overseas researcher Cooper and others have discussed
the traveling route problems [1-3], while domestic re-
searcher Dongyun Fang has a wide range of study about
the nearest insertion method to search for the nearest
traveling lines based on graph theory [4]. And Linzhi Liu
has designed different traveling routes for different trav-
elers’ demands [5].
This paper mainly concentrates on the personal travel-
ing, especially for the large amount of attractions condi-
tion. The optimization objective for it is to make travel-
ing time shorter. Our essay sets an objective optimization
model based on the improved Ant Colony Algorithm.
Above all, the algorithm has been proved to be effective
and reasonable.
2. Problem Description
Traveling routes setting contributes to the travelers’ sa-
tisfaction. When people choose the attractions, there is a
strong desire to establish a good route. Besides, the route
arrangeme nt s hould s a tisfy travelers’ demands. Within this
limit, the route setting deserves better optimization.
For this problem, we need to make the following as-
sumptions:
• The time of traveling every day is limited. When
time out, travelers should come back to the hotel to end
that day’s trip.
• When setting the route, we only take the visiting
time into account except the time of having meals and
resting.
• The speed of the cars is fixed, so that we can count
the time of transfer to another spot.
• The distance between the various attractions is cal-
culated by latitude and longitude.
3. Model Building
3.1. The Transfer Time Among Attractions
Suppose the earth radius is R and the center of earth is O.
Thus, the distance between two points
12
(, )A αα
and
12
(, )B ββ
is.
1 212
12
( ,)arccos[coscoscos()
sinsin] 180
d ABR
β βαα
π
ββ
=×−
+×
(1)

Z. C. YU ET AL.
607
And v stands for the speed of transfer. Then the trans-
fer time
AB
T
among attractions can be counted by:
( ,)/
AB
Td ABv=
(2)
3.2. Optimization Objective
1) The first goal: traveling days
Traveling days are relatively large unit of time in con-
sideration, which is the most direct measure of the route
arrangement. Not only related to the time of trans-fer
among attractions, but also it is connected to the order of
visiting. Differen t attractions have differ ent visiting time,
thus reasonable arrangement will make the days shorter
and better.
Travel order to set the dwell time for each attraction,
different specified time with the number of days, rea-
sonable attractions with the number of travel days w ill be
optimized.
2) The second goal: time spent on roads
This time stands for the one spent on roads, that is to
say the transfer time among attractions. When the travel-
ing days are the same, the less time spent on roads the
better results it obtains.
3) Model of traveling routes Setting
max
min
s.t. ,
,
.
cp
zT
yt
TT
tab
mm
=
=
≤
+≤
≤
(3)
Suppose the limited time of traveling days is
max
T
.
While
a
stands for the visiting time of attraction,
b
shows the limited time of traveling every day. The jour-
ney cost is
c
m
, and the money expected is
p
m
.
4. Design for Improved Ant Colony
Algorithm
4.1. Design for the Max-Min Ant Colony
Algorithm
As the basic Ant Colony Algorithm for the shortest path,
the search often falls into local optimal solution, that is to
say after searching for a long time, the solutions found by
all individuals are exactly the same. Thus the process
will break off, which lead to the consequence that it may
not be able to find the global optimal solution. So we
take the Max-Min Ant Colony Algorithm into considera-
tion. This algorithm owns the maximum and minimum
values of the pheromone concentration in case of the big
gap between the relative concentration resulting in the
early ending of searching. Besides, the Max-Min Ant Co-
lony Algorithm has been proved by Stutzle for the best
effect [6].
Referring to the studies of Dorigo [7-14], the parame-
ter adjustment can be summarized as follows: The phe-
romone concentration
min max
/4n ττ =
, the number of
ants
m
is twice as the number of attractions. And the
pheromone residues
ρ
are 0.7. Besides, the importance
of pheromone
α
and the inspired factor
β
change
within the whole iteration process. The degree of phero-
mone is bigger in the later period, while the inspired fac-
tor in the former period.
4.2. The Adjustment of Inspired Factor
Basic Ant Colony Algorithm inspired factor is set as
1/
ij
d
. And
ij
d
stands for the transfer time between the
two attractions
i
and
j
. In this way, however, the dis-
tance between the hotel and attractions is not taken into
account. In fact, the distance is too important to ignore.
Besides, regarding the traveling route setting problem as
a TSP simply is unable to find the shortest time arranged
attractions combination. So we consider making the in-
spired factor in the Ant Colony Algorithm adjusted by
the method of dynamic distance. The calculating of in-
spired factor is divided into two conditions:
11
ac
ac ac
ac ac
if Qtb
ddd
else dd
+>
= +
=
(4)
Suppose
a
Q
is the cumulative time between the hotel
and the attraction
a
and
c
t
stands for the visiting time
of attraction
c
. The inspired factor of attraction
a
and
c
can be counted by the Equation (4).
Summarized by the testing process, the adjustment of
desired factor makes great contribution to the optimiza-
tion. But there are still some problems like unreasonable
routes establish ed. This situation can be explained as fol-
lows.
The dashed line indicates the general algorithm route:
from A to O and then from O to B and C till back to O.
And the solid line shows the improved algorithm route:
from A to C and O, and then from O to B and O. It has
been four hours when reaching point A, which means
that there are only two points left. For sake of the time
limit, the improved algorithm will let C in, but the dis-
tance on roads will increase. Besides, the two choices are
same in total days.
Therefore, in such conditions, it is useless to take the
improved algorithm. Maybe the optimal solution will be
ignored.
4.3. The Adjustment of Searching Ways
According to the defects of inspired factor’s adjustment,
we can classify the searching ants into two parts. One
group searches the solution by general algorithm, and the
other by improved algorithm. Thus, we can compare the

Z. C. YU ET AL.
608
former one with the latter one in order to find a better
one. Also, we can avoid choosi ng a long route.
For example, as to the case of Figure 1, the route tak-
en by the above searching ways is adjusted to the former
one instead of the latter choice. Only in this way can we
avoid the loss of optimal solution.
4.4. Steps for Solving Model
 Step 1: Assuming the setting problem as a TSP
problem, this aims at visiting all the attractions from
hotel and back to hotel in the end.
 Step 2: Turn into the Ant Colony Algorithm, setting
the inspired factor as the reciprocal of the transfer
time, thus getting a route according to the probability.
 Step 3: Single-day TSP route is divided into a mul-
ti-day trip. When the day’s total travel hours reach the
maximum time, return to the hotel. Calculate the num-
ber of days and the time spent on roads.
 Step 4: After searching for each route, choose the
best route according to the constraint condition. Then
repeat step 2.
 Step 5: After getting the best route, optimize the
single day’s arrangement again.
5. Simulation
5.1. The Simulation of the Algorithm
The data for simulation of the improved Ant Colony Al-
gorithm come from the capital city in China, Beijing.
And 100 attractions are chosen, which possess the coor-
dinate, cost and visiting time shown in F igure 2.
Figure 1. Route explanation.
Figure 2. Attractions chosen in Beijing.
After more than 100 testing times, it is found that the
improved Max-Min Ant Colony Algorithm roles effec-
tively. And the parameters are set as follows:
Within the process of 300 iteration, the former 200
iteration owns , wh ile the latter 100 owns
. And the phero mone resi dues are 0.3.
Take a number of different attractions as examples to
test the algorithm. Such conditions are tested 100 times.
Simulate every case and get the number of attractions
(NA), the optimization rate (OR), the average reduction
of the number of days and the rate (AD), and the maxi-
mum reduction of the number of days and the rate (MD) .
Table 1 shows the details. Besides, the benefit can be
shown in Figure 3 more directly.
It can be observed that the improved Ant Colony Al-
gorithm can greatly redu ce the number of days of the trip,
which contribute to the cost reducing. So, the improved
algorithm has good features to solve such problems.
5.2. The Simulation of the Real Example
The data for this par t come from a travel agency. It shows
a traveling route in Beijing for 6 days, which includes 20
attractions shown in Table 2.
Solve the case using MATLAB, based on the im-
proved algorithm. And assuming that tourists only have 8
hours to visit attractio n each day, we can get the route as
follows:
 Day 1: Hotel > Temple of Heaven > Tiananmen
Square > Nanluoguxiang>National Art Museum of
China > Hotel
 Day 2: Hotel > Winter Palace > Summer Palace >
China Millennium Monument > Military Museum >
Hotel
 Day 3: Hotel > Great Hall of the People > National
Grand Theatre > Forbidden City > Wangfujing > Mo-
nument to the People’s Heroes>Chairman Mao Me-
morial Hall > Hotel
Table 1. Indexes of all attractions.
NA OR AD MD
10 37% 1(18.8%) 1(25%)
14 43% 1.1(14.9%) 2(25%)
18 55% 1.1(12.2%) 2(22.2%)
22 70% 1.2(10.7%) 3(23.1%)
26 75% 1.2(9.2%) 3(18.8%)
30 89% 1.4(9.1%) 3(20.0%)
34 94% 1.7(9.8%) 4(19.1%)
38 96% 1.7(9.2%) 4(21.0%)
42 99% 2.0(9.7%) 4(18.1%)
46 100% 2.1(9.2%) 4(16.7%)
50 100% 2.3(9.4%) 4(15.4%)
0.5, 2 αβ
= =
2,0.5 αβ = =
ρ

Z. C. YU ET AL.
609
Table 2. Attractions information (unit: hour).
Attractions T i me Attractions Time
Temple of Heaven 2 Forbidden City 2.5
Tiananmen Square 1 Wangfujing 2
Nanluoguxiang 1 Xidan 4
Natio na l Ar t M u seum of China 2 Chairman Mao Memorial Hall 1
Winter Palace 2 .5 Jingsha n Park 0.5
Summer Palace 2.5 National Stadium 0.5
China Millennium Monum ent 1 National Aquatics Center 0.5
Military Museum 1 The Great Wall 4
Great Hall of the People 0.5 Monument to the People’s Heroes 0.5
National Grand Theater 1 Grand View Garden 2.5
Figure 3.
 Day 4: Hotel > Jingshan Park- > N ational Stadium >
National Aquatics Center > The Great Wall > Hotel
 Day 5: Hotel > Xidan > Grand View Garden > Ho-
tel
Compared with the route provided by the travel agen-
cy, the result not only reduces the number of days, but
also makes the route more reasonable. Tourists will enjoy
themselves in Beijing within the 5 days. And the detailed
route pictures are shown in Figure 3.
6. Conclusion
The essay shows how to obtain a reasonable traveling
route among given attractions. We set an objective opti-
mization model, using the improved Ant Colony Algo-
rithm to simulate as well. The models are simple and can
be extended. Even when the number of attractions is
huge, the algorithm can still get a good solution in a short
time. If other detailed information about attractions can

Z. C. YU ET AL.
610
be added into the model, the result may be more useful.
This is a new researching direction.
7. Acknowledgments
We would like to thank Professor Suohai Fan for many
comments and suggestions. We also appreciate the im-
portant device support and suggestions from the Depart-
ment of Mathematics at Jinan University. The work is
supported by the National College Students’ Innovative
Entrepreneurial Training Programs (No. 1210559085) in
Jinan University.
REFERENCES
[1] C. Cooper, J. Fletcher, D. Gilbert and S. Wanhil, “Tour-
ism Principles and Practice,” Longman, New York, 1998.
[2] C. A. Gunn and T. Var, “Tourism Planning: Basics Con-
cepts Cases,” Routledge, New York, 2002.
[3] A M. Mill, “The Tourism System,” Prentice-Hall, En-
glewood Cliffs, 1985.
[4] D. Y. Fang, “The Application of Graph Theory in the
Selection of Tourist Routes,” Changchun University of
Technology, 2009, pp. 582-586.
[5] Z. L. Liu, C. Li and L. Wang, “Design and Evaluation
Level Analysis and Graph Theory Model-Based Tours,”
Managers, No. 15, 2009, pp. 386-387.
[6] T. Stutzle and H. Hoos, “Max-Min Ant System and Local
Search for the Travelling Salesman Problem,” IEEE In-
ternational Conference on Evolutionary Computation and
Evolutionary Programming Conference, 1997, pp. 309-
314.
[7] T. Stuezle and M. Dorigo, “A Short Convergence Proof
for a Class of Ant Colony Optimization Algorithms,”
IEEE Transactions on Evolutionary Computation, Vol. 6,
No. 4, 2002, pp. 358-365.
http://dx.doi.org/10.1109/TEVC.2002.802444
[8] M. Dorigo and L. M. Gambardella, “Ant Colonies for the
Travelling Salesman Problem,” BioSystems, Vol. 43, No.
2, 1997, pp. 73-81.
http://dx.doi.org/10.1016/S0303-2647(97)01708-5
[9] M. Dorigo and T. Stutzle, “Ant colony opitimization,”
MIT Press, Cambridge, 2004.
[10] W. J. Gutjahr, “A Graph-Based Ant System and Its Con-
vergence,” Future Generation Computer System, Vol. 16,
No. 8, 2000, pp. 873-888.
http://dx.doi.org/10.1016/S0167-739X(00)00044-3
[11] K. Dai, S. W. Lu and X. G. Jiang, “Genetic Algorithm
Based Solution of Multiple Travelling Salesman Problem,”
Computer Engineering, Vol. 30, No. 16, 2004, pp. 139-
145.
[12] J. H. Yoo, R. J. La and A. M. Makowski, “Convergence
of Ant Routing Algorithms—Results for Simple Parallel
Network and Perspectives,” Technical Report CSHCN
2003-44, Institute for Systems Research, University of
Maryland, College Park (MD), 2003.
[13] Y. Zhang, “An Improved Ant Colony Optimization Algo-
rithm Based on Route Optimization and Its Applications
in Travelling Salesman Problem,” IEEE, BIBE, 2007.
[14] L.Y. Li and Y. Xiang, “Research of Multi-Path Touting
Protocol Based on Parallel Ant Colony Algorithm Opti-
mization in Mobile Ad Hoc Networds,” 5th International
Conference on Information Technology: New Genera-
tions, 2008.