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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、方法 對于此類問題，將實(shí)際問題具體給出的客戶數(shù)量，貨車最大載重量和車速，每個(gè)客戶所需貨物重量，在每個(gè)客戶處的卸貨時(shí)間，每個(gè)客戶要求到達(dá)的規(guī)定時(shí)間范圍以及客戶與物流中心、客戶與客戶之間的距離代入以上數(shù)學(xué)模型，按照算法計(jì)算。在matlab上運(yùn)行該遺傳算法程序，得出近似最優(yōu)解。五、問題二模型的建立與分析5.1 模型的建立根據(jù)問題一中所建立的一般數(shù)學(xué)模型，我們將題中所給的數(shù)據(jù)代入，就可以得到本題所需的模型。目標(biāo)函數(shù)： 約束條件： 5.2 模型的求解在遺傳算法的基礎(chǔ)上，我們根據(jù)目標(biāo)函數(shù)和約束條件通過matlab運(yùn)行遺傳算法程序，得出程序運(yùn)行結(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ù)，我們得出了一個(gè)針對本題的使總運(yùn)行里程最短的相對優(yōu)化的路徑最優(yōu)方案：表一：配送最優(yōu)方案配送車輛配送路線配送時(shí)間（h）車載量(t)運(yùn)輸里程(km)總懲罰時(shí)間(h)車輛1物流中心客戶8客戶5客戶7物流中心11.974050車輛2物流中心客戶3客戶1客戶2物流中心8.882400車輛3物流中心客戶6客戶4物流中心10.872650根據(jù)表一，我們得到最優(yōu)方案為：出動(dòng)車輛數(shù)為3輛 總行駛時(shí)間:31.5h 總車載量：22t 無懲罰時(shí)間 總運(yùn)輸里程最小為：910km其圖形可以表示為：圖二 最

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