Multi-Strategy MAX-MIN Ant System for Solving Quota Traveling Salesman Problem with Passengers, Incomplete Ride and Collection Time

Abstract

This study proposes a novel adaptation of MAX-MIN Ant System algorithm for the Quota Traveling Salesman Problem with Passengers, Incomplete Ride, and Collection Time. There are different types of decisions to solve this problem: satisfaction of the minimum quota, acceptance of ride requests, and minimization of travel costs under the viewpoint of the salesman. The Algorithmic components proposed regards vehicle capacity, travel time, passenger limitations, and a penalty for delivering a passenger deliverance out of the required destination. The ant-based algorithm incorporates different sources of heuristic information for the ants and memory-based principles. Computational results are reported, showing the effectiveness of this ant-based algorithm.

1. Introduction

The lives of ordinary consumers have changed almost beyond recognition in the past 20 years. First, with the introduction of high-speed internet access; but, more recently, with the arrival of mobile computing devices such as smartphones and tablets. According to data from the 2017 Gallup World Survey [1], 93 of adults in high-income economies have their cell phones, while 79$\%$ in developing economies. In India, 69$\%$ of adults have a cell phone, as well as 85$\%$ in Brazil and 93$\%$ in China [1]. Smartphones and the internet have created a novel digital ecosystem where the adoption of new paradigms is increasingly fast, and each innovation that appears and presents itself to the market can disrupt an entire segment.

In the transportation segment, a central theme is how the digital revolution has created opportunities to consider new models of delivering services under the paradigm of Mobility as a Service (MaaS) [2]. There is a growing interes$\%$t in MaaS due to the notion of a sharing economy. Millennials own fewer vehicles than previous generations [3]. As evidenced by the ascension of on-demand mobility platforms, they are quickly adopting car sharing as a mainstream transportation solution. Investments in new travel patterns have become a priority to enable the transformation of opportunities in the urban mobility segment into new revenue streams.

This study deals with a novel optimization model that can improve the services provided by on-demand mobility platforms, called Quota Traveling Salesman Problem with Passengers, Incomplete Ride, and Collection Time (QTSP-PIC). In this problem, the salesman is the vehicle driver and can reduce travel costs by sharing expenses with passengers. He must respect the budget limitations and the maximum travel time of every passenger. Each passenger can be transported directly to the desired destination or an alternate destination. Lira et al. [4] suggest pro-environmental or money-saving concerns can induce users of a ride-sharing service to agree to fulfill their needs at an alternate destination.

The QTSP-PIC can model a wide variety of real-world applications. Cases related to sales and tourism are the most pertinent ones. The salesman must choose which cities to visit to reach a minimum sales quota, and the order to visit them to fulfill travel requests. In the tourism case, the salesman is a tourist that chooses the best tourist attractions to visit during a vacation trip and can use a ride-sharing system to reduce travel expenses. In both cases, the driver negotiates discounts with passengers transported to a destination similar to the desired one.

The QTSP-PIC was introduced by Silva et al. [5]. They presented a mathematical formulation and heuristics based on Ant Colony Optimization (ACO) [6]. To support the ant algorithms, they proposed a Ride-Matching Heuristic (RMH) and a local search with multiple neighborhood operators, called Multi-neighborhood Local Search (MnLS). They tested the performances of the ant algorithms on 144 instances up to 500 vertices. One of these algorithms, the Multi-Strategy Ant Colony System (MS-ACS), provided the best results. They concluded that their most promising algorithm could improve with learning techniques to choose the source of information regarding the instance type and the search space.

In this study, a MAX-MIN Ant System (MMAS) adaptation to the QTSP-PIC, called Multi-Strategy MAX-MIN Ant System (MS-MMAS), is discussed. MMAS improves the design of Ant System [6], the first ACO algorithm, with three important aspects: only the best ants are allowed to add pheromone during the pheromone trail update; use of a mechanism for limiting the strengths of the pheromone trails; and, incorporation of local search algorithms to improve the best solutions. Plenty of recent studies proved good effectiveness of the MMAS in correlated problems to QTSP-PIC [7, 8, 9, 10]. However, none of these explored the Multi-Strategy (MS) concept.

In the traditional ant algorithms applied to Traveling Salesman Problem (TSP), ants use the arcs’ cost as heuristic information [6]. The heuristic information adopted is called visibility. When solving the QTSP-PIC, different types of decisions must be considered: the accomplishment of the minimum quota, management of the ride requests, and minimization of travel costs. The MS idea is to use different mechanisms of visibility for the ants to improve diversification. Every ant decides which strategy to use at random with uniform distribution. The MS proposed in this study extends the original implementation proposed in [5]. MS-MMAS also incorporates RMH and MnLS and uses a memory-based technique proposed in [11] to avoid redundant work. In MS-MMAS, a hash table stores every solution constructed and used as initial solutions to a local algorithm. When the algorithm constructs a new solution, it starts the local search phase if the new solution is not in the hash table.

The benchmark for the tests consisted of 144 QTSP-PIC instances. It was proposed by Silva et al. [5]. Numerical results confirmed the effectiveness of the MS-MMAS by comparing it to other ACO variants proposed in [5].

The main contributions of this chapter are summarized in the following.

• The extension of the MS concept proposed in [5] with a roulette mechanism that orients the ants to choose their heuristic information based on the best quality solutions achieved;

• Improvement of the MMAS design with a memory based technique proposed in [11];

• Presentation of a novel MMAS variant that combines the improved MS concept and memory-based principles and assessment of its performance;

• Experiments on a set of QTSP-PIC instances ranging: 10 to 500 cities; and 30 to 10.000 travel requests. The results showed that the proposed MMAS variant is competitive regarding the other three ACO variants presented in [5] for the QTSP-PIC.

The remainder of this chapter is organized as follows. Section 2 presents the QTSP-PIC and its formulation. Section 3 presents the Ant Colony Optimization metaheuristic and the implementation design of the MS-MMAS. Section 4 presents experimental results. The performance of the proposed ant-based algorithm is discussed in Section 5. Conclusions and future research directions are outlined in Section 6.

