An Efficient ACO+RVND for Solving the Resource-Constrained Deliveryman Problem

Ha-Bang Ban School of Information and Communication Technology Hanoi University of Science and Technology

Abstract

In this paper, Resource-Constrained Deliveryman
Problem (RCDMP) is introduced. The RCDMP problem deals
with finding a tour with minimum waiting time sum so that
it consumes not more than ???????????????? units of resources, where
???????????????? is some constant. Recently, an algorithm developed in a
trajectory-based metaheuristic has been proposed. Since the
search space of the problem is a combinatorial explosion,
the trajectory-based sequential can only explore a subset of
the search space, therefore, they easily fall into local optimal
in some cases. To overcome the drawback of the current
algorithms, we propose a population-based algorithm that
combines an Ant Colony Algorithm (ACO), and Random
Variable Neighborhood Descent (RVND). In the algorithm, the
ACO explores the promising solution areas while the RVND
exploits them with the hope of improving a solution. Extensive
numerical experiments and comparisons with the state-of-theart metaheuristic algorithms in the literature show that the
proposed algorithm reaches better solutions in many cases.