雙層過道布置問題的混合整數(shù)規(guī)劃模型及啟發(fā)式求解方法

管 超，張則強(qiáng)，毛麗麗，李六柯

(西南交通大學(xué) 機(jī)械工程學(xué)院，四川 成都 610031)

0 引言

設(shè)施布局問題(Facility Layout Problem, FLP)是以最小化總物流成本為目標(biāo)，對空間的設(shè)施或設(shè)備進(jìn)行組合排序，良好的布局可以有效改善前置時(shí)間，提高作業(yè)效率，降低成本[1]。據(jù)估計(jì)，生產(chǎn)過程中總支出的20%～50%用于物料搬運(yùn)，其中10%～30%的物料搬運(yùn)成本[2]可通過合理布局來降低。因?yàn)樵搯栴}具有重要的研究意義和實(shí)用價(jià)值，近幾十年來一直受到工業(yè)界和學(xué)術(shù)界的關(guān)注[1-4]。

作為一種特殊的設(shè)施布局問題，過道布置問題(Corridor Allocation Problem, CAP)由Amaral[5]于2012年首次提出，并建立了該問題的混合整數(shù)規(guī)劃模型。CAP是將給定數(shù)目的設(shè)施安排在過道兩邊，尋求以最小化總物流成本為目標(biāo)的最優(yōu)化布局問題。和雙行布局問題[6]相似，CAP也具有良好的物料搬運(yùn)結(jié)構(gòu)與效率，在布局活動中被廣泛采用，兩者的主要區(qū)別在于CAPD必須滿足兩個(gè)條件：①相鄰設(shè)施之間沒有間隙；②上下兩行設(shè)施的布置起點(diǎn)相同。而雙行布局則無需滿足[5]。CAP在實(shí)際中具有廣泛的應(yīng)用，在服務(wù)部門領(lǐng)域，如教學(xué)樓中教室及校園管理部門的安排、超市貨架沿走廊兩邊的布置、醫(yī)院走廊兩側(cè)病房和各診室的安置[7]、行政辦公樓過道兩邊部門的安排[8]、大型購物中心商店的布置等;在工業(yè)制造領(lǐng)域，如微電子元器件在集成電路板中的布局、設(shè)施沿中心脊柱在凹陷處的布局設(shè)計(jì)等，其中半導(dǎo)體生產(chǎn)線的布局就是一種常見的脊柱式結(jié)構(gòu)[9]。通過對具有密切聯(lián)系的部門、元器件或設(shè)施設(shè)備進(jìn)行過道布置優(yōu)化，可進(jìn)一步提高服務(wù)質(zhì)量、產(chǎn)品性能和生產(chǎn)效率。因此，自2012年提出以來，該問題便快速成為設(shè)施布局領(lǐng)域一個(gè)新的研究熱點(diǎn)[5,7-8,10-13]。

FLP為典型的NP-hard組合優(yōu)化問題[1]，啟發(fā)式方法是求解該問題的有效方法。Amaral[5]針對CAP提出3種啟發(fā)式算法，并經(jīng)大量算例測試驗(yàn)證算法不但有效，而且其求解性能明顯優(yōu)于精確算法。為進(jìn)一步提高求解效率，Ghosh等[10]應(yīng)用混合遺傳算法和結(jié)合路徑再連接的分散搜索算法求解該問題，并對小于50個(gè)設(shè)施規(guī)模的算例進(jìn)行計(jì)算，實(shí)驗(yàn)結(jié)果表明，分散搜索算法在運(yùn)行效率上較遺傳算法更有優(yōu)勢;Ahonen等[11]采用禁忌搜索算法和模擬退火算法對不同規(guī)模的測試問題進(jìn)行了驗(yàn)算和對比，證明在求解質(zhì)量和求解效率方面模擬退火算法的性能更加優(yōu)異;Anjos等[12]針對多行布局問題提出一種半正定規(guī)劃方法，并用小規(guī)模算例進(jìn)行驗(yàn)算，在合理時(shí)間內(nèi)得到了高質(zhì)量的求解結(jié)果，而且針對難度更大的問題，將半正定優(yōu)化與啟發(fā)式方法相結(jié)合，求得了較高質(zhì)量的可行解并給出了目標(biāo)值下界;Hajipour等[14]應(yīng)用排隊(duì)系統(tǒng)構(gòu)建了一種多目標(biāo)設(shè)施位置分配模型，通過算法仿真確定了每層最佳設(shè)施和服務(wù)分配數(shù)量，并驗(yàn)證了模型的有效性;Zhao等[15]應(yīng)用一種兩階段方法研究不規(guī)則形狀的物流設(shè)施多層布局問題，為物流設(shè)施的多層布局提供了一定的參考依據(jù)。國內(nèi)研究方面，李聰波等[16]針對再制造工藝過程的不確定性問題，建立了再制造車間設(shè)施動態(tài)布局模型，并提出一種基于模擬退火算法的再制造車間設(shè)施布局優(yōu)化求解方法;鄭永前等[17]等針對動態(tài)單元構(gòu)建與布局問題中產(chǎn)品需求與機(jī)器產(chǎn)能的不確定性，建立了基于模糊需求和機(jī)器產(chǎn)能的基本問題模型，并提出一種基于結(jié)構(gòu)化編碼的分散搜索算法，通過與LINGO和模擬退火算法進(jìn)行對比，驗(yàn)證了模型的正確性與算法的有效性。