2. Problem definition

The TSP can be formulated as a complete weighted directed graph $G=\left(N,A\right)$ where $N$ is the set of vertices and $A=\left\{\left(i,j\right)|i,j\in N\right\}$ is the set of arcs. $C=\left[c_{\mathit{ij}}\right]$ is the arc-weight matrix such that $c_{\mathit{ij}}$ is the cost of arc $\left(i,j\right)$. The objective is to determine the shortest Hamiltonian cycle in $G$. Due to its applicability, many TSP variants deal with specific constraints [12]. Awerbuch et al. [13] presented several quota-driven variants. One of them, called Quota Traveling Salesman Problem (QTSP), is the basis for the problem investigated in this study. In the QTSP, there is a bonus associated with each vertex of $G$. The salesman has to collect a minimum quota of bonuses in the visited vertices. Thus the salesman needs to figure out which cities to visit to achieve the minimum quota. The goal is to find a minimum cost tour such that the sum of the bonuses collected in the visited vertices is at least the minimum quota.

The QTSP-PIC is a QTSP variant in which the salesman is the driver of a vehicle and can reduce travel costs by sharing expenses with passengers. There is a travel request, associated with each person demanding a ride, consisting of a pickup and a drop off point, a budget limit, a limit for the travel duration, and penalties associated with alternative drop-off points. There is a penalty associated with each point different from the destination demanded by each person. The salesman can accept or decline travel requests. This model combines elements of ride-sharing systems [14] with alternative destinations [4], and the selective pickup and delivery problem [15].

Let $G\left(N,A\right)$ be a connected graph, where $N$ is the set of vertices and $A=\left\{\left(i,j\right)|i,j\in N\right\}$ is the set of arcs. Parameter $q_i$ denotes the quota associated with vertex $i\in N$ and $g_i$ the time required to collect the quota. $c_{\mathit{ij}}$ and $t_{\mathit{ij}}$ denote, respectively, the cost and time required to traverse edge $\left(i,j\right)\in A$. Let $L$ be the set of passengers. List $l_i\subseteq L$ denotes the subset of passengers who depart from $i\in N$. Let $\mathit{org}\left(l\right)$ and $\mathit{dst}\left(l\right)\in N$ be the pickup and drop-off points requested by passenger $l$. The salesman departs from city $s=1$, visits exactly once each city of subset $N^{\prime }\subseteq N$ and returns to $s$. The quota collected by the salesman must be at least $K$ units. Along the trip, the salesman may choose which travel requests to fulfill. The travel costs are shared with vehicle occupants. The number of vehicle occupants, or passengers, cannot exceed $R$. Each passenger $l\in L$ imposes a budget limit $w_l$ and a trip’s maximum duration $b_l$. Let $h_{\mathit{lj}}$ be the penalty to deliver passenger $l\in L$ at city $j\in N$, $j\ne \mathit{dst}\left(l\right)$. The value of variable $h_{\mathit{lj}}$ is computed in the final cost of the tour if passenger $l$ is delivered to city $j$. If $j=\mathit{dst}\left(l\right)$, then $h_{\mathit{lj}}=0$. The objective of the QTSP-PIC is to find a Hamiltonian cycle $\mathrm{\Psi }=\left(N^{\prime },A^{\prime }\right)$ such that the ride-sharing cost and eventual penalties are minimized, and the quota constraint is satisfied.

The QTSP is NP-hard [13]. It is a particular case of the QTSP-PIC, in which the list of persons demanding a ride is empty and the time spent to collect the bonus in each vertex is zero. Thus, QTSP-PIC also belongs to the NP-hard class.

Silva et al. [5] presented an integer non-linear programming model for the QTSP-PIC. They defined a solution as $S=\left(N^{\prime },Q^{\prime },L^{\prime },H^{\prime }\right)$, where $N^{\prime }$ is a list of vertices that represents a cycle, $\mathrm{\Psi }$, such that the minimum quota restriction, $K$, is satisfied; $Q^{\prime }$ is a binary list in which the $i$-th element is 1 if the salesman collects the bonus from city $i$, $i\in N^{\prime }$; $L^{\prime }$ is a binary list in which the $l$-th element is 1 if the salesman accepts the $l$-th travel request; and $H^{\prime }$ is a list of integers in which the $l$-th element is the index of the city where the $l$-th passenger leaves the car. If $L^{\prime }\left[l\right]=0$, then $H^{\prime }\left[l\right]=0$. The cost of solution $S$, denoted by $S.\mathit{\text{cost}}$, is calculated by Eq. (1).

$$S.\mathit{\text{cost}}=\sum _{i,j\in N^{\text{'}}}\frac{c_{\mathit{ij}}}{1+{\sum }_{l\in L^{\text{'}}}{v}_{\mathit{ij}}^l}+\sum _{l\in L^{\text{'}}}{h}_{{\mathit{lH}}_l^{\text{'}}}$$E1

3. Ant Colony Optimization

In the Ant Colony Optimization, artificial ants build and share information about the quality of solutions achieved with a communication scheme similar to what occurs with some real ants species. Deneubourg et al. [16] investigated the behavior of Argentine ants and performed some experiments, where there were two bridges between the nest and a food source. He observed that the ants initially walked on the two bridges at random, depositing pheromone in the paths. Over time, due to random fluctuations, the pheromone concentration of one bridge was higher than the other. Thus, more ants were attracted to that route. Finally, the whole colony ended up converging towards the same route. The behavior of artificial ants preserves four notions of the natural behavior of ants:

• Pheromone deposit on the traveled trail;

• Predilection for trails with pheromone concentration;

• Concentration of the amount of pheromone in shorter trails;

• Communication between ants through the pheromone deposit.

Pheromone is a chemical structure of communication [17]. According to Dorigo et al. [18], pheromone enables the process of stigmergy and self-organization in which simple agents perform complex and objective-oriented behaviors. Stigmergy is a particular form of indirect communication used by social insects to coordinate their activities [18].

