Vehicle routing problems with soft time windows

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.