通過上述CAP相關(guān)文獻(xiàn)的分析可知，前述工作均是針對單層CAP進(jìn)行的研究。然而經(jīng)實(shí)際調(diào)研發(fā)現(xiàn)，當(dāng)對數(shù)量龐大的設(shè)施組進(jìn)行過道布置優(yōu)化時(shí)，過長的通道會增加占地面積，從而增加布局成本。為實(shí)現(xiàn)土地的集約利用，降低不必要的成本，設(shè)施被迫轉(zhuǎn)向多層空間布置。隨著多層布局在實(shí)際中被越來越多地采用，研究設(shè)施在多層空間中的布局優(yōu)化越發(fā)重要。參考已有文獻(xiàn)，尚未發(fā)現(xiàn)有關(guān)雙層CAP的公開報(bào)道。

本文考慮生產(chǎn)實(shí)際中布局用地成本因素和布置場地受限等情況對過道布置的影響，提出雙層CAP，并建立了該問題的混合整數(shù)規(guī)劃模型,通過對28個(gè)測試問題進(jìn)行精確求解，驗(yàn)證了模型的正確性。針對精確方法難以在合理時(shí)間內(nèi)求解大規(guī)模問題的不足，提出一種基于C2Opt鄰域搜索的啟發(fā)式算法，應(yīng)用該算法對所選測試算例進(jìn)行測試，并與其他3種啟發(fā)式算法進(jìn)行對比，驗(yàn)證了所提算法的求解性能。

1 雙層過道布置問題模型

1.1 問題描述

CAP是將一系列給定數(shù)目的設(shè)施布置到過道兩側(cè)，尋求一種最優(yōu)布置，使設(shè)施間的總物流成本最小。本文在此基礎(chǔ)上考慮用地成本因素、布置場地受限等情況對設(shè)施布局的影響，提出雙層CAP，該問題的示意圖如圖1所示。其中，設(shè)備組1～3布置在第一層，A～F布置在第二層，各設(shè)備組由多臺設(shè)備組成，共同完成一項(xiàng)作業(yè)，可看作為一個(gè)“設(shè)施”，設(shè)備組之間存在一定的物流關(guān)系。

與傳統(tǒng)CAP相比，雙層CAP的特點(diǎn)為：①設(shè)施在兩層空間布置，各層設(shè)施沿過道兩邊布置；②不是傳統(tǒng)CAP的簡單相加，不僅同層設(shè)施間存在物流關(guān)系，不同層設(shè)施之間也存在物流交互，交互通道為放置在過道最左邊的貨梯。根據(jù)該問題的特點(diǎn)，對各層空間中的設(shè)施進(jìn)行組合排序，找到最優(yōu)布置序列，并確定此時(shí)各層設(shè)施布置的排列順序，從而最小化總物流成本。

1.2 基本假設(shè)條件

(1)各設(shè)施間物流和每個(gè)矩形設(shè)施靠過道邊線的寬度為已知量。

(2)每個(gè)設(shè)施靠過道邊線的中點(diǎn)即為該設(shè)施物流的交互點(diǎn)。

(3)相鄰兩設(shè)施之間沒有間隙。

(4)各層過道兩邊設(shè)施均從最左邊同一點(diǎn)開始布置，并記該點(diǎn)的橫坐標(biāo)為0。

(5)假設(shè)每層設(shè)施間的通道寬度為0。

(6)不同層設(shè)施之間通過貨梯進(jìn)行物流交互，假設(shè)貨梯長度、寬度為0，只考慮其運(yùn)輸路程。

