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