一種基于阻抗等級(jí)劃分的整體最優(yōu)空間位置分配方法

郭文月，劉海硯，余岸竹，劉晨帆

（信息工程大學(xué) 地理空間信息學(xué)院，河南 鄭州450001）

地理位置通常被視為影響服務(wù)設(shè)施運(yùn)轉(zhuǎn)效率的關(guān)鍵因素［1］，良好的地理位置有助于保證成本穩(wěn)定低廉，提高設(shè)施點(diǎn)對(duì)需求點(diǎn)的吸引力?？臻g分析是依賴(lài)分析對(duì)象位置信息的技術(shù)［2－3］，空間位置分配根據(jù)地理實(shí)體的空間位置、空間關(guān)系和屬性特征，結(jié)合用戶(hù)需求，研究和確定空間對(duì)象的最優(yōu)位置和資源分配，為用戶(hù)提供輔助決策依據(jù)。位置分配的目的是以合適的方式定位設(shè)施點(diǎn)，從而保證最高效地滿(mǎn)足需求，顧名思義，位置分配是定位設(shè)施點(diǎn)的同時(shí)將需求點(diǎn)分配給設(shè)施點(diǎn)的雙重問(wèn)題。

解算整體最優(yōu)空間位置分配問(wèn)題的方法主要有啟發(fā)式 算 法［4－6］、蟻 群 算 法［7－8］等。這 些 算 法 從 不同角度考慮空間位置分配問(wèn)題的影響因素，并以總成本最小為原則實(shí)現(xiàn)對(duì)整體最優(yōu)空間位置分配問(wèn)題的解算，但在解算效率、參數(shù)選取等方面仍可進(jìn)一步改進(jìn)。本文在解決整體最優(yōu)空間位置分配問(wèn)題時(shí)，將通過(guò)設(shè)施點(diǎn)和需求點(diǎn)間的網(wǎng)絡(luò)元素所要消耗的成本整合為阻抗，用阻抗大小作為影響成本的因素，并在解算時(shí)引入等級(jí)劃分的方法，提出基于阻抗等級(jí)劃分的空間位置分配算法，有效提高解算效率。

1 整體最優(yōu)位置分配及算法

整體最優(yōu)空間位置分配問(wèn)題是以指定區(qū)域內(nèi)若干需求點(diǎn)與設(shè)施點(diǎn)間的整體成本最優(yōu)作為求解標(biāo)準(zhǔn)，實(shí)現(xiàn)整體資源配置最佳化，旨在解決多條件、大范圍、多數(shù)量的空間點(diǎn)位分配分析問(wèn)題，用于設(shè)施點(diǎn)的宏觀(guān)部署和整體利益優(yōu)化。目前，常用于解決此類(lèi)問(wèn)題的算法——貪婪取走啟發(fā)式算法，該算法需多次掃描比較數(shù)據(jù)集，在運(yùn)算效率方面還有較大提升空間。

1．1 基于阻抗的整體最優(yōu)位置分配表達(dá)

判斷某一候選設(shè)施點(diǎn)的優(yōu)劣時(shí)需要考慮的影響因素隨用戶(hù)需求的不同而不同，總體來(lái)說(shuō)，用戶(hù)希望盡可能減少?gòu)脑O(shè)施點(diǎn)到需求點(diǎn)的成本消耗，因而將通過(guò)設(shè)施點(diǎn)和需求點(diǎn)間的網(wǎng)絡(luò)元素所要消耗的成本整合為阻抗，將其表示為