Considering the context of ant algorithms applied to the TSP, when moving through the graph $G$, artificial ants tend to follow paths with higher pheromone deposits rates. As ants tend to deposit pheromone along the path they follow, as more ants choose the same path, the pheromone rate tends to increase in these paths. This cooperation mechanism induces artificial ants to find good solutions, as it works as a shared memory that is continuously updated and can be consulted by every ant in the colony [19].

The base-line of the Ant Colony Optimization is the algorithm Ant System [6]. In the TSP application, $N$ is the set of vertices to visit. Ants construct solutions iteratively. Every iteration, the ant chooses the next vertex based on heuristic information, $\eta$, and pheromone trails, $\tau$. Initially, pheromone trails have the same amount of pheromone, ${\tau }_0$, computed by Eq. (2), where $n$ is the number of vertices in $N$ and $\mathit{\text{Cost}}\left(D\right)$ is the value of the TSP tour built by a greedy heuristic.

$${\tau }_{\mathit{ij}}^0={\left(n\times \mathit{\text{Cost}}\left(D\right)\right)}^{-1}$$E2

The $k$-th ant iteratively adds new vertices to the solution. The algorithm uses Eq. (3) to compute the probability of the $k$-th ant to move from vertex $i$ to $j$ at the $t$-th iteration, where ${\eta }_{\mathit{ij}}=\frac{1}{c_{\mathit{ij}}}$ is the heuristic factor, ${\tau }_{\mathit{ij}}\left(t\right)$ is the pheromone in arc $\left(i,j\right)$ in the $t$-th iteration, and ${\mathrm{\Lambda }}^k$ is the list of vertices not visited by the $k$-th ant. Coefficients $\alpha$ and $\beta$ weight the influence of the pheromone and heuristic information, respectively. They are user-defined parameters. If $\alpha =0$, the probability computed by Eq. (3) depends only on the heuristic information. So, the ant algorithm behaves like a greedy method. If $\beta =0$, ants tend to select paths with higher pheromone levels. It may lead the algorithm to early stagnation. So, balancing the values of $\alpha$ and $\beta$ is critical to guarantee a suitable search strategy [5].

$${\mathrm{\Upsilon }}_{\mathit{ij}}^k\left(t\right)=\frac{{\left[{\tau }_{\mathit{ij}}\left(t\right)\right]}^{\alpha }\cdot {\left[{\eta }_{\mathit{ij}}\right]}^{\beta }}{{\sum }_{w\in {\mathrm{\Lambda }}^k}\left[{\left[{\tau }_{\mathit{iw}}\left(t\right)\right]}^{\alpha }\cdot {\left[{\eta }_{\mathit{iw}}\right]}^{\beta }\right]},j\in {\mathrm{\Lambda }}^k$$E3

Eqs. (4) and (5) show the formulas used to update pheromone trails, where $\rho$ is the evaporation coefficient, $\mathit{\text{Cost}}\left(W^k\right)$ is the cost of the route $W^k$ built by the $k$-th ant, and $\mathrm{\Delta }{\tau }_{\mathit{ij}}^k$ is the pheromone deposited on arc $\left(i,j\right)$ by the $k$-th ant, computed by expression (6).

$${\tau }_{\mathit{ij}}=\left(1-\rho \right)\times {\tau }_{\mathit{ij}}+\rho \times \mathrm{\Delta }{\tau }_{\mathit{ij}},\rho \in \left[0,1\right]$$E4

$$\mathrm{\Delta }{\tau }_{\mathit{ij}}=\sum _{k=1}^m\mathrm{\Delta }{\tau }_{\mathit{ij}}^k$$E5

