Site dependent vehicle routing problem with soft time window: Modeling and solution approach

• An integer linear programming model is presented for Site Dependent Vehicle Routing Problem with Soft Time Window (SDVRPSTW).
• An Ant Colony System (ACS) based algorithm is presented for SDVRPSTW.
• A new algorithm based on tabu search algorithm is presented for SDVRPSTW.
• Four local searches are adopted in both of algorithms.
• To evaluate the efficiency of the presented algorithms, experimental tests were designed in various environments and scales.

This paper presents two meta-heuristic algorithms, an ant colony system with local searches and a tabu search algorithm, for Site-Dependent Vehicle Routing Problem with Soft Time Window (SDVRPSTW). In the SDVRPSTW a fleet of vehicles must deliver goods to their allowable set of customers, preferably in their time windows while the capacity constraints of the vehicles must be respected. Based on our best knowledge, this problem which challenges the distribution task of public services and private organizations in an urban context with heavy traffic has not yet been considered in practical aspects, especially where the vehicles entrance to some areas needs traffic license. Hence, in addition to present an Integer Linear Programming (ILP) model, we present the two mentioned algorithms to handle the problem in large scale instances. Furthermore, the algorithms efficiency and their optimality are analyzed by experimental results both in small and large dimensions.