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

• Published in: Sadhana (Bangalore) 2017-12, Vol.42 (12), p.2067-2080
• Main Authors: CÖMERT, SERAP ERCAN, YAZGAN, HARUN REŞİT, SERTVURAN, İREM, ŞENGÜL, HANİFE
• Format: Article
• Language: English
• Subjects: Clustering; Customers; Engineering; Heuristic methods; Route planning; Routing; Supermarkets; Vehicle routing; Windows (intervals)
• ISSN: 0256-2499; 0973-7677
• DOI: 10.1007/s12046-017-0754-1

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.