(7)假設(shè)貨梯布置在過道最左邊，即貨梯口與每層過道的布置起點(diǎn)相同。

1.3 變量與參數(shù)定義

為描述方便，雙層過道布置模型中所用數(shù)學(xué)符號的意義如下：

P為樓層集合P={1,2}；

p為樓層編號，p∈P；

n為問題規(guī)模；

Np為第p層所要布置的設(shè)施集合；

h為貨梯運(yùn)輸路程；

rp,i為設(shè)施下標(biāo)符號，表示布置在第p層的第i個(gè)設(shè)施，p∈P；

cij為設(shè)施i,j之間單位距離的物流成本,?i∈I1，?j∈I2,其中I1={1,2,…,n-1},I2={i+1,i+2,…,n}；

li為設(shè)施i的寬度；

dij為設(shè)施i和設(shè)施j的設(shè)施物流交互點(diǎn)之間的距離；

αij為二進(jìn)制變量，若設(shè)施i，j分配在同一行，且設(shè)施i布置在設(shè)施j的左邊，則αij=1，否則αij=0。

1.4 數(shù)學(xué)模型

借鑒單層CAP模型，建立了如下雙層CAP的混合整數(shù)規(guī)劃模型：

(1)

s.t.

i

(2)

(3)

(4)

αrp,jrp,i≥0,i,j∈Np,i

(5)

-αrp,irp,j+αrp,irp,k+αrp,jrp,k-αrp,jrp,i+αrp,krp,i+

αrp,krp,j≤1,i,j,k∈Np,

i

(6)

-αrp,irp,j+αrp,irp,k-αrp,jrp,k+αrp,jrp,i-

αrp,krp,i+αrp,krp,j≤1,

i,j,k∈Np,i

(7)

αrp,irp,j+αrp,irp.k+αrp,jrp,k+αrp,jrp,i+

αrp,krp,i+αrp,krp,j≥1,

i,j,k∈Np,i

(8)

αrp,irp,j∈{0,1},1≤i,j≤n,i≠j,p∈P。

(9)

可知，約束(2)和(3)用于計(jì)算同一層各設(shè)施間的距離；約束(4)用于計(jì)算第一層與第二層各設(shè)施間的距離；約束(5)用以防止每層同行設(shè)施發(fā)生重疊放置；約束(6)～(8)用于確定每層的決策變量αrp,irp,j；式(9)給定決策變量αrp,irp,j的定義域。

2 啟發(fā)式算法

雙層CAP作為典型的NP-hard組合優(yōu)化問題，具有較大的求解難度，特別是針對大規(guī)模問題，精確方法難以在合理時(shí)間內(nèi)求得最優(yōu)解，因此本文提出一種啟發(fā)式算法，以期快速求得高質(zhì)量的近優(yōu)解。

2.1 解的編碼和解碼表示

結(jié)合雙層CAP的特點(diǎn)，本文采用一種基于設(shè)施的表示方式，通過這種編碼方式可將一種布局方案編碼成一個(gè)設(shè)施編號的序列。針對假設(shè)(1)，首先確定各層所要布置設(shè)施的編號，以設(shè)施數(shù)目n=9的問題為例，一個(gè)可行的分配方案為N=[N1;N2]，N1={1,3,5,7,9}，N2={2,4,6,8}，其中N1表示需要布置在第一層的設(shè)施編號集合，N2表示需要布置在第二層的設(shè)施編號集合。

針對以上確定的分配方案，布局方案中一個(gè)可行解的編碼和解碼如圖2所示。

該可行解表示為x=[x1;x2]=[5,3,1,7,9;6,2,8,4]，n1=5，n2=4，t1=2，t2=3。其中：n1，n2分別表示布置在第一、二層的設(shè)施總數(shù)；t1，t2分別表示第一、二層中布置在第一行的設(shè)施數(shù)。即第一層布局方案x1=[5,3,1,7,9]中布置到第一行的設(shè)施數(shù)為2，序列為[5,3]，第二行序列為[1,7,9]；第二層布局方案x2=[6,2,8,4]中布置到第一行的設(shè)施數(shù)目為3，序列為[6,2,8]，第二行序列為[4]。

2.2 C2Opt鄰域搜索程序與inversion程序

