A Route Planning Method For Supermarket Shuttle Service Based On Taxi GPS Data

With the rapid development of China’s economy and the accelerating process of urbanization,there is an increasing demand to improve the quality of life.As an important part of retail business,supermarket is closely related to the quality of healthy life.The demand to improve the quality of supermarket service is increasing.More and more supermarkets provide free shopping shuttle service,so that residents go shopping more conveniently and greatly improve the satisfaction of residents.The supermarket shuttle service could have a direct impact on extending supermarket access,increasing shared transport and enlarging customers’ satisfaction.However,traditional supermarket shuttle bus route planning method is difficult to explore the law of the customer’s travel and can not provide reasonable routes for them.The routes planning of major supermarkets are unreasonable in the design,and these phenomena disturb traffic order,which has brought adverse effects in urban traffic safety.Many taxis are equipped with a global positioning system(GPS),these devices record taxi trajectory data,including the taxi passengers’ pick-up/drop-off records(PDRs),the latitude and longitude of the origin/destination(OD),the time of pick-up/drop-off records,the taxi running distance and other information.A large number of taxi GPS data contains rich information.Through the analysis of taxi GPS data,the purpose of this paper is to detect the travel mode of supermarket customers and optimize the supermarket bus routes to maximize the benefits for customers and supermarkets.In this paper,the shuttle route planning method is divided into the following two steps:(1)Firstly,determine the location of the bus stops.Some constraints are designed to make the data more representative of the supermarket’s consumers travel data,rather than other ordinary passengers’ data.The DBSCAN-PAM hybrid clustering algorithm is proposed to find the hot spots where customers often appear.The earth sphere distance is applied as the similarity of the clustering algorithm,so as to improve the accuracy of clustering.Then,centers of these hot spots are selected to be the bus stops.(2)Secondly,bus routes are generated according to the bus stops selected by the former step.Based on the traditional sweep algorithm,the nearest distance sweep algorithm(NDSA)is proposed.In each group of bus stops,using the similar ideas of TSP problem,we use the standard genetic algorithm to plan the optimal routes,whose purpose is to get the shortest route.Taking advantage of Baidu map API,we can use it to find the actual shortest route between two bus stops.The route recommended by API is more consistent with the actual traffic conditions,which is highly feasible in real life.Through the experiment of GPS trajectory data collected in reality,the feasibility of the proposed method is verified.The results show that the supermarket bus route planning method we proposed effectively identify hot regions where customers go intensively,the locations of bus stops are reasonable.Compared with the existing bus routes,the shuttle routes generated by our method not only reduce the driving distance of bus,but also bring more convenience for the customers.