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

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

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

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

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

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

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

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

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

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