終稿4軟時間窗限制的車輛調(diào)度物資的配送問題03

1、物資的配送問題摘要本文主要討論其中的物流配送的路徑優(yōu)化問題，即通過制定合理的配送路徑方案，快速而經(jīng)濟地將貨物送達用戶手中。配送路徑選擇是否合理，對加快配送速度，提高服務(wù)質(zhì)量，降低配送成本及增加經(jīng)濟效益有極大的影響。作為一個優(yōu)化類問題，必然包括目標函數(shù)、變量和約束條件三要素，我們首先以此為基礎(chǔ)，找到本題的約束條件，得出該問題的性質(zhì)，即有軟時間窗約束非滿載多車輛的調(diào)度問題。經(jīng)過查閱相關(guān)文獻后，我們最終決定采用普遍的遺傳算法來解決該問題。所謂遺傳算法，指的是模擬達爾文生物進化論的自然選擇和遺傳學(xué)機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法，該方法主要采用了改進的交叉算子，

2、可以最大限度的將已經(jīng)具有雙親優(yōu)良特性的子串復(fù)制到下一代，有效的提高了染色體的質(zhì)量，增強種群的適應(yīng)度，另外在種群中各個個體均相同的情況下，也不會影響遺傳迭代的進行，擺脫了對種群多樣性的要求，有效的提高了對種群的搜索能力。在選擇上應(yīng)用輪盤賭選則法和最佳個體保存策略并行的方法，從而有效的避免了最優(yōu)個體的中途丟失，并且可以加速算法向最優(yōu)解的收斂。在解決本問題之前，我們應(yīng)該指出該問題的一大前提，即：每個客戶所需的貨物應(yīng)有且只有一輛車派送，以此來盡可能地將派送車輛的費用大大降低，從而使問題簡明化。在解題過程中，根據(jù)遺傳算法，在所規(guī)定的前提下，我們首先對需要的車輛進行估計，依照公式確定車輛數(shù)。在確定車輛數(shù)后

3、，我們就可以列出簡單的目標函數(shù)。在這里，我們需要明確幾個約束條件：1、約束經(jīng)過每個客戶的車輛有且只有一輛；2、保證每個客戶都有車輛運送到所需貨物；3、每輛車所載的貨物量不超過其車載量；4、使每輛車受到的懲罰費用盡可能地小。有了這些約束條件之后，我們便可以根據(jù)所列出的約束式，加上適當?shù)膽土P因子，即引入罰函數(shù)，將約束條件加入到簡單目標函數(shù)中，得到一個優(yōu)化后的目標函數(shù)，使之在同一量綱上。此外，我們就可以利用Matlab軟件得到使種群適應(yīng)度最強的染色體，即最優(yōu)的配送路徑。最終，我們得到的最優(yōu)配送路徑為：派送3輛車，車輛1的行使路線為物流中心客戶8客戶5客戶7物流中心，行駛時間為11.9h，裝載量為7t

4、，運送里程為405；車輛2的行駛路線為物流中心客戶3客戶1客戶2物流中心，行駛時間為8.8h，裝載量為8t,運送里程為240,；車輛3的行使路線為物流中心客戶6客戶4物流中心，行駛時間為10.8h，裝載量為7t，運送里程為265.該方案總配送時間為31.5h，裝載量為22t，運送里程為910，達到了滿意的優(yōu)化結(jié)果。最后，我們又對所得出的方案進行了分析，找出其優(yōu)缺點，提出了我們的一些改進意見，希望能夠得到更加完善的方案。 關(guān)鍵詞：路徑優(yōu)化 遺傳算法 約束條件 適應(yīng)度 罰函數(shù) Matlab軟件一、 問題重述1.1 問題背景車輛調(diào)度問題（Vehicle Routing Problem,簡稱VRP）問

