Research on Traveling Routes Problems Based on Improved Ant Colony Algorithm

doi:10.4236/cn.2013.53B2109

Paper Menu >>

Journal Menu >>

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

Email: [email protected]

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

(, )A

αα

and

(, )B

ββ

is.

1 212

( ,)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

among attractions can be counted by:

( ,)/

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. ,

tab

≤

+≤

≤

(3)

Suppose the limited time of traveling days is

max

While

stands for the visiting time of attraction,

shows the limited time of traveling every day. The jour-

ney cost is

, and the money expected is

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

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

. And

stands for the transfer time between the

two attractions

and

. 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:

ac ac

if Qtb

ddd

else dd

= +

(4)

Suppose

is the cumulative time between the hotel

and the attraction

and

stands for the visiting time

of attraction

. The inspired factor of attraction

and

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.