Space-time Clustering Based Analysis And Optimization Of Vehicle Routing Problem

In recent years, as ‘the third source of profit’, the research and application oflogistics have already caused great attention of the government, enterprises, as well asacademia. With economic development and market competition, scale of customers inarea covered by distribution center is increasing, manufacturers or retailers becomemore and more demanding of delivery time from the suppliers or the third partylogistics. However, the uncertainty in distribution is a big challenge for analysis andoptimization of the vehicle routing problem. It is not difficult to find all ofthese uncertainties have strong spatial and temporal characteristics.Therefore, it’snecessary to consider both time factors and space factors in the study. But fornow, space-time integrated method is still not fully appreciated in Logistics. Thepurpose of this paper is to study the temporal and spatial distribution of logisticsbusiness distribution, using method combines logistics, intelligent transportation andthe theory of time-geography. It provides analysis and optimization methods andtools for vehicle routing problem through the calculation of spatiotemporal distance.This article draws much experience in successfully solving VRPTW recently,and improves the structure of the traditional two-phase algorithm. First, we useSolomon I1insertion algorithm to construct an initial solution, and then clustercustomers on the basis of spatiotemporal distance. At last, we improve itwith variable neighborhood search algorithm.In view of three-dimensional spatiotemporal distance, we can reduce the scopeof search space, so that the improvement will be more targeted. In partition phase ofcustomers, we designed a spatiotemporal distance metric instead of space distance tomeasure the similarity between two customers. When improve the initial route, wepropose kinds of neighborhood structures and operators, such as2-opt, exchange,relocate, etc. The quality of the solution has been improved effectively, andthe algorithm is made more suitable to solve especially large-scale problems. Finally,the program is implemented in C++, and the performance of the improved algorithm is tested and evaluated by a set of Gehring&Homberger’s benchmark problems.The proposed algorithm takes the time and space factors into account in theprocess of solving. It offers less time-consuming and better performance, so as tomeet the needs of practical applications. Introduction of the concept of space-timeclustering and use of integrated method to analysis, diagnose and optimize, providea new perspective for solving vehicle routing problem.