式中：i，j為需求點(diǎn)和設(shè)施點(diǎn)序號(hào)；Nj為設(shè)施點(diǎn)；x為需求點(diǎn)為設(shè)施點(diǎn)與需求點(diǎn)間可行路徑長(zhǎng)度；ωi為需求點(diǎn)權(quán)重；fij為設(shè)施點(diǎn)與需求點(diǎn)間單位路程運(yùn)費(fèi)。設(shè)施點(diǎn)對(duì)需求點(diǎn)的吸引力與兩點(diǎn)間的阻抗成反比，阻抗值越大，表示該設(shè)施點(diǎn)對(duì)某需求點(diǎn)的吸引力越小。在可提供貨物與服務(wù)的候選設(shè)施點(diǎn)以及消耗這些貨物及服務(wù)的需求點(diǎn)已經(jīng)給定的情況下，從候選設(shè)施點(diǎn)中選取用戶(hù)指定數(shù)量的點(diǎn)作為設(shè)施定位點(diǎn)，并將需求點(diǎn)分配給選出的設(shè)施點(diǎn)，使得各個(gè)需求點(diǎn)與所分配到的設(shè)施點(diǎn)間阻抗總和最小?；谧杩沟恼w最優(yōu)空間位置分配問(wèn)題表示

式中：m為需求點(diǎn)的數(shù)量；k為最終確定的設(shè)施點(diǎn)數(shù)量，且由用戶(hù)指定；nk為分配到第j個(gè)設(shè)施點(diǎn)的需求點(diǎn)數(shù)量；δ為分配時(shí)允許的最大阻抗。整體最優(yōu)空間位置分配問(wèn)題是選擇候選設(shè)施點(diǎn)集N的子集P，使得所有需求點(diǎn)到其分配設(shè)施點(diǎn)之間的阻抗總和最小。

1．2 貪婪取走啟發(fā)式算法

貪婪取走啟發(fā)式算法是解決上述整體最優(yōu)空間位置分配問(wèn)題的常用算法之一［5－7］，其解算步驟：

步驟1：假設(shè)設(shè)施定位點(diǎn)集合P＝N，即選中所有候選設(shè)施點(diǎn)；

步驟2：將各個(gè)需求點(diǎn)分配給與該需求點(diǎn)間阻抗最小的候選設(shè)施點(diǎn)；

步驟3：選擇并取走一個(gè)候選設(shè)施點(diǎn)Nj，將其取走并將其對(duì)應(yīng)的需求點(diǎn)，按照阻抗最小原則分配給其它候選設(shè)施點(diǎn)，總阻抗增加值最??；

步驟4：從P中刪除點(diǎn)Nj，重復(fù)步驟3，直到剩余的候選設(shè)施點(diǎn)數(shù)目與用戶(hù)需求相同。

貪婪取走啟發(fā)式算法從候選設(shè)施點(diǎn)集合中逐一刪除對(duì)最優(yōu)整體阻抗值影響最小的候選設(shè)施點(diǎn)，直到剩余的候選設(shè)施點(diǎn)個(gè)數(shù)滿(mǎn)足用戶(hù)需求。這種算法保證了每次迭代時(shí)的整體阻抗值最小，有效實(shí)現(xiàn)設(shè)施點(diǎn)的選取，但該算法每排除一個(gè)候選設(shè)施點(diǎn)就需要至少一次掃描數(shù)據(jù)集，當(dāng)候選設(shè)施點(diǎn)數(shù)目遠(yuǎn)遠(yuǎn)大于需求設(shè)施點(diǎn)數(shù)目時(shí)，該算法的解算效率明顯過(guò)低。為提高整體最優(yōu)空間位置分配問(wèn)題的解算效率，本文在貪婪取走啟發(fā)式算法基礎(chǔ)上提出一種基于等級(jí)劃分的解算方法。

2 空間位置分配方法

本文采用等級(jí)劃分的方法，將候選設(shè)施點(diǎn)與需求點(diǎn)間的阻抗按照值相近的原則聚合為若干等級(jí)，在求解計(jì)算時(shí)，用阻抗等級(jí)替代阻抗值，這樣的等級(jí)劃分方法實(shí)現(xiàn)了在保證整體最優(yōu)的前提下，較大程度地減少了空間位置分配問(wèn)題求解的運(yùn)算量。

2．1 阻抗等級(jí)劃分

