A new approach for solution of vehicle routing problem with hard time window: an application in a supermarket chain

Abstract

In this study, a vehicle routing problem with hard time windows (VRPHTW) that appears to meet demands of customers' service within time intervals in a supermarket chain is solved. In VRPHTW, to reach a solution by an exact method is quite difficult and sometimes impossible if number of constraints is large enough (i.e., NP-hard), and solution time of a VRPHTW grows exponentially. As the size of the problem grows, a near optimal solution can be found using a heuristic method. A hierarchical approach consisting of two stages as "cluster-first route-second" is proposed. In the first stage, customers are assigned to vehicles using three different clustering algorithms (i.e., K-means, K-medoids and DBSCAN). In the second stage, a VRPHTW is solved using a MILP. The main contribution of the article is that the proposed hierarchical approach enables us to deal with a large size real problem and to solve it in a short time using the exact method. Finally, the proposed approach is employed on a supermarket chain. An instance of the algorithm is demonstrated to illustrate the applicability of the proposed approach and the results obtained are highly favourable.