5、題最早是由Dantzig和Ramser于1959年提出的。VRP問題的解法豐富，基本可以分為精確算法和啟發(fā)式算法兩大類。由于VRP屬于強NP問題，運用精確算法求解計算量會隨著問題規(guī)模的增大而呈現(xiàn)指數(shù)增加，因此，實際中其應(yīng)用范圍比較有限。實際應(yīng)用中多采用啟發(fā)式計算法，其種類也很多，常用的有：Clarke和Wright提出的CW節(jié)約啟發(fā)式，Gillett和Miller提出的Sweep算法等。但這些算法也存在一定的問題，節(jié)約法雖然運算速度快，但是組合點零亂、邊緣點難以組合，往往在客戶數(shù)目較多、問題規(guī)模增大時，可行解的空間也相應(yīng)增大，節(jié)約算法的優(yōu)化效果也相應(yīng)的下降；而掃描法為非漸進優(yōu)化。隨著科學(xué)的發(fā)展

6、，不斷有新的算法引入到VRP的求解中來，例如，模擬退火算法，遺傳算法，神經(jīng)網(wǎng)絡(luò)算法等。針對本題，我們主要采用了遺傳算法。在此問題中，我們考慮到一個軟硬時間窗的問題，關(guān)于這個問題，我們以題中實例來說。所謂軟時間窗即配送車輛在運送過程中因到達時間不在規(guī)定范圍內(nèi)而產(chǎn)生的一些成本費用，這些費用在加上一個懲罰因子后可估計該損失。至于硬時間窗，在本題中指的是因車輛載重超重而產(chǎn)生的成本費用，由于車輛載重關(guān)乎安全等問題，所產(chǎn)生的損失較大，亦可使用懲罰因子來進行實際評估。軟時間窗與硬時間窗的最根本區(qū)別在于，硬時間窗較軟時間窗產(chǎn)生更巨大的損失。1.2 問題提出某物流中心擁有一支貨運車隊，為若干個客戶配送物資，物流

7、中心與客戶以及客戶與客戶之間的公路里程(千米)為已知。每天，各客戶所需物資的重量(噸)均已知，并且每個客戶所需物資的重量都小于一臺貨運車輛的載重量，所有送貨車輛都從物流中心出發(fā)，最后回到物流中心。物流中心每天的配送方案應(yīng)當包括：當天出動多少臺車？行駛路徑如何？由此形成的當天總運行里程是多少？一個合格的配送方案要求送貨車輛必須在一定的時間范圍內(nèi)到達客戶處，早到達將產(chǎn)生等待損失，遲到達將予以一定的懲罰。要求： 1. 建立送貨車輛每天總運行里程最短的一般數(shù)學(xué)模型，并給出求解方法。2. 對于載重量為 噸，平均速度為50千米/小時的送貨車輛從物流中心()出發(fā)，為編號是=1,2,8的8個客戶配送物資。某日

8、，第個客戶所需物資的重量為噸，在第個客戶處卸貨時間為小時，第個客戶要求送貨車輛到達的時間范圍由表1給出。物流中心與各客戶以及各客戶間的公路里程(單位:千米)由表2給出。問當日如何安排送貨車輛(包括出動車輛的臺數(shù)以及每一臺車輛的具體行駛路徑)才能使總運行里程最短。二、模型假設(shè)1、每個客戶的貨物有且只有由一輛貨車運送。2、針對到達時間存在一個與成本相關(guān)的懲罰因子，而這個懲罰因子必然存在且為正解。3、對于車載量問題，我們制定一個超載系數(shù)，該超載系數(shù)與懲罰因子相似，但比懲罰因子要大得多，以嚴格控制安全和成本。4、不考慮在該問題中的一些意外事故問題，如車禍、紅綠燈等。5、從配送中心出發(fā)的時間為0時。三、

9、符號說明為運貨車輛數(shù)表示第輛車，是對裝載車以及卸載車的復(fù)雜程度及約束多少的估計是指車輛的載重量客戶及物流中心客戶及物流中心客戶及物流中心之和為車輛從客戶行駛到客戶的時間表示客戶的運貨任務(wù)開始時間為完成該任務(wù)的所需時間（本題主要指卸貨）為任務(wù)允許最早開始時間為任務(wù)允許最遲開始的時間表示各項系數(shù)的值為第個染色體的適應(yīng)度為當前染色體對應(yīng)的運輸路徑四、問題一模型的建立與分析4.1 簡單一般模型的建立本題針對的是物資配送中的路徑優(yōu)化問題，題意要求我們建立該類問題的一般數(shù)學(xué)模型。我們根據(jù)題中所給出的條件，分析得該問題可知，該問題的類型為有時間窗的非滿載車輛調(diào)度問題。為了方便求解，將問題簡化為某一個配送中心

