設(shè)施服務(wù)區(qū)劃分問(wèn)題-精確算法還是元啟發(fā)算法

設(shè)施服務(wù)區(qū)劃分問(wèn)題：精確算法還是元啟發(fā)算法？?jī)?nèi)容研究背景數(shù)學(xué)模型元啟發(fā)算法案例測(cè)試討論與結(jié)論一、研究背景區(qū)劃問(wèn)題類型：均質(zhì)性：區(qū)內(nèi)均質(zhì)、區(qū)間異質(zhì)、分區(qū)連續(xù)等；功能性：區(qū)內(nèi)聯(lián)系緊密、區(qū)間聯(lián)系較弱、分區(qū)連續(xù)等；均衡性：分區(qū)均衡(或均等)、緊湊、連續(xù)，等。設(shè)施服務(wù)區(qū)劃分問(wèn)題：學(xué)校、診所、避難所、應(yīng)急等設(shè)施服務(wù)區(qū)的劃分…Wonk

Blog設(shè)施服務(wù)區(qū)劃分問(wèn)題某一地理區(qū)域，給定空間單元及服務(wù)需求、服務(wù)設(shè)施位置及服務(wù)容量、交通網(wǎng)絡(luò)等信息，劃定最最優(yōu)的設(shè)施服務(wù)范圍，要求：分區(qū)均衡：供需平衡(分區(qū)內(nèi)服務(wù)需求小于服務(wù)供給)；分區(qū)緊湊：使用服務(wù)便捷(使用服務(wù)的旅行距離最短)；分區(qū)連續(xù)：分區(qū)內(nèi)部連通；單元完整：基本單元不拆分(保持基本空間單元不被分割)。服務(wù)區(qū)劃分問(wèn)題求解方法精確算法：建立線性規(guī)劃模型，使用MIP優(yōu)化器求解模型模型的求解能力未知多使用簡(jiǎn)化模型(不考慮某些分區(qū)要求)啟發(fā)式算法：方法簡(jiǎn)單，但性能不高元啟發(fā)算法：主流方法，方法眾多，仍在探索中局部搜索類算法、種群類算法、混合算法算法測(cè)試不充分，算法通用性、可重復(fù)性有待驗(yàn)證超啟發(fā)算法：處于起步階段研究?jī)?nèi)容精確算法：隨MIP優(yōu)化器技術(shù)進(jìn)步和計(jì)算機(jī)性能大幅提升，精確算法的求解能力如何？元啟發(fā)算法：設(shè)計(jì)基于進(jìn)化框架的混合元啟發(fā)算法：遺傳進(jìn)化(GA)+局部搜素(LS)+全局選擇改進(jìn)(SPP)，其性能如何？比較精確算法與元啟發(fā)算法的性能，為通用、高性能算法設(shè)計(jì)奠定基礎(chǔ)。二、數(shù)學(xué)模型問(wèn)題描述：集合V={1,2…n}表示n個(gè)空間單元，單元i服務(wù)需求量為pi；集合S={s1,s2…sK}表示K個(gè)提供服務(wù)的空間單元，單元k提供服務(wù)量為qk；dij表示單元i與單元j之間的距離；集合Ni表示單元i的相鄰單元集合；如何劃分最優(yōu)的設(shè)施服務(wù)區(qū)，滿足分區(qū)供需均衡、空間連續(xù)，且服務(wù)使用最便捷？數(shù)學(xué)模型設(shè)施服務(wù)分區(qū)問(wèn)題：空間連續(xù)約束的一般指派問(wèn)題：決策變量：

