空間數(shù)據(jù)最優(yōu)位置查詢(xún)問(wèn)題的研究與應(yīng)用.pdf

1、隨著地理信息技術(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ē)選擇停車(chē)場(chǎng)時(shí)的停車(chē)位分配問(wèn)題等等。對(duì)于空間中分布的客戶(hù)點(diǎn)和服務(wù)點(diǎn)，每個(gè)服務(wù)點(diǎn)具有一定的服務(wù)容量，并為一定數(shù)量的客戶(hù)點(diǎn)提供服務(wù)，而客戶(hù)點(diǎn)則需要選擇一個(gè)最佳服務(wù)點(diǎn)來(lái)獲取服務(wù)。本文主要研究了新建服務(wù)點(diǎn)最優(yōu)位置選擇問(wèn)題，分析了為客戶(hù)點(diǎn)選擇最佳可用服

2、務(wù)點(diǎn)的分配策略，提出了解決新建k個(gè)服務(wù)點(diǎn)位置選擇問(wèn)題的組合最優(yōu)位置查詢(xún)算法。
　　服務(wù)點(diǎn)相對(duì)于客戶(hù)點(diǎn)的位置決定了客戶(hù)點(diǎn)選擇哪個(gè)服務(wù)點(diǎn)來(lái)獲取服務(wù)，本文首先分析了為客戶(hù)點(diǎn)選擇最佳可用服務(wù)點(diǎn)的分配策略?？蛻?hù)點(diǎn)優(yōu)先選擇最近鄰服務(wù)點(diǎn)為其目標(biāo)服務(wù)點(diǎn)，服務(wù)點(diǎn)能且僅能為距離他最近的m個(gè)客戶(hù)點(diǎn)提供服務(wù)，如果某個(gè)客戶(hù)點(diǎn)的目標(biāo)服務(wù)點(diǎn)被其他m個(gè)客戶(hù)點(diǎn)占用，則需要繼續(xù)為該客戶(hù)點(diǎn)分配其他可用服務(wù)點(diǎn)。以停車(chē)位的分配問(wèn)題為例，每個(gè)車(chē)輛需要查詢(xún)距離自己最近的目標(biāo)停

3、車(chē)位，同時(shí)要求該停車(chē)位不能被其他車(chē)輛搶先占用完。本文提出了Strip-CPM算法來(lái)完成服務(wù)點(diǎn)的分配任務(wù)。
　　本文提出了組合最優(yōu)位置查詢(xún)算法來(lái)解決新建服務(wù)點(diǎn)最優(yōu)位置選擇問(wèn)題。組合最優(yōu)位置查詢(xún)的目標(biāo)是新建k個(gè)服務(wù)點(diǎn)，要求該k個(gè)服務(wù)點(diǎn)能夠吸引最多數(shù)量的客戶(hù)。本文提出了精確算法和近似算法來(lái)解決該問(wèn)題，精確算法對(duì)所有候選新服務(wù)點(diǎn)進(jìn)行組合枚舉查詢(xún)，以計(jì)算一個(gè)準(zhǔn)確的最優(yōu)組合方案。為了解決精確算法在數(shù)據(jù)量較大時(shí)的查詢(xún)低效問(wèn)題，近似算法根據(jù)候選新