基于禁忌搜索算法求解定位-運(yùn)輸路線安排問(wèn)題

1、基于禁忌搜索算法求解定位運(yùn)輸路線安排問(wèn)題林暉鋼1，胡大偉1，徐麗蕊1，21 長(zhǎng)安大學(xué)汽車(chē)學(xué)院，西安（710064）2 陜西工業(yè)職業(yè)技術(shù)學(xué)院工商管理系，陜西咸陽(yáng)（712000）摘 要：定位運(yùn)輸路線安排問(wèn)題（location routing problems, LRP）是集成化物流系統(tǒng)分銷(xiāo)網(wǎng)絡(luò)設(shè)計(jì)和管理決策中的難題，也是任何一個(gè)大型物流配送企業(yè)必須要面對(duì)的問(wèn)題。由于LRP 的NPHARD屬性，其求解方法目前大多局限在將定位配給問(wèn)題（location allocation problems, LAP）的輸出作為車(chē)輛路線安排問(wèn)題（vehicle routing problems, VRP）的輸入而求解

2、。然而，在LAP 最優(yōu)的前提下求出的VRP 的最優(yōu)并不一定就是LRP 的最優(yōu)解，從而導(dǎo)致這樣的處理方式不可避免的會(huì)陷入局部最優(yōu)解的狀態(tài)。本文針對(duì)多站點(diǎn)定位運(yùn)輸路線安排問(wèn)題（multi-depot location routing problems, MDLRP）數(shù)學(xué)模型，用Lingo 軟件對(duì)小規(guī)模測(cè)試數(shù)據(jù)情形進(jìn)行了驗(yàn)證, 然后采用禁忌搜索法(TS）分別求解LAP 和對(duì)應(yīng)的每一個(gè)設(shè)施的VRP ，并將VRP 的結(jié)果作為L(zhǎng)AP 的輸入，再將LAP 解及其鄰域解作為VRP 輸入不斷反復(fù)循環(huán)求解MDLRP ，并在此基礎(chǔ)上對(duì)較大規(guī)模測(cè)試數(shù)據(jù)進(jìn)行了仿真運(yùn)算。結(jié)果表明采用禁忌搜索方法求解一定規(guī)模的MDLRP

3、快速有效。關(guān)鍵詞：定位運(yùn)輸路線安排問(wèn)題；定位配給問(wèn)題；車(chē)輛路線問(wèn)題；禁忌搜索1. 引言設(shè)施定位、車(chē)輛路線各自作為單獨(dú)的問(wèn)題，國(guó)內(nèi)外已有較多學(xué)者進(jìn)行了研究，其理論也已比較完善，這些研究為物流管理的優(yōu)化決策奠定了堅(jiān)實(shí)的基礎(chǔ)。國(guó)外一批學(xué)者對(duì)LRP 進(jìn)行了一系列的研究1。LRP 的概念認(rèn)為：在設(shè)施（制造廠、庫(kù)存點(diǎn)或分銷(xiāo)中心）相對(duì)于客戶(hù)的位置、貨物的配給、貨物運(yùn)輸?shù)能?chē)輛路線安排之間存在相互依賴(lài)的關(guān)系，根據(jù)這種關(guān)系來(lái)進(jìn)行綜合優(yōu)化與管理；相比單一的物流系統(tǒng)優(yōu)化問(wèn)題，LRP 更加貼近目前物流系統(tǒng)復(fù)雜的實(shí)際特征，對(duì)進(jìn)一步優(yōu)化整個(gè)物流系統(tǒng)，降低系統(tǒng)成本具有一定的理論價(jià)值和現(xiàn)實(shí)意義。而當(dāng)前大部分學(xué)者對(duì)LRP 的研究

