【摘要】：隨著地理信息技術(shù)的普及和發(fā)展,大量包含空間位置信息的數(shù)據(jù)不斷產(chǎn)生,基于空間數(shù)據(jù)的最優(yōu)位置選擇問(wèn)題作為一個(gè)熱門(mén)研究方向,在現(xiàn)實(shí)生活中具有廣泛的應(yīng)用場(chǎng)景,如城市建設(shè)規(guī)劃中的新建服務(wù)設(shè)施場(chǎng)所選址問(wèn)題,機(jī)動(dòng)車選擇停車場(chǎng)時(shí)的停車位分配問(wèn)題等等。對(duì)于空間中分布的客戶點(diǎn)和服務(wù)點(diǎn),每個(gè)服務(wù)點(diǎn)具有一定的服務(wù)容量,并為一定數(shù)量的客戶點(diǎn)提供服務(wù),而客戶點(diǎn)則需要選擇一個(gè)最佳服務(wù)點(diǎn)來(lái)獲取服務(wù)。本文主要研究了新建服務(wù)點(diǎn)最優(yōu)位置選擇問(wèn)題,分析了為客戶點(diǎn)選擇最佳可用服務(wù)點(diǎn)的分配策略,提出了解決新建k個(gè)服務(wù)點(diǎn)位置選擇問(wèn)題的組合最優(yōu)位置查詢算法。服務(wù)點(diǎn)相對(duì)于客戶點(diǎn)的位置決定了客戶點(diǎn)選擇哪個(gè)服務(wù)點(diǎn)來(lái)獲取服務(wù),本文首先分析了為客戶點(diǎn)選擇最佳可用服務(wù)點(diǎn)的分配策略�？蛻酎c(diǎn)優(yōu)先選擇最近鄰服務(wù)點(diǎn)為其目標(biāo)服務(wù)點(diǎn),服務(wù)點(diǎn)能且僅能為距離他最近的m個(gè)客戶點(diǎn)提供服務(wù),如果某個(gè)客戶點(diǎn)的目標(biāo)服務(wù)點(diǎn)被其他m個(gè)客戶點(diǎn)占用,則需要繼續(xù)為該客戶點(diǎn)分配其他可用服務(wù)點(diǎn)。以停車位的分配問(wèn)題為例,每個(gè)車輛需要查詢距離自己最近的目標(biāo)停車位,同時(shí)要求該停車位不能被其他車輛搶先占用完。本文提出了Strip-CPM算法來(lái)完成服務(wù)點(diǎn)的分配任務(wù)。本文提出了組合最優(yōu)位置查詢算法來(lái)解決新建服務(wù)點(diǎn)最優(yōu)位置選擇問(wèn)題。組合最優(yōu)位置查詢的目標(biāo)是新建k個(gè)服務(wù)點(diǎn),要求該k個(gè)服務(wù)點(diǎn)能夠吸引最多數(shù)量的客戶。本文提出了精確算法和近似算法來(lái)解決該問(wèn)題,精確算法對(duì)所有候選新服務(wù)點(diǎn)進(jìn)行組合枚舉查詢,以計(jì)算一個(gè)準(zhǔn)確的最優(yōu)組合方案。為了解決精確算法在數(shù)據(jù)量較大時(shí)的查詢低效問(wèn)題,近似算法根據(jù)候選新服務(wù)點(diǎn)吸引客戶點(diǎn)集合的相似度進(jìn)行聚類,然后利用聚類中心點(diǎn)進(jìn)行查詢,降低了查詢代價(jià)。本文通過(guò)大量實(shí)驗(yàn)驗(yàn)證了近似算法的效率,并對(duì)比了近似算法相對(duì)于精確算法的準(zhǔn)確度。
[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.
【學(xué)位授予單位】：浙江大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP311.13

【相似文獻(xiàn)】

相關(guān)期刊論文 前2條

1 付連寧;崔文;曾華;;并行節(jié)約算法的自適應(yīng)鄰域選擇策略[J];山東大學(xué)學(xué)報(bào)(工學(xué)版);2012年01期

2 孟春華;王洪國(guó);邵增珍;于洪玲;丁艷輝;;基于客戶分級(jí)及換乘的多車輛合乘問(wèn)題算法研究[J];計(jì)算機(jī)科學(xué);2013年09期

相關(guān)重要報(bào)紙文章 前1條

1 劉月輝;善于發(fā)現(xiàn)潛在目標(biāo)用戶[N];中國(guó)婦女報(bào);2004年

相關(guān)碩士學(xué)位論文 前4條

1 侯占亭;基于分解和決策空間相似性度量的進(jìn)化多目標(biāo)車輛路徑規(guī)劃算法研究[D];西安電子科技大學(xué);2014年

2 伊桂花;配送網(wǎng)絡(luò)拓?fù)錁?gòu)建研究及應(yīng)用[D];山東大學(xué);2007年

3 許敏;時(shí)間窗限制下的車輛調(diào)度子路徑平衡問(wèn)題[D];華南理工大學(xué);2010年

4 張洪奉;基于聚類的物流管理信息系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D];西南交通大學(xué);2012年

，

本文編號(hào)：2373450