根據(jù)雙層CAP的特點(diǎn)，為實(shí)現(xiàn)對鄰域空間的局部搜索，對原C2Opt的擾動機(jī)制加以改進(jìn)，構(gòu)建適應(yīng)該問題的兩待交換設(shè)施編號選取方法和設(shè)施位置互換機(jī)制，確保尋優(yōu)過程中各層所要布置的設(shè)施編號不發(fā)生變化，且僅當(dāng)兩設(shè)施位置交換所得的新序列能對當(dāng)前較優(yōu)解做出有益改善時(shí)保留計(jì)算結(jié)果。該C2Opt鄰域搜索子程序的具體執(zhí)行步驟如下：

步驟2令i=1，j=1。

步驟3若i≤n1則執(zhí)行步驟4，否則轉(zhuǎn)步驟7。

步驟4若j≤n2則執(zhí)行步驟5，否則i=i+1，轉(zhuǎn)步驟3。

步驟6若V

為避免算法陷入局部最優(yōu)，本文引入inversion程序，該程序的具體執(zhí)行過程為：以圖2所示的布局方案為例，分別從序列x1，x2中等概率隨機(jī)選擇任意兩個(gè)不同的設(shè)施編號，并倒置這兩個(gè)設(shè)施間的序列，重新排列當(dāng)前設(shè)施序列，具體過程如圖3所示。

圖中，分別選取設(shè)施集合x1，x2中的設(shè)施編號5，7與2，8之間的連續(xù)序列進(jìn)行倒置，所得新解為x*=[7,1,3,5,9;6,8,2,4]。

2.3 算法步驟

本文所提啟發(fā)式算法主要包括C2Opt鄰域搜索程序和inversion程序，通過不斷擾動產(chǎn)生新解序列，擴(kuò)大搜索空間，最終獲得滿意解甚至全局最優(yōu)解。

C2Opt子程序通過交換兩個(gè)設(shè)施位置，產(chǎn)生新的布局序列，若新序列的總物流成本小于原序列物流成本，則保留該交換結(jié)果，用交換之后的序列替代原序列，否則放棄交換結(jié)果繼續(xù)下一循環(huán)。

針對C2Opt子程序在鄰域搜索過程中可能會陷入局部最優(yōu)而無法求得全局最優(yōu)解的問題，加入inversion子程序，在C2Opt子程序無法跳出局部最優(yōu)時(shí)，重新隨機(jī)選擇一個(gè)新可行解繼續(xù)搜索。

為避免在搜索過程中遺失當(dāng)前最優(yōu)解，在啟發(fā)式算法執(zhí)行過程中內(nèi)嵌一個(gè)記憶解OFV，用于保存在鄰域搜索過程中找到的最優(yōu)解，在迭代過程中，當(dāng)搜索到一個(gè)新解[x1′;x2′]時(shí)，比較目標(biāo)函數(shù)值ofv和OFV，若ofv

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

為驗(yàn)證雙層CAP模型的正確性，針對設(shè)施數(shù)目從9～49不同規(guī)模的28個(gè)基準(zhǔn)算例，首先應(yīng)用Lingo11.0軟件進(jìn)行精確求解，測試數(shù)據(jù)來源于文獻(xiàn)[5,18-22]。計(jì)算實(shí)驗(yàn)采用的計(jì)算機(jī)硬件配置為Pentium(R)Dual-Core CPU E6700 3.2 GHz，4 GB內(nèi)存，在Windows 7操作系統(tǒng)下運(yùn)行Lingo試驗(yàn)程序求出精確解。

對于所選28個(gè)不同規(guī)模的基準(zhǔn)算例，根據(jù)實(shí)際中各層布置的設(shè)施數(shù)相差不大時(shí)，占地面積最小的原則，本文假設(shè)上下層的設(shè)施數(shù)均為問題規(guī)模的一半，且將設(shè)施編號為奇數(shù)的設(shè)施布置在第一層，編號為偶數(shù)的設(shè)施布置在第二層。對于本文所提混合整數(shù)規(guī)劃模型，各層布置的設(shè)施集合可任意給定，不局限于上述假設(shè)情況。

確定各層所要布置的設(shè)施集合后，假設(shè)貨梯運(yùn)輸路程h=10，運(yùn)用Lingo軟件，依據(jù)1.4節(jié)給出的混合整數(shù)規(guī)劃模型，采用分支定界法進(jìn)行求解。針對設(shè)施數(shù)目為9～25的13個(gè)中小規(guī)模測試問題，Lingo軟件在合理時(shí)間內(nèi)求得了最優(yōu)解，驗(yàn)證了模型的正確性。但隨著問題規(guī)模的增大，精確方法的求解時(shí)間大幅度增加，難以在合理時(shí)間內(nèi)求得大規(guī)模問題的最優(yōu)解。為給所提啟發(fā)式算法的求解結(jié)果提供參考依據(jù)，針對規(guī)模大于25的測試算例，設(shè)置Lingo軟件中的運(yùn)行時(shí)間為600 s。