Yik,Fijk,Hk目標(biāo)函數(shù)：旅行總距離+設(shè)施容量限制懲罰(α足夠大)約束條件：需求指派、設(shè)施容量、空間連續(xù)約束模型解釋目標(biāo)函數(shù)(1)：最小化使用設(shè)施的總旅行距離，以及設(shè)施超容量；約束(2)：保證每一個(gè)單元被一個(gè)設(shè)施服務(wù)；約束(7)：設(shè)施容量約束；約束(3)-(6)：網(wǎng)絡(luò)流模型(Shirabe,

2005;

Duque

et

al.

2011)，保證分區(qū)空間連續(xù)；軟約束：引入決策變量Hk，約束(7)為是一個(gè)“軟”約束，目標(biāo)函數(shù)對(duì)設(shè)施超容量Hk進(jìn)行懲罰，有利于快速發(fā)現(xiàn)可行解；僅考慮將某一需求單元分配給周邊的Nf個(gè)設(shè)施，可減少?zèng)Q策變量數(shù)量模型應(yīng)用技巧：決策變量化簡(jiǎn)案例規(guī)模決策變量個(gè)數(shù)需求單元1000不化簡(jiǎn)變量50,000設(shè)施單元50化簡(jiǎn)變量(Nf=8)8,000化簡(jiǎn)變量(Nf=6)6,000Xij=0三、元啟發(fā)算法設(shè)計(jì)基于進(jìn)化算法框架，設(shè)計(jì)混合元啟發(fā)算法。參數(shù)：種群數(shù)量M、迭代次數(shù)N、交叉概率Pc、交叉基因比率(Rc)、變異概率Pm。構(gòu)造M個(gè)初始分區(qū)方案，作為種群集合P；迭代執(zhí)行(3)-(7)直到滿足終止條件；隨機(jī)選擇個(gè)體P1和P2，進(jìn)行交叉操作，獲得新個(gè)體P’；對(duì)個(gè)體P’進(jìn)行變異操作，獲得P’’；對(duì)個(gè)體P’’進(jìn)行局部搜索，獲得P’’’，記錄當(dāng)前分區(qū)，更新最好解；根據(jù)P’’’的適宜度、差異度更新種群P；評(píng)價(jià)前期進(jìn)化過(guò)程，調(diào)整變異率Pm；根據(jù)歷史分區(qū)記錄，建立SPP模型，嘗試選擇更好的分區(qū)方案；輸出最好解。三、元啟發(fā)算法設(shè)計(jì)基于進(jìn)化算法框架，設(shè)計(jì)混合元啟發(fā)算法。參數(shù)：種群數(shù)量M、迭代次數(shù)N、交叉概率Pc、交叉基因比率(Rc)、變異概率Pm。Readinstance

data;CreateMinitialsolutionsaspopulation

P;Pool=[];For(loop=0;loop<N;

loop++)SelectindividualsP1andP2fromP

randomly;P’=crossover(P1,P2,Pc,

Rc);P’=mutation(P’,

Pm);P’’=Localsearch(P’’,

local_search_operators)；UpdateServiceAreaPool(Pool,P’

’);UpdatePopulation(P,P’

’);Pm=AdjustParameter(Pm);P’=SPPModeling(Pool)；Outputthebest

solution.算法要點(diǎn)(1)：初始種群生成不考慮空間連續(xù)，建立數(shù)學(xué)模型，并求解；可將模型目標(biāo)值作為問(wèn)題解的下界；對(duì)模型結(jié)果進(jìn)行修復(fù)，滿足空間連續(xù)、單元完整要求，作為初始解。算法要點(diǎn)(2)：交叉操作基因編碼：將分區(qū)方案表達(dá)為分區(qū)編號(hào)索引，對(duì)應(yīng)于空間單元V={1,2,3…n}四種交叉方法：Uniform：以交叉概率Pc選擇P2基因替換P1對(duì)應(yīng)的基因；Ordered1：以概率Pc選擇P1的分區(qū)，替換為P2中對(duì)應(yīng)的基因；Ordered2：以概率Pc選擇P2的分區(qū)，用所選擇分區(qū)中的基因置換P1對(duì)應(yīng)的基因；MergeSplit：將P1和P2基因進(jìn)行Overlay操作，以概率Pc選擇碎片斑塊，用斑塊中P2的基因置換P1對(duì)應(yīng)的基因。交叉后，對(duì)基因進(jìn)行修復(fù)，滿足空間連續(xù)要求。交叉操作意圖UniformCrossoverOrder1CrossoverOrder2Crossover算法要點(diǎn)(3)：變異操作查找處于分區(qū)邊界的單元；以Pm的概率，將邊界單元移動(dòng)到相鄰的分區(qū)；若違背分區(qū)連續(xù)，進(jìn)行修復(fù)。變異操作示意(Pm=0.05)：算法要點(diǎn)(4)：局部搜索改進(jìn)鄰域搜索算子：One-unit

shiftTwo-unit

