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

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

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

3、何區(qū)段車速都相同。2. 公路系統(tǒng)暢通無阻，不考慮中途發(fā)生故障堵車等情況。3. 不考慮司機(jī)短時間休息之類的人為因素。4. 各路徑發(fā)車頻度相同。5. 將車輛裝卸時間認(rèn)為是車輛總運(yùn)輸時間的一部分。6. 貨運(yùn)地中之一為物流裝配中心，全部車輛從物流裝配中心出發(fā)，最后回到裝配中心。3 符號說明 車輛擁有的容量 表示點(diǎn)到點(diǎn)的距離 點(diǎn)和點(diǎn)連接后的線路上總運(yùn)量 已知任務(wù)i的貨運(yùn)量 點(diǎn)和點(diǎn)連接在一條線路上的距離節(jié)約值 表示配送中心4模型的理論基礎(chǔ)本文中的物流配送路徑優(yōu)化問題可以描述為:從配送中心(物流據(jù)點(diǎn))用多輛汽車向多個需求點(diǎn)送貨，每個需求點(diǎn)的位置和需求量一定，每輛汽車的載重量一定，并且某些需求點(diǎn)的需求量超過一

4、輛貨車的最大額載。要求根據(jù)貨車的載重和行駛距離合理安排車輛路線，使總運(yùn)距最短。(1)因?yàn)樗拓浳锟傊亓砍^一輛貨車的額載，所以需要若干輛貨車一起送貨。(2)每輛車一次可以給幾個需求點(diǎn)送貨，從配送中心出發(fā)到返回稱之為一條行駛路徑。(3)運(yùn)輸成本的含義可以是車輛行駛距離、費(fèi)用和時間等，本文用行駛距離來表示運(yùn)輸成本。5模型建立建立如下模型：有一個物流配送中心，擁有多臺容量為q的車輛，現(xiàn)在有m項(xiàng)貨物運(yùn)輸任務(wù)需要完成，以1，2，m表示，已知任務(wù)的貨運(yùn)量為 (=1，2， ，m)，且，求滿足貨運(yùn)需求的費(fèi)用最小的車輛運(yùn)輸線路。為構(gòu)造數(shù)學(xué)模型方便，將物流配送中心編號為0，任務(wù)編號為1，2， ，m，任務(wù)及物流配送

5、中心均以點(diǎn) (=0，1，2，m)來表示。定義變量如下：則分送式配送車輛優(yōu)化調(diào)度問題一般數(shù)學(xué)模型如下：模型中， 表示從點(diǎn)到點(diǎn)的運(yùn)輸成本，它的含義可以是距離、費(fèi)用、時間等；為車輛容量；為支路消去約束，即消去構(gòu)成不完整線路的解。圖1 支路示意圖如圖1所示，兩條支路均滿足分配約束，但沒有構(gòu)成一條完整的線路，因此不是問題的解。在實(shí)際問題中，分送式配送問題，其車輛路線選擇不僅要受到車輛容量限制，而且有時還會受到運(yùn)行距離、運(yùn)行時間、不同區(qū)段的車速以及運(yùn)行途中的障礙物、司機(jī)的短時間休息等因素影響?，F(xiàn)在假設(shè)一條線路上允許的最大的運(yùn)行距離為l，則有約束條件：將該約束條件加到上述模型中，于是得到帶有運(yùn)行距離約束的配

6、送車輛優(yōu)化調(diào)度模型。6模型求解6.1節(jié)約算法6.1.1算法原理算法基于節(jié)約法的基本思想。設(shè)P0為配送中心，分別向用戶 和 送貨。P0到 和 的距離分別為 和， 兩個用戶Pi、 之間的距離為 ，送貨方案只有兩種，即配送中心ro向用戶Pi、P；分別送貨和配送中心向用戶Pi、P；同時送貨，如圖2所示。比較兩種配送方案：圖2 節(jié)約法方案方案(b)配送線路為：，配送距離為：；方案(b)配送線路為：，配送距離為：。顯然,我們用表示路線節(jié)約值，即方案(b)比方案(a)節(jié)約的配送路程 ：即是將點(diǎn)和點(diǎn)連接在一條線路上的距離節(jié)約值，值越大，說明把和連接在一起時總路程減少越多。旅行商問題的c-w節(jié)約算法就是基于這種

7、最大節(jié)約值準(zhǔn)則，首先對兩點(diǎn)進(jìn)行比較，把不在線路上的點(diǎn)插入線路，已在線路中的點(diǎn)合并為一集合 ，直到所有點(diǎn)都被 安排到線路中。對于分送式配送問題，在連接點(diǎn)對時需 要考慮車輛的容量約束和運(yùn)行路程約束，即一條線路上 各任務(wù)的貨運(yùn)量之和應(yīng)不大于車輛的容量和車輛運(yùn)行路 程不大于額定路程。 6.1.2 算法步驟 根據(jù)前述求解原理，給出具體求解步驟如下:s t e p 1 ：計(jì)算，令；s t e p 2 ：在內(nèi)按從大到小的順序排列；s t e p 3 ： 若，則終止，否則對第一項(xiàng)，考察對應(yīng)的，若滿足下述條件之一：( 1 )點(diǎn)和點(diǎn)均不在已構(gòu)成的線路上；( 2 )點(diǎn)或點(diǎn)在已構(gòu)成的線路上，但不是線路內(nèi)點(diǎn)；( 3 )

