《基于遺傳算法的物流企業(yè)配送路徑優(yōu)化實(shí)證研究案例》11000字

基于遺傳算法的物流企業(yè)配送路徑優(yōu)化實(shí)證研究案例目錄TOC\o"1-2"\h\u112271遺傳算法的定義 [58]。4.2遺傳算法設(shè)計(jì)與求解流程4.2.1遺傳算法求解設(shè)計(jì)通過(guò)上文對(duì)Y物流公司的配送路徑的介紹，將Y物流公司的車輛路徑問(wèn)題描述為單目標(biāo)、帶軟時(shí)間窗、一個(gè)配送中心、一種車型、靜態(tài)和閉合型，根據(jù)此內(nèi)容構(gòu)建本文的路徑優(yōu)化模型。用精確算法對(duì)構(gòu)建的模型進(jìn)行求解，經(jīng)典啟發(fā)式算法適合解決比較簡(jiǎn)單的路徑優(yōu)化模型，當(dāng)路徑問(wèn)題復(fù)雜時(shí)，就會(huì)遇到很多問(wèn)題，很難得到模型的最優(yōu)解。現(xiàn)代啟發(fā)式算法是目前使用最多的算法，現(xiàn)代啟發(fā)式算法種的遺傳算法運(yùn)算速度快，具有全局搜索最優(yōu)解的能力，不易陷入局部最優(yōu)，選擇遺傳算法作為求解本文構(gòu)建模型的最優(yōu)解。用遺傳算法在Matlab上求解配送路徑優(yōu)化模型時(shí)，需要提前對(duì)遺傳算法進(jìn)行設(shè)計(jì)，使其更好的融入需要解決的問(wèn)題，從而求得該問(wèn)題的近似最優(yōu)解。首先確定運(yùn)行參數(shù)種群規(guī)模、交叉概率、變異概率、終止條件，再經(jīng)過(guò)編碼、確定初始種群、選擇、交叉、變異、適應(yīng)度評(píng)價(jià)這一系列步驟后求得問(wèn)題最優(yōu)解。（1）編碼操作編碼是將實(shí)際路徑優(yōu)化問(wèn)題轉(zhuǎn)化為計(jì)算機(jī)能夠識(shí)別的語(yǔ)言，因此進(jìn)行求解時(shí)，首先對(duì)實(shí)際問(wèn)題進(jìn)行編碼。路徑優(yōu)化問(wèn)題的編碼是配送中心和客戶點(diǎn)不同順序的組合，用計(jì)算機(jī)能夠識(shí)別的語(yǔ)言表示出來(lái)。因本研究求解Y物流公司配送問(wèn)題的客戶點(diǎn)有14個(gè)，為了提高求解的效率和有效性，選擇自然數(shù)編碼方式，0代表配送中心，1-14為14個(gè)客戶點(diǎn)，0與0中間按某個(gè)順序排列的一些數(shù)字，表示配送車輛從配送中心開(kāi)始出發(fā)，依次經(jīng)過(guò)各個(gè)數(shù)字代表的客戶點(diǎn)進(jìn)行服務(wù)，完成任務(wù)后配送車輛返回配送中心。如0，14，13，12，0，11，10，9，8，0，7，6，5，4，0，3，2，1，0。表示第一個(gè)配送車輛在配送中心裝滿貨物后，按照順序?yàn)?4，13，12這3個(gè)客戶點(diǎn)進(jìn)行服務(wù)，在為12這個(gè)客戶點(diǎn)完成服務(wù)后返回配送中心；第二輛配送車輛依次按照11，10，9，8四個(gè)客戶點(diǎn)的順序進(jìn)行服務(wù)，從客戶點(diǎn)8返回配送中心；第三輛車的配送路徑為7，6，5，4；第四輛車的配送路徑為3，2，1；其中每一個(gè)不同路徑上的客戶點(diǎn)順序是一定的，不能變換各自的順序，如果變換順序目標(biāo)函數(shù)的值會(huì)受到影響。（2）生成初始種群生成初始種群是為了后面種群迭代的基礎(chǔ)，選擇初始種群的規(guī)模一般在30-200個(gè)中間。如果種群規(guī)模太小，在后續(xù)迭代中容易陷入局部最優(yōu)；如果種群規(guī)模太大，會(huì)增加后續(xù)適應(yīng)度值計(jì)算的難度，降低整體的計(jì)算速度，搜索最優(yōu)解的范圍會(huì)增加，求得最優(yōu)解的效率會(huì)降低，能夠防止搜索最優(yōu)解時(shí)過(guò)早收斂。因此，要選擇恰當(dāng)?shù)某跏挤N群。本研究一共有14個(gè)客戶，將種群規(guī)模設(shè)定為50。在初始種群時(shí)，首先產(chǎn)生第一的數(shù)為0的N+k-1個(gè)數(shù)的數(shù)列，染色體的數(shù)列是由0-N+k-1個(gè)數(shù)不同排列組合，其次將數(shù)列中大于N的數(shù)設(shè)置為0，生成多個(gè)子路徑，使用0將各個(gè)子路徑分開(kāi)，其中如果產(chǎn)生了連續(xù)多個(gè)0，0和0之間不需要車輛進(jìn)行配送，0表示配送中心，不會(huì)影響劃分各個(gè)子路徑的過(guò)程。不斷地的進(jìn)行上述過(guò)程，直到生成所需要種群的規(guī)模。（3）適應(yīng)度函數(shù)遺傳算法對(duì)路徑優(yōu)化模型進(jìn)行求解時(shí)，適應(yīng)度函數(shù)用來(lái)判斷染色體的優(yōu)劣，優(yōu)秀的染色體遺傳給下一代，產(chǎn)生的子代染色體比父代染色更優(yōu)秀，不斷地迭代，直到達(dá)到種群最優(yōu)。而適應(yīng)度函數(shù)能夠計(jì)算適應(yīng)度的大小，適應(yīng)度大的染色體越優(yōu)秀。本文的目標(biāo)函數(shù)是車輛的配送成本和違反時(shí)間窗的懲罰成本兩者之和，最小目標(biāo)函數(shù)值的配送路徑是構(gòu)建模型進(jìn)行路徑優(yōu)化的最佳路線?？梢詫⒛繕?biāo)函數(shù)作為Y物流公司的適應(yīng)度函數(shù)，則Y物流公司的目標(biāo)函數(shù)越小，適應(yīng)度越大；目標(biāo)函數(shù)越大，適應(yīng)度越小。（4）選擇算子遺傳算法的選擇是根據(jù)適應(yīng)度的大小來(lái)進(jìn)實(shí)現(xiàn)，通過(guò)適應(yīng)度函數(shù)計(jì)算適應(yīng)度，選擇適應(yīng)度值大的個(gè)體代替適應(yīng)度小的個(gè)體，進(jìn)行種群的迭代。選擇能夠?qū)?yōu)秀的基因保留遺傳給下一代，生成適應(yīng)度值更大的染色體，隨著不斷地迭代，越來(lái)越接近最優(yōu)解，本文的適應(yīng)度函數(shù)為目標(biāo)函數(shù)，目標(biāo)函數(shù)值越小越好，選擇的方式是將適應(yīng)度值大的個(gè)體替換適應(yīng)度小的個(gè)體，重復(fù)此操作，直至生成同等規(guī)模的新種群。（5）交叉算子遺傳算法交叉的過(guò)程是按照規(guī)定的交叉概率，選擇交叉點(diǎn)，交換兩個(gè)交叉點(diǎn)的基因片段，產(chǎn)生不同于交叉之前的染色體，從而生成新的種群。選擇雙點(diǎn)交叉作為本文的交叉算子，對(duì)Y物流公司路徑優(yōu)化模型的求解，設(shè)置的交叉概率為，將父代種群，根據(jù)此交叉概率任意且不重復(fù)的選擇染色體互換交差點(diǎn)基因片段的位置，完成遺傳算法的交叉操作。雙點(diǎn)交叉的操作過(guò)程如下，假如父代兩條染色體的基因片段為A=2-6-3-7-1-4-8-9-5，B=7-5-8-1-3-6-2-9-2。隨機(jī)概率產(chǎn)生的交叉點(diǎn)分別為6，8；5，2。則交叉區(qū)域就變成A=2-6|3-7-1-4|8-9-5，B=7-5|8-1-3-6|2-9-2。A1=|3-7-1-4|，B1=|8-1-3-6|,則在A中刪除與B1中重復(fù)的基因，再把B1基因全部添加到A相應(yīng)的基因片段中。例如A=2-6-3-7-1-4-8-9-5，B1=|8-1-3-6|，刪除后A剩下的為2-7-4-9-5，把B1基因全部添加到A相應(yīng)的基因片段中,那么A的新基因就變成了2-7-|8-1-3-6|-4-9-5。接下來(lái)對(duì)于B染色體也執(zhí)行同樣的操作，從而形成新的子代種群進(jìn)入下次迭代。（6）變異算子遺傳算法的變異是將父代染色體的基因片段用其他的基因片段進(jìn)行替換，生成新的不同序列的子代染色體。染色體根據(jù)變異概率進(jìn)行變異，Y物流公司路徑優(yōu)化模型的求解，選取的變異概率為變異的方式有互換變異算子、逆轉(zhuǎn)變異算子、均勻變異算子等，本文遺傳算法研究選取了逆轉(zhuǎn)變異。假設(shè)：父代A為439165872，如果變異概率產(chǎn)生的變異點(diǎn)為(4，6)，表示該染色體基因的第四位和第六位發(fā)生變異，將染色體基因的第四位到第六位按照逆序進(jìn)行排列，生成新的子代染色體為439561872。進(jìn)行變異的操作之后，分別計(jì)算父代和子代染色體的適應(yīng)度，如果子代更優(yōu)秀則將子代替換父代，如果父代更優(yōu)秀，變異失敗繼續(xù)選擇父代進(jìn)行迭代。（7）終止條件在用遺傳算法進(jìn)行配送車路路徑優(yōu)化問(wèn)題求解時(shí)，終止遺傳算法的方式有通過(guò)迭代得到最優(yōu)解，在之后的次之后未改進(jìn)，可以終止運(yùn)行遺傳算法；或者規(guī)定終止的迭代次數(shù)，遺傳算法運(yùn)算到達(dá)規(guī)定的迭代次數(shù)時(shí)終止迭代，本文選擇在得到最優(yōu)解之后進(jìn)行，在進(jìn)行迭代300次，停止運(yùn)算，并輸出此次遺傳算法運(yùn)行的最優(yōu)解。4.2.2遺傳算法的求解流程遺傳算法求解的流程圖如4-1所示，遺傳算法主要利用選擇算子、交叉算子、變異算子搜索最優(yōu)解，在求解過(guò)程中，達(dá)到種群的迭代次數(shù)或者其他終止要求時(shí)，終止求解過(guò)程，此時(shí)種群停止進(jìn)化，輸出最優(yōu)解。圖4-1遺傳算法求解流程圖Figure4-1Flowchartofgeneticalgorithm遺傳算法詳細(xì)的求解過(guò)程主要包括以下六個(gè)步驟。第一步：首先將車輛路徑問(wèn)題轉(zhuǎn)化成計(jì)算機(jī)能夠識(shí)別的問(wèn)題，其次選擇合適的編碼方式，確定實(shí)際問(wèn)題的參數(shù)集，對(duì)參數(shù)集進(jìn)行編碼，構(gòu)造適合該問(wèn)題的染色體。當(dāng)對(duì)現(xiàn)實(shí)問(wèn)題對(duì)染色體進(jìn)行編碼時(shí)，應(yīng)該選擇適合構(gòu)建模型約束條件的編碼方式，能夠提高計(jì)算的速度和效率。第二步：首先篩選被編碼的染色體，隨機(jī)產(chǎn)生初始種群，形成一組初始的染色體，初代染色體的數(shù)量應(yīng)該合理設(shè)置，其次設(shè)置初始迭代次數(shù)，確定該問(wèn)題適應(yīng)度函數(shù)；第三步：根據(jù)第二步中確定的適應(yīng)度函數(shù)，計(jì)算每個(gè)染色體的適應(yīng)度值。第四步：經(jīng)過(guò)第三步計(jì)算每一個(gè)染色體的適應(yīng)度值，將染色體進(jìn)行選擇、交叉、變異之后，再次進(jìn)行解碼計(jì)算每個(gè)新產(chǎn)生染色體的適應(yīng)度值。新的染色體在進(jìn)行選擇、交叉、變異一系列操作后，產(chǎn)生新的子代染色體，種群可以不斷地進(jìn)行迭代；第五步：不斷地繼續(xù)地進(jìn)行第四步直到滿足迭代次數(shù)到達(dá)終止次數(shù)，停止迭代。當(dāng)?shù)谒牟降拇螖?shù)小于終止條件地迭代次數(shù)時(shí)，繼續(xù)進(jìn)行迭代，否則種群停止迭代，繼續(xù)第六步第六步：此時(shí)迭代達(dá)到了終止條件，種群停止迭代，計(jì)算并輸出迭代的最優(yōu)解。4.3本章小結(jié)本章首先對(duì)Y物流公司現(xiàn)存情況進(jìn)行假定的基礎(chǔ)上建立了一個(gè)目標(biāo)函數(shù)即總配送成本最小化路徑優(yōu)化數(shù)學(xué)模型，配送總成本包括車輛的配送成本和違反時(shí)間窗的懲罰成本，然后在對(duì)遺傳算法的基礎(chǔ)上，從開(kāi)始的編碼到算法的終止條件，對(duì)遺傳算法的求解過(guò)程進(jìn)行詳細(xì)設(shè)計(jì)，最后運(yùn)用遺傳算法通過(guò)matlab對(duì)此模型進(jìn)行求解，此章為第五章的求解分析提供理論與技術(shù)支持。5模型求解及優(yōu)化結(jié)果分析5.1遺傳算法求解對(duì)模型最優(yōu)解的影響分析根據(jù)配送優(yōu)化方案，進(jìn)行優(yōu)化配送路徑，并利用Matlab編程求解，將構(gòu)建模型需要的數(shù)據(jù)帶入，運(yùn)行450次后終止運(yùn)行，程序運(yùn)行10次的目標(biāo)函數(shù)值和收斂的迭代次數(shù)如圖5-1所示，分析遺傳算法的選擇算子、交叉算子和遺傳算子對(duì)Y物流公司目標(biāo)函數(shù)值的影響。圖5-1運(yùn)行次數(shù)圖Figure5-1operationtimes（1）選擇算子根據(jù)圖5-1所示，利用matlab運(yùn)行程序10次的結(jié)果顯示，種群迭代在100代附近開(kāi)始收斂得到模型的最優(yōu)解，每次運(yùn)行的結(jié)果相差比較小，并且算法的收斂速度快。選擇算子在進(jìn)行選擇時(shí)，用種群中適應(yīng)度高的個(gè)體代替適應(yīng)度低的個(gè)體，這樣適應(yīng)度低的個(gè)體能夠被選擇，確保了種群中優(yōu)秀的個(gè)體能夠進(jìn)行復(fù)制將優(yōu)秀基因遺傳給下一代，這種選擇的方法使得適應(yīng)度高的個(gè)體沒(méi)有被淘汰的可能，如均勻分布選擇法和錦標(biāo)賽選擇法均是利用概率進(jìn)行選擇，使得適應(yīng)度高的個(gè)體也有被淘汰的可能。（2）交叉算子在用遺傳算法進(jìn)行求解時(shí)，選擇和交叉算子能夠保證遺傳算法的全局搜索能力，在種群中選擇優(yōu)秀的個(gè)體遺傳給下一代之后，交叉算子進(jìn)行染色體的交叉產(chǎn)生新的個(gè)體，交叉算子操作對(duì)象作用的范圍是整體的染色體，因此遺傳算法具有的全局搜索能力，并且交叉算子是遺傳算法產(chǎn)生新個(gè)體的重要算子。交叉算法的作用比選擇算法的作用更大，利用交叉算子全局搜索最優(yōu)解時(shí)可能造成染色體具有相似性，求解過(guò)程陷入局部最優(yōu)，本文使用兩點(diǎn)交叉算子進(jìn)行計(jì)算，如圖5-1能夠得到較好的效果。（3）變異算子。 遺傳算法的變異算子保證了其局部搜索最優(yōu)解的能力，當(dāng)選擇算子和交叉算子在解空間進(jìn)行搜索最優(yōu)解，能夠在全局進(jìn)行搜索的同時(shí)在最優(yōu)解的空間收斂，此時(shí)的解已經(jīng)接近最優(yōu)解，利用變異算子的局部搜索能力，能夠更快的搜索到最優(yōu)解，保證了遺傳算法在搜索最優(yōu)解時(shí)收斂的質(zhì)量和效率，有效防止選擇和交叉操作過(guò)程中一部分信息的遺失和早熟收斂。其次變異的概率過(guò)大，會(huì)破環(huán)種群的優(yōu)良度，變異概率過(guò)小，在搜索最優(yōu)解的時(shí)候，不能向最優(yōu)解所在空間的其他地方搜索，容易造成過(guò)早收斂。有本文選擇逆轉(zhuǎn)變異作為變異算子和采用變異的概率為0.1，遺傳算法求得優(yōu)解的運(yùn)算速時(shí)間在3-4秒，快速得到了建立模型的最優(yōu)解。根據(jù)圖5-1所示，利用逆轉(zhuǎn)變異進(jìn)行遺傳算法的變異算子，沒(méi)有出現(xiàn)過(guò)早收斂的現(xiàn)象。5.2優(yōu)化結(jié)果對(duì)比分析利用遺傳算法并用Matlab編程求解可以得到14個(gè)的最優(yōu)的配送路線，根據(jù)上一節(jié)的求解結(jié)果，選擇其中費(fèi)用最少的一次求解結(jié)果與未優(yōu)化的結(jié)果進(jìn)行對(duì)比分析，遺傳算法迭代曲線及優(yōu)化結(jié)果如圖所示：圖5-2遺傳算法求解的配送路徑示意圖Figure5-2Distributionroutediagramsolvedbygeneticalgorithm圖5-3遺傳算法求解的迭代圖Figure5-3Iterativegraphsolvedbygeneticalgorithm根據(jù)上述遺傳算法求解的得迭代圖可以得到，當(dāng)種群迭代到100次以后基本保持不變，得到模型的最優(yōu)解。遺傳算法求解的最優(yōu)配送路徑如圖5-2所示，根據(jù)車輛配送路線可以得到每輛車在配送過(guò)程中的實(shí)際貨物載重量以及行駛時(shí)間、配送總成本。將配送方案進(jìn)行優(yōu)化后的結(jié)果與Y物流公司之前進(jìn)行對(duì)比，分別從車輛配送的總成本、車輛的裝載率、配送總行使距離和時(shí)間進(jìn)行對(duì)比分析，優(yōu)化前和優(yōu)化后的配送情況如表5-1和表5-2所示，求解結(jié)果與優(yōu)化前情況對(duì)比如表5-3所示，能夠看出Y物流公司的配送成本顯著減少，可以說(shuō)明構(gòu)建優(yōu)化模型和遺傳算法求解的有效性。表5-1優(yōu)化前的配送信息Table5-1Distributioninformationbeforeoptimization路徑序號(hào)配送順序行駛距離/km行駛時(shí)間/min實(shí)際容量/㎡額定容量/㎡實(shí)載率/%10→1→0132.60174.124.3150.2920→2→0153.60199.324.7150.3130→3→0232.00293.407.53150.5040→4→0265.00333.005.11150.3450→5→0180.00231.008.97150.6060→6→0180.00231.008.31150.5570→7→0234.00295.805.22150.3580→8→0331.60412.927.24150.4890→9→0409.60506.524.91150.33100→10→0476.20586.448.94150.60110→11→0380.80471.968.86150.59120→12→0441.80545.164.99150.33130→13→0316.40394.688.57150.57140→14→0336.20418.444.92150.33表5-2優(yōu)化后的配送信息Table5-2Optimizeddistributioninformation路徑序號(hào)配送順序行駛距離/km行駛時(shí)間/min實(shí)際容量/㎡額定容量/㎡實(shí)載率/%懲罰成本/元10→1→6→0192.70276.2412.61150.846.7620→12→8→0461.70599.0412.23150.81375.2430→14→13→0336.20448.4413.49150.89100.840→11→7→0402.40527.8814.08150.93517.4450→4→5→0294.00397.8014.08150.93329.460→9→10→0484.20626.0413.85150.924.6870→3→2→0223.90313.6812.23150.81139.56表5-3遺傳算法求解結(jié)果與優(yōu)化前情況對(duì)比Table5-3Theresultofgeneticalgorithmiscomparedwiththatbeforeoptimization配送車輛/輛總行使距離/km總成本/元總行使時(shí)間/min平均裝載率/%優(yōu)化前144069.8020349.005093.760