空间数据最优位置查询问题的研究与应用
发布时间：2018-12-11 23:42
【摘要】：随着地理信息技术的普及和发展,大量包含空间位置信息的数据不断产生,基于空间数据的最优位置选择问题作为一个热门研究方向,在现实生活中具有广泛的应用场景,如城市建设规划中的新建服务设施场所选址问题,机动车选择停车场时的停车位分配问题等等。对于空间中分布的客户点和服务点,每个服务点具有一定的服务容量,并为一定数量的客户点提供服务,而客户点则需要选择一个最佳服务点来获取服务。本文主要研究了新建服务点最优位置选择问题,分析了为客户点选择最佳可用服务点的分配策略,提出了解决新建k个服务点位置选择问题的组合最优位置查询算法。服务点相对于客户点的位置决定了客户点选择哪个服务点来获取服务,本文首先分析了为客户点选择最佳可用服务点的分配策略。客户点优先选择最近邻服务点为其目标服务点,服务点能且仅能为距离他最近的m个客户点提供服务,如果某个客户点的目标服务点被其他m个客户点占用,则需要继续为该客户点分配其他可用服务点。以停车位的分配问题为例,每个车辆需要查询距离自己最近的目标停车位,同时要求该停车位不能被其他车辆抢先占用完。本文提出了Strip-CPM算法来完成服务点的分配任务。本文提出了组合最优位置查询算法来解决新建服务点最优位置选择问题。组合最优位置查询的目标是新建k个服务点,要求该k个服务点能够吸引最多数量的客户。本文提出了精确算法和近似算法来解决该问题,精确算法对所有候选新服务点进行组合枚举查询,以计算一个准确的最优组合方案。为了解决精确算法在数据量较大时的查询低效问题,近似算法根据候选新服务点吸引客户点集合的相似度进行聚类,然后利用聚类中心点进行查询,降低了查询代价。本文通过大量实验验证了近似算法的效率,并对比了近似算法相对于精确算法的准确度。
[Abstract]:With the popularization and development of geographic information technology, a large number of data containing spatial location information are constantly produced. As a hot research direction, the problem of optimal location selection based on spatial data has been widely used in real life. For example, the location of new service facilities in urban construction planning, the allocation of parking spaces when motor vehicles choose parking lots and so on. For the spatial distribution of customer points and service points, each service point has a certain service capacity and provides services for a certain number of customer points, and customer points need to select an optimal service point to obtain services. In this paper, the problem of optimal location selection for new service points is studied, the allocation strategy for selecting optimal available service points for customer points is analyzed, and a combinatorial optimal location query algorithm is proposed to solve the problem of location selection of new service points. The location of service point relative to customer point determines which service point is selected by customer point to obtain service. This paper first analyzes the allocation strategy of selecting the best available service point for customer point. The customer preferred to select the nearest neighbor service point as its target service point. The service point can and can only serve the nearest m customer points, if the target service point of one customer point is occupied by other m customer points, You need to continue to assign other available service points to the customer point. Taking the allocation of parking spaces as an example, each vehicle needs to inquire about the nearest target parking space, and it is required that the parking space should not be occupied by other vehicles. In this paper, Strip-CPM algorithm is proposed to accomplish the assignment of service points. In this paper, a combinatorial optimal location query algorithm is proposed to solve the problem of optimal location selection for new service points. The goal of combinatorial optimal location query is to create new k service points, which can attract the largest number of customers. In this paper, an exact algorithm and an approximate algorithm are proposed to solve the problem. The exact algorithm performs combinatorial enumeration queries on all candidate new service points to calculate an accurate optimal combination scheme. In order to solve the query inefficiency problem of accurate algorithm when the data is large, the approximate algorithm clusters according to the similarity of candidate new service points to attract customer points, and then makes use of clustering center points to query, which reduces the query cost. In this paper, the efficiency of the approximate algorithm is verified by a large number of experiments, and the accuracy of the approximate algorithm relative to the exact algorithm is compared.
【学位授予单位】：浙江大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13
本文编号：2373450
[Abstract]:With the popularization and development of geographic information technology, a large number of data containing spatial location information are constantly produced. As a hot research direction, the problem of optimal location selection based on spatial data has been widely used in real life. For example, the location of new service facilities in urban construction planning, the allocation of parking spaces when motor vehicles choose parking lots and so on. For the spatial distribution of customer points and service points, each service point has a certain service capacity and provides services for a certain number of customer points, and customer points need to select an optimal service point to obtain services. In this paper, the problem of optimal location selection for new service points is studied, the allocation strategy for selecting optimal available service points for customer points is analyzed, and a combinatorial optimal location query algorithm is proposed to solve the problem of location selection of new service points. The location of service point relative to customer point determines which service point is selected by customer point to obtain service. This paper first analyzes the allocation strategy of selecting the best available service point for customer point. The customer preferred to select the nearest neighbor service point as its target service point. The service point can and can only serve the nearest m customer points, if the target service point of one customer point is occupied by other m customer points, You need to continue to assign other available service points to the customer point. Taking the allocation of parking spaces as an example, each vehicle needs to inquire about the nearest target parking space, and it is required that the parking space should not be occupied by other vehicles. In this paper, Strip-CPM algorithm is proposed to accomplish the assignment of service points. In this paper, a combinatorial optimal location query algorithm is proposed to solve the problem of optimal location selection for new service points. The goal of combinatorial optimal location query is to create new k service points, which can attract the largest number of customers. In this paper, an exact algorithm and an approximate algorithm are proposed to solve the problem. The exact algorithm performs combinatorial enumeration queries on all candidate new service points to calculate an accurate optimal combination scheme. In order to solve the query inefficiency problem of accurate algorithm when the data is large, the approximate algorithm clusters according to the similarity of candidate new service points to attract customer points, and then makes use of clustering center points to query, which reduces the query cost. In this paper, the efficiency of the approximate algorithm is verified by a large number of experiments, and the accuracy of the approximate algorithm relative to the exact algorithm is compared.
【学位授予单位】：浙江大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13
【相似文献】
相关期刊论文 前2条
1 付连宁;崔文;曾华;;并行节约算法的自适应邻域选择策略[J];山东大学学报(工学版);2012年01期
2 孟春华;王洪国;邵增珍;于洪玲;丁艳辉;;基于客户分级及换乘的多车辆合乘问题算法研究[J];计算机科学;2013年09期
相关重要报纸文章 前1条
1 刘月辉;善于发现潜在目标用户[N];中国妇女报;2004年
相关硕士学位论文 前4条
1 侯占亭;基于分解和决策空间相似性度量的进化多目标车辆路径规划算法研究[D];西安电子科技大学;2014年
2 伊桂花;配送网络拓扑构建研究及应用[D];山东大学;2007年
3 许敏;时间窗限制下的车辆调度子路径平衡问题[D];华南理工大学;2010年
4 张洪奉;基于聚类的物流管理信息系统设计与实现[D];西南交通大学;2012年
，本文编号：2373450
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2373450.html