8、點(diǎn)和點(diǎn)位于已構(gòu)成的不同線路上，均不是內(nèi)點(diǎn)，且個是起點(diǎn)，一個是終點(diǎn)。則轉(zhuǎn)下步， 否則轉(zhuǎn)s t e p 7。s t e p 4 ：考察點(diǎn)和點(diǎn)連接后的線路上總運(yùn)量，若，則轉(zhuǎn)下步，否則轉(zhuǎn)s t e p 7 。s t e p 5 ：考察點(diǎn)和點(diǎn)連接后的線路上總路程 L， 若 L l，則轉(zhuǎn)下步，否則轉(zhuǎn) s t e p 7 。s t e p 6 ：連接點(diǎn)和點(diǎn)。s t e p 7 ：令，轉(zhuǎn)s t e p 3。6.2求解結(jié)果某物流公司現(xiàn)在需要制定六個貨運(yùn)站A、B、C、D、E、F之間的四條路線的往來運(yùn)輸業(yè)務(wù)。已知各條路線的起點(diǎn)、終點(diǎn)城市之間的運(yùn)行時間及每個小時的運(yùn)輸次數(shù)見下表。又知每輛貨車每次裝卸的時間各需1小時，

9、每輛貨車的載貨量為154噸,貨車運(yùn)行的平均速度28.則該物流公司應(yīng)如何配備貨車，才能滿足要求。路線起點(diǎn)貨運(yùn)站終點(diǎn)貨運(yùn)站每小時運(yùn)輸量(噸)1ED4602BC3003AF1504DB150距離(公里)ABCDEFA02856392196196B28084364224224C56840420140140D3923644200476560E196224140476084F196224140560840把C地分為C1和C2，D分為D1、D2和D3，如表1，則符合上面所建模型的條件：，由此列出表2表1 各貨運(yùn)站的貨物需求量客戶ABC1C2D1D2D3EF需求量01501501501531531540150

10、表2 物流配送中心及各貨運(yùn)站之間的距離PjDPiPABC1C2D1D2D3EFP00285656392392392196196A00285656392392392196196B282808484364364364224224C156568400420420420140140C256568400420420420140140D1392392364420420000476560D2392392364420420000476560D3392392364420420000476560E196196224140140476476476084F196196224140140560560560840所耗時間

11、分為運(yùn)輸時間和裝卸時間，運(yùn)輸時間由求出，列出表3如下。表3 物流配送中心及各貨運(yùn)站之間所耗時間PjDPiPABC1C2D1D2D3EFP0012214141477+2A0012214141477+2B1103+23+213+213+213+288C1223+20015151555C2223+20015151555D1141413+2151500017+220D2141413+2151500017+220D3141413+2151500017+220E7785517+217+217+203F7+27+285520202030約束條件為每小時運(yùn)輸量，為便于計(jì)算，用各連線所耗時間乘以其各自實(shí)際距離，

12、得出各貨運(yùn)站之間的假想距離，列出表4如下。表4 物流配送中心及各貨運(yùn)站之間的假想距離PjDPiPABC1C2D1D2D3EFP002811211254885488548813721764A002811211254885488548813721764B2828042042054605460546017921792C111211242000630063006300700700C211211242000630063006300700700D154885488546063006300000904411200D254885488546063006300000904411200D3548854885460

13、63006300000904411200E1372137217927007009044904490440252F1764176417927007001120011200112002520首先計(jì)算各點(diǎn)對間連接的距離節(jié)約值：例如，連接點(diǎn)A和B時，有：類似地，可得到連接其他各點(diǎn)對時的距離節(jié)約值，按從大到小的順序示于表5中。表5 點(diǎn)對間連接的距離節(jié)約值序號路線節(jié)約值序號路線節(jié)約值1EF28849BF02C1F117618BC1-2802C2F117618BC2-2804C1E78420BE-3924C2E78421C1D1-7006BD15621C1D2-7006BD25621C1D3-7006BD3

14、5621C2D1-7009AB021C2D2-7009AC1021C2D3-7009AC2027D1E-21849AD1027D2E-21849AD2027D3E-21849AD3030D1F-39489AE030D2F-39489AF030D3F-3948根據(jù)表5所示的的順序，逐項(xiàng)考察對應(yīng)的線路，點(diǎn)對之間的連接過程如表6所示。表6 點(diǎn)對間的連接過程線路連接否EF0+150qC2F150+150qC1E150+0qC2E150+0qBD2150+153qBD3150+154qAB0+150qAC10+150qAC20+150qAD10+153qAD20+153qAD30+154qAE0+0qAF0+150qBC1150+150qBC2150+150qBE150+0qC1D2150+153qC1D3150+154qC2D1150+153qC2D2150+153qC2D3150+154qD1E153+0qD2E153+0qD3E154+0qD2F153+150qD3F154+150q由表6可得最終配送線路為：線路1：P-A-F-P線路2：P-B-E-C-P線路3：P-E-D-P線路4：P-D-E-B-P按照所得的最終配送線路，可以使此物流公司所有貨車行駛路程最短，可以減少消耗的費(fèi)用。7.優(yōu)缺點(diǎn)分析以旅行商問題的Cw節(jié)約算法為基礎(chǔ)，構(gòu)造了連接點(diǎn)對時對線路上各需求點(diǎn)的最小需求量約