采取等差劃分的方法，假設(shè)n個(gè)候選設(shè)施點(diǎn)與m個(gè)需求點(diǎn)間所有小于阻抗中斷的阻抗值為｛d11，d12，…，dnm｝，找出其中的最大值dmax和最小值dmin，根據(jù)阻抗值大小和用戶(hù)需要選擇的設(shè)施點(diǎn)數(shù)目k，確定劃分阻抗等級(jí)數(shù)目h，那么每個(gè)阻抗等級(jí)跨度

根據(jù)等級(jí)跨度，確定每個(gè)阻抗等級(jí)的分界值，最終將阻抗值劃分為h個(gè)等間隔的區(qū)間：

根據(jù)這些區(qū)間，將阻抗值聚合為D1，D2，…，Dh個(gè)等級(jí)，在求解計(jì)算中用阻抗等級(jí)代替阻抗值。

2．2 求解算法

基于阻抗等級(jí)的空間位置分配的解算思路：首先，根據(jù)各候選設(shè)施點(diǎn)和需求點(diǎn)間的阻抗值大小，以及設(shè)施點(diǎn)的數(shù)目將阻抗值劃分成若干阻抗等級(jí)。解算時(shí)，先將各個(gè)需求點(diǎn)分配給阻抗等級(jí)最低的候選設(shè)施點(diǎn)，再依次選擇并取走對(duì)總阻抗等級(jí)影響最小的候選設(shè)施點(diǎn)，并將其分配到的需求點(diǎn)分配給其它候選設(shè)施點(diǎn)，直至候選設(shè)施點(diǎn)數(shù)目滿(mǎn)足用戶(hù)需求，具體解算步驟為

步驟1：設(shè)候選設(shè)施點(diǎn)集合 N＝｛N1，N2，Nj，…，Nn｝，其子集 P＝｛P1，P2，…，Pk｝為最終確定的設(shè)施點(diǎn)集合，設(shè)需求點(diǎn)集合為x＝｛x1，x2，xi，…，xm｝，為每個(gè)候選設(shè)施點(diǎn)創(chuàng)建一個(gè)需求點(diǎn)分配集合Xj，用以記錄分配給該候選設(shè)施點(diǎn)的需求點(diǎn)位置和數(shù)目，初始Xj＝φ；

步驟2按照各候選設(shè)施點(diǎn)和需求點(diǎn)的阻抗值大小，將所有小于阻抗中斷的阻抗值進(jìn)行等級(jí)劃分，聚合成h個(gè)阻抗等級(jí)，按照阻抗值從小到大依次為D1，D2，…，Dh，大于阻抗中斷的阻抗等級(jí)表示為∞；

步驟3：標(biāo)記所有D1級(jí)阻抗，將需求點(diǎn)分配給D1級(jí)阻抗對(duì)應(yīng)的候選設(shè)施點(diǎn)，若D1級(jí)阻抗對(duì)應(yīng)多個(gè)候選設(shè)施點(diǎn)，則其為比較真實(shí)的阻抗值，選擇真實(shí)值最小的候選設(shè)施點(diǎn)，并更新候選設(shè)施點(diǎn)Nj的需求點(diǎn)分配集合Xj；

步驟4：排除所有需求點(diǎn)分配集合為空的候選設(shè)施點(diǎn)，判斷選出的設(shè)施點(diǎn)數(shù)目是否滿(mǎn)足用戶(hù)需求，則進(jìn)行步驟5，否則，除去候選設(shè)施點(diǎn)Nj，將分配集合Xj中的需求點(diǎn)分配給其它候選設(shè)施點(diǎn)，總阻抗等級(jí)增加最小，直到剩余的候選設(shè)施點(diǎn)數(shù)目滿(mǎn)足用戶(hù)需求；

步驟5：結(jié)束計(jì)算，最終確定的設(shè)施點(diǎn)為P1，P2，…，Pk，各需求點(diǎn)的分配情況用分配集合X1，X2Xk表示。