$$\mathrm{\Delta }{\tau }_{\mathit{ij}}=\left\{\begin{array}{cc}\frac{1}{\mathit{\text{Cost}}\left(W^k\right)},& \text{if}\mathrm{arc}\left(i,j\right)\in W^k.\\ 0,& \text{otherwise}.\end{array}\right.$$E6

The ant algorithms proposed after AS improved its implementation design with elitist pheromone update strategies and local search algorithms to improve solutions [6]. Two well-known variants of AS are the Ant Colony System (ACS) [20] and MAX-MIN Ant System [21]. Silva et al. [5] presented AS and ACS adaptations for the QTSP-PIC. Section 3.1 presents the MAX-MIN Ant System algorithm.

3.1 Multi-strategy MAX-MIN ant system

MMAS uses Eq. (3) to compute the probability of an ant to move from vertex $i$ to $j$. Besides, it incorporates improvements to avoid search stagnation and a pheromone update rule that limits pheromone concentration rates. Eq. (7) presents the pheromone update rule. Limits ${\tau }_{\mathit{max}}$ and ${\tau }_{\mathit{min}}$ prevent stagnation of pheromone values.

$${\tau }_{\mathit{ij}}=\mathit{max}\left\{{\tau }_{\mathit{min}},\mathit{min}\left\{{\tau }_{\mathit{max}},\left(1-\rho \right)\times {\tau }_{\mathit{ij}}+\rho \times \mathrm{\Delta }{\tau }_{\mathit{ij}}^{\mathit{\text{best}}}\right\}\right\},\rho \in \left[0,1\right]$$E7

$$\mathrm{\Delta }{\tau }_{\mathit{ij}}^{\mathit{\text{best}}}=\left\{\begin{array}{cc}\frac{1}{\mathit{\text{Cost}}\left(W^{\mathit{\text{best}}}\right)},& \text{if}\mathrm{arc}\left(i,j\right)\in W^{\mathit{\text{best}}}.\\ 0,& \text{otherwise}.\end{array}\right.$$E8

There are three possibilities for the best route ($W^{\mathit{\text{best}}}$) considered in the algorithm: the best route in the current iteration, the best route found so far, and the best route since the last time pheromone trails were reinitiated. In the MMAS original design [21], these routes were chosen alternately. The initial value of pheromone trails was $t_{\mathit{max}}$. If the algorithm reached stagnation, i.e., the best current route remained the same for several iterations, the pheromone value reinitialized to $t_{\mathit{max}}$. Assigning $t_{\mathit{max}}$ to pheromone trails produces a small variability among pheromone levels at the start of the search [21].

The implementation of the MMAS for the QTSP-PIC extends the original proposal [21] with the following adaptions:

• Ants start at vertex $s$;

• Ants include vertices in the route up to reach the minimum quota;

• Solution $S^k$, built by the $k$-th ant, is computed by assigning passengers to route $W^k$ with the $\mathit{RMH}$ algorithm [5];

• Use of the MS concept.

The ants in the MMAS, use arc costs to compute heuristic information. In the MS-MMAS, ants use four sources for this task, listed in the following.

• Cost oriented: uses $c_{\mathit{ij}}$ as heuristic information, such that ${\eta }_{\mathit{ij}}=\frac{1}{c_{\mathit{ij}}}$;

• Time oriented: uses $t_{\mathit{ij}}$ as heuristic information, such that ${\eta }_{\mathit{ij}}=\frac{1}{t_{\mathit{ij}}}$. This heuristic information guides ants to vertices that lead to travel time savings.

• Quota oriented: $q_j$ is used as heuristic information, ${\eta }_{\mathit{ij}}=\frac{q_j}{c_{\mathit{ij}}}$. This heuristic information guides ants to go to vertices that lead to the maximization of the quota collected.

• Passenger oriented: the heuristic information is ${\eta }_{\mathit{ij}}=\frac{\mid L_j\mid }{c_{\mathit{ij}}}$. This strategy orients ants to maximize the number of travel requests fulfilled.

In the MS concept proposed in [5], every ant decides which strategy to use at random with uniform distribution. A roulette wheel selection improves this concept. The proportion of the wheel assigned to each heuristic information is directly related to the quality of solutions achieved. So, ants learn, at each iteration, the best heuristic information. At the final iterations, ants tend to use the heuristic information that proved to be most promising.

Algorithm 1 presents the pseudo-code of the MS-MMAS. It has the following parameters: maximum number of iterations ($\mathit{\text{maxIter}}$), number of ants ($m\in {\mathcal{Z}}_{>0}$), pheromone coefficient ($\alpha \in {\mathcal{R}}_{>0}$), heuristic coefficient ($\beta \in {\mathcal{R}}_{>0}$), evaporation factor ($\rho \in \left[0,1\right]$), and pheromone limits (${\tau }_{\mathit{max}}$, ${\tau }_{\mathit{min}}\in {\mathcal{R}}_{>0}$). It also has the following parameters and variables:

• $N$: set of vertices;

• $\xi$: index of the heuristic information source;

• $W^k$: route built by the $k$-th ant;

• $S^k$: solution produced after applying the $\mathit{RMH}$ heuristic [5] to route $W^k$;

• $W^i$: the best route built in the $i$-th iteration;

• $S^i$: the best solution produced in the $i$-th iteration;

• $W^{\ast }$: the best route found so far;

• $S^{\ast }$: the best solution found so far;

• $W^{\mathit{\text{best}}}$: route used as input to the pheromone updating procedure;

• $\mathrm{\Pi }$: hash table that stores every solution $S^i$ constructed and used as initial solution to the local search algorithm;

Algorithm 1: MS-MMAS($\mathit{\text{maxIter}}$, $m$, $\alpha$, $\beta$, $\rho$${\tau }_{\mathit{max}}$, ${\tau }_{\mathit{min}}$)

1. $\mathrm{\Pi }\leftarrow \varnothing$

2. Initialize pheromone trails

3. For $k=1$ to $m$.

4.   $W^k\left[2\right]\leftarrow$ random_city($N\backslash \left\{s\right\}$)

5. For $i=1$ to $\mathit{\text{maxIter}}$

6.  For $k=1$ to $m$

7.    $\xi \leftarrow$ chose_heuristic_information()

8.    $W^k\leftarrow$ build_route($\alpha$, $\beta$, $\xi$)

9.    $S^k\leftarrow$ assign_passengers($W^k$)

10.   Update($W^i$,$S^i$)

11.  If $S^i\notin \mathrm{\Pi }$

12.   $S^i\leftarrow$ MnLS($S^i$)

13.   Store($\mathrm{\Pi }$, $S^i$)

14.  Update($W^{\ast }$,$S^{\ast }$)

15.  $W^{\mathit{\text{best}}}\leftarrow$ alternate($\mathit{\text{maxIter}}$, $i$, $W^i$, $W^{\ast }$)

16.  Pheromone_update($W^{\mathit{\text{best}}}$,$\rho$, ${\tau }_{\mathit{max}}$, ${\tau }_{\mathit{min}}$)

17. Return $S^{\ast }$

The algorithm sets ${\tau }_{\mathit{max}}$ as the initial value of pheromone trails (step 2). Since ants begin at vertex $s$, the second vertex is selected randomly with uniform distribution (steps 3 and 4). The $k$-th ant decides which heuristic information, $\xi$, to use (step 7) and builds a route (step 8). The algorithm uses the $\mathit{RMH}$ heuristic to assign passengers to $W^k$, completing a solution (step 9). The algorithm updates $W^i$ and $S^i$ (step 10). The MnLS algorithm is applied to $S^i$ (step 12) if the solution $S^i\notin \mathrm{\Pi }$. After the local search, the algorithm stores $S^i$ in the hash table $\mathrm{\Pi }$. At the next iteration, the current $S^i$ is the starting solution of the local search if it is not in $\mathrm{\Pi }$. This procedure prevents redundant work. The algorithm updates the best route and the best solution found so far, $W^{\ast }$ and $S^{\ast }$ (step 14). Similar to the original design of MMAS, $W^i$ is assigned to $W^{\mathit{\text{best}}}$ at the first 25$\%$ iterations or if $i$ ranges from [50$\%$,75$\%$] of $\mathit{\text{maxIter}}$. $W^{\ast }$ is assigned to $W^{\mathit{\text{best}}}$ if $i$ ranges from [25$\%$,50$\%$] of $\mathit{\text{maxIter}}$ or if it is greater than or equal to 75$\%$ of $\mathit{\text{maxIter}}$ (step 15). This procedure improves diversification by shifting the emphasis over the search space. $W^{\mathit{\text{best}}}$ is used to update pheromones (step 16). Finally, the algorithm returns $S^{\ast }$.

4. Experiments and results

This section presents the methodology for the experiments and results from the experiments. Section 4.1 presents the methodology. Section 4.2 presents the parameters used in the MS-MMAS algorithm. Section 4.3 presents the results.

4.1 Methodology

The experiments were executed on a computer with an Intel Core i5, 2.6 GHz processor, Windows 10, 64-bit, and 6GB RAM memory. The algorithms were implemented in C ++ lan and compiled with GNU g++ version 4.8.4. The benchmark set proposed in [5] was used to test the effectiveness of the MS-MMAS. The sizes of those instances range from 10 to 500 vertices. Small instances have up to 40 vertices, medium up to 100, and large more than 100 vertices. The instances are available for download at https://github.com/brunocastrohs/QTSP-PIC.

The best, average results, and average processing times (in seconds) are reported from 20 independent executions of the MS-MMAS. Experiments are conducted to report the distance between the best-known solutions and the best results provided by the MS-MMAS. The variability in which the MS-MMAS achieved the best-known solutions stated in the benchmark set is also calculated. With these experiments, it is possible to conclude if the MS-MMAS algorithm was able to find the best-known solution of each instance and with what variability this happens.

The Friedman test [23] with the Nemenyi post-hoc procedure [24] are applied, with a significance level 0.05, to conclude about significant differences among the results of the MS-MMAS and the other three ACO variants proposed in this [5]. The instances were grouped according to their sizes (number of vertices) for the Friedman test. There are eight groups of symmetric (asymmetric) instances, each of them contains nine instances, called $g<n>$, where $<n>$ stands for the size.

4.2 Parameter tuning

The IRACE software was used, presented by [22], to tune the parameters of the MS-MMAS algorithm. 20 symmetric and 20 asymmetric instances were submitted to adjust the parameters. Those instances were selected at random. The IRACE uses the $\mathit{\text{maxExperiments}}$ and $\mathit{\text{maxTime}}$ parameters as stopping criteria. This parameters were set as follows: $\mathit{\text{maxExperiments}}={10}^3$; and, $\mathit{\text{maxTime}}=\infty$.

For the asymmetric instance set, the parameters were defined as follows: $\mathit{\text{maxIter}}=31$; $m=51$; $\alpha =3.08$; $\beta =10.31$; $\rho =0.52$; ${\tau }_{\mathit{max}}=0.8$; and ${\tau }_{\mathit{min}}=0.2$. For the symmetric instance set, the parameters were: $\mathit{\text{maxIter}}=29$; $m=57$; $\alpha =2.92$; $\beta =9.53$; $\rho =0.67$; ${\tau }_{\mathit{max}}=0.7$; and ${\tau }_{\mathit{min}}=0.2$.

4.3 Results

In this section, the results of the MS-MMAS are tested and compared to those produced by the other three ACO variants proposed in [5]: AS, ACS, and MS-ACS.

Table 1 presents the comparison between the ant algorithms. The best results obtained by MS-MMAS were compared with those achieved by each ant algorithm proposed in [5]. The results are in the $X\times Y$ format, where $X$ and $Y$ stand for the number of instances in which the ant algorithm $X$ found the best solution and the number of instances in which the ant algorithm $Y$ found the best solution, respectively.

	Asymmetric			Symmetric
	AS	ACS	MS-ACS	AS	ACS	MS-ACS
MS-MMAS	68 x 0	68 x 1	45 x 17	66 x 1	68 x 2	48 x 14

Table 1.

Comparison between the ant algorithms.

Table 1 shows that the MS-MMAS was the algorithm that reported the best solution for most instances. This algorithm performed best than other ACO variants due to its enhanced pheromone update procedures. The MS implementation with roulette wheel selection proved to be effective at finding the best heuristic information used by the ants during the run. Table 1 also shows that the MS-MMAS provides results with better quality than the MS-ACS in the most symmetric cases. The MS-ACS was superior to the MS-MMAS in seventeen asymmetric cases and fourteen symmetric instances. Was observed that the pseudo-random action choice rule of MS-ACS [20], which allows for a greedier solution construction, proved to be a good algorithmic strategy for solving large instances.

Tables 2 and 3 shows the ranks of the ant algorithms based on the Friedman test [23] with the Nemenyi [24] post-hoc test. The first column of this Tables presents the subsets of instances grouped according to their sizes. The other columns of this Tables present the p-values of the Friedman test and the ranks from the Nemenyi post-hoc test. In the post-hoc test, the order ranks from $a$ to $c$. The $c$ rank indicates that the algorithm achieved the worst performance in comparison to the others. The $a$ rank indicates the opposite. If the performances of two or more algorithms are similar, the test assigns the same rank for them. In this experiment, the significance level was assigned with 0.05.

	Asymmetric
Subset	p-value	AS	ACS	MS-ACS	MS-MMAS
$g10$	0.003159	b	b	a	a
$g20$	0.000040	b	c	a	a
$g30$	0.000017	c	c	a	a
$g40$	0.000024	b	c	a	a
$g50$	0.000048	c	c	b	a
$g100$	0.000045	b	c	a	a
$g200$	0.000031	b	c	a	a
$g500$	0.000037	c	b	a	a

Table 2.

Results of Friedman’s test and Nemenyi post-hoc test over asymmetric instances set.

	Symmetric
Subset	p-value	AS	ACS	MS-ACS	MS-MMAS
$g10$	0.003543	b	b	a	a
$g20$	0.000205	b	c	a	a
$g30$	0.000045	c	c	b	a
$g40$	0.000059	b	c	a	a
$g50$	0.000035	b	b	a	a
$g100$	0.000024	b	b	a	a
$g200$	0.000045	c	b	a	a
$g500$	0.000098	c	b	a	a

Table 3.

Results of Friedman’s test and Nemenyi post-hoc test over symmetric instances set.

The p-values presented in Tables 2 and 3 show that the performance of the ant algorithms was not similar, i.e., the null hypothesis [24] is rejected in all cases. In these Tables, can be observed that MS-MMAS ranks higher than AS and ACS for all subsets. The ranks of MS-ACS and MS-MMAS were the same in the most cases. This implies that the performance of only these two algorithms where similar, i. e., the relative distance between the results achieved by these two algorithms are short.

To analyze the variability of the results provided by each ant algorithm compared to the best results so far for the benchmark set, three metrics regarding the results produced by the experiments were adopted. The first metric, $\nu$, shows the percentages relative to the number of times an ant algorithm found the best-known solution along 20 independent executions. The second metric, $\mathrm{\Phi }$, is the relative distance between the cost of the best-known solution ${\chi }^{\ast }$ and the best solution ${\chi }^{\mathit{min}}$ of each ant algorithm. The third metric, $\mathrm{\Omega }$, is the relative distance between ${\chi }^{\ast }$ and the average solution ${\chi }^a$ of each ant algorithm. To calculate $\mathrm{\Phi }$, the Eq. (9) was used. $\mathrm{\Omega }$ is calculated using the formula (10). The average values of $\nu$, $\mathrm{\Phi }$ and $\mathrm{\Omega }$ are reported in Tables 4 and 5.

	Asymmetric
Metric	AS	ACS	MS-ACS	MS-MMAS
$\nu$	4.30$\%$	2.56$\%$	6.8$\%$	11.84$\%$
$\mathrm{\Phi }$	0.2075333	0.2773624	0.0541799	0.0054741
$\mathrm{\Omega }$	0.2835401	0.4023659	0.1754952	0.5854892

Table 4.

Variability of the ants algorithms for asymmetric instances.

	Symmetric
Metric	AS	ACS	MS-ACS	MS-MMAS
$\nu$	2.01$\%$	0.69$\%$	8.75$\%$	9.05$\%$
$\mathrm{\Phi }$	0.2169756	0.2285948	0.0547890	0.0113889
$\mathrm{\Omega }$	0.3017957	0.3620682	0.1656022	0.6432748

Table 5.

Variability of the ants algorithms for symmetric instances.

$$\mathrm{\Phi }=\frac{{\chi }^{\mathit{min}}}{{\chi }^{\ast }}-1$$E9

$$\mathrm{\Omega }=\frac{{\chi }^a}{{\chi }^{\ast }}-1$$E10

It can be observed from Tables 4 and 5 that the MS-MMAS is the best one concerning the $\nu$ and $\mathrm{\Phi }$ metrics. The MS-ACS is the best algorithm concerning the $\mathrm{\Omega }$ metric. Tables 6 and 7 show the data regarding the results of MS-MMAS reported in Tables 4 and 5. The results of the other ACO variants can be seen in [5].

Tables 8 and 9 present the average processing time (in seconds) spent by each heuristic. Instances are grouped by the number of vertices. From these tables, it can be conclude that the MS-MMAS was the ant algorithm that demanded more processing time. Tables 6 and 7 (1) present detailed results concerning the average time required by the MS-MMAS. Data regarding the time consumption of the other ACO variants can be seen in [5].

	Asymmetric				Symmetric
Instance	Best	Average	Time	Percentage	Best	Average	Time	Percentage
A-10-3	478.42	863.13	0.15	100$\%$	545.92	996.34	0.15	25$\%$
A-10-4	523.57	1069.33	0.14	80$\%$	460.00	838.84	0.18	20$\%$
A-10-5	482.60	690.08	0.14	5$\%$	371.93	658.97	0.19	10$\%$
A-20-3	519.67	936.47	0.35	5$\%$	679.75	1363.59	0.32	20$\%$
A-20-4	458.10	1145.88	0.38	0$\%$	346.30	661.82	0.43	35$\%$
A-20-5	398.75	669.82	0.35	10$\%$	351.50	1006.24	0.48	5$\%$
A-30-3	618.33	1180.70	0.48	10$\%$	574.33	1469.68	0.50	5$\%$
A-30-4	401.20	805.32	1.28	5$\%$	654.80	1202.15	0.40	5$\%$
A-30-5	475.83	1033.91	0.58	10$\%$	464.05	911.56	0.66	5$\%$
A-40-3	692.00	1060.67	2.83	5$\%$	718.25	1399.04	0.72	10$\%$
A-40-4	658.95	1088.41	2.52	5$\%$	570.98	961.13	2.95	5$\%$
A-40-5	460.90	900.51	3.11	5$\%$	441.22	836.52	2.89	5$\%$
B-10-3	729.50	925.35	0.13	5$\%$	834.67	1485.47	0.20	20$\%$
B-10-4	306.90	421.35	0.13	15$\%$	493.58	757.45	0.16	10$\%$
B-10-5	434.75	835.01	0.18	55$\%$	726.35	1160.97	0.23	5$\%$
B-20-3	805.42	1251.39	0.28	10$\%$	950.00	1666.22	0.45	5$\%$
B-20-4	848.62	1366.69	0.35	5$\%$	822.82	1386.67	0.49	5$\%$
B-20-5	895.17	1275.78	0.28	70$\%$	660.22	1215.12	0.35	5$\%$
B-30-3	747.75	1316.96	1.31	5$\%$	718.67	1358.11	0.93	5$\%$
B-30-4	723.27	1301.57	1.51	5$\%$	650.35	1272.86	0.69	5$\%$
B-30-5	700.75	1205.96	1.39	5$\%$	504.68	1091.11	0.89	5$\%$
B-40-3	964.42	1574.00	2.02	0$\%$	889.83	1682.76	1.97	5$\%$
B-40-4	1195.62	2134.73	1.20	5$\%$	743.82	1508.16	2.09	0$\%$
B-40-5	819.28	1537.71	1.11	10$\%$	749.82	1351.64	0.85	5$\%$
C-10-3	359.25	604.70	0.17	55$\%$	597.83	697.51	0.05	0$\%$
C-10-4	307.10	514.66	0.20	5$\%$	408.45	514.65	0.15	85$\%$
C-10-5	566.58	783.35	0.17	10$\%$	409.60	846.51	0.23	10$\%$
C-20-3	650.25	978.84	0.46	10$\%$	629.92	1063.99	0.36	0$\%$
C-20-4	563.78	938.50	0.72	5$\%$	441.65	1019.96	1.06	10$\%$
C-20-5	739.22	1056.77	1.02	0$\%$	711.87	1095.84	0.63	5$\%$
C-30-3	837.58	1198.09	1.05	5$\%$	830.17	1221.65	0.61	10$\%$
C-30-4	754.10	1144.99	2.47	5$\%$	745.92	1096.55	1.16	5$\%$
C-30-5	560.18	998.28	2.29	10$\%$	490.80	931.81	2.21	5$\%$
C-40-3	1008.00	1541.54	2.59	5$\%$	607.00	946.57	3.45	10$\%$
C-40-4	695.30	1172.76	2.06	10$\%$	699.80	1136.17	2.25	0$\%$
C-40-5	623.33	1097.22	3.24	10$\%$	475.67	898.80	7.82	0$\%$

Table 6.

Results of the MS-MMAS executions for small instances.

	Asymmetric				Symmetric
Instance	Best	Average	Time	Percentage	Best	Average	Time	Percentage
A-50-3	1058.33	2128.68	2.31	5$\%$	1000.33	1943.13	2.91	5$\%$
A-50-4	774.93	1473.57	4.48	5$\%$	783.40	1345.19	3.53	5$\%$
A-50-5	673.42	1314.54	4.16	5$\%$	583.08	1008.33	2.59	0$\%$
A-100-3	1431.42	2046.96	53.44	5$\%$	1514.08	2292.08	15.66	20$\%$
A-100-4	1456.47	2705.07	23.12	5$\%$	1165.90	1595.91	37.11	5$\%$
A-100-5	1106.17	1778.38	40.57	10$\%$	980.28	1366.09	58.20	5$\%$
A-200-3	2806.75	3610.22	424.60	0$\%$	2793.33	3272.00	257.42	0$\%$
A-200-4	2388.88	3196.15	381.07	0$\%$	2199.45	2807.06	79.32	10$\%$
A-200-5	1753.00	2286.08	1380.26	10$\%$	2086.82	3237.85	55.37	10$\%$
A-500-3	6878.42	7165.39	1641.92	33$\%$	6331.75	7679.65	732.94	10$\%$
A-500-4	5572.42	5637.26	4939.84	0$\%$	5030.48	5080.66	913.82	0$\%$
A-500-5	4389.92	4539.44	16990.77	50$\%$	4610.95	4696.91	73.97	33$\%$
B-50-3	1338.42	2356.24	5.82	10$\%$	966.42	1770.88	4.60	5$\%$
B-50-4	951.87	1757.61	5.00	5$\%$	772.67	1490.01	1.47	5$\%$
B-50-5	1083.18	1943.22	3.91	5$\%$	692.42	1342.78	4.74	5$\%$
B-100-3	1781.00	3115.78	30.96	5$\%$	1803.33	3258.90	15.11	5$\%$
B-100-4	1409.65	2467.02	61.76	5$\%$	1648.58	3360.93	11.00	5$\%$
B-100-5	1361.20	2734.24	39.89	5$\%$	1018.37	1536.34	99.02	5$\%$
B-200-3	3302.83	4840.94	317.37	0$\%$	3016.67	4267.17	56.62	0$\%$
B-200-4	2536.80	3477.13	681.75	0$\%$	2326.97	3139.57	81.34	10$\%$
B-200-5	2127.88	2814.24	906.74	0$\%$	1893.67	2506.64	102.33	10$\%$
B-500-3	6994.84	7203.61	3857.77	0$\%$	6433.92	6475.67	126.51	0$\%$
B-500-4	5419.87	5730.97	24183.87	100$\%$	5191.77	5276.98	267.72	0$\%$
B-500-5	4546.28	4643.03	21118.98	0$\%$	4379.43	4494.11	164.08	33$\%$
C-50-3	1201.92	1801.68	3.12	5$\%$	829.75	1482.86	2.82	5$\%$
C-50-4	937.25	1651.11	7.96	5$\%$	901.40	1605.24	6.16	10$\%$
C-50-5	609.60	1127.99	16.58	5$\%$	766.48	1366.58	7.43	5$\%$
C-100-3	1496.58	2001.76	47.62	0$\%$	1364.00	1819.03	14.21	10$\%$
C-100-4	1352.85	2458.82	32.32	5$\%$	1099.00	1445.29	23.98	0$\%$
C-100-5	1022.70	1466.42	127.11	0$\%$	991.12	1472.23	35.21	5$\%$
C-200-3	2629.00	3197.13	478.90	10$\%$	2510.50	3171.66	65.07	10$\%$
C-200-4	2184.85	2648.38	710.70	10$\%$	2141.40	2741.11	52.59	0$\%$
C-200-5	1881.03	2296.53	486.62	0$\%$	1713.17	2127.84	126.85	10$\%$
C-500-3	6528.08	6618.16	2484.52	0$\%$	6023.42	6087.14	138.12	33$\%$
C-500-4	5139.54	5298.21	8188.46	0$\%$	4942.28	4958.64	65.19	33$\%$
C-500-5	4286.45	4278.49	6061.78	0$\%$	4167.67	4178.10	302.79	0$\%$

Table 7.

Results of the MS-MMAS executions for medium and large instances.

n	AS	ACS	MS-ACS	MS-MMAS
10	0.05	0.06	0.12	0.15
20	0.10	0.13	0.26	0.46
30	0.20	0.30	1.92	1.37
40	0.34	0.48	2.29	2.29
50	0.41	2.20	5.77	5.92
100	6.68	28.85	32.69	50.75
200	31.81	270.94	409.72	640.89
500	41.72	3477.13	3545.20	9940.87

Table 8.

Average time spent by the ant algorithms for the set of asymmetric instances.

n	AS	ACS	MS-ACS	MS-MMAS
10	0.05	0.06	0.12	0.17
20	0.10	0.13	0.27	0.51
30	0.18	0.24	0.49	0.89
40	0.28	0.38	0.73	2.78
50	0.40	0.56	5.41	4.02
100	8.13	13.51	29.17	34.93
200	22.94	51.92	112.58	97.43
500	40.53	75.72	127.83	309.46

Table 9.

Average time spent by the ant algorithms for the set of symmetric instances.

5. Discussion

The purpose of this study was to adapt MMAS to the QTSP-PIC and compare its performance with the ACO variants proposed in [5]. As expected, MS-MMAS proved to be competitive regarding the other ACO variants proposed to solve QTSP-PIC. Similarities and differences that were observed in the results are discussed in section 5.1. The limitations of the study are discussed in Section 5.2.

5.1 Comparison between ACO algorithms

The ACO algorithms proposed by Silva et al. [5] showed to be a viable method for solving QTSP-PIC. Yet, the performance of AS and ACS algorithms, when compared to MS-MMAS, was rather poor for the benchmark set studied. MS-MMAS improved the results achieved by AS in 134 instances. Compared to ACS, MS-MMAS performed better in 136 instances. The results achieved by MS-MMAS improved those produced by MS-ACS in 93 instances. It is interesting to note that the MS-ACS algorithm performed slightly better on the large instances than the MS-MMAS. The Friedman test and Nemenyi post-hoc ranked these two ACO algorithms with the same scale for the most instance groups, which means that difference between the results achieved by the MS-ACS and MS-MMAS was significantly small.

These observations are also supported by the variability results of each ACO algorithm. Metric $\nu$ showed that MS-MMAS was the algorithm that achieved the best know solutions of the benchmark set in most cases. Metric $\mathrm{\Phi }$ showed that the MS-MMAS performed slightly better overall on the benchmark set than the MS-ACS. A possible explanation for this is that the MS-ACS variation might converge to a local minimum faster than the MS-MMAS.

Results presented in this study showed that the MS-MMAS algorithm is better suited than the other three ACO variants proposed in [5] to solve QTSP-PIC. This suggests a positive impact of the implementation design proposed in this study and a contribution to the MAX-MIN Ant System state of the art.

5.2 Limitations

Due to limited time, parallel computing techniques could not be tested to improve the performance of MS-MMAS. A previous study done by Skinderowicz [10] investigated the potential effectiveness of a GPU-based parallel MAX-MIN Ant System in solving the TSP. In this study, the most promising MMAS variant was able to generate over 1 million candidate solutions per second when solving a large instance of the TSP benchmark set. Other techniques can improve the MS-MMAS design and could not be tested due to the lack of time:

• A rank-based pheromone updating rule [25];

• The application of the pseudo-random action choice rule proposed in [21];

• Hybridization with other meta-heuristics [26, 27, 28].

6. Conclusions

This work dealt with a recently proposed variant of the Traveling Salesman Problem named The Quota Traveling Salesman Problem with Passengers, Incomplete Ride, and Collection Time. In this problem, the salesman uses a flexible ride-sharing system to minimize travel costs while visiting some vertices to satisfy a pre-established quota. He must respect the budget limitations and the maximum travel time of every passenger. Each passenger can be transported directly to the desired destination or an alternate destination. The alternative destination idea suggests that when sharing a ride, pro-environmental or money-saving concerns can induce persons to agree to fulfill their needs at a similar destination. Operational constraints regarding vehicle capacity and travel time were also considered.

The Multi-Strategy MAX-MIN Ant System, a variant from the Ant Colony Optimization (ACO) family of algorithms, was presented. This algorithm uses the MS concept improved with roulette wheel selection and memory-based principles to avoid redundant executions of the local search algorithm. The results of MS-MMAS were compared with those produced by the ACO algorithms presented in [5]. To support MS-MMAS, the ride-matching heuristic and the local search heuristic based on multiple neighborhood operators proposed by [5] were reused.

The computational experiments reported in this study comprised one hundred forty-four instances. The experimental results show that the proposed ant algorithm variant could update the best-known solutions for this benchmark set according to the statistical results. The comparison results with three other ACO variants proposed in [5] showed that MS-MMAS improved the best results of MS-ACS for ninety-three instances, and a significant superiority of MS-MMAS over AS and ACS.

The presented work may be extended in multiple directions. First, it would be interesting to investigate if the application of the pseudo-random action choice rule [20] could improve the MS-MMAS results. Another further promising idea is the use of pheromone update rule based on ants ranking [25]. Extension of the MS-MMAS implementation design with parallel computing techniques [10] and hybridization with other meta-heuristics [26, 27, 28] is other interesting opportunity for the future research.

Abbreviations

MaaS	Mobility as a Service
QTSP-PIC	Quota Traveling Salesman Problem with Passengers, Incomplete Ride and Collection Time
ACO	Ant Colony Optimization
RMH	Ride-Matching Heuristic
MnLS	Multi-neighborhood Local Search
MS-ACS	Multi-Strategy Ant Colony System
MMAS	MAX-MIN Ant System
MS-MMAS	Multi-Strategy MAX-MIN Ant System
MS	Multi-Strategy
TSP	Traveling Salesman Problem
QTSP	Quota Traveling Salesman Problem
AS	Ant System
ACS	Ant Colony System