4、都局限在將LAP 的輸出作為VRP 的輸入而進(jìn)行求解，這種方法得出的LRP 解往往并不是最優(yōu)的?；谶@樣一個(gè)現(xiàn)實(shí)情況，本文將LAP 和VRP 綜合統(tǒng)籌考慮，得出了相應(yīng)的MDLRP 優(yōu)化解，首先用C+編程軟件與Lingo 軟件對(duì)小規(guī)模數(shù)據(jù)集（8點(diǎn)數(shù)據(jù)集）進(jìn)行了計(jì)算及其對(duì)比驗(yàn)證本文算法計(jì)算結(jié)果的精確性，然后對(duì)較大規(guī)模數(shù)據(jù)（25點(diǎn)、50點(diǎn)、100點(diǎn)數(shù)據(jù)集）用本文算法求出了相應(yīng)的優(yōu)化解，證明了本文算法對(duì)求解MDLRP 問(wèn)題的有效性和準(zhǔn)確性。2. MDLRP 參數(shù)定義及其數(shù)學(xué)模型與驗(yàn)算本文研究的LRP 模型基于如下假設(shè)：客戶(hù)數(shù)量、位置及需求已知；候選設(shè)施位置及容量已知；各客戶(hù)需求均能得到滿(mǎn)足且每個(gè)客戶(hù)只

5、由一輛車(chē)服務(wù)；每輛車(chē)在完成全部運(yùn)輸任務(wù)后回到出發(fā)點(diǎn)；各線路的總需求小于或等于車(chē)輛的容量；車(chē)輛類(lèi)型給定。2.1 參數(shù)定義ijk x 在路線 k 上，如果點(diǎn) i 在 j 之前值為1，否則為0；i y 如果建立 i 設(shè)施則值為1，否則為0；ij z 如果客戶(hù) j 由設(shè)施 i 來(lái)服務(wù)則值為1，否則為0；R 配送設(shè)施點(diǎn)潛在位置的集合；J 所有客戶(hù)點(diǎn)的集合；V 所有車(chē)輛集合；N 代表客戶(hù)的數(shù)量；ij C i ，j 兩點(diǎn)之間的距離（作為i ，j 兩點(diǎn)間的運(yùn)輸費(fèi)用）；S R J =U 所有客戶(hù)點(diǎn)和潛在設(shè)施點(diǎn)的集合；r G 設(shè)施r 建設(shè)和運(yùn)行的固定成本；k F 使用車(chē)輛 k 的固定成本；r V 設(shè)施 r 的最大