10、對一定范圍內(nèi)的客戶進行物流配送服務(wù)。配送中心根據(jù)不同的客戶需求點安排路線執(zhí)行配送任務(wù)，且各配送點所需貨物量不超過運貨車的車載量。根據(jù)題意，各需求點到配送中心的距離已知，客戶規(guī)定配送車輛送貨到達和完成的時間已知，由于題意中的配送車輛數(shù)未知，我們需要預(yù)先對需要的車輛進行評估。經(jīng)過查閱文獻資料，我們可按照下式確定車輛數(shù)： （1）式中，表示不大于括號數(shù)字的最大整數(shù)；，是對裝載車以及卸載車的復(fù)雜程度及約束多少的估計，越復(fù)雜越小。在本題中，限制條件僅有時間，卸載車輛并不復(fù)雜，再根據(jù)所查閱的資料，將的值取為0.95。我們在此采用客戶之間的距離，目標為使車輛總距離最短。我們將物流中心編號為0，客戶及物流中心以

11、點來表示。設(shè)為車輛從點行駛到點的時間，用表示客戶的運貨任務(wù)開始時間， 為完成該任務(wù)的所需時間（本題主要指卸貨）。設(shè)任務(wù)的開始時間需要在一定的時間范圍內(nèi)，其中為任務(wù)允許最早開始時間，為任務(wù)允許最遲開始的時間。如果車輛早于，則要加乘懲罰因子（對于此類問題，一般取2），如果車輛到達時間晚于，則要加乘懲罰因子（根據(jù)實際情況，一般取3）。如果車輛載重超過規(guī)定數(shù)，則要加乘超載懲罰因子（為嚴格滿足容量約束，應(yīng)取，但為了計算機的實現(xiàn)，在此?。，F(xiàn)定義變量如下： 車輛由點駛向點 否則 點的貨運任務(wù)由車輛完成否則 則得到數(shù)學(xué)模型如下：目標函數(shù)： （1） 約束條件： （2） （3） （4） （5） （6） （7）

12、（8）在上述式子中，（1）式表示路程極小時的目標；（2）式表示運貨車輛在客戶規(guī)定的時間段內(nèi)到達；（3）式表示點的貨運任務(wù)只由一輛車完成；（4）式（5）式表示兩個變量之間的關(guān)系（6）式和（7）式表示路線的可行性。為了使目標函數(shù)和約束條件處于同一量綱，我們引入了罰函數(shù)，即在加入懲罰因子的前提下，將約束條件融入目標函數(shù)中，最終得到了如下目標函數(shù)： 4.2 遺傳算法的設(shè)計從建立的模型中，我們可以看到，求解車輛路徑問題的關(guān)鍵是合理確定車輛和客戶的關(guān)系，在滿足約束條件的前提下，使總運距最小。由此我們借鑒一些遺傳算法的例子構(gòu)建了如下遺傳算法。4.2.1 遺傳算法的原理我們首先基于染色體結(jié)構(gòu)對該問題進行分析。

13、采用自然編碼，VSP的一條可行路線可以編成長度為的染色體，其中表示第輛車到第個客戶，這樣的染色體結(jié)構(gòu)可以理解為車輛從物流中心出發(fā)，經(jīng)過客戶后回到物流中心，形成子路徑1；而第二輛車也是從物流中心出發(fā)，經(jīng)過后，返回物流中心0，從而形成了子路徑2，如此反復(fù)，直到所有客戶被訪問到。這樣，使染色體具有了子路徑內(nèi)部有序，而各個子路徑之間無序的特征。通過Rnd子函數(shù)隨機產(chǎn)生初始種群，然后在輪盤賭選擇法的基礎(chǔ)上，采用最佳個體保留選擇策略，按照適應(yīng)度的高低來選擇雙親。再通過基因重組和染色體變異，產(chǎn)生子代。然后用子代代替父代，執(zhí)行新一輪的進化，直到滿足停止條件，產(chǎn)生最優(yōu)個體，獲得最優(yōu)解。 遺傳算法的步驟 Step

