The travelling salesman problem (TSP) consists of a set of cities and the distance between each pair of cities. The goal is to determine the shortest path that makes exactly
In artificial intelligence, optimization, logistics, and other applications, combinatorial optimization is one of the most studied disciplines. A novel local search heuristic has been developed for solving Euclidean TSP based on nearest insertion into the convex hull construction heuristic
In the Euclidean TSP
Different modes of transportation between cities have different standpoints and journey times. Although research has been done for multiple conveyance TSP where two objectives are considered
In this paper, we have proposed a multiconveyance TSP with limited cost and time. The main contributions of the paper are:
For each pair of cities, multiple modes of transportation are available.
The travel cost and time for different modes of transportation between cities differ.
Simultaneously, the total travel cost and travel time for a complete tour are fixed.
The proposed research with multiple conveyance facilities along with a fixed total travel time and cost is a novelty of the proposed research. As far as we are aware, no researcher has combined these three factors into a single TSP model.
Another novelty of this research is that the authors have developed a modified version of ACO by adopting a new feature, namely "tuning solution".
The rest of this paper is organized as follows. We discussed the problem’s practical significance in subsection 1.2. In subsection 1.3, we define the suggested problem in detail. Section 2 describes the proposed problem’s algorithm. The findings of the experiments are presented in Section 3. Section 4 brings the paper to a close.
In a reallife scenario, the cost of travel varies depending on the time of day, weather, and traffic conditions. As a result, the cost of travel between two cities cannot be calculated in this situation. To handle the ambiguity in the cost and time estimation of TSP, the decision maker introduces tolerance. However, the cost of travelling from one node to another is determined by the mode of transportation used. It also fluctuates slightly based on the availability of the mode of transportation, the state of the road, and other factors, albeit its value usually falls within a range. Because these estimates are based on an expert’s opinion, they are less prone to inaccuracy. Furthermore, the problem should be treated in such a way that a salesman can visit multiple cities utilizing various modes of transportation.
In a classical twodimensional travelling salesman cities using minimum cost. Let c(i,j) be the cost for travelling fromith city to jth city. Total cost limit is Cost_{MAX} and time limit is Time_{. T}hen the problem can be mathematically formulated as:
where y_{ij}_{ } = 1 if the salesman travels from cityi to cityj, otherwise y_{ij}_{ } = 0 and; Cost_{MAX} and Time_{MAX} are the maximum cost limit and time limit of the tour, respectively. Let (x_{1}, x_{2}, ..., x_{N}, x_{1}) be a complete tour of a salesman, where
where co(i,j) and tm(i,j) are the travel cost and time, respectively, for travelling from the ith city to the jth city.
In a multiconveyance travelling salesman problem, a salesman must travel between N cities for the least amount of cost by taking any of the M available modes of transportation. In his/her trip, the salesman begins in one city, visits all of the cities exactly once using the best mode of transportation available in each city, and then returns to the starting city for the least amount of cost. Travelling from one city to another using various modes of transportation has varied costs and times. Let co(i, j, k) and tm(i, j, k) be the cost and time, respectively, it takes to travel from ith city to jth city using the kth type of conveyance. The salesperson must then determine a complete tour (x_{1}, x_{2}, ..., x_{N}, x_{1}) in which a specific or different combination of conveyance types (con_{1}, con_{2}, ..., con_{N}) is to be employed for the tour, where
where Cost_{MAX} and Time_{MAX} are the maximum travel cost and time limit of a complete tour, respectively, that should be maintained by the salesman.
In 1992, based on observations of ants’ foraging behaviour and their ability to locate the shortest path between their colony and food sources
1. Start
2. Initialize parameters
3. Initialize pheromone
4. For i = 1 to MaxIt (Maximum number of iterations)
5. For j = 1 to NOANT
6. Construct path for each ant
7. End for
8. Perform evaporation
9. Perform pheromone update for each ant’s path.
10. End for
11. Tuning solution
12. End
Because the goal of a TSP is to reduce costs, the initial value of r_{ij} = 1/C(i, j) is assumed for pair (i, j). Similarly for multiconveyance TSP, it is assumed as r_{ijk} = 1/C(i, j, k) using multiconveyance TSP for ith city to jth city using kth type of conveyance. C(i, j, k) is the cost of travelling from ith city to jth using kth type of conveyance.
p_{ijv = }
where
with
1. For k = 1 to Noant do
2. Calculate the objective value of kth ant, say BEFORETOBJ;
3. For l = 1 to N1 do
4. Swap the pair of elements PATH[k][l] and PATH[k][l+1]
5. Calculate the objective value after swapping, say TEMPOBJ
6. If (TEMPOBJ< BEFORETOBJ then
7. Replace the kth ant’s path by the path after swapping (PATH[k][l] and PATH[k][l+1]
8. End if
9. End for
10. Find objective value of PATH for kth ant, say KTOBJ
11. End For
(Here, Noant is the number of ant and N is the number of city)
The number of ants (Noant) and the maximum number of iteration is set by random experiment for different instances.
In this section, first of all we have considered some benchmark instances of TSPLIB and compared with that available in existing literature. In the next subsection, we have redefined a benchmark instance for the proposed problem and computed the results.
We used various benchmark asymmetric TSP situations reported by the existing literature













br17 
39 
Noants: 40 MaxIt: 500 
39 
39 
0 



ftv35 
1473 
Noants: 40 MaxIt: 1000 
1473 
1493.7 
8.0 



ftv38 
1530 
Noants: 40 MaxIt: 1000 
1530 
1562.0 
13.79 



ftv70 
1950 
Noants: 70 MaxIt: 1000 
2111 
2233.2 
48.8 



From
Now we have considered two instances in




ftv34 
500 
1358 
1332 
ry48p 
500 
15322 
15012 
From
Now we have redefined a few instances of TSPLIB. The proposed TSP has two parameters, namely, cost and time, respectively. A cost matrix is considered from TSPLIB and a time matrix is generated in the range




Redefined ftv33 
34 
Number of ants: 30 Maximum iterations: 1000 Cost limit:1330, Time limit:300 
Objective/cost: 1329.96 Time: 294.87 
Redefined ftv35 
36 
Number of ants: 30 Maximum iterations: 1000 Cost limit:1500, Time limit:330 
Objective/cost: 1454.53 Time: 321.84 
Redefined ftv70 
70 
Number of ants: 60 Maximum iterations: 1000 Cost limit:2100, Time limit:900 
Objective/cost: 2019.18 Time: 883.96 
Redefined ftv33 
(1; 1), (14; 1), (17; 1), (16; 1), (15; 1), (13; 1), (10; 1), (33; 1), (8; 1), ( 9; 1), (11; 1), (12; 1), (32; 1), (19; 1), (20; 1), (21; 1), (22; 1), (23; 1), (27; 1), (28; 1), (29; 1), (30; 3), (26; 1), (25; 1), (24; 2), (18; 2), ( 5; 1), (7; 1), ( 6; 1), (31; 3), (34; 1), (3; 1), ( 4; 1), ( 1; 1) 
Redefined ftv35 
(1; 1), (14; 1), (13; 1), (6; 1), ( 8; 1), ( 7; 1), ( 5; 1), (33; 1), (31; 1), (28; 1), (24; 1), (21; 1), (22; 1), (23; 1), (29; 1), (30; 1), (32; 1), (36; 1), (3; 1), ( 4; 1), ( 2; 1), (27; 1), (26; 1), (25; 3), (20; 1), (18; 1), (11; 1), (34; 1), (19; 1), (35; 1), (9; 1), (10; 1), (12; 1), (15; 1), (16; 1), (1; 1) 
From
Here, we have presented the results of a 6city multiconveyance where the input cost and time matrix for three types of conveyances are randomly generated and given in
i/j 
1 
2 
3 
4 
5 
6 
1 
8.34, 6.87, 6.15 
9.97, 9.65, 8.96 
8.30, 8.31, 9.37 
4.21, 9.36, 8.22 
9.21, 7.28, 7.86 
5.90, 4.21, 5.14 
2 
8.83, 9.34, 8.37 
4.50, 9.72, 8.54 
5.94, 7.22, 7.23 
8.22, 9.58, 9.86 
8.97, 8.66, 7.44 
7.93, 7.44, 4.19 
3 
5.15, 4.04, 6.02 
5.33, 7.53, 6.53 
7.93, 6.46, 6.15 
5.75, 9.02, 6.24 
8.40, 4.32, 9.99 
7.89, 6.90, 8.84 
4 
6.71, 7.60, 5.49 
9.93, 8.21, 5.17 
5.20, 6.75, 7.71 
6.83, 7.73, 7.23 
9.33, 4.94, 7.07 
9.25, 6.60, 9.21 
5 
8.19, 7.34, 6.86 
9.17, 8.13, 6.41 
6.56, 7.70, 8.54 
6.21, 8.15, 6.55 
8.52, 4.83, 6.54 
5.16, 5.17, 5.78 
6 
8.21, 5.90, 8.03 
8.99, 9.67, 5.88 
5.33, 4.77, 4.97 
5.52, 4.14, 4.92 
4.11, 8.72, 9.43 
6.00, 9.24, 6.23 
i/j 
1 
2 
3 
4 
5 
6 
1 
10.85, 8.86, 9.82 
8.74, 8.56, 9.42 
8.79, 9.90, 10.08 
10.24, 8.29, 8.33 
9.65, 10.03, 7.15 
10.37, 8.15, 7.42 
2 
8.48, 8.40, 7.02 
10.36, 10.86, 8.50 
7.47, 7.33, 10.72 
8.22, 9.69, 8.54 
7.39, 9.05, 10.94 
7.21, 8.40, 7.60 
3 
8.83, 8.15, 10.01 
10.78, 9.02, 7.12 
9.50, 9.15, 9.19 
7.08, 9.38, 7.08 
8.67, 10.75, 10.60 
8.68, 8.24, 9.47 
4 
9.08, 9.22, 10.19 
8.94, 7.37, 8.37 
9.32, 10.18, 10.19 
8.17, 7.15, 7.72 
7.81, 9.54, 8.09 
7.57, 10.38, 8.66 
5 
10.57, 8.56, 7.30 
10.16, 8.02, 8.69 
10.33, 10.73, 7.68 
9.22, 8.74, 9.20 
8.12, 10.98, 9.75 
8.66, 8.14, 7.42 
6 
10.14, 8.05, 8.25 
10.02, 8.28, 9.23 
9.14, 8.80, 7.69 
9.04, 9.98, 9.60 
10.83, 8.56, 7.81 
7.64, 10.33, 7.28 
Obtained tour 
(1; 1), (4; 3), (2; 3), (6; 1), (5; 1), (3; 1) 
Cost 
Time 
28.26 
41.95 
Each pair (x, y) in
In this paper, we have presented an ACObased approach to solve a multiconveyance TSP. This is a new version of TSP where there is a different conveyance facility to travel from city to city, and the total travel cost and time of tour are fixed. To the best of our knowledge, this is a new variant of TSP where time and cost limits are also fixed with different conveyance facilities. A novel ACObased approach has been used to solve the TSP. A new operation "tuning solution" has been adopted for ACO to recover better neighbour solutions of each path. This is a unique feature of the ACO, which is one of the contributions of this research. To check the efficiency of the proposed ACO, a set of benchmark instances from TSPLIB has been considered. The results of benchmark instances are able to show that the proposed ACO is an efficient algorithm for TSP.
Our future aim is to implement a multiobjective TSP. Next, our other future plan is to solve the probabilistic TSP. Further we want to solve a random fuzzy type2 TSP by a bee colony optimization algorithm. In the future, we also want to solve a multidepot multiconveyance TSP with a bat algorithm. Later on, we also want to focus on precedence constraints multipleconveyance TSP in a fuzzy random environment.