6、容量；j q 客戶(hù) j 的需求量；k Q 車(chē)輛 k 的容量；2.2 多站點(diǎn)定位配給問(wèn)題的數(shù)學(xué)模型Min +R i Jj ijk V k k ijk S i S j V k ij r R r r x F x C y G. s t ：=V k S i ijk x, 1 J j ， （1）, k S i J j ijk j Q x q V k ， （2）R r y V zq r r J j rj j , 0， （3）=S i Sj pjk ipk x x , 0 V k ，, S p i j （4）R r J j rjk x, 1 V k ， （5）( 1rlk ljk rj l S xx z +

7、， R r ，J j ， V k （6）10或=ijk x ， , , , , j i V k S j i （7）10或=r y ， , R r （8）10或=ij z ，, R i J j （9）在上述這個(gè)模型中，目標(biāo)函數(shù)為總成本（包括設(shè)施建設(shè)和運(yùn)作成本、運(yùn)輸成本以及車(chē)輛投入及其使用成本）最小。約束（1）保證每一個(gè)客戶(hù)只由一個(gè)運(yùn)輸車(chē)輛服務(wù)；約束（2）為運(yùn)輸車(chē)輛容量約束條件；約束（3）為倉(cāng)庫(kù)的容量限制條件；約束（4）保證路線連續(xù)；約束（5）保證每一個(gè)運(yùn)輸工具的路線只能從一個(gè)設(shè)施駛出；約束（6）保證客戶(hù)只能由選中的設(shè)施提供服務(wù)；約束（7）（9）表示0、1變量約束。2.3 模型檢驗(yàn)由于目前學(xué)術(shù)界并

8、不存在任何定位路線問(wèn)題的測(cè)試數(shù)據(jù)。為了檢驗(yàn)此模型的正確性，本文以VRP 的Solomon 測(cè)試數(shù)據(jù)源R101數(shù)據(jù)系列為基礎(chǔ)隨機(jī)產(chǎn)生包含3個(gè)候選設(shè)施點(diǎn)和5個(gè)客戶(hù)需求點(diǎn)的數(shù)據(jù)組，對(duì)定位路線問(wèn)題數(shù)學(xué)模型進(jìn)行檢驗(yàn)。通過(guò)產(chǎn)生1100范圍內(nèi)的8個(gè)隨機(jī)數(shù)對(duì)應(yīng)于100個(gè)客戶(hù)中的各個(gè)客戶(hù)編號(hào)，將其中三個(gè)作為本算例中候選設(shè)施點(diǎn)的數(shù)據(jù)，其余5個(gè)作為客戶(hù)點(diǎn)的數(shù)據(jù)。這樣隨機(jī)產(chǎn)生的一組候選設(shè)施點(diǎn)和客戶(hù)，潛在設(shè)施點(diǎn)的坐標(biāo)、容量和建設(shè)成本如表1所示；客戶(hù)點(diǎn)的坐標(biāo)和需求量如表2所示。車(chē)輛容量取40，車(chē)輛固定成本取30。表1 潛在設(shè)施點(diǎn)的坐標(biāo)、容量和建設(shè)成本 X 坐標(biāo)10 Y 坐標(biāo)43 設(shè)施點(diǎn)的容量70 建設(shè)成本 200表2 客

9、戶(hù)點(diǎn)的坐標(biāo)和需求量 C2C3C4C5 X 坐標(biāo)3050104545 Y 坐標(biāo)6035206510 客戶(hù)需求量161919 用Lingo10.0對(duì)MDLRP 模型進(jìn)行編程，計(jì)算時(shí)間為156s ，結(jié)果表明兩個(gè)設(shè)施被選中，對(duì)應(yīng)的目標(biāo)函數(shù)值為666.406，從而證明了本文帶容量約束的MDLRP 數(shù)學(xué)模型的正確性。3. 禁忌搜索算法介紹TS （Tabu Search）算法是近年來(lái)受到普遍關(guān)注的一種高效率的現(xiàn)代啟發(fā)式優(yōu)化算法，該算法由F.Glover 2于1986年首先提出，進(jìn)而形成一套完整算法34。并隨著計(jì)算機(jī)技術(shù)的發(fā)展而成功的應(yīng)用于各個(gè)領(lǐng)域，解決了大量復(fù)雜的優(yōu)化問(wèn)題。近幾年，該算法被廣泛領(lǐng)域引入，如水

10、火電聯(lián)合經(jīng)濟(jì)調(diào)度3、電力系統(tǒng)無(wú)功優(yōu)化4 、輸電系統(tǒng)最優(yōu)規(guī)劃5 以及交通運(yùn)輸系統(tǒng)規(guī)劃5等領(lǐng)域，并取得了一定研究成果。部鄰域搜索陷入局部最優(yōu)的不足，禁忌搜索算法用一個(gè)禁忌表記錄下已經(jīng)到達(dá)過(guò)的局部最優(yōu)點(diǎn)，在下一次搜索中，利用禁忌表中的信息不再或有選擇地搜索這些點(diǎn)，以此來(lái)跳出局部最優(yōu)點(diǎn)。本文利用禁忌搜索算法求解組合優(yōu)化問(wèn)題時(shí)，首先產(chǎn)生一個(gè)初始解作為當(dāng)前解，然后在當(dāng)前解的鄰域中搜索若干鄰域解，取其中的最好解作為新的當(dāng)前解。為了避免對(duì)已搜索過(guò)的局部最優(yōu)解的重復(fù)，禁忌搜索算法使用禁忌表記錄已搜索的局部最優(yōu)解的歷史信息，這使得算法可在一定程度上避開(kāi)局部最優(yōu)點(diǎn)，從而開(kāi)辟新的搜索區(qū)域。本文設(shè)計(jì)的禁忌搜索算法流程圖

11、如圖1所示，禁忌搜索算法的特點(diǎn)是使用了禁忌技術(shù)。所謂禁忌就是禁止重復(fù)前面搜索，為了回避局 圖1 禁忌搜索算法流程圖禁忌搜索算法作為一種人工智能算法，涉及解的表示、解的評(píng)價(jià)、鄰域解的構(gòu)造及算法終止準(zhǔn)則，并且實(shí)現(xiàn)的技術(shù)問(wèn)題是算法的關(guān)鍵，不同的算法策略將會(huì)對(duì)解的好壞產(chǎn)生重要影響。禁忌搜索算法的主要策略有：禁忌對(duì)象和禁忌長(zhǎng)度的確定、候選集的產(chǎn)生方法、特赦規(guī)則以及終止規(guī)則。解的表示89不同編碼方式的運(yùn)行時(shí)間和適應(yīng)度函數(shù)值以及目標(biāo)函數(shù)值計(jì)算的復(fù)雜程度不同，并且編碼方式也影響著解空間的大小。一般來(lái)說(shuō)，在與車(chē)輛路線問(wèn)題有關(guān)問(wèn)題的求解中都采用自然數(shù)編碼的方式，而自然數(shù)編碼方式也存在著如下三種不同形式：第一種，客

12、戶(hù)和配送中心共同排列的編碼方式。第二種，車(chē)輛和客戶(hù)對(duì)應(yīng)排列的編碼方式。第三種，客戶(hù)直接排列的編碼方式。根據(jù)本文研究問(wèn)題的特征，本文采用第三種編碼方式，即客戶(hù)直接排列的編碼方式確定一組MDLRP 的初始可行解。禁忌對(duì)象的確定禁忌對(duì)象是指禁忌表中被禁的元素。由于解狀態(tài)的變化可分為解的簡(jiǎn)單變化、解向量分量的變化和目標(biāo)值變化三種情況，則在確定禁忌對(duì)象時(shí)也有對(duì)解的簡(jiǎn)單變化進(jìn)行禁忌、對(duì)解的分量變化進(jìn)行禁忌及對(duì)解的目標(biāo)值變化進(jìn)行禁忌三種情況。一般來(lái)說(shuō)，對(duì)解的簡(jiǎn)單變化進(jìn)行禁忌比對(duì)解的分量變化進(jìn)行禁忌和對(duì)解的目標(biāo)值變化進(jìn)行禁忌的受禁范圍要小，因此可能造成計(jì)算時(shí)間的增加，但其優(yōu)點(diǎn)是提供了較大的搜索范圍。解分量的變

13、化和目標(biāo)函數(shù)變化的禁忌范圍要大，這減少了計(jì)算的時(shí)間，可能引發(fā)的問(wèn)題時(shí)禁忌的范圍增大以至陷入局部最優(yōu)點(diǎn)。根據(jù)定位配給問(wèn)題和車(chē)輛路線問(wèn)題的特點(diǎn)，可采用對(duì)解的簡(jiǎn)單變化進(jìn)行禁忌的方法。其原理是：當(dāng)解從x 變化到y(tǒng) 時(shí)，Y 可能是局部最優(yōu)解，為了避開(kāi)局部最優(yōu)解，禁忌y 這一解再度出現(xiàn)，可采用如下禁忌規(guī)則：當(dāng)y 的鄰域中有比它更優(yōu)的解時(shí)，選擇更優(yōu)的解；當(dāng)Y 為N (y的局部最優(yōu)解時(shí)，不再選Y ，而選比y 稍差的解。禁忌長(zhǎng)度的確定禁忌長(zhǎng)度是指被禁對(duì)象不允許被選取的迭代步數(shù)，一般是給被禁忌對(duì)象x 一個(gè)數(shù)L(稱(chēng)為禁忌長(zhǎng)度 ，要求禁忌對(duì)象x 在L 步迭代內(nèi)被禁，在禁忌表中采用Tabu(x=L記憶，每迭代一步，該項(xiàng)

14、指標(biāo)做運(yùn)算Tabu(x=L-1，直到Tabu(x=0時(shí)解禁。禁忌長(zhǎng)度在同一問(wèn)題求解過(guò)程中是固定的，但是隨問(wèn)題規(guī)模的不同取不同的值，一般來(lái)說(shuō)，問(wèn)題規(guī)模越大，禁忌長(zhǎng)度越長(zhǎng)。禁忌長(zhǎng)度短會(huì)造成循環(huán)，也可能在一個(gè)局部最優(yōu)解附近循環(huán)。禁忌長(zhǎng)度長(zhǎng)會(huì)造成算法的記憶存儲(chǔ)量增加，使得算法計(jì)算時(shí)間增加，還可能造成算法無(wú)法繼續(xù)計(jì)算下去。本文L 取為常數(shù)，L =為鄰域中鄰居的總個(gè)數(shù) ，這種規(guī)則容易在算法中實(shí)現(xiàn)。 候選集的產(chǎn)生方法候選集合由鄰域中的鄰居組成。常規(guī)的方法是從鄰域中選擇若干個(gè)目標(biāo)值或評(píng)價(jià)值最佳的鄰居入選。有時(shí)這種計(jì)算量較大，而且容易導(dǎo)致局部收斂的情況，所以本文采用不在鄰域的所有鄰居中選擇，而是在鄰域中的一部分

15、鄰居中隨機(jī)選擇若干個(gè)目標(biāo)值或評(píng)價(jià)值最佳的狀態(tài)實(shí)現(xiàn)部分鄰居的選取。由于考慮到計(jì)算時(shí)間的復(fù)雜度問(wèn)題，本文設(shè)計(jì)每次對(duì)當(dāng)前解隨機(jī)進(jìn)行5次鄰域解產(chǎn)生操作，將其作為當(dāng)前解的候選集。在定位階段既要確定配送中心數(shù)目，又要選擇具體的配送中心，因此設(shè)計(jì)兩種鄰域搜索方法，分別是 “客戶(hù)交換”和“客戶(hù)插入”操作。根據(jù)本文特點(diǎn)，在路線優(yōu)化階段，設(shè)計(jì)隨機(jī)從插入法、2-opt 、路線內(nèi)2swap 和路線間2-swap 四種鄰域搜索方法中選擇其中一種來(lái)產(chǎn)生鄰域解，這樣增強(qiáng)了禁忌搜索算法的搜索性能，擴(kuò)大了搜索范圍，以便能在車(chē)輛行駛費(fèi)用方面得到更好的改進(jìn)。插入法插入法是考慮一條路線中任意一個(gè)點(diǎn)插入到其他路線中的方法，即從一條路線

16、中隨機(jī)選擇一個(gè)點(diǎn)，插入到另一條路線中隨機(jī)選擇的兩個(gè)點(diǎn)之間，如圖2，從一條路線中隨機(jī)選擇點(diǎn)4，另一條路線中隨機(jī)選擇點(diǎn)7，通過(guò)插入法，則路線由012340和056780變?yōu)?1230和0567480。 代表選中DC ，代表客戶(hù)， 和代表路線圖2 插入法示意圖 2opt將當(dāng)前路線中的k 條邊用另外k 條邊代替，這種變換稱(chēng)為k opt 10, 最為常見(jiàn)的是2opt ，主要思想是隨機(jī)選擇兩個(gè)點(diǎn)i 和j ，將邊(i,i+1、(j,j+1用(i,j、(i+1,j+1代替，如圖3所示，隨機(jī)選擇2和5，進(jìn)行2opt 交換，則路線由01234560變?yōu)?1254360。 代表選中DC ，代表客戶(hù)，和 代表路線圖3

17、 2opt 交換法示意圖11 路線內(nèi)2Swap路線內(nèi)2swap 主要思想是交換一條路線上兩個(gè)點(diǎn)的位置，如圖4所示，隨機(jī)選擇2和5，進(jìn)行路線內(nèi)2Swap ，則路線由01234560變?yōu)?1534260。路線間2Swap路線間2swap 主要思想是交換不同路線上兩個(gè)點(diǎn)的位置，如圖5所示，隨機(jī)選擇兩條路線上的兩個(gè)點(diǎn)2和5，進(jìn)行路線間2Swap ，則路線由01230和04560變?yōu)?1530和04260。這種思想在車(chē)輛路線問(wèn)題的客戶(hù)分配中可以起到優(yōu)1化分組的作用。 代表選中DC ，代表客戶(hù)，和代表路線圖4 2Swap 路線內(nèi)交換法示意圖 圖5 2swap 路線間交換示意圖特赦規(guī)則在禁忌搜索算法的迭代過(guò)

18、程中，會(huì)出現(xiàn)候選集中的全部對(duì)象都被禁忌，或某一對(duì)象被禁，但若解禁后其目標(biāo)值將下降情況。在這樣的情況下，為了達(dá)到全局的最優(yōu)，讓一些禁忌對(duì)象重新可選，這種方法稱(chēng)為特赦，相應(yīng)的規(guī)則稱(chēng)為特赦規(guī)則，也即解禁原則。本文采用基于評(píng)價(jià)值的特赦規(guī)則。即在整個(gè)計(jì)算過(guò)程中，記憶已出現(xiàn)的最好解bestx ，當(dāng)候選集中被禁忌解的鄰域中，出現(xiàn)一個(gè)解nowx 優(yōu)于bestx，則解禁nowx使其自由，并更新為當(dāng)前解和最好解。 評(píng)價(jià)函數(shù)評(píng)價(jià)函數(shù)賦予候選集合中每一個(gè)元素一個(gè)實(shí)數(shù)值，通過(guò)評(píng)價(jià)函數(shù)值來(lái)選取下一步計(jì)算的替代點(diǎn)。領(lǐng)域搜索中需要對(duì)在得到的幾個(gè)解中選擇質(zhì)量最優(yōu)的解作為新的當(dāng)前解，為了提高算法效率，在定位階段評(píng)價(jià)解的優(yōu)劣時(shí)，我

19、們通過(guò)目標(biāo)函數(shù)預(yù)測(cè)值來(lái)比較這幾個(gè)解的質(zhì)量。預(yù)測(cè)方法是：根據(jù)求解的設(shè)施定位方案，在滿(mǎn)足設(shè)施容量約束的前提下，將客戶(hù)分配至距離最近的設(shè)施點(diǎn)，假設(shè)設(shè)施與客戶(hù)間的運(yùn)輸路線為直線距離，并且不考慮車(chē)輛路線，而采用各客戶(hù)與設(shè)施點(diǎn)距離總和作為目標(biāo)函數(shù)預(yù)測(cè)值。而在路線優(yōu)化階段，則用配送路線方案的目標(biāo)函數(shù)值作為評(píng)價(jià)函數(shù)，對(duì)候選解進(jìn)行評(píng)價(jià)和選取最優(yōu)值。其目標(biāo)函數(shù)值越優(yōu)，則解的質(zhì)量越高。終止準(zhǔn)則67禁忌搜索是一種啟發(fā)式算法，希望在可接受的時(shí)間里能得到一個(gè)滿(mǎn)意的解。終止規(guī)則就是確定什么時(shí)候終止算法，通常使用的有以下幾種方法：確定步數(shù)終止；頻率控制原則； 目標(biāo)值變化控制原則； 目標(biāo)值偏離程度原則。為便于算法實(shí)現(xiàn)，本文綜合

20、方法和方法，采用事先確定最大迭代代數(shù)和最好解保持不變的最大連續(xù)迭代步數(shù)作為終止規(guī)則。4. 實(shí)例計(jì)算及結(jié)果分析本文中所有計(jì)算實(shí)例中的單位距離運(yùn)輸費(fèi)用均取為1；對(duì)于8點(diǎn)數(shù)據(jù)由于有可比對(duì)象（LINGO 計(jì)算結(jié)果），為了對(duì)比方便程序當(dāng)中車(chē)輛費(fèi)用取為30；而對(duì)于25點(diǎn)、50點(diǎn)和100點(diǎn)的數(shù)據(jù)由于沒(méi)有可比對(duì)象，所以在程序中車(chē)輛容量暫時(shí)設(shè)定為：50，90，150；車(chē)輛費(fèi)用暫時(shí)分別設(shè)定為30，0，0；當(dāng)然也可以根據(jù)需要自行設(shè)定。根據(jù)模型檢驗(yàn)中的8點(diǎn)數(shù)據(jù)，對(duì)本文禁忌搜索算法運(yùn)用C+語(yǔ)言編程計(jì)算，對(duì)應(yīng)的參數(shù)設(shè)置如下：禁忌長(zhǎng)度取為3，最大迭代次數(shù)max_cons_iter取為800，候選解數(shù)量取為5，LRP 迭代次

21、數(shù)取為20時(shí)，得出目標(biāo)函數(shù)的結(jié)果如表3所示。表3 計(jì)算結(jié)果選中的設(shè)施對(duì)應(yīng)的車(chē)輛路線 目標(biāo)函數(shù)值CPU 運(yùn)行時(shí)間120-4-1-0 ，0-2-5-00-3-0666.406 0.0922秒根據(jù)上表可以看出，由本文算法模擬計(jì)算，得出的結(jié)果與我們應(yīng)用Lingo10.0對(duì)MDLRP 模型8點(diǎn)數(shù)據(jù)進(jìn)行編程計(jì)算得出的目標(biāo)函數(shù)值完全相同，并且計(jì)算20次得出該最優(yōu)解的頻率為85%以上，計(jì)算機(jī)運(yùn)行時(shí)間也很快。從而驗(yàn)證了本文程序的有效性。在solomon 數(shù)據(jù)集中R101數(shù)據(jù)集合（見(jiàn)表4）中隨機(jī)選取其中5個(gè)客戶(hù)點(diǎn)作為設(shè)施節(jié)點(diǎn)，其余20個(gè)作為客戶(hù)點(diǎn)，用本文算法進(jìn)行編程計(jì)算在相應(yīng)的參數(shù)設(shè)置為：禁忌長(zhǎng)度取為5，最大迭代次數(shù)max_cons_iter取為8000，候選解數(shù)量取為25，LRP 迭代次數(shù)取為50時(shí)，計(jì)算20次得出的最好結(jié)果如表5所示，最好結(jié)果出現(xiàn)的頻率為75%以上。表4 設(shè)施點(diǎn)坐標(biāo)、容量、建設(shè)費(fèi)用和客戶(hù)點(diǎn)坐標(biāo)、需求量潛在設(shè)施容量 建設(shè)費(fèi)用客戶(hù)需求量客戶(hù)X Y 需求量客戶(hù) 需求量65121665102017201919表5 計(jì)算結(jié)果選中的設(shè)施對(duì)應(yīng)的車(chē)輛路線 目標(biāo)函數(shù)值CPU 運(yùn)行時(shí)間1 2 50-5-1-7-13-0 ，0-12-10-00-6-15-9-0 ，0-1-3-8-16-00-17-18-0 ，0-2-11-4