Abstract:
The Vehicle Routing Problem (VRP) and its variants thereof are classical problems in
computer science with diverse applications. The vehicle routing problem seeks to serve
a number of customers with a
eet of vehicles. It can be described as the problem of
designing optimal delivery or collection routes from one or several depots to a number
of geographically scattered customers, subject to several constraints. It has been used
to model various transportation and distribution related processes. Many other practical
applications nd the need for satisfying additional constraints and these necessities lead
to many variants and extensions of VRP problems, which are complex to solve.
Due to the wide applicability and economic importance, the Vehicle Routing Problem
with Time Windows (VRPTW) as well as its di erent variants has been extensively studied
in computer science and transportation engineering literature. The vehicle routing
problem with time windows consists of computing a minimum cost set of routes for a
eet of vehicles of limited capacity visiting a given set of customers with known demand,
with the additional constraint that each customer must be visited within a speci c time
window.
Vehicle Routing Problem with Soft Windows (VRPSTW) is a relaxation of Vehicle
Routing Problem with Hard Time Windows (VRPHTW)- in the former time window can
be violated if a penalty is paid, whereas, in the latter, violations are not allowed. We
consider the case in which time window constraints are relaxed into \soft" constraints,
that is, penalty terms are added to the solution cost whenever a vehicle serves a customer
outside the hard time window, but within the soft time window.
Vehicle routing problem is a combinatorial optimization problem and proved to be
an NP-hard problem. VRPTW and its variants have been studied extensively in the literature. There have been both exact and heuristic approaches for solving VRPTW and
its variants. The main contribution of this research is to focus on a new and e cient
metaheuristic, Arti cial Bee Colony (ABC), inspired by the intelligent foraging behavior
of the honey bee swarm and the application of ABC metaheuristic to solve the VRPTW
problem with soft time windows. This research also focuses on how our approach can be
easily modi ed to solve not only the VRPTW problem with soft time windows, but also
many other variants of VRPTW problem. We have compared the performance of our ABC
approach against the best approaches reported in the literature. Experimental results
demonstrate the superiority of the new ABC approach over all the other approaches. The
modular and intuitive approach obtains better quality solutions in reasonable amount of
time.
