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

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

2、提出物流被稱為“第三利潤(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)系。而在物流配送中，車(chē)輛運(yùn)輸占有不可或缺的地位，因此車(chē)輛運(yùn)輸?shù)膬?yōu)化是非常關(guān)鍵的一環(huán)。對(duì)運(yùn)輸車(chē)輛進(jìn)行的優(yōu)化調(diào)度，不僅可以提高經(jīng)濟(jì)效益，還可以促進(jìn)物流的科學(xué)化。通過(guò)對(duì)車(chē)輛配送的合理調(diào)度，可以實(shí)現(xiàn)最短路徑、最少時(shí)間、最少車(chē)輛、最低費(fèi)用等目標(biāo)。本文所探究的問(wèn)題是單車(chē)型滿載車(chē)輛的分送優(yōu)化制度，我們以路徑最短為目標(biāo)，以各需求點(diǎn)的最小需求量為約束，求解出總路徑最短的車(chē)輛運(yùn)輸線路。2模型假設(shè)1. 車(chē)輛行駛中始終做勻速直線運(yùn)動(dòng)，即在任

3、何區(qū)段車(chē)速都相同。2. 公路系統(tǒng)暢通無(wú)阻，不考慮中途發(fā)生故障堵車(chē)等情況。3. 不考慮司機(jī)短時(shí)間休息之類的人為因素。4. 各路徑發(fā)車(chē)頻度相同。5. 將車(chē)輛裝卸時(shí)間認(rèn)為是車(chē)輛總運(yùn)輸時(shí)間的一部分。6. 貨運(yùn)地中之一為物流裝配中心，全部車(chē)輛從物流裝配中心出發(fā)，最后回到裝配中心。3 符號(hào)說(shuō)明 車(chē)輛擁有的容量 表示點(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)題可以描述為:從配送中心(物流據(jù)點(diǎn))用多輛汽車(chē)向多個(gè)需求點(diǎn)送貨，每個(gè)需求點(diǎn)的位置和需求量一定，每輛汽車(chē)的載重量一定，并且某些需求點(diǎn)的需求量超過(guò)一

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

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

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

7、最大節(jié)約值準(zhǔn)則，首先對(duì)兩點(diǎn)進(jìn)行比較，把不在線路上的點(diǎn)插入線路，已在線路中的點(diǎn)合并為一集合 ，直到所有點(diǎn)都被 安排到線路中。對(duì)于分送式配送問(wèn)題，在連接點(diǎn)對(duì)時(shí)需 要考慮車(chē)輛的容量約束和運(yùn)行路程約束，即一條線路上 各任務(wù)的貨運(yùn)量之和應(yīng)不大于車(chē)輛的容量和車(chē)輛運(yùn)行路 程不大于額定路程。 6.1.2 算法步驟 根據(jù)前述求解原理，給出具體求解步驟如下:s t e p 1 ：計(jì)算，令；s t e p 2 ：在內(nèi)按從大到小的順序排列；s t e p 3 ： 若，則終止，否則對(duì)第一項(xiàng)，考察對(duì)應(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)，且個(gè)是起點(diǎn)，一個(gè)是終點(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)在需要制定六個(gè)貨運(yùn)站A、B、C、D、E、F之間的四條路線的往來(lái)運(yùn)輸業(yè)務(wù)。已知各條路線的起點(diǎn)、終點(diǎn)城市之間的運(yùn)行時(shí)間及每個(gè)小時(shí)的運(yùn)輸次數(shù)見(jiàn)下表。又知每輛貨車(chē)每次裝卸的時(shí)間各需1小時(shí)，

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

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

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

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

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

14、5621C2D1-7009AB021C2D2-7009AC1021C2D3-7009AC2027D1E-21849AD1027D2E-21849AD2027D3E-21849AD3030D1F-39489AE030D2F-39489AF030D3F-3948根據(jù)表5所示的的順序，逐項(xiàng)考察對(duì)應(yīng)的線路，點(diǎn)對(duì)之間的連接過(guò)程如表6所示。表6 點(diǎn)對(duì)間的連接過(guò)程線路連接否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按照所得的最終配送線路，可以使此物流公司所有貨車(chē)行駛路程最短，可以減少消耗的費(fèi)用。7.優(yōu)缺點(diǎn)分析以旅行商問(wèn)題的Cw節(jié)約算法為基礎(chǔ)，構(gòu)造了連接點(diǎn)對(duì)時(shí)對(duì)線路上各需求點(diǎn)的最小需求量約