This article has been accepted for inclusion in a future issue of this journal.

Content is final as presented, with the exception of pagination.

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 1

Novel Ant Colony Optimization Methods

for Simplifying Solution Construction
in Vehicle Routing Problems
Xinyu Wang, Tsan-Ming Choi, Haikuo Liu, and Xiaohang Yue

Abstract—As a novel evolutionary searching technique, ant depot, with all customers being visited once and only once. In
colony optimization (ACO) has gained wide research attention and the traditional VRP, a fleet of vehicles are dispatched from the
can be used as a tool for optimizing an array of mathematical depot to serve a number of customers. Since the vehicle capac-
functions. In transportation systems, when ACO is applied to solve
the vehicle routing problem (VRP), the path of each ant is only ity is a key factor in real-life applications, one generalization
“part” of a feasible solution. In other words, multiple ants’ paths of VRP is called the capacitated VRP (CVRP) [1], [4]. The
may constitute one feasible solution. Previous works mainly focus goals of TSP and VRP are to find the “cheapest” tour under
on the algorithm itself, such as revising the pheromone updating certain circumstances. In the real world, these applications
scheme and combining ACO with other optimization methods. can be found everywhere, such as waste collection, inventory
However, this body of literature ignores the important procedure
of constructing feasible solutions with those “parts”. To overcome distribution, and post-disaster relief logistics. In most cases,
this problem, this paper presents a novel ACO algorithm (called planners need an intelligent transportation system, in the form
AMR) to solve the VRP. The proposed algorithm allows ants to go of a decision support system, to devise the routes for vehicles
in and out the depots more than once until they have visited all to minimize the operational cost [5].
customers, which simplifies the procedure of constructing feasible The VRP has been the subject of intensive research for
solutions. To further enhance AMR, we propose two extensions
(AMR-SA and AMR-SA-II) by integrating AMR with other saving more than 50 years, and the broad range of actual applications
algorithms. The computational results for standard benchmark also lead to many VRP variants [6]. During the past decades,
problems are reported and compared with those from other ACO these problems have been tackled by a plethora of approaches
methods. Experimental results indicate that the proposed algo- and techniques, ranging from operational research to artificial
rithms outperform the existing ACO algorithms. intelligence. The solution methods can be mainly divided into
Index Terms—Ant colony optimization (ACO), vehicle routing two categories: exact solution methods and heuristic methods.
problem (VRP), paths, feasible solutions, saving algorithm. The exact algorithms always guarantee to yield an optimal
solution. However, it may require intolerable computation time,
especially when the problem scale is large. As for the heuris-
I. I NTRODUCTION tics, they aim to provide satisfactory suboptimal solutions in

T HE effective management of vehicle and personnel

scheduling is of critical importance in transportation
systems [1]–[3]. The traveling salesman problem (TSP) and the
acceptable computing time, while could not theoretically guar-
antee that the attained solutions are the globally optimal ones
[24], [25]. Performance of the heuristics is typically assessed
vehicle routing problem (VRP) are NP-hard in combinatorial by comparisons with each other (or with best known solutions)
optimization. But they are essentially important and widely under the well-known benchmarks [26].
used in the fields of operational research and theoretical com- Ant colony optimization, originally proposed by Dorigo [27],
puter science. In TSP, one vehicle starts and ends at the same is a relatively new optimization method, which simulates food-
seeking behaviors of ant colonies in nature. As a population-
based paradigm, ACO needs to be properly adapted to the
Manuscript received October 15, 2015; revised January 22, 2016 and specific problem on hand to ensure the best performance. In
March 10, 2016; accepted March 11, 2016. This work was supported ACO, different ants communicate with each other by deposit-
in part by the National Natural Science Foundation of China under Grant
61402086, by the Scientific Research Foundation of Liaoning Provincial Ed- ing the pheromone, and the pheromone evaporates over time.
ucation Department under Grant L2015165, by the Fund for International This mechanism enhances and adapts to the global and local
Cooperation and Exchange of the National Natural Science Foundation of exploration. Compared to other optimization methods, the ACO
China under Grant 71110107024, and by DUFE Excellent Talents Project under
Grant DUFE2015R06. The Associate Editor for this paper was X. Cheng. has a number of advantages which contribute to its wide use.
(Corresponding author: Tsan-Ming Choi.) Some of the key advantages of ACO include: (i) this method
X. Wang and H. Liu are with the Department of Management Science and does not need the calculation of derivatives, (ii) the knowledge
Engineering, Dongbei University of Finance and Economics, Dalian 116025,
China (e-mail: Distribute_2008@163.com; sea_liuhaikuo@163.com). of good solutions is retained by all ants, and (iii) the ants in the
T.-M. Choi is with the Institute of Textiles and Clothing, Hong Kong Poly- colony share information between them. Moreover, ACO is less
technic University, Hung Hom, Hong Kong (e-mail: jason.choi@polyu.edu.hk). sensitive to the nature of the objective function, and hence it can
X. Yue is with the Sheldon B. Lubar School of Business, University of
Wisconsin—Milwaukee, Milwaukee, WI 53202 USA (e-mail: xyue@uwm.edu). be used for various objective functions, and can easily escape
Digital Object Identifier 10.1109/TITS.2016.2542264 from local minima. Concerning its implementation, ACO can
1524-9050 © 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

2 IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS

easily be programmed, and it can be combined with other meth- propose an insertion heuristic and study the impact of incor-
ods. Besides, the assessment of the optimum is independent porating complicating constraints on the efficiency of insertion
of the initial solution. Therefore, ACO has been successfully heuristics. Other methods based on metaheuristics (such as
applied to solve many hard combinatorial optimization prob- the genetic algorithm [16], [17], particle swarm optimization
lems [28], such as TSP, VRP, quadratic assignment problems, [18], [19], the memetic algorithm [20], ant colony optimiza-
scheduling problems, sequential ordering problem, and sequen- tion [21], local search [22], [23]) have also been proposed to
tial ordering problem. (Early research in the theory of ACO is find suboptimal solutions for the problem. Gong et al. [18]
reviewed in [29].) propose a set-based particle swarm optimization (PSO) algo-
The general ACO for CVRP includes three main processes, rithm, in which the operators are defined on the set. By using
namely, initializing, solution constructing and pheromone up- the PSO framework, an optimal subgraph could be selected
dating. In the second process, ants utilize pheromone trails and out of the complete graph and the problem is solved. In [16],
heuristic information to construct feasible solutions. Due to the the guide of fuzzy logic is added to the genetic algorithm
capacity constraint, each ant visits some (not all) customers (GA) to dynamically adjust the crossover rate and mutation
before returning to the depot. When all ants return to the depot, rate of GA.
feasible solutions are constructed with the paths of ants. Notice ACO belongs to the class of metaheuristics. It aims to ob-
that, several ants’ paths, which together cover all customers, tain good enough solutions to hard combinatorial optimization
constitute one feasible solution. With all ants’ paths, we may problems in a reasonable amount of computation time. When
construct a number of feasible solutions. Finding all feasible ACO is applied to solve TSP, the path traveled by each ant
solutions and then giving the best one is identical to the NP- itself is a feasible solution to the original problem. After a finite
hard set covering problem. Previous works mainly optimize the number of iterations, the algorithm yields a “best” solution from
foraging process of ants, while they do not deal with the process those feasible solutions [43]. However, when ACO is applied to
on final feasible solution construction after all ants return to the solve VRP, an ant can be viewed as a vehicle with capacity,
depot. and it will visit some (not all) customers before getting back
The main contributions of this paper are1 : 1) to simplify the to the depot. Therefore, one ant’s path is only “part” of a
process of feasible solution construction with AMR, 2) to pro- feasible solution. In other words, several ants’ paths together
pose a simple tabu modifying scheme for the implementation of constitute a feasible solution. In each iteration, after all ants
AMR, and 3) to propose two efficient hybrid algorithms (AMR- return to the depot, how to find the optimal solution with the
SA, AMR-SA-II) by integrating AMR with saving algorithms. paths traveled by those ants is a critical issue. This process can
In the proposed algorithms, ants are allowed to go in and out be converted into a set covering problem with the constraint
the depot several times, until they have visited all the required condition that the intersection of any two subsets is empty.
customers. The path traveled by each ant corresponds to a It is known that, the set covering problem is NP-hard [44].
feasible solution for the problem. Therefore, the set covering Therefore, it is not appropriate to ignore the final process to
problem is avoided. find the optimal solution after all ants get back to the depot.
The remainder of this paper is organized as follows. We state It is meaningful to avoid the set covering problem by directly
the problem and review some existing techniques in Section II. constructing feasible solutions when ants visit customers.
Section III presents the research motivation and provides details Roberto et al. [45] propose the mathematical formulations of
of the proposed methodologies. Computational experiments CVRP and its variants for exact solution approaches. Given the
and analysis of the algorithms are shown in Section IV. Finally, feasible route set, the authors present an NP-hard set covering
Section V concludes the paper. formulation, and review some exact methods based on branch-
and-cut methods with additional cuts. Clearly, the key factor of
these approaches is the effective combination of set covering
II. P ROBLEM D ESCRIPTION AND R ELATED W ORK
and vehicle flow formulations of the problem. The objective of
In the literature, many researchers have made great effort CVRP is to minimize the total traveling cost of vehicles while
to solve the VRP and both exact and heuristic approaches adhering to the imposed capacity restrictions. One important
have been proposed. For example, researchers have designed aspect of ACO is related to the state transition rule. In [33], [34],
exact algorithms based on integer programming [7], column the vehicle capacity is taken into account when ants construct
generation algorithm [8], branch-and-bound [9], branch-and- solutions. The tabu of each ant records the infeasible customers,
price [10], [11], and Bellman-Ford algorithm [12]. In [13], an and a customer, whose demand exceeds the current available
implementation of the integer L-shaped method for finding the capacity in terms of weight or who has been visited by the
exact solution is studied, which largely depends on the com- ant during the past time, belongs to the tabu. Therefore, each
putation of lower bounds and the generation of more efficient ant’s route is only part of a final feasible solution. Unless
lower bounding functionals. As for the heuristic approaches, both the number of customers and the number of simulated
Prins et al. [14] propose a tour splitting heuristic, which first artificial ants are small, feasible solutions can be constructed
builds a “big” tour visiting all customers and then splits the in a reasonable time frame. Besides, there is a possibility that
tour into capacity-feasible vehicle trips. Campbell et al. [15] no feasible solution can be derived from the paths of all ants.
Fig. 1 shows such an example. As shown in Fig. 1, we can not
1 We are grateful for the anonymous reviewers whose comments inspire us to construct a feasible solution to serve the 4 customers from those
better present the contribution and the literature positioning of this paper. 6 ants’ paths.
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

WANG et al.: ACO METHODS FOR SIMPLIFYING SOLUTION CONSTRUCTION IN VRPS 3

discard the capacity constraint when constructing solutions.

