Solving the multi-objective Vehicle Routing Problem with Soft Time Windows with the help of bees

摘要

This paper presents a new model and solution for the multi-objective Vehicle Routing Problem with Soft Time Windows (VRPSTW) using a hybrid metaheuristic technique. The proposed methodology is developed on the basics of a new swarm based Artificial Bee Colony (ABC) algorithm combined with two-step constrained local search for neighborhood selection. VRPSTW involves computing the routes of a set of vehicles with fixed capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. Here, the time window constraints are relaxed into "soft", that is penalty terms are added to the solution cost whenever a vehicle serves a customer outside of his time window. The solution of routing problems with soft time windows has valuable practical applications. This paper uses a direct interpretation of the VRPSTW as a multi-objective optimization problem where the total traveling distance, number of window violations and number of required vehicles are minimized while capacity and time window constraints are met. Our work aims at using ABC inspired foraging behavior of honey bees which balances exploration and exploitation to avoid local optima and reach the global optima. The algorithm is applied to solve the well known benchmark Solomon's problem instances. Experimental results show that our suggested approach is quite effective, as it provides solutions that are competitive with the best known results in the literature. Finally, we present an analysis of our proposed algorithm in terms of computational time. (C) 2015 Elsevier B.V. All rights reserved.