shiftThree-unitshift依次使用搜索算子，改進(jìn)分區(qū)方案。算法要點(diǎn)(5)：變異概率Pm更新周期性進(jìn)行變異概率Pm更新；每次迭代均記錄子代P’’’，累計(jì)迭代次數(shù)達(dá)到一定數(shù)值后，評(píng)價(jià)子代基因差異度；子代P’’’基因平均差異度大于某一閾值時(shí),Pm=Pm+d；否則，Pm=max(Pm-d,0.0)；若子代P’’’適宜度(目標(biāo)值)接近下界時(shí)，Pm取最小值(如Pm=0.005)。算法要點(diǎn)(6)：SPP模型令集合Ω={1,2,3…}為進(jìn)化過(guò)程中所發(fā)現(xiàn)的所有分區(qū)；分區(qū)i屬性：目標(biāo)值ci，單元集合Ui；SPP(set

partitioning

problem)模型如下：其他重要操作邊界單元判斷空間連續(xù)判斷空間連續(xù)修復(fù)種群更新：按個(gè)體適宜度排序、按基因差異度選擇…算法特征修改算法參數(shù)，控制算法執(zhí)行；改變參數(shù)，也可以實(shí)現(xiàn)多種算法。算法選擇交叉變異LSSPP混合算法MA-SPP

遺傳算法GA

文化基因算法MA

迭代局部搜索ILS

混合算法GA-SPP

混合算法ILS-SPP

分區(qū)問(wèn)題算法框架設(shè)計(jì)四、算法測(cè)試三個(gè)案例區(qū)域案例區(qū)域ZYGYGY2空間單元數(shù)量3242971276鄰接數(shù)量8097993910總需求387336824819812設(shè)施數(shù)量13-1737-4118-22案例數(shù)量：60=3個(gè)區(qū)域*5個(gè)設(shè)施數(shù)量*2組設(shè)施分布*2組設(shè)施容量模型計(jì)算結(jié)果(MIPGap=E-10)InstanceObjMipgapTime/szy_13a2882.09opt627.16zy_14a2505.25opt645.06zy_15a2196.25opt318.53zy_16a1995.61opt313.44zy_17a1972.27opt895.30gy_37a76856.92opt6945.33gy_38a75941.88opt5662.15gy_39a75193.32opt5457.44gy_40a74046.95opt4404.17gy_41a73368.85opt1594.42gy2_18a2377508.740.07%7206.98gy2_19a2123755.170.05%7205.84gy2_20a2012921.650.01%7203.23gy2_21a1931624.28opt634.22gy2_22a1875355.92opt701.17zy_13b1897.42opt358.23zy_14b1755.88opt149.28zy_15b1656.53opt67.35zy_16b1591.86opt121.04zy_17b1536.53opt73.32gy_37b75105.07opt3257.84gy_38b73943.37opt1172.37gy_39b72908.70opt672.22gy_40b72166.58opt2320.32gy_41b71202.99opt665.62gy2_18b1986777.50opt159.29gy2_19b1927032.00opt67.03gy2_20b1904637.49opt74.10gy2_21b1889743.21opt86.73gy2_22b1875355.92opt59.46InstanceObjMipgapTime/szy_13c2822.23opt43.70zy_14c2589.93opt514.55zy_15c2405.40opt399.81zy_16c2260.01opt274.39zy_17c2250.94opt575.95gy_37c79924.280.12%7204.52gy_38c79514.67opt1112.73gy_39c78748.95opt1280.30gy_40c78402.60opt1088.69gy_41c79771.000.21%7203.73gy2_18c2317477.990.03%7204.80gy2_19c2142243.120.03%7205.44gy2_20c2119263.560.04%7205.84gy2_21c2026852.860.00%7205.17gy2_22c2003951.770.01%7204.17zy_13d2050.88opt77.56zy_14d1927.72opt202.80zy_15d1874.58opt104.13zy_16d1840.85opt787.34zy_17d1841.48opt3965.80gy_37d76744.96opt1090.05gy_38d77792.10opt2035.78gy_39d79150.720.24%7206.91gy_40d78572.690.32%7205.88gy_41d80533.510.13%7205.42gy2_18d2016743.88opt6941.55gy2_19d1986365.28opt929.58gy2_20d2026991.940.01%7205.20gy2_21d2016529.840.02%7208.63gy2_22d2028631.850.03%7207.47計(jì)算環(huán)境：Inter

Core

i7600

CPU@3.4G

CPU,8GB

RAM,

CPLEX