However, vehicle capacity has a direct effect on the final
solutions, and should be considered by ants. To overcome this
problem, we present a novel method to solve the problem by
allowing each ant after returning to the depot, to set out again,
until it has visited all customers. In the proposed scheme,
simulated artificial ants will take capacity, visible information
(distance), and pheromone into consideration. The compre-
Fig. 1. Situation of no feasible solution in ACO.
hensive utilization of different information directly contributes
to the quality improvement of the final optimal solution.
Table II compares the implementation details between our pro-
To avoid the situation of having no feasible solution, one posed methods and the existing methods to show the advantages
possible method is to increase the number of simulated ants, of our proposed methods in this paper.
which further complicates the process of constructing feasi-
ble solutions. Another intuitive method is to first construct
a “big” trip and then divide it into capacity-feasible vehicle III. M OTIVATION AND M ETHODOLOGY
trips. This first-route-then-cluster scheme is introduced in [14]
A. Motivation
and [46], and it can be easily implemented in ACO in the
following two steps: (1) remove the capacity constraint, and In the literature, researchers generally use two steps to solve
convert the CVRP into a TSP. Ants are required to visit all the CVRP. In the first step, ants travel in the road network,
customers before returning to the depot. We herein call the and each ant departs from the depot at the beginning, visits
situation as ants traveling in a TSP manner; (2) consider the customers, and then returns to the depot at the end. In the
capacity constraint and split the route given in process (1) second step, feasible solutions are constructed based on the
into multiple routes with the capacity constraint. Given that ants’ paths from the previous step.
a solution of VRP is made of multiple routes, the depot is If we take the vehicle capacity into account in the first step,
represented as 0 and the customers are denoted by integers each ant will visit some customers (not all) before getting
from 1 to n. Suppose that there are k vehicles and n customers. back to the depot. Then, the path traveled by each ant is
With the route given in process (1), the first vehicle sets out only part of a feasible solution. How to identify the feasible
beforehand from the depot and gets back to the depot after solutions, and further find the “best” one from them is an
visiting customers, and other vehicles leave the depot one important issue. In this case, the process of the second step
by one following the order. The arrangement of each vehi- can be converted into a set covering problem, which is also
cle is repeated until every customer has been visited by one NP-hard.
vehicle. If we ignore the vehicle capacity in the first step, each
When solving CVRP, previous studies mainly focus on im- ant travels in the road network in a TSP manner, that is, it
proving ACO techniques by adjusting parameters [30], [31], will visit all customers once and only once before getting
updating pheromone trail [32]–[34], reducing searching space back to the depot. In the second step, a long-travel route is
[35], introducing multiple types of ants [36], and integrating divided into several short routes with the capacity constraint.
it with other methods [37]–[40]. For instance, Balseiro et al. We call this scheme first-route-then-cluster. When the number
[41] propose a hybrid algorithm by combining ACO with a of vehicles is not strictly constrained, the scheme mentioned
new insertion heuristic, whereas the insertion heuristic relies above always yields feasible solutions. However, it is common
on a minimum delay metric. In [37], a hybrid PS-ACO al- that the number of vehicles is fixed (or is optimized to be as
gorithm is presented, in which the search space is expanded small as possible) in order to reduce cost. Unfortunately, the
by local exploration and the search process is directed by the first-route-then-cluster scheme often fails to yield a feasible so-
global experience. In [42], a hybrid algorithm is developed, lution, let alone the optimal solution. Take the dataset P-n23-k8
which integrates ACO with tabu search. However, they do (available on website “http://www.bernabe.dorronsoro.es/vrp/”)
not consider the process of constructing the final feasible as an example, the optimal number of vehicles is 8, while
solutions [33], [34], [39] which introduces another NP-hard the first-route-then-cluster method could only yield solutions
problem (e.g. the set covering problem). In this paper, we with at least 9 vehicles. Besides, as for datasets P-n19-k2
mainly focus on ant colony optimization to solve VRP with and P-n20-k2, when the capacity is set to 40 units, the
a practical scheme to simplify solution construction. To show first-route-then-cluster method still fails to yield feasible
the literature positioning of this paper, a systematic comparison solutions.
between this paper and the other ACO-based studies is shown Motivated by the above arguments, it is important to put
in Table I. forward an intelligent algorithm to overcome the said chal-
In CVRP, the routes traveled by the ants are only part of a lenges. Furthermore, it is even more important to extend their
feasible solution. Thus, a combination scheme should be de- applications and verify their competence in different problems
signed to construct the final solution from those parts. We sim- [47]. In this paper, based on an improved ACO scheme, we aim
ply name this method as “first-route-then-combine”. In ACO to find a simple method to construct the feasible solution. In
adopting the first-route-then-cluster scheme [46], ants will the meanwhile, when deciding the next visiting customer, ants
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

4 IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS

TABLE I
C OMPARISONS B ETWEEN T HIS PAPER AND O THER R ELATED ACO-BASED S TUDIES R EVIEWED IN T HIS PAPER

TABLE II
C OMPARISONS OF I MPLEMENTATION D ETAILS B ETWEEN O UR Algorithm 1 The main procedure of the proposed AMR.2
P ROPOSED M ETHODS AND THE E XISTING M ETHODS
Input: a CVRP instance to be solved
Output: the best solution so far xb and cost cb
1) begin
2) Initialize the pheromone trails on each arc
3) Initialize the tabu (T ) and the available capacity (AC)
for each ant
4) cb ← G /∗G is a sufficiently large positive constant∗/
5) while the termination condition does not satisfy do
6) N AntsHalting ← 0
7) while (true) do
8) for k = 1 to N Ants do
should take into account the factors such as vehicle capacity, 9) if Antk in halting state then
requirement of each customer, number of vehicles, distance, as 10) N AntsHalting ← N AntsHalting + 1
well as pheromone. 11) else if Antk returned to the depot then
12) ACk ← Capacity
13) else
B. The Improved ACO for CVRP (AMR) 14) select next customer for Antk
15) update Tk and ACk for Antk
As discussed above, ACO usually consists of three main 16) end if
phases: initialization, pheromone update and solution construc- 17) end for
tion. All of these phases constitute a complete search of the 18) local pheromone update
global optimum through multiple iterations. 19) if N AntsHalting = N Ants then
The main procedure of the proposed AMR algorithm is 20) global pheromone update
given in Algorithm 1, in which different ants communicate 21) break
with each other indirectly by making modifications to the 22) end if
concentration of pheromone in their neighbor environment. 23) end while
Each ant, with the ability to search for paths, constructs a 24) for k = 1 to N Ants do
feasible solution by using a tabu list. In the algorithm, we use 25) let s denote the solution of Antk
N Ants (N AntsHalting) to represent the number of all ants 26) if f (s) < cb then
(ants in the halting state). Given the tabu of an ant, the feasible 27) xb ← s, cb ← f (s)
solution s can be easily derived in our AMR, and we use f (s) to 28) end if
compute the cost of s. The AMR algorithm differs from other 29) Initialize Tk and ACk for Antk
ACO algorithms in the following point: when an ant returns 30) end for
to the depot and it is not in the halting state, it will be driven 31) end while
to depart from the depot again and continue to search in the 32) end
road network (Lines 11 to 12 of Algorithm 1). Each ant selects
the next customer using the random proportional rule (Lines 13 In the following paragraphs, we first describe the structure
to 15 of Algorithm 1). The entire inner loop (Lines 7 to 23 of of the tabu and its modification process. Then, we present the
Algorithm 1) shows the process of solution construction. The three main phases of the searching process for AMR.
algorithm stops iterating once the termination condition is
satisfied. In our study, it is terminated when a given time limit 2 We sincerely thank the anonymous reviewers who advised us to include the
has been reached. implementation steps of the proposed methods in this paper.
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

WANG et al.: ACO METHODS FOR SIMPLIFYING SOLUTION CONSTRUCTION IN VRPS 5

vehicles. For any arc (road) between two customers:

release phmin pheromone in order to trigger the ACO
system. The M ants, which move in parallel, are
initially moved to their first customers from the depot
with an equal probability. This amounts to placing
ants randomly at different customers.
Step 2: Solution Construction. For an arbitrary ant Ai , sup-
Fig. 2. Feasible solution construction from tabu of an ant. pose that it is located in customer c (or depot 0),
then, it selects the next customer j using the following
The tabu list for each ant indicates the visiting sequence of random proportional rule (1):
different customers, and it is of great importance for construct- ⎧ β
⎪
α
τc,j ×ηc,j
ing the final solutions. In an N -dimensional problem space, the ⎪ 
⎨ m∈T τc,m ×ηc,m
α β ,
i
tabu list can be defined as a 1-dimensional array with N digits. Pc,j =
⎪ where ACi ≥ Lj and ACi ≥ Lm
Unless noted otherwise, the problem scale is associated with N ⎪
⎩
customers in CVRP. Each element in the tabu list is initialized 0 others.
to be 0, representing that the corresponding customer has not The expression above has two fundamental parame-
been visited. When the ant arrives at a customer, the element in ters between customers c and j: the pheromone trail
the tabu is altered to be a non-zero value. The bigger the value intensity (τc,j ) and the visibility (ηc,j ). The visibility
is, the later the corresponding customer is visited. To decide the is a piece of heuristic information that shows the de-
next visiting customer, the ant will take into account of factors sirability of moving from one customer to another. In
such as the available capacity, the requirement of each customer ACO, the visibility value between a pair of customers
in the tabu list, and the distance. In this paper, ants are allowed is the inverse of their distance, ηc,j = 1/dc,j , where
to go back to the depot when it may fulfill the requirements of dc,j is the distance between customers c and j. So,
some customers, which will provide the diversity of solutions. if the distance between two customers is long, visiting
Also, when an ant gets back to the depot, it will be driven to customer j after customer i (or vice-versa) will be less
depart from the depot again if there is a zero-element in its tabu desirable. Once ant i is moving to a new customer j,
list. When an ant has visited all customers and returns to the the parameters such as ACi and Ti will be modified.
depot, the ant will stop moving, here we say that the ant runs An ant may encounter the following situation that
into the halting state. Since our method allows ants to go in and every Pj is 0, then, it will move to the depot 0. If
out the depot multiple rounds, we call the proposed algorithm the ant does not run into the halting state, it will
“AMR” (MR = Multiple Rounds). depart again according to the above random propor-
For any ant in the halting state, it is important to note that, tional rule, with its available capacity modified to the
its tabu list is not a permutation of N digits from 1 to N , in maximum value.
order to record the information of vehicle number and visiting Step 3: Pheromone Update. Pheromone update consists
sequence. Then, how to determine each element in the tabu list of three parts: local pheromone update, global
for an ant? Here, we give the rules for modifying tabu lists. pheromone update, and best solution strengthening.
Suppose that the ant has departed from the depot for i times, Once all ants move a hop (to a new position), the local
and has visited j customers after its departure from the depot pheromone update is applied. While once all ants
in this round, and the ant will destine for customer k from the generate a solution, that is, all ants run into the halting
current position, then the kth element in the tabu list is cal- state, the global pheromone updating rule is applied.
culated as ((i − 1) × N + j). Conversely, given an element p When a “best” solution in the current iteration is
in the tabu list, the corresponding customer will be serviced found, the pheromone along the path will be strength-
by vehicle (p/N  + 1), and its servicing sequence is (p%N ). ened, which will speed up the convergence. The
Fig. 2 shows an example of 8 customers with 3 vehicles. From pheromone updating rule is applied in two phases: an
the tabu we can compute the vehicle number and the servicing evaporation phase where a fraction of the pheromone
sequence for each customer. Take the customer 2 as an example, evaporates, and a reinforcement phase where each
its tabu element is 10, then its vehicle number is (10/8 + 1), ant deposits an amount of pheromone. To prevent
and its servicing sequence is (10%8). It is easy to find that the early convergence, the value of pheromone trails on
ant corresponding to the tabu yields a 3-vehicle solution: {(0-3- each solution is confined to the interval [τmin , τmax ]
5-7-0), (0-8-2-0), (0-6-4-1-0)}. according to [48].
Suppose that the load requirement at customer i (i = Generally speaking, the first step mainly focuses on the
1, 2, . . . , N ) is referred to Li in the following discussion, the initialization of ants and pheromone trail. Each ant builds a
procedure of the improved ACO is described in the following: complete feasible solution according to a probabilistic state
Step 1: Initialization. A colony of ants are initialized, Ai for transition rule, and is allowed to go in and out the depot for
i = 1, 2, . . . , M . Here M refers to the number of multiple times, until it has visited all customers. The local
traveling ants. For ant Ai , its tabu list Ti is initialized pheromone updating scheme is activated when all ants move
with each element set to zero; and its available capac- one hop. The global pheromone updating and best solution
ity ACi is set to the maximum capacity defined by strengthening are applied when all ants run into the halting
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

6 IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS

state. The processes are repeated until the stopping criterion

(such as the maximum iterating time) is met.

C. Further Extensions
Clarke and Wright suggest a simple method (called the sav-
ing algorithm) for optimally routing a fleet of vehicles in [49].
Variants of the saving method are proposed in the literature
[50], [51]. Besides, the saving algorithm can be combined
with other algorithms [51], [52] like meta heuristics, simulated
annealing, ACO, and genetic algorithm.
In order to further improve the performance, we propose two
extensions by introducing the saving algorithms into AMR. The
classical saving algorithm is adopted in computing the probabil-
ity of state transition. Usually, si,j = di,0 + d0,j − di,j , here,
di,j (di,0 ) denotes the distance between customers i and j
(the depot). Since a high value of si,j indicates that visiting
customer j after customer i is a desired choice, the tour length
is expected to be shorter if the probability of moving from
customer i to customer j increases with si,j . In this subsection,
we will propose a hybrid approach (AMR-SA) by combining
AMR with a saving algorithm, which differs from AMR in Fig. 3. Flowchart of AMR-SA-II.
the probabilistic state transition rule. In AMR-SA, the ant Ai
located at customer c selects the next customer j using the Obviously, AMR-SA-II is an extended version of AMR-SA.
following random proportional rule (2): There exist two types of ants in AMR-SA-II, and each type has
⎧ β γ
its own merits. The ordinary ants construct solutions with the
⎪
α
τc,j ×ηc,j ×θc,j
⎪
⎨ m∈T τc,mα ×η β γ capacity constraint, which helps to sample different areas of
c,m ×θc,m
Pc,j =
i
the whole search space. The special ants discard the capacity
⎪ where ACi ≥ Lj and ACi ≥ Lm
⎪
⎩ constraint and travel in the TSP manner, which helps to pick up
0 others. the “short path” between two customers and elapse pheromone
accordingly. Thus, the special ants help to exploit the local
The parameters τc,j and ηc,j are the same as that in AMR. As optima. Based on the above analysis, AMR-SA-II could further
for θc,j , it refers to the saving distance (sc,j ) between c and j. improve the overall performance of the algorithm. In order
Obviously, the design and implementation of AMR-SA are to establish a balance between exploration and exploitation
the same as that of AMR except for the random proportional efforts, the percentage of the special ants should be properly
rule used. In AMR-SA, the parameter of saving distance is determined.
included in the rule. To avoid repetition, we do not provide the
pseudo-code for AMR-SA.
D. Time Complexity
In both AMR and AMR-SA, when an ant selects the next
customer, the available capacity must be no less than the As discussed in Section II, the problem of constructing
requirement of the alternative customer. This strict constraint feasible solutions from ants’ route “parts” is NP-hard [34], [39].
limits the searching space of solutions, which further degrades In this subsection, we mainly discuss the time complexity of
the quality of solutions. As a further extension of AMR-SA, we the two-phase ACO heuristic (first-route-then-cluster) and our
introduce two types of ants in the algorithm: (1) the ordinary proposed methods (AMR, AMR-SA and AMR-SA-II).
ants that travel in the road network as stated above, and (2) the No matter in the two-phase ACO or in our proposed methods,
special ants that travel in the TSP manner. This extension is an each ant will visit all customers in the solution construction
enhancement of AMR-SA, and we call it AMR-SA-II. phase. In the two-phase ACO, the route path traveled by an ant
In AMR-SA-II, two types of ants (ordinary and special) are is decomposed into several small paths (one feasible solution)
introduced, and each type of ants route in their own manner. with the capacity constraint. The complexity of this process is
Fig. 3 shows the flow chart of the AMR-SA-II algorithm. o(n). The main difference between AMR and AMR-SA is the
The ordinary ants construct routes in the same manner as the random proportional rule used, while it has no impact on the
ants in AMR-SA. That is, the ordinary ants select the next time complexity. In AMR and AMR-SA, each ant has a tabu
customer based on the random proportional rule (2), with the with a length of n. Scanning the tabu from left to right, we can
available capacity constraint considered. In contrast, the special compute the vehicle number and the visiting sequence directly,
ants construct routes in the TSP manner, without considering and derive the final solution. Details about this process can be
the available capacity constraint. These two types of ants found in Section III. Clearly, the time complexity of this process
communicate with each other through depositing pheromone is also o(n). Therefore, AMR and AMR-SA have the same time
on the road. complexity as the two-phase ACO.
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

