Two phase heuristic algorithm for the multiple-travelling salesman problem

The salesman problem (TSP) is typically an NP problem Garey and Johnson (1979), whose objective is to determine the shortest path across a set of randomly located cities, each of them visited only once (with the exception of the starting point). From a graph theory perspective, the core task of TSP is to obtain a minimum Hamiltonian cycle. However, some real-world problems cannot be modelled via a traditional simple TSP with one single salesman, including personnel scheduling Masmoudi and Mellouli (2014), patrol planning Ghadiry et al. (2015), and goods distributing (Liu and Zhang 2014; An and Wei 2011). To address this issue, Multiple TSP (MTSP) has been specifically designed to consider a multiple-travelling salesman problem.

The aim of MTSP is to minimise the overall distance across n cities where m salesmen start and complete their journeys at the same city, and the other locations are visited only once. Clearly, TSP is a special case of MTSP for \(m=1\). Heuristic approaches can be utilised to solve MTSP Kiraly and Abonyi (2011), such as the ant colony optimisation algorithm (ACO) Singh and Mehta (2014), particle swarm optimisation algorithm (PSO) Yan et al. (2012), and the genetic algorithm (GA) Avin et al. (2012), to name but a few. However, there are a variety of aspects, which require further improvements. For example, ACO has a slow convergence speed, PSO tends to have local optimisation issues, and GA is prone to be trapped in the premature convergence and heavily depends on the initial population.

In this article, we propose a heuristic MTSP algorithm to obtain an optimised workload balance, whilst minimising the overall salesmen’s travelling distance. The main contributions of our method include:The rest of the paper is organised as follows: in Sect. 2, we discuss the current state-of-the-art methods and techniques in the field. Section 3 provides a detailed description of MTSP in detail and the mathematical model used in this context is introduced. Section 4 focuses on the properties of TPHA, and in Sect. 5 the evaluation results are discussed. Finally, Sect. 6 concludes the article by summarising its main contributions discussing future research directions.

There is extensive research on TSP, including TSP with time windows Falcon and Nayak (2010), TSP with minimum ratio (Ghadle and Muley 2014). Most of the existing solutions consider different constraints, whilst finding a minimum Hamiltonian cycle. Currently, the approaches to TSP are divided into exact and approximate algorithms. The former mainly includes dynamic programming Li (2013), branch and bound Mahfoudh et al. (2015), integer linear programming Pham and Huynh (2015), etc. However, if the scale of the TSP becomes too large, its overall computational time and solution space will increase exponentially.

Inspired by biological activities or natural phenomena, some well-known heuristic algorithms have been developed to solve large-scale TSPs, including ACO, PSO, and GA. There are significant research opportunities in the improvement in such heuristic algorithms and their combination. Pham and Huynh (2015) propose two new crossover operators to improve the global ergodic property of GA, which is a better solution for classical TSP, but not for complex TSP with multiple constraints. Ye et al. (2014) introduce an improved dynamic programming algorithm to deal with large-scale data, used as crossover and mutation operator in GA. Atif et al. (2012) integrate K-means algorithm Hu (2014) with the greedy algorithm and Lin Kernighan’s algorithm Helsgun (2014) to create an enhanced solution for large-scale TSP. However, this method is significantly affected by the scale of the subset partition.

A Multi-travelling salesman problem (MTSP) is characterised by more than one salesman and as a consequence, MTSP typically has a higher level of complexity compared to TSP. MTSP can be converted into TSP, and Gorenstein (1970) propose a basic strategy to achieve this, based on m salesmen, and \(m-1\) virtual cities. These are used to define a gap between different travelling salesmen, whilst the distance between the virtual cities is considered infinite. Yuan et al. (2013) discuss a new crossover operator called two-part chromosome crossover for the genetic algorithm in order to obtain near-optimal solutions of MTSP. However, this method is affected by the growth of the chromosome length and the overall cost of the solution. Kaliaperumal et al. (2015) present the Modified Two-Part Chromosome Crossover to address MTSP by employing a genetic algorithm for nearby optimal solutions. However, this method allocates a different number of the cities for each salesman, and therefore, it cannot successfully address MTSP with workload balance. Osaba et al. Hosseinabadi et al. (2014) propose the Real-World Dial-a-Ride problem, which is modelled as a MTSP. In particular, they propose GELS-GA, a new hybrid algorithm, which achieves optimal values even in highly complex scenarios. Finally, Alves and Lopes (2015) consider the workload balance of MTSP and develop GA to reduce both the overall distance and the difference between the distances travelled by each salesman.

