12.07.2017  Methodologies and Application  Ausgabe 19/2018 Open Access
Two phase heuristic algorithm for the multipletravelling salesman problem
 Zeitschrift:
 Soft Computing > Ausgabe 19/2018
1 Introduction
2 Related work
3 Modelling of the MTSP

i refers to a city (\(i =1,\ldots ,n\)), so that the starting location is 0;

t refers to a salesman (\(t=1,\ldots ,m\)), where m is the total number of salesmen;

\(d_{ij}\) represents the distance between the cities i and j;

Q is the maximum number of cities travelled by each salesman;

\(r_{ijt} \in \{0,1\}\), such that \(r_{ijt}=1\) if the salesman t travels directly from city i to city j, and \(r_{ijt}=0\), otherwise;

\(y_{ti}\in \{0,1\}\) and \(y_{ti}=1\) if the salesman t visited the city i, and \(y_{ti}=0\), otherwise.
4 Two phase heuristic algorithm for MTSP
4.1 City clustering based on improved Kmeans
4.2 Route planning based on GA
Parameters  Description 

G
 Total number of iterations 
\(P_{\mathrm{size}}\)
 Size of population 
\(p_{c}\)
 Crossover probability 
\(p_{m}\)
 Mutation probability 
K
 Number of iterations 
\(X^{k}\)
 All population of the kth generation 
\(X_{i}^{k}\)
 The ith individual in \(X^{k}\)

\(D_{i}^{k}\)
 The ith individual’s evaluation value in \(X^{k}\), \(D_{i}^{k}=D(X_{i}^{k})\)

\(F_{i}^{k}\)
 The ith individual’s evaluation value in \(X^{k}\), \(F_{i}^{k}=F(X_{i}^{k})\)

\([sub \, x_{1} \; sub \, x_{2}]=CS(x_{1}, x_{2})\)
 The new generation \(sub \, x_{1}\) and \(sub \, x_{2}\), which is obtained by the parents of \(x_{1}\) and \(x_{2}\) through the method of ameliorate order crossover 
U(0, 1)  Random function generating number subject to (0, 1) uniform distribution 
\(X_{\mathrm{best}}\)
 The current best individual 
\(D_{\mathrm{best}}\)
 The current best individual evaluation value 
4.3 Initial population encoding
4.4 Fitness function
4.5 Selection strategy
4.6 Crossover operation
4.7 Mutation operation
4.8 Detailed workflow
Serial number  Scenic locations  Abbreviation  Latitude and longitude coordinates 

1  Laoshan National Forest Park  LSFP  (118.600362, 32.102836) 
2  Zhenzhu Fountain  ZF  (118.665367, 32.128073) 
3  Yuejiang Tower  YJT  (118.753228, 32.099638) 
4  Youth Olympic Games  YOGP  (118.671459, 32.055351) 
Sports Park  
5  Swallow rocky Park  SRP  (118.823312, 32.153159) 
6  Mufu Mountain  MM  (118.784569, 32.121674) 
7  Nanjing Hongshan Forest Zoo  HSZ  (118.808457, 32.102101) 
8  The Shence Gate Park  SGP  (118.793415, 32.090744) 
9  Yuhuatai martyrs cemetery  YMC  (118.785541, 32.009374) 
10  Memorial Hall of the Victims in Nanjing Massacre by Japanese Invaders  MHVNM  (118.752705, 32.040775) 
11  Mochou Lake  MCL  (118.765195, 32.043606) 
12  Presidential Palace  PP  (118.803388, 32.049069) 
13  Nanjing Museum  NM  (118.831876, 32.045068) 
14  Sun Yatsen Mausoleum  SYM  (118.859411, 32.064341) 
15  Confucius Temple  CT  (118.795398, 32.026971) 
16  Nanjing Green Garden  NGG  (118.795398, 32.026971) 
5 Applications and experiments

The tourist will not change his/her hotel accommodation during his staying in a city.

Each location is visited once and only once.

The daily travel time is fixed, which limits the number of locations visited each day.

The tourist will return to his/her hotel every day.
5.1 Experiments
TSP instance  OHC  ACA  NNM  The improved GA  

Best  err  Best  err  Best  err  
Eil51  426  435  2.11  453  6.34  443  3.74 
Eil76  538  551  2.41  582  8.18  568  5.57 
Eill0l  629  682  8.42  715  13.6  693  9.65 
Berlin52  7542  7543  0.01  7976  5.57  7644  1.35 
5.2 Design of the prototype

Class MainActivity describes the completion of the Baidu electronic map loading, including the verification of API key, the detection of network states and the management of map life cycle.

Class TPHA invokes the class MKsearchListener, which obtains the location information, whilst GA carries out the path planning.

Class ItemizedOverlay invokes the class GpsActivity to obtain the current location, and marks it on the map.

Class RouteOverlay is used to identify the route

GraphicsOverlay is utilised to show the path information on the Baidu electronic map.

Finally, getDistance() is used to obtain the associated cost.
Algorithm  Time (s)  Distance 

TPHA  2.442360  0.9941 
GA  10.698919  1.1648 
Route  Scenic spots  Distance (km) 

With TPHA  
Day 1  Starting point, NGG, YOGP, LSFP, ZF  58.4 
Day 2  Starting point, PP, NM, SYM, SGP  30.2 
Day 3  Starting point, HSZ, SRP, MM, YJT  27.4 
Day 4  Starting point, CT, YMC, MHVNM, MCL  34.7 
WithGA  
Day 1  Starting point, SGP, ZF, LSFP, YOGP  60.3 
Day 2  Starting point, SYM, NM, CT, YMC  42.2 
Day 3  Starting point, HSZ, SRP, MM, YJT  27.4 
Day 4  Starting point, PP, MCL, MHVNM, NGG  29.5 