基于節(jié)約算法的車輛調(diào)度優(yōu)化

《基于節(jié)約算法的車輛調(diào)度優(yōu)化》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。

1、基于節(jié)約算法的車輛調(diào)度優(yōu)化李天昊邵子楠宋曲摘要本文建立了單車型滿載車輛的分送優(yōu)化模型，并基于節(jié)約算法進行了求解。首先對于問題進行分析，確定模型的方向?qū)⑹且愿餍枨簏c的最小需求量為約束，以總運輸路徑最短為目標。影響運輸路徑的因素有車輛的載重與車輛的行駛距離。基于這些分析建立模型。以節(jié)約算法的基本思想為基礎，對模型進行具體求解。最后給出了本處理方法的優(yōu)缺點分析。關鍵詞：車輛；最短路程；節(jié)約算法；分配調(diào)度14目錄1問題提出22模型假設23符號說明34模型的理論基礎35模型建立46模型求解66.1節(jié)約算法66.1.1算法原理66.1.2算法步驟76.2求解結(jié)

2、果77.優(yōu)缺點分析14參考文獻14141問題提出物流被稱為“第三利潤源泉”，引起了越來越多的重視，成為當前“最重要的競爭領域”。配送是物流中的一個重要核心環(huán)節(jié)，是貨物從物流結(jié)點送達收貨人的過程，它實現(xiàn)了生產(chǎn)者與消費者的相互聯(lián)系。而在物流配送中，車輛運輸占有不可或缺的地位，因此車輛運輸?shù)膬?yōu)化是非常關鍵的一環(huán)。對運輸車輛進行的優(yōu)化調(diào)度，不僅可以提高經(jīng)濟效益，還可以促進物流的科學化。通過對車輛配送的合理調(diào)度，可以實現(xiàn)最短路徑、最少時間、最少車輛、最低費用等目標。本文所探究的問題是單車型滿載車輛的分送優(yōu)化制度，我們以路徑最短為目標，以各需求點的最小需求量為

3、約束，求解出總路徑最短的車輛運輸線路。2模型假設1.車輛行駛中始終做勻速直線運動，即在任何區(qū)段車速都相同。2.公路系統(tǒng)暢通無阻，不考慮中途發(fā)生故障堵車等情況。3.不考慮司機短時間休息之類的人為因素。4.各路徑發(fā)車頻度相同。5.將車輛裝卸時間認為是車輛總運輸時間的一部分。6.貨運地中之一為物流裝配中心，全部車輛從物流裝配中心出發(fā)，最后回到裝配中心。143符號說明車輛擁有的容量表示點到點的距離點和點連接后的線路上總運量已知任務i的貨運量點和點連接在一條線路上的距離節(jié)約值表示配送中心4模型的理論基礎本文中的物流配送路徑優(yōu)化問題可以描述為:從配送中心(物流

4、據(jù)點)用多輛汽車向多個需求點送貨，每個需求點的位置和需求量一定，每輛汽車的載重量一定，并且某些需求點的需求量超過一輛貨車的最大額載。要求根據(jù)貨車的載重和行駛距離合理安排車輛路線，使總運距最短。(1)因為所送貨物總重量超過一輛貨車的額載，所以需要若干輛貨車一起送貨。(2)每輛車一次可以給幾個需求點送貨，從配送中心出發(fā)到返回稱之為一條行駛路徑。(3)運輸成本的含義可以是車輛行駛距離、費用和時間等，本文用行駛距離來表示運輸成本。145模型建立建立如下模型：有一個物流配送中心，擁有多臺容量為q的車輛，現(xiàn)在有m項貨物運輸任務需要完成，以1，2，??，m表示，

5、已知任務的貨運量為(=1，2，??，m)，且，求滿足貨運需求的費用最小的車輛運輸線路。為構造數(shù)學模型方便，將物流配送中心編號為0，任務編號為1，2，??，m，任務及物流配送中心均以點(=0，1，2，??，m)來表示。定義變量如下：則分送式配送車輛優(yōu)化調(diào)度問題一般數(shù)學模型如下：模型中，表示從點到點的運輸成本，它的含義可以是距離、費用、時間等；為車輛容量；為支路消去約束，即消去構成不完整線路的解。14圖1支路示意圖如圖1所示，兩條支路均滿足分配約束，但沒有構成一條完整的線路，因此不是問題的解。在實際問題中，分送式配送問題，其車輛路線選擇不僅要受到車輛容

6、量限制，而且有時還會受到運行距離、運行時間、不同區(qū)段的車速以及運行途中的障礙物、司機的短時間休息等因素影響?，F(xiàn)在假設一條線路上允許的最大的運行距離為l，則有約束條件：將該約束條件加到上述模型中，于是得到帶有運行距離約束的配送車輛優(yōu)化調(diào)度模型。146模型求解6.1節(jié)約算法6.1.1算法原理算法基于節(jié)約法的基本思想。設P0為配送中心，分別向用戶和送貨。P0到和的距離分別為和，兩個用戶Pi、之間的距離為，送貨方案只有兩種，即配送中心r'o向用戶Pi、P；分別送貨和配送中心向用戶Pi、P；同時送貨，如圖2所示。比較兩種配送方案：圖2節(jié)約法方案方案(b)配送

7、線路為：，配送距離為：；方案(b)配送線路為：，配送距離為：。顯然,我們用表示路線節(jié)約值，即方案(b)比方案(a)節(jié)約的配送路程：即是將點和點連接在一條線路上的距離節(jié)約值，值越大，說明把和連接在一起時總路程減少越多。旅行商問題的c-w節(jié)約算法就是基于這種最大節(jié)約值準則，首先對兩點進行比較，把不在線路上的點插入線路，已在線路中的點合并為一集合14，直到所有點都被安排到線路中。對于分送式配送問題，在連接點對時需要考慮車輛的容量約束和運行路程約束，即一條線路上各任務的貨運量之和應不大于車輛的容量和車輛運行路程不大于額定路程。6.1.2算法步驟根據(jù)前述求解

8、原理，給出具體求解步驟如下:step1：計算，令；step2：在內(nèi)按從大到小的順序排列；step3：若，則終止，否則對第一