針對精確方法運(yùn)算時(shí)間長、難以求解大規(guī)模問題的不足，本文提出一種啟發(fā)式算法Heuristic_C2Opt，以期在保證求解精度的前提下進(jìn)一步提高求解效率。為說明本文所提算法求解雙層CAP的有效性，將Heuristic_C2Opt算法與文獻(xiàn)[5]提出的3種啟發(fā)式算法進(jìn)行對比，3種啟發(fā)式算法分別記為Heuristic_1(2-opt),Heuristic_1(3-opt)和Heuristic_2。隨后在同一運(yùn)行環(huán)境下使用MATLAB R2010a軟件開發(fā)了啟發(fā)式算法的實(shí)驗(yàn)程序。兼顧求解性能與求解效率，經(jīng)多次運(yùn)算測試，算法的參數(shù)設(shè)置如表1和表2所示。通過對傳統(tǒng)CAP的研究可知，當(dāng)過道兩邊設(shè)施數(shù)相差不大時(shí)，總物流成本最小，由此確定各層布置在第一行設(shè)施數(shù)的上下限,如表1第5～8列所示。

為準(zhǔn)確測試所提啟發(fā)式算法的求解性能，針對每個(gè)測試問題，算法均運(yùn)行60次，所求得的最優(yōu)目標(biāo)函數(shù)值OFV及程序運(yùn)行時(shí)間Time/s如表3的第5～12列所示，所得最優(yōu)解序列如表4所示。

表3 算法求解結(jié)果對比

續(xù)表3

表4 啟發(fā)式算法求得的最優(yōu)設(shè)施序列

續(xù)表4

將Lingo求得的目標(biāo)函數(shù)值OFV0及程序運(yùn)行時(shí)間Time(單位：s)列于表3中第3，4列，通過對比表3中Lingo和啟發(fā)式算法的求解結(jié)果可以看出，針對13個(gè)中小規(guī)模的基準(zhǔn)算例，Heuristic_C2Opt算法均求得了和精確方法相同的最優(yōu)解，而其他3種算法未全部求得。對于測試問題N30_01，Lingo11.0軟件在求解了69 780 s后仍未找到全局最優(yōu)解，停止程序運(yùn)行時(shí)所得的當(dāng)前最優(yōu)解為10 899，而4種啟發(fā)式算法所得結(jié)果均為10 898，優(yōu)于Lingo的當(dāng)前最優(yōu)解，其中Heuristic_C2Opt算法用時(shí)最少。對于所選的28個(gè)測試算例，問題規(guī)模從9增大到49，精確方法的求解難度呈指數(shù)級增長，但Heuristic_C2Opt算法僅在92.99 s的時(shí)間內(nèi)求得了比Lingo運(yùn)行600 s更好的近優(yōu)解，且與其他3種啟發(fā)式算法相比，Heuristic_C2Opt算法也取得了更優(yōu)結(jié)果，由此說明，本文所提Heuristic_C2Opt算法具有優(yōu)異的求解性能。

Heuristic_C2Opt算法不僅在求解質(zhì)量上優(yōu)于其他方法，在求解效率方面亦具有優(yōu)勢。通過對比表3數(shù)據(jù)可以看出，針對28個(gè)測試算例，4種啟發(fā)式算法中，Heuristic_C2Opt算法在最短時(shí)間內(nèi)求得了最優(yōu)結(jié)果，說明了該算法求解效率的優(yōu)越性。進(jìn)一步對比精確方法可知，針對N25_05規(guī)模問題，Lingo求得的精確解為13 123，求解時(shí)間為1 409 s,而Heuristic_C2Opt算法求得相同解所用的時(shí)間為11.02 s，僅為精確求解時(shí)間的1/1 193。對于其他大規(guī)模算例問題，該算法也在較短時(shí)間內(nèi)求得了高質(zhì)量的滿意解。為更直觀地觀察該算法的求解優(yōu)勢，針對精確方法與Heuristic_C2Opt算法均能求得最優(yōu)解的13個(gè)中小規(guī)模算例，繪制兩者的求解時(shí)間對比圖，如圖5所示。