Typically, MTSP only aims to obtain the least total cost of distance or time. For example, Fig. 1 depicts a scenario defined by 3 salesmen and 9 cities, where node 0 is the starting and ending point.

As shown in Fig. 1a, there are two salesmen traversing two cities, respectively, whereas all the other ones are traversed by the third salesman. It is clear that the salesmen’s workloads are unbalanced. As discussed above, the main objective of MTSP is to minimise the overall distance travelled by all salesmen, which may cause an unbalanced workload problem. Figure 1b shows an ideal solution for MTSP with workload balance. In order to achieve a balanced allocation of workload, there are typically two different strategies. The first aims to balance the number of cities assigned to each salesman, whereas the second focuses on optimising the balance of the distances travelled by each salesman.

Formally speaking, MTSP with m salesmen and n cities is defined as a complete graphwhere \(V = \{v_{1}, \ldots , v_{n}\}\) represents cities with the starting location at vertex \(v_0\), and each edge \((v_{i},v_{j})\) is associated with a weight \(d_{ij}\) (\(d_{ij} >0\), \(d_{ii} = \infty , v_{i},v_{j} \in V\)), which represents the cost of the path (in terms of distance or time) between cities i and j. We define the maximum number of cities Q for each salesman to achieve workloads balance asAs a consequence, one of the objectives of MTSP is to determine m sequences of Hamiltonian cycles over G, with the least total cost so that each salesman visit one and only one city. The objective function of MTSP is thereforesubject to whereIn particular, Eq. 4 ensures that each city must be visited by one salesman exactly once. Equations 5 and 6 indicate that all the salesmen’s itineraries must begin and end at the same city. Finally, Eq. 7 ensures that the number of cities traversed by each salesman cannot exceed a specific value.

As discussed above, TPHA consists of a clustering algorithm, which aims to assign individual cities to m sets, and subsequently, a heuristic algorithm is implemented to plan a route for each city set. K-means is a very popular algorithm for partitioning a large dataset into multiple subsets, which is based on the Euclidean distance as the fitness function. This implies that the elements within a cluster are relatively concentrated and therefore meet the MTSP requirements. In this article, we combine K-means with the maximal capacity constraint to balance the number of cities belonging to the corresponding subsets. Despite a relatively large variety of clustering algorithms, which could be potentially applied in this context, K-means currently offers the most appropriate option. In fact, our proposed method focuses on city locations measured in terms of Euclidean distance, supporting our choice. In future research, we aim to comparatively assess the accuracy and feasibility of other clustering algorithms.

GA is renowned for its global search efficiency, and good scalability. In this work, we utilise the roulette wheel method and the elitist strategy as the selection operation of GA, where MOC is set to be the gene segment associated with the initial step. This operation can produce a new generation, even if the two parent chromosomes are identical. Furthermore, MOC can address the issue of local optima and premature convergence.

Tourism route planning is a well-known application of MTSP, where a tourist needs to traverse various scenic locations subject to minimising the travelled distance. Due to the constraint of a limited daily travel time, the number of locations need to be balanced. Suppose there are n scenic locations, therefore a tourist will spend m days visiting all of them. Another important requirement is minimising the time spent travelling between different locations. Furthermore, it is assumed that a tourist starts and completes his/her journey at the same hotel every day. In other words, we have the following constraints:As part of the evaluation process, sixteen scenic areas in Nanjing city (China) were selected as shown on the Baidu map in Fig. 6. The hotel accommodation was set as the Phoenix Universal Hotel. Table 2 shows a detailed description of the locations, and Fig. 7 shows their corresponding latitude and longitude coordinates.

Future research efforts will include the investigation of the time cost, the traffic and other constraints in order to model more complex and dynamic MTSP, whilst improving the performance and function of the route planning algorithm. Furthermore, we are aiming to consider different locations by analysing the corresponding datasets whenever available. This will be also facilitated by integrating text mining techniques to extract information from social media, blogs and general websites to validate the accuracy of the identified routes.