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

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

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

4、輛貨車的最大額載。要求根據貨車的載重和行駛距離合理安排車輛路線，使總運距最短。(1)因為所送貨物總重量超過一輛貨車的額載，所以需要若干輛貨車一起送貨。(2)每輛車一次可以給幾個需求點送貨，從配送中心出發到返回稱之為一條行駛路徑。(3)運輸成本的含義可以是車輛行駛距離、費用和時間等，本文用行駛距離來表示運輸成本。5模型建立建立如下模型：有一個物流配送中心，擁有多臺容量為q的車輛，現在有m項貨物運輸任務需要完成，以1，2，m表示，已知任務的貨運量為 (=1，2， ，m)，且，求滿足貨運需求的費用最小的車輛運輸線路。為構造數學模型方便，將物流配送中心編號為0，任務編號為1，2， ，m，任務及物流配送

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

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

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

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

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

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

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

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

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

14、5621C2D1-7009AB021C2D2-7009AC1021C2D3-7009AC2027D1E-21849AD1027D2E-21849AD2027D3E-21849AD3030D1F-39489AE030D2F-39489AF030D3F-3948根據表5所示的的順序，逐項考察對應的線路，點對之間的連接過程如表6所示。表6 點對間的連接過程線路連接否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按照所得的最終配送線路，可以使此物流公司所有貨車行駛路程最短，可以減少消耗的費用。7.優缺點分析以旅行商問題的Cw節約算法為基礎，構造了連接點對時對線路上各需求點的最小需求量約