WANG et al.: ACO METHODS FOR SIMPLIFYING SOLUTION CONSTRUCTION IN VRPS 7

In AMR-SA-II, the ordinary ant travels in the same manner TABLE III
B ENCHMARK D ATA S ETS
as that in AMR-SA, while the special ant travels in the same
manner as that in ARC. Then, AMR-SA-II also shares the
same time complexity with AMR. In short, the overall time
complexity of the two-phase ACO and our proposed methods
are the same.

IV. R ESULTS AND A NALYSIS

After proposing and discussing the details of AMR-SA and
AMR-SA-II, we proceed to conduct the computational analysis.
All the heuristics are coded in C++ and run on a PC with the
Intel i7-4650U 1.70 GHz dual-core processor. The proposed
methods are tested on standard data-sets. In order to evaluate
the proposed algorithms, we compare with ACO adopting the
first-route-then-cluster scheme in [46]. For ease of descrip-
tion, the method of ACO adopting the first-route-then-cluster
scheme is abbreviated as ARC. For fairness, the specific
ARC also adopts a saving algorithm in its probabilistic state
transition rule. data sets, the comparison is equivalent between the proposed
algorithm and the exact algorithm. For those larger data sets,
A. Data Sets and Evaluation Metrics it’s reasonable to use the best known solution as a comparison
because there is no available global optimal solution provided
In the different ACO variations (AMR-SA, AMR-SA-II and by the exact algorithm. The relative percentage deviation of the
ARC), extensive simulations are conducted with different com- obtained best solution from the best known solution (RD1) for
binations of parameters so as to find suitable parameters. The different methods is calculated as follows:
best results are achieved with α = 1, β = 3, γ = 2, ρ = 0.15.
In AMR-SA-II, the percentage of ants traveling in a TSP Obtained best solution − Best known solution
RD1 = .
manner is chosen as 0.2. Since all the heuristics have the same Best known solution
time complexity, the elapsed time is chosen as the stopping Since ACO is a stochastic algorithm, several runs of the
condition in the experiments. Through observation on the test algorithm are usually performed for each testing instance. To
instances, we find that all heuristics converge within 10 seconds evaluate the stability of each ACO-based heuristic in this paper,
when the problem scale is no more than 40. When the problem the relative percentage deviation between solutions from all
scale grows to 75, the convergence time of these heuristics runs (RD2) is computed as follows:
is no more than 400 seconds. To have a fair comparison, the
elapsed times for all the heuristics are the same in each testing Mean of all solutions − Obtained best solution
RD2 = .
instance. Obtained best solution
For the purpose of verification, 13 standard data sets in-
The indicator RD2 provides additional information about the
cluding problem scale are listed in Table III. All these data
stability of an algorithm.
sets are publicly available on the web site: http://www.bernabe.
dorronsoro.es/vrp/. They have the following characters: 1) the
problem scale (NC) ranges from 15 to 75, with both small scale B. Comparisons on Standard Benchmarks
(problem scale < 30) problems and large scale (40 < problem Table IV summarizes results of ARC, AMR-SA, and AMR-
scale < 75) problems considered; 2) the number of vehicles SA-II for each data set. Each data set is run for 10 times, and
(NV) used in the data sets ranges from 2 to 14; 3) the data sets the obtained best results are reported in the table. Column 2 of
cover two types of vehicles, namely the small vehicles with a the table reports the best known results, and columns 3 and 4
capacity of 35 (or 40) and the large vehicles with a capacity of report the obtained results with ARC, and the last four columns
100 (or more). report the results obtained from our proposed heuristics (AMR-
Since our algorithms are heuristic in nature, we run the algo- SA and AMR-SA-II). The symbol (-) in the table means that
rithms for several times and use the best result of each data set no feasible solutions are found by the corresponding method.
as the obtained solution. The obtained best solution is taken as When the problem scale is no more than 50, the three heuristics
an evaluating metric for granted. To prove the effectiveness of have comparable results in all test cases except for cases 6
the proposed algorithm, we compare the obtained solution with and 7. In data set 6, the proposed AMR-SA and AMR-SA-II
the best known solution. The best known solution is provided give the solutions with 617.869 and 604.481, while ARC gives
by the exact algorithm or the heuristic algorithm, which means a much worse result of 641.862. Compared to ARC, we find
for larger data sets that the exact algorithm couldn’t give the that AMR-SA and AMR-SA-II can improve the results by 3.7%
global optimal solution in an acceptable time, the heuristic algo- and 5.8% in this test. For another special case (data set 7),
rithm is adopted to give the best known solution. For the smaller the proposed AMR-SA yields a solution with RD1 ≤ 0.014,
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

8 IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS

TABLE IV TABLE VI
R ESULTS ON THE S TANDARD D ATA S ETS S TABILITY S TATISTICS W ITH THE C ONSTRAINTS
OF M INIMAL N UMBER OF V EHICLES

TABLE VII
S TABILITY S TATISTICS W ITH R ESPECT TO THE R ELATIVE
P ERCENTAGE D EVIATION B ETWEEN S OLUTIONS (RD2)

TABLE V
R ESULTS W ITH V EHICLE C APACITY M ODIFIED TO 40

