The Vehicle Routing Problem with Time Windows Based on a Multi-conditional Clustering and Tabu Search Approach

A company distributes goods to stores all over the country through one warehouse. The warehouse processes orders from different stores daily and decides on order allocation and shipping routes for each vehicle. In a long-haul transport, drivers must obey traffic safety regulations, such as day/night speed limits and continuous driving hours. This paper considers a long-haul vehicle routing problem in terms of time windows and order priorities. An integer programming model is built to minimize the total transportation time of all vehicles. Then, a multi-conditional clustering method based on K-means is adopted to achieve regional division. Moreover, a Tabu Search (TS) algorithm, based on the regional division with creating mixed neighborhood structure, is proposed to optimize the solutions for the model. The preliminary results of a series of experiments, which are conducted on real data, are able to verify the effectiveness and efficiency of the proposed algorithm.