14、1 設(shè)置算法參數(shù) 種群數(shù)量eranum=200（代數(shù)取100-1000(默認200)）種群規(guī)模 popsize=100（種群規(guī)模取50-200(默認100)）交叉概率 pcross=0.8 (一般取0.5-0.85之間較好(默認0.8)初始變異概率pmutation=0.1 （一般取0.05-0.2之間較好(默認0.1)）Step2 產(chǎn)生初始種群Step3 計算種群中染色體的目標函數(shù)和適應(yīng)度目標函數(shù)： 適應(yīng)度：Step4 根據(jù)適應(yīng)度選擇雙親Step5 進行交叉遺傳和變異遺傳Step6 判斷是否滿足進化代數(shù)200代，如果進化代數(shù)滿足200代，程序算法終止；若不滿足，返回step34.3 一般求解

15、方法 對于此類問題，將實際問題具體給出的客戶數(shù)量，貨車最大載重量和車速，每個客戶所需貨物重量，在每個客戶處的卸貨時間，每個客戶要求到達的規(guī)定時間范圍以及客戶與物流中心、客戶與客戶之間的距離代入以上數(shù)學(xué)模型，按照算法計算。在matlab上運行該遺傳算法程序，得出近似最優(yōu)解。五、問題二模型的建立與分析5.1 模型的建立根據(jù)問題一中所建立的一般數(shù)學(xué)模型，我們將題中所給的數(shù)據(jù)代入，就可以得到本題所需的模型。目標函數(shù)： 約束條件： 5.2 模型的求解在遺傳算法的基礎(chǔ)上，我們根據(jù)目標函數(shù)和約束條件通過matlab運行遺傳算法程序，得出程序運行結(jié)果：g =0   &#

16、160; 6     4     0     8     5     7     0     3     1     2 

17、0;   0 fvalue =9105.3 優(yōu)化模型的最終方案根據(jù)處理后的數(shù)據(jù)，我們得出了一個針對本題的使總運行里程最短的相對優(yōu)化的路徑最優(yōu)方案：表一：配送最優(yōu)方案配送車輛配送路線配送時間（h）車載量(t)運輸里程(km)總懲罰時間(h)車輛1物流中心客戶8客戶5客戶7物流中心11.974050車輛2物流中心客戶3客戶1客戶2物流中心8.882400車輛3物流中心客戶6客戶4物流中心10.872650根據(jù)表一，我們得到最優(yōu)方案為：出動車輛數(shù)為3輛 總行駛時間:31.5h 總車載量：22t 無懲罰時間 總運輸里程最小為：910km其圖形可以表示為：圖二 最

18、優(yōu)化配送路徑六、模型評價與推廣改進6.1 模型的評價優(yōu)點：1、與問題領(lǐng)域無關(guān)切快速隨機的搜索能力。2、搜索從群體出發(fā)，具有潛在的并行性，可以進行多個個體的同時比較。3、搜索使用評價函數(shù)啟發(fā)，過程簡單。4、使用概率機制進行迭代，具有隨機性。5、具有可拓展性，容易與其他算法結(jié)合。缺點：1、遺傳算法的編程實現(xiàn)比較復(fù)雜，首先需要對問題進行編碼，找到最優(yōu)解之后還需要對問題進行解碼。 2、另外三個算子的實現(xiàn)也有許多參數(shù)，如交叉率和變異率，并且這些參數(shù)的選擇嚴重影響解的品質(zhì)，而且這些參數(shù)的選擇大部分是依靠經(jīng)驗。 3、沒有能夠及時利用網(wǎng)絡(luò)的反饋信息，故算法的搜索速度比較慢，要得到較精確的解需要較多的訓(xùn)練時間。 4、算法對初始種群的選擇有一定依賴性，能夠結(jié)合一些啟發(fā)算法進行改進。 5、算法的并行機制潛在能力沒有得到充分的利用，這也是當前遺傳算法的一個研究熱點方向。在現(xiàn)在的工作中，遺傳算法（1972年提出）已經(jīng)不能很好的解決大規(guī)模計算量問題，它很容易陷入“早熟”。 采用何種選擇方法既要使優(yōu)良個體得以保留，又要維持群體的多樣性，一直是遺傳算法中較難解決的問題。6.2 模型的推廣改進遺傳算法不僅僅可以解決本題中1個物流中心與8個客戶