【作者】 张翔；

【导师】 杨光飞；

【作者基本信息】 大连理工大学 ， 管理科学与工程， 2017， 硕士

【摘要】 随着中国经济的快速发展和城市化进程的不断加快,居民的物质生活需求越来越高。超市作为零售商业的重要组成部分,和居民的生活质量息息相关。居民对于提高超市服务质量的需求不断增加。越来越多的超市提供了免费购物班车服务,使居民购物更加便捷,大大提高了居民的满意度。班车服务拓展了超市经营的范围,缩短了居民前往超市的时间。然而,传统方法很难探究顾客的出行规律,无法为他们规划合理的班车路线。各大超市设计的班车路线由于规划不合理,反而扰乱了交通,为城市交通安全带来了不利影响。如今很多出租车都配备了全球定位系统(GPS),这些设备记录出租车的轨迹数据,包含上下客地点的经纬度、上下车时间、行驶距离等信息。大量的出租车GPS数据中蕴含了价值丰富的信息。本文的目的就是通过对出租车GPS数据的分析,挖掘超市顾客的出行信息,将它们应用于超市班车路线设计中,辅助超市管理者决策,为超市规划更加合理的班车路线。本文进行班车路线规划的方法主要分为以下两个步骤:(1)首先进行班车站点的选址。通过对出租车出发点/终点经纬度的范围、行驶距离、行驶时间等因素的限制,我们将收集到的出租车上下客GPS数据进行预处理,筛选出超市顾客的出行数据。提出了DBSCAN-PAM混合聚类算法,选择地球球面距离作为聚类算法中的相似度,从而提升聚类的精度。基于筛选出来的数据,利用混合算法,发现居民出行的热点地区,将这些热点地区的中心点作为班车的站点位置。(2)其次根据发现的班车站点进行路线规划。基于传统的扫描法,提出了最近距离扫描法,将它用来进行班车站点的分组。在每一组站点中,利用TSP问题相似的思想,使用基本遗传算法规划最优路线,目的使班车行驶距离最短。其中,我们使用百度地图提供的API进行路线搜索,确定站点之间实际的距离最短路线,使最后得到的路线更加符合实际交通路况,提高路线的实用性。通过现实中采集的出租车GPS轨迹数据进行实验,验证本文提出的方法可行性。结果表明,我们提出的超市班车路线规划方法有效地识别了居民密集出行的热点区域,班车站点选址合理符合实际情况,最后得到的班车路线与现有班车路线相比,不仅行驶距离减少,居民乘坐班车也更加便捷。更多还原

【Abstract】 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.更多还原