and AMR-SA-II gives the solution with RD1 ≤ 0.017, while

ARC could not find feasible solutions. When the problem scale
grows bigger, AMR-SA-II performs much better than ARC.
Take the data set 12 for example, the obtained best results D. Stability Comparisons
from ARC, AMR-SA and AMR-SA-II are 1312.295, 1275.222,
and 1222.447, respectively. When compared to ARC, we find As noted above, the algorithms run independently for
that AMR-SA-II and AMR-SA improve the results by 3.5% 10 times. First, we analyze the stability regarding the number
and 7.5% in the test case. In total, according to Table IV, the of vehicles required in different runs. We say that an algorithm
proposed AMR-SA-II obtains optimal solutions for almost all is stable if it always gives the solution with the same number of
CVRP data sets. Besides, the RD1 of AMR-SA-II is no more vehicles as defined in each simulation. As shown in Table VI,
than 1% in 7 cases, and is no more than 3% in 10 cases. Among ARC could not find feasible solutions with the constraint of
all the test cases, our proposed methods could always find minimal vehicles in three cases (no. 2, 3, 7). Another ob-
solutions for both small and large data sets, while the existing servation is that ARC could not find solutions in the worst
ARC method may fail in some cases. situations for all cases. Our proposed methods (AMR-SA and
AMR-SA-II) could always find optimal solutions in all runs for
all cases. This means that the proposed methods are more stable
in dealing with different benchmark instances.
C. Impacts of Vehicle Capacity
Besides, the relative percentage deviation between solutions
In this subsection, we study the impact of vehicle capacity (RD2) provides additional information about the stability with
on the efficiency of the three methods. The load capacity is the respect to the solution quality. Table VII shows the RD2
set to be 40, and we select those benchmarks in which each for different algorithms. As reported in the table, the RD2s of
customer has the requirement with no more than 40. The results AMR-SA-II are ≤ 0.01 in 10 cases, and are ≤ 0.039 in all
are presented in Table V. It can be seen that ARC can give cases. As for AMR-SA, the RD2s are ≤ 0.01 in 9 cases, and are
the optimal solution in only 3 cases, which could not find any ≤ 0.042 in all cases. As for ARC, the RD2 varies from 0.001 to
feasible solution in the remaining ones. However, the proposed 0.061. The average RD2s of ARC, AMR-SA-II and AMR-SA
AMR-SA and AMR-SA-II could perfectly adapt to the capacity are 0.029, 0.019, and 0.021, respectively. Therefore, from the
change. Thus, the proposed algorithms are more robust than the perspective of RD2, our proposed methods are more stable than
traditional method. the existing ARC algorithm.
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

WANG et al.: ACO METHODS FOR SIMPLIFYING SOLUTION CONSTRUCTION IN VRPS 9

V. C ONCLUSION [10] J. Lysgaard and S. Wohlk, “A branch-and-cut-and-price algorithm for the