12.6計(jì)算時(shí)間40.3h；44個(gè)案例獲得最優(yōu)解；16個(gè)案例2h內(nèi)未獲得最優(yōu)解，但獲得近似最優(yōu)解(Mipgap=0.00%-0.32%)模型計(jì)算結(jié)果(MIPGap=0.1%)InstanceObjMipgapTime/szy_13a2883.600.08%76.55zy_14a2505.610.10%49.91zy_15a2197.850.10%73.17zy_16a1996.610.07%81.39zy_17a1972.270.10%147.31gy_37a76893.810.10%1000.41gy_38a75957.220.07%1546.51gy_39a75194.220.10%1011.94gy_40a74046.950.03%181.16gy_41a73368.850.10%705.13gy2_18a2377925.440.10%2970.20gy2_19a2124790.730.10%1232.28gy2_20a2013710.230.07%87.33gy2_21a1932569.410.09%9.63gy2_22a1875640.730.04%9.78zy_13b1897.420.05%48.44zy_14b1756.750.08%56.95zy_15b1657.140.10%68.41zy_16b1591.860.10%27.30zy_17b1536.530.10%29.28gy_37b75155.590.09%501.13gy_38b74003.950.10%356.23gy_39b72955.540.10%181.28gy_40b72166.580.04%126.73gy_41b71202.990.06%147.67gy2_18b1988013.040.10%9.06gy2_19b1927633.970.04%15.83gy2_20b1905283.180.06%9.41gy2_21b1890373.970.05%16.22gy2_22b1875793.650.04%21.22InstanceObjMipgapTime/szy_13c2822.230.03%41.19zy_14c2591.260.10%294.53zy_15c2406.730.07%236.59zy_16c2261.610.10%271.67zy_17c2251.300.07%285.47gy_37c79924.280.13%7206.30gy_38c79514.670.10%1519.88gy_39c78748.950.07%1468.88gy_40c78402.600.10%584.56gy_41c79858.560.36%7204.70gy2_18c2318738.310.09%3917.47gy2_19c2143268.980.10%2429.09gy2_20c2119710.120.10%367.50gy2_21c2027933.750.10%78.42gy2_22c2004970.700.10%168.47zy_13d2051.940.10%53.64zy_14d1928.180.10%117.78zy_15d1875.160.10%56.73zy_16d1840.850.09%263.58zy_17d1841.480.10%851.28gy_37d76744.960.10%259.61gy_38d77792.100.10%999.95gy_39d79365.890.91%7212.16gy_40d78572.690.27%7204.80gy_41d80533.510.10%4017.06gy2_18d2017112.030.05%120.08gy2_19d1987168.870.10%19.83gy2_20d2027771.820.09%109.42gy2_21d2017206.930.09%430.25gy2_22d2029248.080.10%1547.50計(jì)算時(shí)間16.7h；4個(gè)案例2h內(nèi)不能滿足MIPGap<0.1%模型計(jì)算結(jié)果(MIPGap=0.3%)instanceObjMipgapTimezy_13c2828.440.30%32.47zy_14c2593.880.28%214.52zy_15c2409.820.23%134.44zy_16c2263.300.30%78.94zy_17c2255.300.30%199.86gy_37c79988.820.30%1913.70gy_38c79514.670.29%774.28gy_39c78777.970.30%1300.80gy_40c78402.600.22%652.13gy_41c79808.180.30%3617.14gy2_18c2320784.580.20%4003.77gy2_19c2145496.260.29%100.23gy2_20c2122781.630.30%13.97gy2_21c2028948.650.16%61.66gy2_22c2005778.290.17%65.50zy_13d2051.170.21%33.05zy_14d1929.480.30%50.74zy_15d1876.000.30%49.69zy_16d1842.460.30%86.33zy_17d1843.800.30%541.09gy_37d76770.130.23%156.41gy_38d77794.940.30%381.78gy_39d79158.070.34%7204.70gy_40d78572.690.30%3520.94gy_41d80577.900.30%6449.64gy2_18d2018824.430.16%24.09gy2_19d1989195.850.30%20.38gy2_20d2028957.110.19%28.27gy2_21d2020525.630.27%96.50gy2_22d2030951.630.27%118.64instanceObjMipgapTimezy_13a2886.130.19%378.95zy_14a2509.980.30%48.06zy_15a2200.240.30%46.16zy_16a1999.300.30%71.28zy_17a1975.170.29%162.55gy_37a76941.680.25%1022.09gy_38a76026.640.30%412.38gy_39a75273.050.29%606.81gy_40a74064.480.15%313.98gy_41a73386.370.08%177.73gy2_18a2379648.770.28%96.95gy2_19a2128421.060.30%544.69gy2_20a2014200.100.09%101.56gy2_21a1932569.410.09%9.39gy2_22a1875640.730.04%9.59zy_13b1898.430.30%24.64zy_14b1758.200.30%30.58zy_15b1657.880.27%34.58zy_16b1592.700.40%27.66zy_17b1536.530.19%27.05gy_37b75245.890.30%309.44gy_38b74086.050.30%249.45gy_39b73080.700.30%151.64gy_40b72309.200.30%83.42gy_41b71280.690.26%88.25gy2_18b1991266.880.28%6.92gy2_19b1927633.970.04%15.55gy2_20b1905283.180.06%8.94gy2_21b1890373.970.05%16.00gy2_22b1879323.470.24%9.30計(jì)算時(shí)間10.3h；1個(gè)案例2h內(nèi)不能滿足MIPGap<0.3%計(jì)算時(shí)間比較各區(qū)域不同求解質(zhì)量要求的計(jì)算時(shí)間：降低求解質(zhì)量，模型計(jì)算時(shí)間大幅降低；模型求解時(shí)間并非取決于案例單元數(shù)量。MIPgap=E-10MIPgap=0.1%MIPgap=0.3%模型計(jì)算時(shí)間分類統(tǒng)計(jì)為獲得高質(zhì)量解(MIPgap<0.3%)

