物流配送問(wèn)題講義(完整版)
【正文】 1)! （ 2）整數(shù)規(guī)劃（分枝定界法、割平面法等） → 小規(guī)模 TSP問(wèn)題 （ 3）啟發(fā)式算法 → 適各種規(guī)模的 TSP問(wèn)題 TSP模型 單回路運(yùn)輸 —— TSP模型及求解 最近鄰點(diǎn)法 1 最近鄰點(diǎn)法是由 Rosen Krantz和 Stearns等人在 1977年提出的一種用于解決 TSP問(wèn)題的算法。 解： 自營(yíng)模式銷(xiāo)售額： 1000 +800 +500 =840(萬(wàn)元 ) 互用模式銷(xiāo)售額： 1200 +700 +400 =890(萬(wàn)元 ) 第三方模式銷(xiāo)售額： 1500 +1000 +300 =1110(萬(wàn)元 ) 結(jié)論：第三方配送模式的期望值最大為 1110萬(wàn)元，故該模式可作為企業(yè)比較滿(mǎn)意的模式。 解： V自營(yíng) =5/10 +220/220 +25/25 +98/99 = V互用 =5/8 +180/220 +17/25 +97/99 = V第三方 =5/5 +140/220 +15/25 +99/99 = 結(jié)論：自營(yíng)配送模式的綜合價(jià)值系數(shù)最大，是企業(yè)所要選擇的配送模式。前者稱(chēng)為最優(yōu)圈（ Optimal Cycle），后者稱(chēng)為最優(yōu)鏈（ Optimal Chain）。 （ 3）重復(fù)步驟（ 2），直到 V中所有頂點(diǎn)都加入到回路中。 單回路運(yùn)輸 —— TSP模型及求解 最近插入法求解： 1 2 3 4 5 6 假如將 V5插入 V1和 V3之間： cik+ckjcij=c15+c53c13=7+76=8 假如將 V5插入 V3和 V2之間： cik+ckjcij=c35+c52c32=7+155=17 假如將 V5插入 V1和 V2之間： cik+ckjcij=c15+c52c12=7+1510=12 所以選最小的 8，即應(yīng)將 V5插入 V1和 V3之間，其他點(diǎn)的插入法以此類(lèi)推。 綜合考慮運(yùn)輸路徑最短、總運(yùn)費(fèi)最少、總運(yùn)輸時(shí)間最短、空載車(chē)總運(yùn)行時(shí)間最少、完成任務(wù)所需的車(chē)輛最少這五個(gè)目標(biāo)時(shí)，總運(yùn)費(fèi)就不應(yīng)單單是距離的函數(shù)，而要考慮到即時(shí)配送、車(chē)輛成本、人員成本的問(wèn)題。 （ 4）路徑優(yōu)化。如前圖所示。 8531 ???Load itLoadLoad lim1 1214653 ??????62 ?Load25 2023年 1月 23日星期一 圖 掃描算法求解結(jié)果 配送需求計(jì)劃 1． DRP的概念 DRP是配送需求計(jì)劃（ distribution requirement planning）的簡(jiǎn)稱(chēng) ,它是流通領(lǐng)域中的一種物流技術(shù)，是 MRP在流通領(lǐng)域應(yīng)用的直接結(jié)果。 (2)安全庫(kù)存。 (6)在途物資。它可劃分為幾個(gè)計(jì)劃周期。 (6)匯總得到所有的進(jìn)貨計(jì)劃，把結(jié)果作為進(jìn)貨的依據(jù)。 地區(qū)倉(cāng)庫(kù) 地區(qū)倉(cāng)庫(kù) 2 的 DRP分別如 表 表 3所示。 ? 當(dāng)配送系統(tǒng)有多個(gè)運(yùn)行單位（如多個(gè)倉(cāng)庫(kù)）時(shí)，需要從系統(tǒng)整體的角度，對(duì)現(xiàn)有的各配送資源進(jìn)行有效地整合，確定個(gè)運(yùn)作單位的經(jīng)營(yíng)方向和經(jīng)營(yíng)內(nèi)容。以下表 5 52的例子來(lái)說(shuō)明。 應(yīng)用過(guò)程 DRP計(jì)劃最基本的工具就明細(xì)表，它用于協(xié)調(diào)整個(gè)計(jì)劃期內(nèi)的需求。從事物流活動(dòng)的具有完善的信息網(wǎng)絡(luò)的場(chǎng)所或組織。 (7)訂貨批量。 (3)期初和期末庫(kù)存。 2． DRP的適用對(duì)象 DRP主要適用于 流通企業(yè) 和自己具有銷(xiāo)售網(wǎng)絡(luò)和儲(chǔ)運(yùn)設(shè)施的生產(chǎn)企業(yè)。下一個(gè)被分組的是顧客 3，送貨量是 6,如果繼續(xù)分到一組， 3+5+6=14,則 超限制了。 掃描算法 22 2023年 1月 23日星期一 例子： 現(xiàn)有一個(gè)倉(cāng)庫(kù) ，需要對(duì) 9個(gè)客戶(hù)提供貨物，它們的需求量及極坐標(biāo)值見(jiàn)下表，它們的位置關(guān)系如下圖所示。 掃描算法的 4個(gè)步驟： （ 1）以起始點(diǎn) 0作為極坐標(biāo)系統(tǒng)的原點(diǎn)，并以連通圖中的任意一顧客點(diǎn)和原點(diǎn)的連線定義為角度零。解決此類(lèi)問(wèn)題時(shí)，核心問(wèn)題是如何對(duì)車(chē)輛進(jìn)行調(diào)度。 單回路運(yùn)輸 —— TSP模型及求解 例 4 現(xiàn)有一個(gè)連通圖， |V|=6，各個(gè)頂點(diǎn)之間的距離矩陣如下表所示，假設(shè) i和 j兩點(diǎn)之間的距離是對(duì)稱(chēng)的。 TSP模型 單回路運(yùn)輸 —— TSP模型及求解 TSP模型的數(shù)學(xué)描述為： 連通圖 H，其頂點(diǎn)集為 頂點(diǎn)間的距離為 TSP模型 ???????????????????????? ???? ?? ???? ?VjVixVSSxVjxVixtsxczijSi Sjijniijnjijninjijij,},1,0{)3(,1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1