3 實(shí)驗(yàn)與結(jié)果分析

3．1 模擬數(shù)據(jù)驗(yàn)證

為驗(yàn)證本文提出算法的合理性和高效性，進(jìn)行模擬實(shí)驗(yàn)。選取平面區(qū)域內(nèi)任意分布的10個(gè)點(diǎn)作為候選設(shè)施點(diǎn)，同一區(qū)域內(nèi)任意分布的10個(gè)點(diǎn)作為需求點(diǎn)，模擬從10個(gè)候選設(shè)施點(diǎn)中選出3個(gè)作為設(shè)施定位點(diǎn)，并將10個(gè)需求點(diǎn)依總阻抗最小原則分配給這3個(gè)設(shè)施定位點(diǎn)。在模擬實(shí)驗(yàn)中為10個(gè)需求點(diǎn)分別賦予權(quán)重值，使得10個(gè)點(diǎn)的權(quán)重相加為1，設(shè)單位里程平均運(yùn)費(fèi)為5。

10個(gè)候選設(shè)施點(diǎn)位置如表1所示，10個(gè)需求點(diǎn)位置及權(quán)重如表2所示，為充分驗(yàn)證等級(jí)劃分對(duì)運(yùn)算效率的影響，分別將阻抗值劃分為3個(gè)等級(jí)（三分法）和6個(gè)等級(jí)（六分法），并與直接運(yùn)用阻抗值進(jìn)行計(jì)算的貪婪取走啟發(fā)式算法在運(yùn)算結(jié)果和效率上進(jìn)行對(duì)比。

表1 候選設(shè)施點(diǎn)分布位置

表2 需求點(diǎn)位置及其權(quán)重

根據(jù)式（1）計(jì)算得到各個(gè)設(shè)施點(diǎn)與候選設(shè)施點(diǎn)間的阻抗值，劃分阻抗等級(jí)。兩次不同等級(jí)劃分方式的模擬實(shí)驗(yàn)結(jié)果均選取N6，N8，N10作為最終的設(shè)施定位點(diǎn)，如表3所示，運(yùn)算結(jié)果、運(yùn)用位置與貪婪取走啟發(fā)式算法進(jìn)行解算的結(jié)果一致，由于基于等級(jí)劃分的空間位置分配算法將相近阻抗值聚合為同一等級(jí)，并在實(shí)際運(yùn)算中用阻抗等級(jí)代替阻抗值進(jìn)行結(jié)算，因而在排除候選設(shè)施點(diǎn)的過(guò)程中，比較范圍不再是整個(gè)候選設(shè)施點(diǎn)集，而是縮小到迭代當(dāng)時(shí)最小阻抗等級(jí)對(duì)應(yīng)的候選設(shè)施點(diǎn)范圍，這樣既保證了分配需求點(diǎn)時(shí)整體阻抗最小，又大大提高運(yùn)算效率，在模擬數(shù)據(jù)情況下，三分法和六分法對(duì)數(shù)據(jù)集的掃描對(duì)比次數(shù)分別為基于阻抗值的貪婪取走啟發(fā)式算法的92%和78%左右。當(dāng)數(shù)據(jù)量較大時(shí)，選擇合適的等級(jí)劃分可以更大程度地提高運(yùn)算效率。但并非等級(jí)劃分越精細(xì)，則解算速度越快，實(shí)際劃分等級(jí)數(shù)目，根據(jù)用戶(hù)候選設(shè)施點(diǎn)數(shù)目和阻抗值來(lái)確定。

表3 空間位置分配結(jié)果

3．2 模型構(gòu)建與應(yīng)用

