【正文】 。 隨著問題輸入規(guī)模的擴大 ， 求解時間呈幾何級數上升 。 實際中的車輛優(yōu)化調度問題可能是以上分類中的一種或幾種的綜合 。 ? 從圖中可以看出 ， 依次確定的 3條路徑均符合配送中心的約束條件 。 A B C D E A — 3 1 1 6 B — 4 0 0 C — 11 4 D — 9 E — 節(jié)約里程表 ? 第三步：根據節(jié)約里程表中節(jié)約數額的多少從大到小排序，編制節(jié)約里程順序表。 ? 第一步：計算配送中心至各用戶及各用戶之間的最短距離。 配送中心備有 2t和 4t載質量的汽車 ， 且汽車一次巡回行駛里程不能超過 30km。 圖中連線上的數字表示公路里程 （ km） 。 ? 實例分析 某配送中心的配送網絡圖如下所示 。 ①基本原理： ? 三角形一邊之長必定小于另外兩邊之和 。 假如由于某些約束條件 （ 如果路線長 ， 無法滿足時間窗口的要求或超過車輛的承載能力 ） ， 則節(jié)約距離最多的站點不能并入該路線 ， 就要考慮節(jié)約距離次多的站點 。 Geographical region Depot 1,000 2,000 3,000 2,000 4,000 2,000 3,000 3,000 1,000 2,000 2,000 2,000 Pickup points Depot 1,000 2,000 3,000 2,000 4,000 2,000 3,000 3,000 1,000 2,000 2,000 2,000 Route 1 10,000 units Route 2 9,000 units Route 3 8,000 units 節(jié)約法 車輛運行計劃法（ VSP， Vehicles Scheduling Program，又稱里程節(jié)約法）， 適用于分送式配送模式（由一個供應點對多個客戶的共同送貨） 基本思路： ? 假設每一個站點都有一輛車運送并返回倉庫 ? 將其中的一個站點合并到某一路徑 ， 以減少一輛運輸車 。 這時考慮在該條路線上增加該站點 ， 是否會超過該條路線上分派車輛的載貨能力 ， 如果沒有 ， 將此站點計入該路線 ， 繼續(xù)旋轉射線 ， 計算累計運貨量 ， 直到累計運貨量超過分派車輛的運載能力 ，則剔除最后這個站點 ， 該條運貨路線確定 。 ? 解決方法：掃描法、節(jié)約法 掃描法 ? 在地圖中確定所有站點 （ 包括倉庫的位置 ） ? 以倉庫為端點向任意方向劃一條射線 。 這類問題求解的目標是尋求訪問各點的次序 ， 以求運行時間或距離最小化 。km 起訖點重合的問題 物流管理人員經常遇到的一個路線選擇問題是始發(fā)點就是終點的路線選擇 。km） ◆ 按初始方案組織運輸，運力消耗為： 40 40＋ 40 10＋ 50 30＋ 40 20＋ 20 50＋ 50 20＝ 6300（ t 檢查新運輸線路圖的里、外圈流向線長 ◆ 本例新的線路流向： 外圈流向總長： 20+50＝ 70（ km） 里圈流向總長： 40＋ 60＝ 100（ km） 均沒有超過全圈總長的一半 105 km， 所以調整后的新線路流向圖所對應的方案為最優(yōu)調運方案。 因為外圈流向線路中運量最小的是 B1→A 3的 “ 20” ， 所以去掉該線路 ， 并在外圈各段流向線上減去 “ 20” 的運量 ， 同時在里圈各流向線上 、 以及原來沒有流向線的 A2到 B3線上各加上 “ 20” 的運量 ， 這樣可得到新的運輸線路流向圖 。 求解 ： 確定初始調運方案 檢查有無迂回現(xiàn)象 ★ 由圖可看出不存在對流現(xiàn)象 ， 但要檢查里 、 外圈流向線長 ， 看是否 超過全圈 （ 封閉回路線 ） 總長的 1/2 ★ 本例：全圈總長： 60+50+40+40+20=210（ km） 半圈長： 210/2＝ 105（ km） 外圈流向總長： 50+40+20=110（ km） 里圈流向總長： 40（ km） ★ 因為外圈流向總長超過了全圈總長的 1/2（ 110＞ 105） ， 可以斷定 ， 初 始運輸線路存在迂回現(xiàn)象 ， 所對應的調運方案不是最優(yōu)方案 ， 因此 ， 必須進行優(yōu)化調整 。 作法（步驟）： ◆ 例題：設有 A A A3三個配送點分別有化肥 40t、 30t、 30t， 需送往四個客戶點 B B B B4， 而且已知各配送點和客戶點的地理位置及它們之間的道路通阻情況 。 ★ 重新去段破圈，調整流向： 在超過全圈總長 1/2的里（外）圈各段流向 線上減去最小運量，然后在相反方向的外（里）圈流向線上和原來沒有 流向線的各段上，加上減去的最小運量，這樣可以得到一個新的線路流 向圖，然后轉到第二步檢查有無迂回現(xiàn)象。分別檢查每個小圈，如果圈內和圈外流向的總長度都 不超過全圈總長度的一半，那么，全圈就沒有迂回現(xiàn)象了，這個線路流 向圖就是最優(yōu)的，對應的就是最優(yōu)運輸方案。 在成圈的線路中，先假設某兩點間的線路 “ 不通 ” ，去掉這段線路，把成圈線路轉化為不成圈的線路即破圈；按照 運輸線路不成圈的圖上作業(yè)法，即可得到初始運輸方案。 ? 運輸線路成圈的流向圖要同時達到既無對流現(xiàn)象 、 又無迂回現(xiàn)象的要求才是最優(yōu)流向圖 。 （ 2）對流向圖的檢查 ——無對流 無迂回 （ 3）圖上作業(yè)法的求解思路 ? 最優(yōu)流向圖：總噸公里數最小的流向圖 ? 總噸公里數：每一條弧上的流量乘以相應的距離，再求和 （ 4）圖上作業(yè)法的求解過程 —— 運輸線路不成圈的情況 ? 對于運輸線路不成圈的流向圖 ， 只要不出現(xiàn)對流現(xiàn)象 ， 即為最優(yōu)調運方案 ? 作法：從各端點開始 ， 按 “ 各站供需就近調撥 ” 的原則進行調配 (10) (8) (7) (7) (9) ◆ 例題：某地區(qū)物資供應情況如圖所示，現(xiàn)要求通過圖上作業(yè)法得到物資調運的最優(yōu)方案。 ◆ 對于成圈 （ 構成回路 ） 的運輸線路 ， 一般來說 ， 從一點到另一點通常有 兩條路可走 。即流向圖中的收點或發(fā)點也有流量的進或出，不一定只進不出或只出不進，進出之差就是該點的收量或發(fā)量 ? 流向要畫在物資運輸方向的右側 ? 流向圖示例： A C B G F D E 10 5 8 9 7 9 (10) (8) (7) (7) (9) ◆ 運輸貨物通常會遇到兩種情況：一種是運輸線路不成圈，一種是成圈。 ? 圖上作業(yè)法 （ 1）編制交通圖和流向圖 ? 交通圖 是由產地（發(fā)點）、銷地（收點）及交通線路組成的圖形 ? 產地用圓圈表示，產量寫在圓圈內 ? 銷地用方框表示，銷量寫在方框內 ? 距離寫在?。ń煌ň€路）的旁邊 ? 交通圖示例： A C B G F D E 10 5 8 9 7 9 3 3 2 5 2 4 ? 在交通圖上表明物質流向的圖，就稱為 流向圖 ? 箭頭表示物資運輸的方向，流量寫在箭頭的旁邊。 ◆ 作圖原則： 流向劃右方，對流不應當；里圈、外圈分別算，要求不能過 半圈長；如若超過半圈長，應去運量最小段；反復運算可得最優(yōu)方案。公里的方法。 Plant 1 Requirements = 600 Plant 2 Requirements = 500 Plant 3 Requirements = 300 Supplier A Supply ? 400 Supplier C Supply ? 500 Supplier B Supply ? 700 4 a 7 6 5 5 5 9 5 8 a