An efficient ACO+RVND for solving the resource-constrained deliveryman problem

   
7DEOH7KHH[SHULPHQWDOUHVXOWVIRU'03LQVWDQFHV
,QVWDQFHV
*5$63±91' *5$63±916 *916 *916 765916 2XUDOJRULWKP
gap
>@ T
gap
>@ T
gap
>@ T
gap
>@ T gap>@ T gap>@ T
            
            
            
            
            
            
            
,PSURYHGJDSLVKLJKOLJKWHGLQEROGIDFH
7DEOH7KHH[SHULPHQWDOUHVXOWVIRUWKHLQVWDQFHVLQ763/,%
,QVWDQFHV UB 2XUDOJRULWKP
Best.Sol Aver.Sol T
GDQW]LJ 
   DWW 
   HLO 
   EHUOLQ 
   VW 
   .UR$ 
  .UR& 
  .UR' 
  (LO   3U  /LQ   

 WKHRSWLPDOYDOXHV
7DEOH&RPSDULVRQRIWKHRSWLPDOVROXWLRQIRUWKH'03ZLWKWKHEHVWIRXQG
&5'03VROXWLRQXVLQJWKH&5'03REMHFWLYHIXQFWLRQ
LQVWDQFHV Į  Į  Į  Į GLII IHDVLELOLW\ GLII IHDVLELOLW\ GLII IHDVLELOLW\ GLII IHDVLELOLW\
WHVW[  1R  1R  1R  1R
WHVW[  1R  1R  1R  1R
This configuration determined in multiple combinations are
tested and the one who has presented the best solution
is chosen. In Table 1, we define a range for each of
the five parameters that yields 1200 different parameter
combinations and run the algorithm for some selected
instances of these combinations. Each run is limited to 1000
iterations but was stopped when the best-known solution
is found. This exhaustive search for the best parameter
combinations is useful as a benchmark for evaluating the
algorithm. Looking at the parameter combinations, we find
the following settings so that our algorithm obtains the best
solutions: 𝛽𝑟 = 5, 𝛽𝜂 = 5, 𝛼 = 1, 𝑝 = 1, and 𝜏0 = 10.
Lastly, the last aspect to discuss is the stop criterium of the
algorithm. The parameter m is set to 10 to balance between
38
Vol. 2020, No. 01, September
TABLE I
THE VARIABLE PARAMETERS
Parameter Value Range
𝛽𝑟 0 ≤ 𝛽𝑟 ≤ 10, incremented by 0.25
𝛼 0.5 ≤ 𝛼 ≤ 1.5, incremented by 0.25
𝛽𝜂 0 ≤ 𝛽𝜂 ≤ 10, incremented by 0.25
𝜏0 0 ≤ 𝜏0 ≤ 20, incremented by 5
𝑝 0.3 ≤ 𝑝 ≤ 1, incremented by 0.2
computation time and efficiency. This parameter setting has
thus been used in the following experiments.
2. Bounds
To evaluate the efficiency of the metaheuristic algorithm,
its solution can be compared to 1) the optimal solution
(OPT); and 2) a good upper bound (UB). We define the
improvement of our algorithm with respect to Best.Sol
(Best.Sol is the best solution found by our algorithm)
in comparison with the optimal solution (𝑔𝑎𝑝1 [%]), and
upper bound (𝑔𝑎𝑝2 [%]) in percent respectively as follows:
𝑔𝑎𝑝1 [%] = 𝐵𝑒𝑠𝑡.𝑆𝑜𝑙 − 𝐿𝐵
𝐿𝐵
× 100% (8)
𝑔𝑎𝑝2 [%] = 𝐵𝑒𝑠𝑡.𝑆𝑜𝑙 −𝑈𝐵
𝑈𝐵
× 100% (9)
We choose several state-of-the-art metaheuristic algorithms
for RCDMP, and DMP [4, 17, 19] as a baseline in our
research. Note that: The value of LB is described in [17]
while the value of UB is given by the algorithm in [4].
3. Results and Comparative Analysis
The tables present Best.Sol, Aver.Sol, and T, respectively.
Tables from 2 to 5 compare the results of our algorithm with
the solutions obtained by Ban et al. [4] for the RCDMP-
instances. Column TS in Tables 2 to 5 corresponds to
the best solution of Tabu Search [4]. Column 𝛼 is cor-
responding to the results with different resource constraint
values. The results in Table 6, which are the average values
calculated from Table 2 to 5. Tables 7 to 8 compare
our algorithm with the state-of-the-art metaheusitics in
terms of 𝑔𝑎𝑝2 for DMP-instances. Table 9 compares the
optimal solutions with the best-found CRDMP-solutions
using the CRDMP objective function. For DMP-instances,
the optimal solutions are extracted from the exact algorithm
in [2].
Tables 2 to 5 compare the results obtained by Ban et al.
[4] to our algorithm for 320 instances. The results show
that our algorithm reaches better solutions at a reasonable
amount of time. Regarding the average 𝑔𝑎𝑝2 in Table 6,
our algorithm quality improves 7.20% compared with Ban
et al.’s algorithm [4]. The improvement is significant since
it can be observed that our algorithm is capable of finding
the new best solutions for the 303 RCDMP-instances. Note
that: the found-best solutions is highlighted in bold line.
Table 7 compares the results of our algorithm with the
lower bounds obtained from [19] with 100, 200, 500, and
1000 vertices for DMP. Our algorithm gives much better
solutions than those of GVNS-1 [17], GRASP-VND and
GRASP-VNS [19] for all instances. In comparison with
GVNS-2 [17], and TS [3], for most cases, our algorithm
gives the same results.
Table 8 presents the average results of our algorithm
on instances with up to 150 vertices selected from the
TSPLIB [23]. These solutions are compared with optimal
values, found by Abeledo et al. [1]. It is noteworthy that
our algorithm obtains the optimal solutions with up to
100 vertices such as KroA100, KroB100, KroC100, and
KroD100 at reasonable amount of time. The experimental
results show that the proposed algorithm can be applied
well to the DMP (note that: the DMP is another variant of
the RCDMP when resource limit is ignored), though it is
not designed to solve it. Therefore, our algorithm can easily
adapt to similar variants of the problem.
Table 9 shows that the optimal solutions for the DMP
are generally not good solutions to the CRDMP on the
same instance. Specifically, our algorithm is better than the
optimal solution for the DMP using the CRDMP objective
function since the difference between their objective values
is up to 6.24%. Although the difference is not large, all
these optimal solutions for the DMP are not feasible solu-
tions for the CRDMP. Therefore, the methods designed for
the DMP may not be adapted easily to solve the CRDMP.
Developing an algorithm for the CRDMP is very necessary.
The average scaled running time of our algorithm is
better than those of A. Salehipour et al.’s [19], and grow
quite moderate with the one of Mladenovic et al.’s [17] and
Ban et al.’s algorithm [4].
IV. DICUSSIONS
In general, metaheuristic is a suitable approach for
solving the NP-hard problems in short computation time.
Recently, a metaheuristic for solving the problem has been
proposed. The algorithm is developed in a sequential heuris-
tic approach which starts with a single initial solution, and
at each step of the search, the current solution is replaced
by another solution found in its neighborhood. Since the
search space of the problem is a combinatorial explosion,
these algorithms only explore a subset of the search space.
Therefore, they can easily fall into the local optimal in
some cases. Our hybrid algorithm that brings together the
components of the ACO, and RVND can overcome this
39
Research and Development on Information and Communication Technology
drawback by searching from multiple promising solution
areas, thus, its exploring search space is extended. As a
result, the chances of finding better solutions are higher. To
summarize, our scheme includes new features as follows:
• Two kinds of ants coexist in the ACO. The ant group
that includes the dull ants can obtain more foods than
the group consisting of only the intelligent ants. It is
suitable in the real ant’s world.
• Every search algorithm needs to address the explo-
ration and exploitation of a search space. Exploration is
the process of visiting entirely new regions of a search
space, whilst exploitation is the process of visiting
those regions of a search space within the neighbor-
hood of previously visited points. To be successful,
a search algorithm needs to establish a good ratio
between exploration and exploitation. The ACO is also
combined with the RVND to keep a balance between
exploration and exploitation. In this combination, the
ACO allows us to explore the promising solution
spaces while the RVND based on a simple principle of
systematic switches between different neighborhoods
to exploit in these spaces.
Our experiments not only prove these expectations but
also indicate that this approach finds the new best known
solutions in the 303 instances in comparison with the-
state-of-art metaheuristic. Moreover, our experiments show
that the methods designed for the DMP [3, 17, 19] may
not be adapted easily to solve the CRDMP since the
optimal solutions for the DMP are infeasible solutions for
the CRDMP. Therefore, it is important for developing a
metaheuristic for the CRDMP .
We discuss more about some optimization techniques
based on swarm intelligence. There are many optimiza-
tion techniques such as Genetic Algorithm [9], Particle
Swarm Optimization (PSO) [12], Artificial Bee Colony
(ABC) [11], and Cuckoo Search (CS) [20], etc. In fact,
no optimization technique is better than the others in all
cases. However, in the paper, the ACO algorithm is used
to solve the problem because: 1) the field of ACO has
attracted a large number of researchers, and nowadays a
large number of research results of both experimental and
theoretical nature exists; 2) Its efficiency is demonstrated
through solving the other variants of problem (Traveling
Salesman Problem (TSP) [22], Vehicle Routing Problem
(VRP) [18], ...); 3) it is very understandable and fast to
implement.
V. CONCLUSIONS
In this paper, we propose the metaheuristic algorithm
which is mainly based on the principles of the ACO,
and RVND to solve the problem. Extensive numerical
experiments on benchmark instances show that on average,
our algorithm finds the new best solutions in 303 instances.
For close variants of the problem, our algorithm can reach
the optimal solutions for the problems with 100 vertices in
a reasonable amount of time. When the problem size is too
large, it takes longer time to operate the whole algorithm,
lowering the efficiency of finding the optimum. In these
cases, to reduce the running time, parallelizing ACO [14]
and divide and conquer ACO [13] can be applied to large-
scale instances. This is a topic for future research.
ACKNOWLEDGEMENT
This research is funded by Hanoi University of Science
and Technology (HUST) under grant number T2017-PC-
082.
REFERENCES
[1] H.G. Abeledo and G. Fukasawa and R. Pessoa and A.
Uchoa, “The Time dependent Traveling Salesman Prob-
lem: Polyhedra and Branch-cut-and price Algorithm",
J. Math. Prog. Comp., Vol. 5, No. 1, 2013, pp. 27-55.
[2] H.B. Ban, K. Nguyen, M.C. Ngo, and D.N. Nguyen,
“An Efficient Exact Algorithm for Minimum Latency
Problem", J. PI, No. 10, 2013, pp. 1-8.
[3] H.B. Ban, and D.N. Nguyen, ”A Meta-Heuristic Algo-
rithm Combining between Tabu and Variable Neigh-
borhood Search for the Minimum Latency Problem",
J. FI, Vol. 156, No. 1, 2017, pp. 21-41
[4] H.B. Ban, “Using Metaheuristic for Solving the
Resource-Constrained Deliveryman Problem", Proc.
SOICT, 2019, pp. 917-935.
[5] A. Lucena, “Time-dependent Traveling Salesman
Problem-the Deliveryman case", J. Networks, Vol. 20,
No. 6, 1990, pp. 753-763.
[6] A. Blum, P. Chalasani, D. Coppersmith, W. Pulley-
blank, P. Raghavan, and M. Sudan, “The Minimum
Latency Problem", Proc. STOC, 1994, pp. 163-171.
[7] M. Dorigo, and T. Stutzle, “Ant Colony Optimization",
Bradford Books, London, 2004.
[8] M. Fischetti, G. Laporte, S. Martello, “The Delivery-
man Problem and Cumulative Matroids", J. Oper Res,
Vol. 41, No. 6, 1993, pp. 1055–1064.
[9] D. E. Goldberg, "Genetic Algorithms in Search, Op-
timization, and Machine Learning", Addison-Wesley,
Reading, Massachusetts, 1989.
[10] H. Hasegawa, “Optimization of GROUP behavior,
Japan Ethological Society Newsletter", Vol. 43, 2004,
pp. 22-23.
40
Vol. 2020, No. 01, September
[11] D. Karaboga, “An Idea Based on Honeybee Swarm
for Numerica Optimization”, Technical Report TR06,
Erciyes University, 2005.
[12] J. Kennedy, R. Eberhart, “Particle Swarm Optimiza-
tion”, Conf. Neural Networks, 1995, pp. 1942–1948.
[13] X. Li, J. Liao, and M. Cai, “Ant Colony Algorithm for
Large Scale TSP”, Proc. ICECING, 2011, pp.573-576.
[14] M. Manfrin, M. Birattari, T. Stu¨tzle, and Marco
Dorigo, “Parallel Ant Colony Optimization for the
Traveling Salesman Problem”, Proc. ANTS, 2006, pp
224-234.
[15] I. Mendez-Diaz, P. Zabala, A. Lucena, “A New For-
mulation for the Traveling Deliveryman Problem", J.
Discret Appl Math, No. 156, 2008, pp. 3223-3237.
[16] N. Mladenovic, P. Hansen, “Variable Neighborhood
Search", J. Operations Research, Vol. 24, 1997, pp.
1097-1100.
[17] N. Mladenovic, D. Urosevi, and S. Hanafi, “Variable
Neighborhood Search for the Travelling Deliveryman
Problem", J. 4OR, Vol. 11, 2012, pp. 1-17.
[18] M. Reimann, K. Doerner, and R.F. Hartl, “Analyzing
a Unified Ant System for the VRP and Some of Its
Variants”. S. Cagnoni et al. (Eds.): EvoWorkshops,
LNCS, pp. 300-310, 2003.
[19] A. Salehipour, K. Sorensen, P. Goos, and O.Braysy,
“Efficient GRASP+VND and GRASP+VNS meta-
heuristics for the Traveling Repairman Problem", J.
Operations Research, Vol. 9, No. 2, 2011, pp. 189-209.
[20] XS. Yang, S. Deb, “Cuckoo Search Via Levy Flights”,
Proc. NaBIC, 2009, pp. 210–214.
[21] D. S. Johnson, and L. A. McGeoch, “The Traveling
Salesman Problem: A Case Study in Local Optimiza-
tion in Local Search in Combinatorial Optimization",
E. Aarts and J. K. Lenstra, eds., 1997, pp. 215-310.
[22] H. X. Huan, N. Linh-Trung, D. Duc-Dong, and T.
Huynh, “Solving the Traveling Salesman Problem with
Ant Colony Optimization: A Revisit and New Efficient
Algorithms”, J. REV, Vol. 2, No. 3–4, 2012, pp. 121-
129.
[23] 
testdata/tsp/tsplib/tsplib.html.
Ha-Bang Ban Ha-Bang Ban received his
B.E. in Information Technology, and Ph.D
in Computer Science at Hanoi University of
Science and Technology (HUST), Vietnam
in 2006, 2015, respectively. He is currently
a lecturer at the School of Information
and Communication Technology (SOICT),
HUST, Vietnam. Research interests of Dr.
Ban include algorithms, graphs, optimization, and logistics, etc.
He has published many publications in peer-reviewed international
journals and conferences.
41