空間分析依賴(lài)于空間分析模型，建立空間分析模型的過(guò)程是綜合分析處理和應(yīng)用空間數(shù)據(jù)的有效手段，也是開(kāi)發(fā)分析決策性GIS不可或缺的步驟［9－13］。為驗(yàn)證本文提出的空間位置分配算法的可用性，實(shí)驗(yàn)利用Arc GIS提供的可視化模型構(gòu)建工具——Model Builder及編程語(yǔ)言構(gòu)建空間位置分配分析模型。構(gòu)建好的模型如圖1所示，將基于阻抗等級(jí)劃分的空間位置分配算法寫(xiě)入到“位置分配”模塊，其余基礎(chǔ)環(huán)節(jié)直接調(diào)用Arc Tool box工具。

圖1 可視化建模模型結(jié)構(gòu)

利用某地區(qū)道路網(wǎng)絡(luò)數(shù)據(jù)和點(diǎn)數(shù)據(jù)，分別選取快遞投送站和重要客戶(hù)所在位置作為候選設(shè)施點(diǎn)和需求點(diǎn)。該地區(qū)按照行政區(qū)劃可分為10個(gè)行政區(qū)域，模擬從248個(gè)快遞投送站候選位置中選出10個(gè)作為設(shè)施定位點(diǎn)，并將208個(gè)重要客戶(hù)分配到這10個(gè)設(shè)施點(diǎn)，由于需求點(diǎn)在10個(gè)行政區(qū)劃范圍內(nèi)不均勻分布，選出的10個(gè)設(shè)施點(diǎn)與行政區(qū)劃模糊對(duì)應(yīng)，且這10個(gè)快遞投送站到各自分配到的重要客戶(hù)的阻抗總和最小。圖2為空間位置分配前候選設(shè)施點(diǎn)與需求點(diǎn)的分布情況，圖3為設(shè)施點(diǎn)的選取和需求點(diǎn)的分配結(jié)果，解決快遞投送站和重要客戶(hù)間基于阻抗的整體最優(yōu)空間位置分配問(wèn)題。

圖2 需求點(diǎn)與候選設(shè)施點(diǎn)分布

為驗(yàn)證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，將全區(qū)域分為若干小區(qū)域，如圖4所示，每個(gè)小區(qū)域內(nèi)包含且僅包含一個(gè)已選設(shè)施點(diǎn)、分配到的需求點(diǎn)、以及未選中的候選設(shè)施點(diǎn)若干。分別將各個(gè)區(qū)域中的需求點(diǎn)分配給阻抗中斷內(nèi)除已選中設(shè)施點(diǎn)之外的候選設(shè)施點(diǎn)，計(jì)算總阻抗值，結(jié)果如圖5所示，在每個(gè)區(qū)域內(nèi)，第一個(gè)值為已選設(shè)施點(diǎn)到各需求點(diǎn)的阻抗和，其余點(diǎn)為該區(qū)域內(nèi)未被選取的候選設(shè)施點(diǎn)到各需求點(diǎn)的阻抗和，數(shù)值證明，每個(gè)區(qū)域內(nèi)已選設(shè)施點(diǎn)到各個(gè)需求點(diǎn)的阻抗和均小于其它候選設(shè)施點(diǎn)到各需求點(diǎn)的阻抗和，因而通過(guò)實(shí)驗(yàn)選出的設(shè)施點(diǎn)滿(mǎn)足全區(qū)域范圍整體阻抗最小。

圖3 空間位置分配結(jié)果

圖4 設(shè)施點(diǎn)及分配的候選設(shè)施點(diǎn)

實(shí)驗(yàn)證明，利用Model Buil der構(gòu)建基于阻抗等級(jí)的整體最優(yōu)空間位置分配分析模型，此模型可以解決本文提出的算法應(yīng)用問(wèn)題。本文提出的利用阻抗等級(jí)劃分的空間位置分配方法可應(yīng)用于多種類(lèi)型的空間位置分配問(wèn)題中，用數(shù)值的等級(jí)代替數(shù)值進(jìn)行解算的方法在保證阻抗最小化原則基礎(chǔ)上，縮小比較區(qū)間，能夠較大程度提高問(wèn)題的解算效率。

