Vehicle routing problem is one of the most useful problems in operation research fields and combinatorial optimization. The problem is seeking to find an effective plan for fleet of vehicles. The plan is delivering goods from a central depot to a set of geographically dispersed customers with known demands, so that some constraints like returning any vehicles to central depot, satisfying customer demands and maximum capacity of each vehicle are considered. It was demonstrated that the vehicle routing is a NP-hard problem and increase in size of the problem increases the difficulty and computational time exponentially. In this research, first we tried to extend mathematical model with a new objective function and some actual assumptions such as site-dependency and time window. We consider site-dependent vehicle routing problem with soft time window (SDVRPSTW), in which a compatibility relation exists between customers and vehicle types and vehicles are allowed to service customers before and after the earliest and latest time window bounds, respectively. This relaxation comes at the expense of appropriate penalties that reflect the effect that time window violations have on the customer's satisfaction. We present the Integer Programming model of the site-dependent vehicle routing problem in which each customer has a time window. Secondly, a hybrid ant colony Optimization-based algorithm and a new tabu search are presented for the problem. The presented algorithms have become more explorative via four local searches. Finally, some test problems are solved and analyzed in both small and large instances of the problem to show the effectiveness and efficiency of this presented algorithm. The results show that ant colony algorithm is more efficient than tabu search.