，所需計(jì)算時(shí)間統(tǒng)計(jì)：設(shè)施數(shù)量多且容量約束緊的案例計(jì)算復(fù)雜度較高。區(qū)域<100100-200200-500500-1000>1000zy143210gy23537gy2153011合計(jì)319758供需比例<100100-200200-500500-1000>1000<1.02001011.02-1.041352371.04-1.1091210>1.1093210合計(jì)319758設(shè)施容量約束對(duì)求解時(shí)間的影響服務(wù)總供給與總需求比值反映了設(shè)施容量約束的松緊程度；隨供需比值增大(容量約束變松)，計(jì)算時(shí)間呈下降趨勢(shì)。MIPgap=0.0% MIPgap=0.1%MIPgap=0.3%MIPgap=0.5%橫軸：服務(wù)供給與服務(wù)需求比值設(shè)施容量約束對(duì)計(jì)算時(shí)間的影響相同的設(shè)施區(qū)位，容量緊時(shí)模型計(jì)算復(fù)雜度高。藍(lán)色表示設(shè)施容量寬松的案例，棕色容量較近的案例。模型求解小結(jié)44/60案例能夠獲得最優(yōu)解；49/60案例能夠在500s內(nèi)獲得高質(zhì)量解(MIPGap<0.3%)；針對(duì)本文案例，模型計(jì)算復(fù)雜度主要取決于設(shè)施區(qū)位和設(shè)施容量設(shè)置，并非取決于案例規(guī)模(空間單元數(shù)量)。設(shè)施服務(wù)容量約束是影響模型計(jì)算時(shí)間的重要因素；是否能夠估計(jì)案例計(jì)算復(fù)雜度，進(jìn)行求解算法選擇？元啟發(fā)算法參數(shù)設(shè)置算法：Memetic-SPP，參數(shù)如下：種群規(guī)模：M=20；迭代次數(shù)：N=1500；交叉率：Pc=0.7(30%概率復(fù)制父體)；交叉方法：隨機(jī)選擇交叉方法Uniform,

Ordered1和Ordered2

，針對(duì)30%的基因進(jìn)行交叉操作；變異概率：Rm=0.03

(3%變異概率)

并周期性調(diào)整；是否SPP改進(jìn)：是。法計(jì)算結(jié)果i7600CPU@3.4GCPU,8GB

RAM;混合元啟發(fā)算計(jì)算環(huán)境：臺(tái)式電腦，Windows

10,

Inter

Core軟件配置：Pypy5.8