由圖5可以看出，針對每個(gè)測試問題，Heuristic_C2Opt算法的求解時(shí)間均小于Lingo的求解時(shí)間，且隨著問題規(guī)模的增大，精確方法的求解時(shí)間大幅度增加，而Heuristic_C2Opt算法的求解時(shí)間增長緩慢，表明所提啟發(fā)式算法具有更高的求解效率。

為進(jìn)一步表明所提啟發(fā)式算法的求解性能，根據(jù)Heuristic_C2Opt算法求得的1 680個(gè)計(jì)算結(jié)果，計(jì)算其與精確方法求解結(jié)果的偏差gap，

gap(%)=|(OFV1-OFV0)/OFV0|×100%，

并繪制成如圖6所示的求解偏差箱形圖。圖中：箱線圖的上下框線、中間線、點(diǎn)畫線分別表示該組計(jì)算結(jié)果的上下四分位數(shù)、中位值、平均偏差;上下框線之外的延伸線表示最大值(最小值)到上(下)四分位數(shù)的取值區(qū)間;符號“+”表示不在正常值分布區(qū)間的異常值?？梢钥闯?，針對28個(gè)不同規(guī)模的基準(zhǔn)算例，方盒長度普遍較小，特別是對規(guī)模小于15的測試問題，其上、下四分位數(shù)幾乎與中位值重合于0，偏差gap的最大值也僅為0.16%，表明所提啟發(fā)式算法具有良好的求解穩(wěn)定性。

通過分析表3中的數(shù)據(jù)可以看出，Heuristic_C2Opt算法可以快速求得近優(yōu)解，尤其對于中小規(guī)模測試問題，所用求解時(shí)間均不足1 s，對于大規(guī)模問題也能較快求解，具有較高的求解效率。為進(jìn)一步說明該啟發(fā)式算法的求解特點(diǎn)，選取N25_05,N30_05,sko_42_05和sko_49_05 4種不同規(guī)模的測試問題繪制相應(yīng)的算法收斂圖，如圖7所示。

由圖7可以看出，4條收斂曲線的下降趨勢明顯，說明所提啟發(fā)式算法具有較快的收斂性，且算法在搜索過程中具有跳出局部最優(yōu)的能力。為進(jìn)一步說明算法的收斂速度，以測試問題N25_05為例，當(dāng)算法進(jìn)行到第323次迭代時(shí)，尋得最優(yōu)目標(biāo)函數(shù)，相當(dāng)于算法運(yùn)行1.41 s后就已經(jīng)找到近優(yōu)解13 123，由此可見該啟發(fā)式算法收斂速度快，具有較強(qiáng)的搜索性能。

4 結(jié)束語

針對實(shí)際布局活動中對多層過道布置的需求，本文構(gòu)建了考慮設(shè)施空間布局的雙層CAP，建立了該問題的混合整數(shù)規(guī)劃模型。為求解該問題，提出一種基于C2Opt鄰域搜索的啟發(fā)式算法。該算法主要由改進(jìn)的C2Opt鄰域搜索程序和inversion程序構(gòu)成，通過引入的記憶機(jī)制保留精英解。運(yùn)用Heuristic_C2Opt算法對28個(gè)不同規(guī)模(9～49個(gè)設(shè)施)的基準(zhǔn)問題進(jìn)行測試，并與3種啟發(fā)式算法進(jìn)行對比，結(jié)果表明Heuristic_C2Opt算法在求解質(zhì)量和求解效率方面均優(yōu)于Heuristic_1(2-opt/3-opt)和Heuristic_2算法。而且對于中小規(guī)模問題，啟發(fā)式算法能求得和精確方法相同的最優(yōu)解，求解時(shí)間不超過1s；對于大規(guī)模問題，所提算法的求解結(jié)果優(yōu)于給定時(shí)間內(nèi)Lingo的精確求解結(jié)果，且隨問題規(guī)模的增大，其求解優(yōu)勢愈加明顯。

由于雙層CAP具有較高的復(fù)雜性，本文在假定分配方案已知的前提下進(jìn)行了研究，下一步將考慮對所有可能的分配方案進(jìn)行布置優(yōu)化，并將用地成本融入目標(biāo)函數(shù)，進(jìn)一步完善雙層CAP。在求解方法層面，將尋求更加優(yōu)異的智能算法，進(jìn)一步提高搜索效率與求解質(zhì)量。