cumulative capacitated vehicle routing problem,” EURO J. Oper. Res.,
CVRP is among the most widely studied and the hardest vol. 236, no. 3, pp. 800–810, 2014.
combinatorial optimization problems in transportation systems. [11] M. Battarra, G. Erdogan, and D. Vigo, “Exact algorithms for the clustered
vehicle routing problem,” Operat. Res., vol. 62, no. 1, pp. 58–71, 2014.
From a theoretical point of view, CVRP is NP-hard. Conse- [12] J. C. Rivera, H. M. Afsar, and C. Prins, “Mathematical formulations and
quently, no exact algorithm is expected to solve the problem exact algorithm for the multitrip cumulative capacitated single-vehicle
in a polynomial time. ACO is a powerful heuristic for tackling routing problem,” Eur. J. Oper. Res., vol. 249, no. 1, pp. 93–104, 2015.
[13] G. Laporte, F. V. Louveaux, and L. V. Hamme, “An integer l-shaped
this problem. Each ant is viewed as a vehicle with a constant algorithm for the capacitated vehicle routing problem with stochastic
capacity. It departs from the depot, visits some (not all) cus- demands,” Oper. Res., vol. 50, no. 3, pp. 415–423, 2002.
[14] C. Prins, N. Labadi, and M. Reghioui, “Tour splitting algorithms for vehi-
tomers, and then gets back to the depot. Therefore, an ant’s cle routing problems,” Int. J. Prod. Res., vol. 47, no. 2, pp. 507–535, 2009.
path is only a “part” of a feasible solution. In other words, one [15] A. M. Campbell and M. Savelsbergh, “Efficient insertion heuristics for
feasible solution usually consists of several ants’ paths. Thus vehicle routing and scheduling problems,” Transp. Sci., vol. 38, no. 3,
pp. 369–378, 2004.
traditionally, the process of constructing feasible solutions from [16] H. C. W. Lau, T. Chan, W. T. Tsui, and W. K. Pang, “Application of genetic
ants’ paths is identical to the NP-hard set covering problem. algorithms to solve the multidepot vehicle routing problem,” IEEE Trans.
In this paper, we develop a novel algorithm (AMR) in which Autom. Sci. Eng., vol. 7, no. 2, pp. 383–392, Apr. 2010.
[17] R. Liu, Z. Jiang, and N. Geng, “A hybrid genetic algorithm for the
ants are allowed to go in and out the depot several times. The multi-depot open vehicle routing problem,” OR Spectr., vol. 36, no. 2,
path of each ant in AMR corresponds to one feasible solution, pp. 401–421, 2014.
thus the NP-hard set covering problem is avoided. Moreover, [18] Y. J. Gong et al., “Optimizing the vehicle routing problem with time
windows: A discrete particle swarm optimization approach,” IEEE
we propose two extensions to further enhance the performance Trans. Syst., Man, Cybern. C, Appl. Rev., vol. 42, no. 2, pp. 254–267,
of AMR. One is AMR-SA, which integrates AMR with a saving Mar. 2012.
algorithm. The other one is AMR-SA-II, which introduces [19] R. Kuo, F. Zulvia, and K. Suryadi, “Hybrid particle swarm optimization
with genetic algorithm for solving capacitated vehicle routing problem
two types of ants in AMR-SA. Computational experiments with fuzzy demand—A case study on garbage collection system,” Appl.
on standard benchmarking instances show that the proposed Math. Comput., vol. 219, no. 5, pp. 2574–2588, Nov. 2012.
algorithms are much more efficient and stable than the existing [20] S. Khebbache-Hadji, C. Prins, A. Yalaoui, and M. Reghioui, “Heuristics
and memetic algorithm for the two-dimensional loading capacitated ve-
method (ARC). hicle routing problem with time windows,” Central Eur. J. Oper. Res.,
We only apply our algorithm to CVRP which contains a few vol. 21, no. 2, pp. 307–336, 2013.
computational limitations. We do not prove that the proposed [21] K. V. Narasimha, E. Kivelevitch, B. Sharma, and M. Kumar, “An
ant colony optimization technique for solving min-max multi-depot
scheme is efficient as well in other CVRP variants (such as vehicle routing problem,” Swarm Evol. Comput., vol. 13, pp. 63–73,
VRPTW, MDVRP). Our future research work will be based Dec. 2013.
[22] A. Stenger, D. Vigo, S. Enz, and M. Schwind, “An adaptive variable
on those VRP variants. Besides, this paper mainly focuses on neighborhood search algorithm for a vehicle routing problem arising in
simplifying the process of constructing feasible solutions, but small package shipping,” Transp. Sci., vol. 47, no. 1, pp. 64–80, 2013.
not on improving the solution quality. Hence, we do not use any [23] L. Wei, Z. Zhang, and A. Lim, “An evolutionary local search for
the capacitated vehicle routing problem minimizing fuel consumption
local search techniques to improve the solution quality. Another under three-dimensional loading constraints,” Transp. Res. B, Methodol.,
future plan is to combine local searching schemes and the pro- vol. 82, pp. 20–35, 2015.
posed AMR to potentially obtain heuristically better solutions. [24] U. Benlic and J.-K. Hao, “Memetic search for the quadratic assignment
problem,” Expert Syst. Appl., vol. 42, no. 1, pp. 584–595, 2015.
[25] C. Blum, J. Puchinger, G. R. Raidl, and A. Roli, “Hybrid metaheuristics
in combinatorial optimization: A survey,” Appl. Soft Comput., vol. 11,
R EFERENCES no. 6, pp. 4135–4151, 2011.
[26] [Online]. Available: http://www.bernabe.dorronsoro.es/vrp/
[1] T. Van Woensel, L. Kerbache, H. Peremans, and N. Vandaele, “Vehicle [27] M. Dorigo and L. Gambardella, “Ant colony: A cooperative learning
routing with dynamic travel times: A queueing approach,” Eur. J. Oper. approach to the travelling salesman problem,” IEEE Trans. Evol. Comput.,
Res., vol. 186, pp. 990–1007, 2008. vol. 1, no. 1, pp. 53–66, Apr. 1997.
[2] S. Kim, M. E. Lewis, and C. C. White Iii, “Optimal vehicle routing with [28] M. Dorigo and C. Blum, “Ant colony optimization theory: A survey,”
real-time traffic information,” IEEE Trans. Intell. Transp. Syst., vol. 6, Theoretical Comput. Sci., vol. 344, no. 1, pp. 243–278, 2005.
no. 2, pp. 178–188, Jun. 2005. [29] M. Dorigo, M. Birattari, and T. Stutzle, “Ant colony optimization-artificial
[3] T. Rajabioun and P. Ioannou, “On-street and off-street parking availability ants as a computational intelligence technique,” IEEE Comput. Intell.
prediction using multivariate spatiotemporal models,” IEEE Trans. Intell. Mag., vol. 1, no. 4, pp. 28–39, Nov. 2006.
Transp. Syst., vol. 16, no. 5, pp. 2913–2924, Oct. 2015. [30] P. Paola, S. Thomas, and B. Mauro, “A critical analysis of parameter
[4] C. Archetti and M. Grazia Speranza, “A survey on matheuristics for adaptation in ant colony optimization,” Swarm Intell., vol. 6, no. 1,
routing problems,” EURO J. Comput. Optim., vol. 2, no. 4, pp. 223–246, pp. 23–48, 2012.
2014. [31] L. Wu and W. Fan, “A parameter model of genetic algorithm regulating
[5] L. Gilbert, T. Paolo, and V. Daniele, “Vehicle routing: Historical perspec- ant colony algorithm,” in Proc. IEEE 10th Int. Conf. e-Business Eng.,
tive and recent contributions,” EURO J. Transp. Logistics, vol. 2, no. 1/2, Hangzhou, China, 2012, pp. 50–54.
pp. 1–4, 2013. [32] M. Mavrovouniotis and S. Yang, “Ant algorithms with immigrants
[6] H. F. Wedde and S. Senge, “Beejama: A distributed, self-adaptive vehicle schemes for the dynamic vehicle routing problem,” Inf. Sci., vol. 294,
routing guidance approach,” IEEE Trans. Intell. Transp. Syst., vol. 14, pp. 456–477, 2015.
no. 4, pp. 1882–1895, Dec. 2013. [33] B. Yu, Z. Z. Yang, and J. X. Xie, “A parallel improved ant colony
[7] S. Almoustafa, S. Hanafi, and N. Mladenovi, “New exact method for large optimization for multi-depot vehicle routing problem,” J. Oper. Res. Soc.,
asymmetric distance-constrained vehicle routing problem,” Eur. J. Oper. vol. 62, no. 1, pp. 183–188, 2011.
Res., vol. 226, no. 3, pp. 386–394, 2013. [34] J. Cruz, C. Paternina-Arboleda, V. Cantillo, and J. Montoya-Torres,
[8] F. Liberatore, G. Righini, and M. Salani, “A column generation algorithm “A two-pheromone trail ant colony system-tabu search approach for the
for the vehicle routing problem with soft time windows,” 4OR Quart. J. heterogeneous vehicle routing problem with time windows and multiple
Belgian French Italian Oper. Res. Soc., vol. 9, no. 1, pp. 49–82, 2011. products,” J. Heuristics, vol. 19, no. 2, pp. 233–252, 2013.
[9] M. Fischetti, P. Toth, and D. Vigo, “A branch-and-bound algorithm for [35] O. Baskan, S. Haldenbilen, H. Ceylan, and H. Ceylan, “A new solution
the capacitated vehicle routing problem on directed graphs,” Oper. Res., algorithm for improving performance of ant colony optimization,” Appl.
vol. 42, no. 5, pp. 846–859, 1994. Math. Comput., vol. 211, pp. 75–84, 2009.
 This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

10 IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS

[36] A. E. Rizzoli, R. Montemanni, E. Lucibello, and L. M. Gambardella, Tsan-Ming Choi received his Ph.D. from
“Ant colony optimization for real-world vehicle routing problems,” The Chinese University of Hong Kong.
Swarm Intell., vol. 1, no. 2, pp. 135–151, 2007. He is currently a Professor of Fashion Business
[37] B. Shuang, J. Chen, and Z. Li, “Study on hybrid PS-ACO algorithm,” with the Institute of Textiles and Clothing, The
Appl. Intell., vol. 34, no. 1, pp. 64–73, Feb. 2011. Hong Kong Polytechnic University, Hung Hom,
[38] I. Ciornei and E. Kyriakides, “Hybrid ant colony-genetic algorithm Hong Kong. Over the past few years, he has ac-
(GAAPI) for global continuous optimization,” IEEE Trans. Syst., Man, tively participated in a variety of research projects in
Cybern. B, Cybern., vol. 42, no. 1, pp. 234–245, Feb. 2012. supply chain optimization and applied optimization.
[39] J. Tang, J. Guan, Y. Yu, and J. Chen, “Beam search combined with max- He is the author or editor of 15 research handbooks
min ant systems and benchmarking data tests for weighted vehicle routing and over 120 papers in Thomson Web of Science
problem,” IEEE Trans. Autom. Sci. Eng., vol. 11, no. 4, pp. 990–1007, listed journals, such as IEEE T RANSACTIONS ON
Oct. 2014. AUTOMATIC C ONTROL, IEEE T RANSACTIONS ON AUTOMATION S CI -
[40] C. Y. Lee, Z. J. Lee, S. W. Lin, and K. C. Ying, “An enhanced ant colony ENCE AND E NGINEERING, IEEE T RANSACTIONS ON C YBERNETICS , IEEE
optimization (EACO) applied to capacitated vehicle routing problem,” T RANSACTIONS ON E NGINEERING M ANAGEMENT, IEEE T RANSACTIONS
Appl. Intell., vol. 32, no. 1, pp. 88–95, Feb. 2010. ON I NDUSTRIAL I NFORMATICS , IEEE T RANSACTIONS ON I NTELLIGENT
[41] S. Balseiro, I. Loiseau, and J. Ramonet, “An ant colony algorithm hy- T RANSPORTATION S YSTEMS , IEEE T RANSACTIONS ON S YSTEMS , M AN ,
bridized with insertion heuristics for the time dependent vehicle rout- AND C YBERNETICS , Automatica, Production and Operations Management,
ing problem with time windows,” Comput. Oper. Res., vol. 38, no. 6, Naval Research Logistics, INFORMS Service Science, European Journal of
pp. 954–966, 2011. Operational Research, Transportation Research—Part E, Decision Support
[42] T. Zhang, W. Chaovalitwongse, and Y. Zhang, “Integrated ant colony Systems, Omega, etc.
and tabu search approach for time dependent vehicle routing problems Prof. Choi currently serves as a Senior Editor for Production and Operations
with simultaneous pickup and delivery,” J. Combinatorial Optim., vol. 28, Management, and Decision Support Systems, as an Associate Editor for IEEE
no. 1, pp. 288–309, 2014. T RANSACTIONS ON S YSTEMS , M AN , AND C YBERNETICS —S YSTEMS , an
[43] M. Alobaedy and K. Ku-Mahamud, “New heuristic function in ant colony editorial board member for Transportation Research—Part E, and a Guest
system for the travelling salesman problem,” in Proc. Int. Conf. Comput. Editor for Risk Analysis. He received the Best Associate Editor Award of the
Convergence Technol., Seoul, South Korea, 2012, pp. 965–969. IEEE Systems, Man, and Cybernetics Society in two consecutive years (2013
[44] H. Peter and R. David, “Maximally disjoint solutions of the set covering and 2014). Most recently, he and his collaborators received The Second Prize
problem,” J. Heuristics, vol. 7, no. 2, pp. 131–144, 2001. of Natural Science Award from Ministry of Education of China in 2016.
[45] B. Roberto, T. Paolo, and V. Daniele, “Exact algorithms for routing prob-
lems under vehicle capacity constraints,” Ann. Oper. Res., vol. 175, no. 1,
pp. 213–245, 2010.
[46] T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins, “Heuristics for multi-
attribute vehicle routing problems: A survey and synthesis,” Eur. J. Oper. Haikuo Liu currently pursuing his Bachelor of
Res., vol. 231, no. 1, pp. 1–21, 2013. Management degree with the Department of Man-
[47] F. Tao, Y. Laili, Y. Liu, and Y. Feng, “Concept, principle and application agement Science and Engineering, Dongbei Univer-
of dynamic configuration for intelligent algorithms,” IEEE Syst. J., vol. 8, sity of Finance and Economics, Dalian, China.
no. 1, pp. 28–42, Mar. 2014. His research interests include operations manage-
[48] T. Stutzle and H. Hoos, “Max-min ant system,” Future Gener. Comput. ment and optimization.
Syst., vol. 16, no. 8, pp. 889–914, 2000.
[49] G. Clarke and W. Wright, “Scheduling of vehicles from a central depot to
a number of delivery points,” Oper. Res., vol. 12, pp. 568–581, 1964.
[50] S. P. Anbuudayasankar, K. Ganesh, S. C. L. Koh, and Y. Ducq, “Modified
savings heuristics and genetic algorithm for bi-objective vehicle rout-
ing problem with forced backhauls,” Expert Syst. Appl., vol. 39, no. 3,
pp. 2296–2305, Feb. 2012.
[51] M. Stanojevic, B. Stanojevic, and M. Vujosevic, “Enhanced savings cal-
culation and its applications for solving capacitated vehicle routing prob- Xiaohang Yue received the Ph.D. degree from the
lem,” Appl. Math. Comput., vol. 219, no. 20, pp. 10, pp. 10 302–10 312, University of Texas at Dallas, Richardson, TX, USA.
Jun. 2013. He is currently an Associate Professor with the
[52] B. Catay, “A new saving-based ant algorithm for the vehicle routing Sheldon B. Lubar School of Business School of
problem with simultaneous pickup and delivery,” Expert Syst. Appl., Business, the University of Wisconsin–Milwaukee,
vol. 37, no. 10, pp. 6809–6817, Oct. 2010. Milwaukee, WI, USA. He has published extensively
in leading journals such as IEEE T RANSACTIONS
ON E NGINEERING M ANAGEMENT, IEEE T RANS -
ACTIONS ON AUTOMATION S CIENCE AND E NGI -
NEERING , IEEE T RANSACTIONS ON S YSTEMS ,
Xinyu Wang received the Ph.D. degree from M AN , AND C YBERNETICS : S YSTEMS , IEEE
Tsinghua University, Beijing, China. T RANSACTIONS ON C YBERNETICS , IIE Transactions, Production and Oper-
She is currently a Lecturer with the Department ations Management, Naval Research Logistics, Decision Sciences, European
of Management Science and Engineering, Dongbei Journal of Operational Research, Omega, etc. His research interests include
University of Finance and Economics, Dalian, China. supply chain and logistics systems management, and industrial manufacturing
Her research interests include information process- systems management.
ing, decision-making, and operational management. Dr. Yue is a member of American Association of Supply Chain Manage-
ment, and the Institute for Operation Research and the Management Sciences
(INFORMS). He has served as an editorial board member for Production and
Operations Management.