forPython2.x,CPLEX12.6每個(gè)案例計(jì)算10次；算法穩(wěn)定性優(yōu)良，具有魯棒性；計(jì)算時(shí)間適中；結(jié)果接近最優(yōu)解，(gap<0.53%,平均0.12%)e O2889.06 0.25052198.85 0.1997197376997609752474077339a 2380608.81 0.a 21268a 2013821.89 0.a 19317Instanczy_13azy_14azy_15azy_16azy_17agy_37agy_38agy_39agy_40agy_41agy2_18gy2_19gy2_20gy2_21gy2_22a 18753bej ObjDev DTeis

TimeG/asp1897..99

17580..1656..77

15920...32

15360..3.21752570..9.34741030..7.06729840..8.21721900..8.45712050..b

198726b201.09927290.b

190472b391.58589800.b871.98575230.%

0.00%Objvme/ DevTimGaep/sGap8086%28205.0.32054%9.73

206.1520.9%.254%

303.00.23%90.11%1084%25905.0.38724%4.60

205.0690.6%.033%

305.01.31%60.23%7096%24008.0.39261%2.07

208.0570.3%.122%

305.70.20%20.15%0093%22603.0.31385%1.79

208.0060.5%.141%

306.10.17%70.14%9092%22504.0.39979%9.48

209.0850.6%.025%

307.90.39%90.18%9213%80107.213.566%13.50303.1940.7%.128%

401.42.09%60.31%0308%79808.703.554%46.71304.3000.1%.271%

309.82.24%80.47%7111%78904.413.304%55.73304.2500.0%.027%

308.01.06%90.25%9078%78509.203.974%49.43304.1690.9%.054%

309.70.36%20.24%3083%79908.703.054%55.49304.1780.6%.024%

401.20.00%20.27%20.562%832102.701011.5%333.41

608.0530.6%.154%1106.032.8%00.16%40.522%814502.801711.4%115.68

607.0230.6%.136%

908.30.15%80.14%40.202%412105.709209.%95.345

609.0330.4%.015%1006.000.6%60.11%70.192%402705.708800.%07.982

702.0410.2%.061%

806.80.05%90.04%60.142%500407.707208.%97.909

703.0620.4%.040874.570.04%InstancInstanceInstanceObjDevTime/sGapzy_13bzy_13czy_13d

2050.880.00%278.300.00%zy_14bzy_14czy_14d

1930.980.11%298.820.17%zy_15bzy_15czy_15d

1875.170.04%307.890.03%zy_16bzy_16czy_16d

1841.500.03%323.150.04%zy_17bzy_17czy_17d

1842.810.03%368.740.07%gy_37bgy_37cgy_37d76848.630.12%359.230.14%gy_38bgy_38cgy_38d77847.770.05%425.330.07%gy_39bgy_39cgy_39d79567.130.23%408.400.53%gy_40bgy_40cgy_40d78879.720.21%436.460.39%gy_41bgy_41cgy_41d80725.880.18%394.130.24%gy2_18gy2_18cgy2_18d2018698.000.00%903.460.10%gy2_19gy2_19cgy2_19d1986774.640.02%690.780.02%gy2_20gy2_20cgy2_20d2028457.440.01%836.860.07%gy2_21gy2_21cgy2_21d2018378.920.01%869.960.09%gy2_22gy2_22cgy2_22d2031058.220.05%1110.090.12%SPP模型改進(jìn)效果對(duì)于案例區(qū)GY，SPP模型改進(jìn)顯著，能夠較大幅度地提升求解質(zhì)量；特別是4個(gè)案例，演化算法未發(fā)現(xiàn)可行解，

