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

1、隨著地理信息技術(shù)的普及和發(fā)展，大量包含空間位置信息的數(shù)據(jù)不斷產(chǎn)生，基于空間數(shù)據(jù)的最優(yōu)位置選擇問題作為一個(gè)熱門研究方向，在現(xiàn)實(shí)生活中具有廣泛的應(yīng)用場景，如城市建設(shè)規(guī)劃中的新建服務(wù)設(shè)施場所選址問題，機(jī)動(dòng)車選擇停車場時(shí)的停車位分配問題等等。對(duì)于空間中分布的客戶點(diǎn)和服務(wù)點(diǎn)，每個(gè)服務(wù)點(diǎn)具有一定的服務(wù)容量，并為一定數(shù)量的客戶點(diǎn)提供服務(wù)，而客戶點(diǎn)則需要選擇一個(gè)最佳服務(wù)點(diǎn)來獲取服務(wù)。本文主要研究了新建服務(wù)點(diǎn)最優(yōu)位置選擇問題，分析了為客戶點(diǎn)選擇最佳可用服

2、務(wù)點(diǎn)的分配策略，提出了解決新建k個(gè)服務(wù)點(diǎn)位置選擇問題的組合最優(yōu)位置查詢算法。
　　服務(wù)點(diǎn)相對(duì)于客戶點(diǎn)的位置決定了客戶點(diǎn)選擇哪個(gè)服務(wù)點(diǎn)來獲取服務(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)。以停車位的分配問題為例，每個(gè)車輛需要查詢距離自己最近的目標(biāo)停

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