【正文】 總長的一半 ， 故需縮小外圈 。 因?yàn)橥馊α飨蚓€路中運(yùn)量最小的是 B1→A 3的 “ 20” ， 所以去掉該線路 ， 并在外圈各段流向線上減去 “ 20” 的運(yùn)量 ， 同時在里圈各流向線上 、 以及原來沒有流向線的 A2到 B3線上各加上 “ 20” 的運(yùn)量 ， 這樣可得到新的運(yùn)輸線路流向圖 。 如圖所示 。 檢查新運(yùn)輸線路圖的里、外圈流向線長 ◆ 本例新的線路流向： 外圈流向總長： 20+50＝ 70（ km） 里圈流向總長： 40＋ 60＝ 100（ km） 均沒有超過全圈總長的一半 105 km， 所以調(diào)整后的新線路流向圖所對應(yīng)的方案為最優(yōu)調(diào)運(yùn)方案。 比較分析： ◆ 按調(diào)整后的新方案組織運(yùn)輸，運(yùn)力消耗為： 40 40＋ 40 30＋ 50 10＋ 60 20＋ 20 30＋ 50 20＝ 6100（ tkm） ◆ 按初始方案組織運(yùn)輸，運(yùn)力消耗為： 40 40＋ 40 10＋ 50 30＋ 40 20＋ 20 50＋ 50 20＝ 6300（ tkm） ◆ 調(diào)整后的調(diào)運(yùn)方案比初始調(diào)運(yùn)方案節(jié)約運(yùn)力 200 tkm 起訖點(diǎn)重合的問題 物流管理人員經(jīng)常遇到的一個路線選擇問題是始發(fā)點(diǎn)就是終點(diǎn)的路線選擇 。 這類問題通常在運(yùn)輸工具是同一部門所有的情況下發(fā)生 。 這類問題求解的目標(biāo)是尋求訪問各點(diǎn)的次序 ， 以求運(yùn)行時間或距離最小化 。始發(fā)點(diǎn)和終點(diǎn)相重合的路線選擇問題通常被稱為 “ 旅行推銷員 ” 問題 ， 制定原則 ? 聚集（見右上圖） ? 避免重疊（見后圖） ? 由遠(yuǎn)及近 ? 水滴（見右下圖） ? 大車優(yōu)先 ? 混合安排取送貨 ? 特殊點(diǎn)特殊處理 ? 延長時間窗口 D D Depot Stops F F F F F F F T T T T T T T D Depot F F F F F T T T F T F T T T D Depot (a) Weak clustering routes cross (b) Better clustering Stop 運(yùn)輸配送中的解決方法 ? 主要解決：行車路線和時刻表的制定問題 ? 運(yùn)輸路徑問題的擴(kuò)展形式 ? 在每個點(diǎn)既要取一定量的貨，又要送一定量的貨； ? 使用多部車輛，每部車的載貨重量和容積不同； ? 司機(jī)的總駕駛時間達(dá)到一定上限時必須休息若干時間； ? 每個站點(diǎn)每天只允許在特定的時間（時間窗口）內(nèi)取貨和（或）送貨； ? 途中只有送貨后才能取貨； ? 允許駕駛員每天在特定的時間休息和用餐。 ? 解決方法：掃描法、節(jié)約法 掃描法 ? 在地圖中確定所有站點(diǎn) （ 包括倉庫的位置 ） ? 以倉庫為端點(diǎn)向任意方向劃一條射線 。 沿順時針或逆時針方向旋轉(zhuǎn)該射線直到與某站點(diǎn)相交 。 這時考慮在該條路線上增加該站點(diǎn) ， 是否會超過該條路線上分派車輛的載貨能力 ， 如果沒有 ， 將此站點(diǎn)計(jì)入該路線 ， 繼續(xù)旋轉(zhuǎn)射線 ， 計(jì)算累計(jì)運(yùn)貨量 ， 直到累計(jì)運(yùn)貨量超過分派車輛的運(yùn)載能力 ，則剔除最后這個站點(diǎn) ， 該條運(yùn)貨路線確定 。 ? 用水滴法或求解起訖點(diǎn)重合的路徑問題的算法來排序每條路線行車順序 ， 使得每條路線上行車距離最短 。 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é)約法 車輛運(yùn)行計(jì)劃法（ VSP， Vehicles Scheduling Program，又稱里程節(jié)約法）， 適用于分送式配送模式（由一個供應(yīng)點(diǎn)對多個客戶的共同送貨） 基本思路： ? 假設(shè)每一個站點(diǎn)都有一輛車運(yùn)送并返回倉庫 ? 將其中的一個站點(diǎn)合并到某一路徑 ， 以減少一輛運(yùn)輸車 。 合并的原則是在在滿足約束條件的前提下 ， 使合并后節(jié)約的距離最大； ? 重復(fù)上述步驟的方法 ， 即每次合并時都要計(jì)算所節(jié)約距離 ， 節(jié)約距離最多的站點(diǎn)就應(yīng)該納入到現(xiàn)有的路線 。 假如由于某些約束條件 （ 如果路線長 ， 無法滿足時間窗口的要求或超過車輛的承載能力 ） ， 則節(jié)約距離最多的站點(diǎn)不能并入該路線 ， 就要考慮節(jié)約距離次多的站點(diǎn) 。 重復(fù)該過程知道所有站點(diǎn)的路線設(shè)計(jì)都完成 。 ①基本原理： ? 三角形一邊之長必定小于另外兩邊之和 。 在汽車載重量允許的情況下，采用巡回發(fā)貨比采用往返發(fā)貨可節(jié)約汽車行走里程為： ?L=[2(L1+L2)](L1+L2+L3)=L1+L2L3 ② 目標(biāo)：配送里程最小 ， 能滿足所有用戶的要求 ③ 基本假定： ? 配送的是同一種貨物； ? 各用戶的坐標(biāo)及需求量已知； ? 配送中心有足夠的運(yùn)輸能力：不使任何一輛車超載；每輛車每天的總運(yùn)行時間或行駛里程不超過規(guī)定的上限 。 ? 實(shí)例分析 某配送中心的配送網(wǎng)絡(luò)圖如下所示 。 由配送中心 P向 A、 B、 C、 D、 E五個用戶配送物品 。 圖中連線上的數(shù)字表示公路里程 （ km） 。 圖中靠近各用戶括號里的數(shù)字 ， 表示對貨物的需求量 （ t） 。 配送中心備有 2t和 4t載質(zhì)量的汽車 ， 且汽車一次巡回行駛里程不能超過 30km。 求解該配送中心滿意的送貨方案 。 ? 第一步：計(jì)算配送中心至各用戶及各用戶之間的最短距離。 P A B C D E P — 8 3 10 8 7 A — 8 17 15 9 B — 9 11 10 C — 7 13 D — 6 E — 最短距離表 ? 第二步：由最短里程表，用節(jié)約法計(jì)算出各用戶之間的節(jié)約里程。 A B C D E A — 3 1 1 6 B — 4 0 0 C — 11 4 D — 9 E — 節(jié)約里程表 ? 第三步：根據(jù)節(jié)約里程表中節(jié)約數(shù)額的多少從大到小排序，編制節(jié)約里程順序表。 序號 路程 節(jié)約數(shù)額 1 CD 11 2 DE 9 3 AE 6 4 BC 4 5 CE 4 6 AB 3 7 AC 1 8 AD 1 節(jié)約里程順序表 ? 第四步：根據(jù)節(jié)約里程順序表和配送中心的約束條件 ， 分步漸進(jìn)地繪出配送路徑 。 ? 從圖中可以看出 ， 依次確定的 3條路徑均符合配送中心的約束條件 。 最后選擇的方案是： 路徑 路線 載貨量 行駛里程 車輛類型 1 PCDEP 30km 4t 2 PAP 16km 2t 3 PBP 3t 6km 4t 配送方案 四 、 車輛調(diào)度問題 貨運(yùn)車輛優(yōu)化調(diào)度問題可根據(jù)不同性質(zhì)具體分為以下幾類： ? 按照運(yùn)輸任務(wù)分為純裝問題 、 純卸問題以及裝卸混合問題； ? 按照車輛載貨狀況分為滿載問題和非滿載問題； ? 按照車輛類型分為單車型問題和多車型問題； ? 按照車輛是否返回車場劃分為車輛開放問題和車輛封閉問題； ? 按照優(yōu)化的目標(biāo)可分為單目標(biāo)優(yōu)化問題和多目標(biāo)優(yōu)化問題； ? 按照有無休息時間要求可分為有休息時間調(diào)度和無休息時間調(diào)度問題 。 實(shí)際中的車輛優(yōu)化調(diào)度問題可能是以上分類中的一種或幾種的綜合 。車輛優(yōu)化調(diào)度問題是一個有約束的組合優(yōu)化問題 ， 屬于 NP難題 （ Nondeterministic Polynomial Problem） 。 隨著問題輸入規(guī)模的擴(kuò)大 ， 求解時間呈幾何級數(shù)上升 。 求解車輛優(yōu)化調(diào)度的方法可以分為精確算法 、 啟發(fā)算法和智能算法 。