而SPP模型找到高質(zhì)量解；SPP模型求解時(shí)間：zy(0.60~3.92s,平均2.44s)、gy(0.28~3.84s,平均1.38s)、gy2(1.28~182.34s,平均43.05s)。instancespp-impinstancespp-impinstancespp-impinstancespp-impzy_13a0.02%zy_13b0.01%zy_13c0.03%zy_13d0.03%zy_14a0.02%zy_14b0.01%zy_14c0.03%zy_14d0.11%zy_15a0.04%zy_15b0.03%zy_15c0.02%zy_15d0.04%zy_16a0.04%zy_16b0.05%zy_16c0.11%zy_16d0.06%zy_17a0.01%zy_17b0.04%zy_17c0.06%zy_17d0.14%gy_37a0.69%gy_37b0.75%gy_37c1.49%gy_37d1.06%gy_38a0.92%gy_38b1.06%gy_38c2.06%gy_38d1.44%gy_39a0.98%gy_39b1.09%gy_39c1.57%gy_39d顯著改進(jìn)gy_40a1.15%gy_40b1.12%gy_40c1.70%gy_40d顯著改進(jìn)gy_41a1.24%gy_41b1.82%gy_41c顯著改進(jìn)gy_41d顯著改進(jìn)gy2_18a0.01%gy2_18b0.01%gy2_18c0.02%gy2_18d0.13%gy2_19a0.06%gy2_19b0.00%gy2_19c0.03%gy2_19d0.02%gy2_20a0.03%gy2_20b0.00%gy2_20c0.03%gy2_20d0.01%gy2_21a0.03%gy2_21b0.00%gy2_21c0.03%gy2_21d0.02%gy2_22a0.01%gy2_22b0.01%gy2_22c0.06%gy2_22d0.00%混合算法：初始解質(zhì)量不考慮分區(qū)連續(xù)、單元完整，模型求解，修復(fù)拆分單元、空間連續(xù)；獲得非可行初始解(GY)、高質(zhì)量初始解(GY2)instanceGapinstanceGapinstanceGapinstanceGapzy_13aInf.zy_13b0.54%zy_13c3.24%zy_13d1.15%zy_14a0.80%zy_14b1.16%zy_14c3.78%zy_14d0.69%zy_15a0.43%zy_15b1.30%zy_15c1.08%zy_15d1.05%zy_16a0.46%zy_16b1.10%zy_16c1.06%zy_16d1.02%zy_17a0.60%zy_17b1.14%zy_17c0.96%zy_17d1.88%gy_37aInf.gy_37bInf.gy_37cInf.gy_37dInf.gy_38aInf.gy_38bInf.gy_38cInf.gy_38dInf.gy_39aInf.gy_39bInf.gy_39cInf.gy_39dInf.gy_40aInf.gy_40bInf.gy_40cInf.gy_40dInf.gy_41aInf.gy_41bInf.gy_41cInf.gy_41dInf.gy2_18a0.18%gy2_18b0.04%gy2_18c0.21%gy2_18d0.32%gy2_19a0.26%gy2_19b0.02%gy2_19c0.17%gy2_19d0.05%gy2_20a0.11%gy2_20b0.01%gy2_20c0.16%gy2_20d0.08%gy2_21a0.05%gy2_21b0.02%gy2_21c0.07%gy2_21d0.11%gy2_22a0.03%gy2_22b0.01%gy2_22c0.14%gy2_22d0.19%精確算法Vs啟發(fā)式算法精確算法計(jì)算時(shí)間差異大，啟發(fā)式算法計(jì)算時(shí)間較為穩(wěn)定；區(qū)域ZY和GY2，精確算法的計(jì)算時(shí)間具有明顯優(yōu)勢(shì)；區(qū)域GY，啟發(fā)式算法的計(jì)算時(shí)間具有明顯優(yōu)勢(shì)，求解質(zhì)量略遜于精確算法；InstExactHeuristicInstExactHeuristicInstExactHeuristicGapTimeGapTimeGapTimeGapTimeGapTimeGapTimezy_13a0.14%378.950.24%359.73gy_37a0.11%1022.090.18%363.50gy2_18a0.10%96.950.14%1153.41zy_13b0.05%24.640.02%265.95gy_37b0.19%309.440.20%339.72gy2_18b0.23%6.920.02%685.65zy_13c0.22%32.470.11%330.39gy_37c0.08%1913.700.31%414.96gy2_18c0.14%4003.770.16%1163.80zy_13d0.01%33.050.00%278.30gy_37d0.03%156.410.14%359.23gy2_18d0.10%24.090.10%903.46zy_14a0.19%48.060.03%324.60gy_38a0.11%412.380.21%346.71gy2_19a0.24%544.690.16%1141.68zy_14b0.13%30.580.13%256.63gy_38b0.19%249.450.22%340.17gy2_19b0.03%15.550.01%672.63zy_14c0.15%214.520.23%350.16gy_38c0.00%774.280.47%398.48gy2_19c0.15%100.230.14%983.58zy_14d0.09%50.740.17%298.82gy_38d0.00%381.780.07%425.33gy2_19d0.14%20.380.02%690.78zy_15a0.18%46.160.12%362.07gy_39a0.11%606.810.07%345.73gy2_20a0.07%101.560.05%995.45zy_15b0.08%34.580.02%285.32gy