4 結(jié) 論

本文探討基于阻抗的整體最優(yōu)空間位置分配問(wèn)題，提出一種利用等級(jí)劃分的空間位置分配求解算法，實(shí)現(xiàn)整體最優(yōu)化空間位置分配分析。用阻抗等級(jí)代替阻抗值，與貪婪取走啟發(fā)式算法相比，較大程度縮小對(duì)比區(qū)間，提高解算速度，實(shí)現(xiàn)優(yōu)化服務(wù)點(diǎn)部署，并通過(guò)可視化建模的方式解決選址中的實(shí)際應(yīng)用問(wèn)題。但是以下問(wèn)題需要深入研究：

1）如何根據(jù)用戶(hù)需求和實(shí)際數(shù)據(jù)，更加合理的確定阻抗等級(jí)和聚合區(qū)間；

圖5 各區(qū)域內(nèi)候選設(shè)施點(diǎn)與需求點(diǎn)的阻抗和對(duì)比

2）本文在進(jìn)行位置分配分析時(shí)，沒(méi)有將阻抗中斷之外的需求點(diǎn)分配，而在很多實(shí)際問(wèn)題中，仍需要考慮這些需求點(diǎn)。

［1］ 李煉，余代俊，曾濤．困難地區(qū)大型工程預(yù)選址新方法探討［J］．測(cè)繪工程，2014，23（1）：61－64．

［2］ 邊馥苓，朱國(guó)賓，余潔．地理信息系統(tǒng)原理與方法［M］．北京：測(cè)繪出版社，1996：149－172．

［3］ 紀(jì)曉東，王雙龍，汪其志．基于工作流的地質(zhì)信息空間分析模型的設(shè)計(jì)與實(shí)現(xiàn)［J］．測(cè)繪工程，2010，19（3）：20－23．

［4］ 劉璇．基于GIS的物流配送中心選址方法的研究［D］．長(zhǎng)沙：中南大學(xué)，2012．

［5］ Arya V，Garg N，Khandekar R et al．Local Search Heuristics for P－median and Facility Location Pr oblems［J］．SIA M Jour nal on co mputering，2004，33（3）：544－562．

［6］ 關(guān)懷慶，張畢西，歐江艷．貪婪取走啟發(fā)式算法在離散網(wǎng)絡(luò)選址中的研究［J］．系統(tǒng)科學(xué)學(xué)報(bào)，2010，18（3）：49－52．

［7］ Deneubourg J L，Gross S，F(xiàn)ranks N，et al．The Dynamics of Collective sorting robot－like ants and ant－like robot［A］．Proceedings of the 1stConference on Si mulation of Adaptive Behavior［C］．1990：356－363．

［8］ 秦固．基于蟻群優(yōu)化的多物流配送中心選址算法［J］．系統(tǒng)工程理論與實(shí)踐，2006（4）：120－124．

［9］ 程滿(mǎn)，梁虹，馮濤．基于空間問(wèn)題建模概念過(guò)程的空間分析建模與實(shí)現(xiàn)［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2007，28（6）：4042－4045．

［10］方芳，徐世武，萬(wàn)波．GIS空間分析建模技術(shù)研究進(jìn)展［J］．測(cè)繪科學(xué)，2010，35（6）：137－138．

［11］左興東．三維GIS的數(shù)據(jù)結(jié)構(gòu)探討［J］．測(cè)繪與空間地理信息，2014，37（7）：120－122．

［12］董孟秋，李景文，張紫萍．基于面向?qū)ο髷?shù)據(jù)模型的地理實(shí)體距離度量關(guān)系分析方法［J］．測(cè)繪與空間地理信息，2014，37（5）：64－67．

［13］周?chē)?guó)清，陳昆華，何素楠，等．來(lái)賓市巖溶塌陷的時(shí)空分布特征分析［J］．測(cè)繪與空間地理信息，2014，37（4）：3－7．