物流線路優(yōu)化技術(shù)

物流線路優(yōu)化技術(shù)一、線路優(yōu)化設(shè)計(jì)的意義物流線路設(shè)計(jì)就是整合影響配送運(yùn)輸?shù)母鞣N因素，適時(shí)適當(dāng)?shù)乩矛F(xiàn)有的運(yùn)輸工具和道路狀況，及時(shí)、安全、方便、經(jīng)濟(jì)地將客戶所需的商品準(zhǔn)確地送達(dá)客戶手中。在配送運(yùn)輸線路設(shè)計(jì)中，需根據(jù)不同客戶群的特點(diǎn)和要求，選擇不同的線路設(shè)計(jì)方法，最終達(dá)到節(jié)省時(shí)間、運(yùn)距和降低配送運(yùn)輸成本的目的1.點(diǎn)點(diǎn)間運(yùn)輸——最短路徑求解方法2.單回路運(yùn)輸——TSP模型及求解3.多回路運(yùn)輸——VRP模型及求解4.多點(diǎn)間運(yùn)輸——運(yùn)輸算法二、最短路徑設(shè)計(jì)步驟：

1．設(shè)VI點(diǎn)為L1=02．求與V1相鄰未標(biāo)點(diǎn)最小距離值并標(biāo)號V2：0+5=5KMV3：0+2=2KM則標(biāo)號L3=2，并描黑V1——V33．求與V1、V3相鄰未標(biāo)號點(diǎn)最小距離值并標(biāo)號V4：2+7=9V2：0+5=5V6：2+4=6則標(biāo)號L2=5，并描黑V1——V24．求與V1、V2、V3相鄰未標(biāo)號點(diǎn)最小距離值并標(biāo)號V5：5+7=12V4：5+2=7V6：2+4=6則標(biāo)號L6=6，并描黑V3——V65．求與V1、V2、V3、V6相鄰未標(biāo)號點(diǎn)最小距離值并標(biāo)號V4：V6——V42+6=8V3——V42+7=9V2——V45+2=7V6——V56+1=7V5：V2——V55+7=12

則標(biāo)號L5=7，L4=7，并描黑V6——V5，V2——V46、求與V1、V2、V3、V4、V5、V6相鄰未標(biāo)號點(diǎn)最小值

V7：

V5——V77+3=10V6——V76+6=12

則標(biāo)號L7=10，并描黑V5——V7

則最短路線為V1——V3——V6——V5——V7，

為10公里作業(yè)：求V1——V6最短距三、TSP問題求解算法真正解法(只能處理非常小的問題)窮舉法、分枝定限法(Branch-and-Bound)傳統(tǒng)啟發(fā)式解法(Heuristics)大致可歸納為以下三種：路線構(gòu)建(routeconstruction)鄰點(diǎn)法、節(jié)省法、插入法、掃瞄法….路線改善(routeimprovement)k-Opt交換法、Or-Opt交換法……綜合型(composite)合并執(zhí)行路線構(gòu)建及路線改善最近鄰點(diǎn)法(Nearest-neighborHeuristic)任選一節(jié)點(diǎn)為起點(diǎn)x尋找距離節(jié)點(diǎn)x最近的節(jié)點(diǎn)y作為下一個(gè)造訪的節(jié)點(diǎn)尋找距離節(jié)點(diǎn)y最近的節(jié)點(diǎn)z作為下一個(gè)造訪的節(jié)點(diǎn)重復(fù)以上步驟，直到所有節(jié)點(diǎn)均已造訪連接最后一個(gè)節(jié)點(diǎn)與起點(diǎn)，即形成一個(gè)TSP的可行解最近鄰點(diǎn)法14235743875534814235123451－473824－755377－344353－858548－插入法(InsertionMethod)任選一節(jié)點(diǎn)為起點(diǎn)a尋找距離節(jié)點(diǎn)a最近的節(jié)點(diǎn)b作為下一個(gè)造訪的節(jié)點(diǎn)，形成a-b-a的子回路尋找距離子回路最近的節(jié)點(diǎn)k作為下一個(gè)插入點(diǎn)尋找插入成本最小的位置(i-j)，將k插入i-j之間，形成新的子回路。?插入成本：Cik+Ckj-Cij重復(fù)步驟3~4，直到所有節(jié)點(diǎn)均已插入回路之中，即形成一個(gè)TSP的可行解插入法14235743875534814141333373337317224525727421455885845455582145542-opt交換法先構(gòu)建一個(gè)起始可行解在可行解中任選兩個(gè)不相鄰的節(jié)線(a?b,c?d)，以及另外兩條對應(yīng)之替換節(jié)線(a?c,b?d)，計(jì)算替換后總成本是否降低(即檢查替換成本是否小于0)。?替換成本：Cac+Cbd-Cab-Ccd(對稱型TSP)若替換后總成本有降低，則予以替換，同時(shí)變更中間相關(guān)弧線的行走方向重復(fù)步驟2~3，直到所有可能的替換均無法再降低成本為止2-opt交換法142357438755348TSP問題求解算法傳統(tǒng)啟發(fā)式解法(Heuristics)只在目標(biāo)值有改善時(shí)才進(jìn)行交換，常會陷入局部最佳解，而無法進(jìn)一步找到更好的解宏啟發(fā)式方法(Meta-heuristics)則以傳統(tǒng)的啟發(fā)式解法為基礎(chǔ)，并根據(jù)一些高階的搜尋策略指導(dǎo)下層的啟發(fā)式方法，以避免陷入局部最佳解TSP問題求解算法常見之宏啟發(fā)式方法(Meta-heuristics)禁制搜尋法(TabuSearch,TS)基因算法(GeneticAlgorithm,GA)模擬退火法(SimulatedAnnealing,SA)門坎接受法(ThresholdAccepting,TA)類神經(jīng)網(wǎng)絡(luò)(NeuralNetwork,NN)蟻群算法(AntColonyOptimization,ACO)其它（一）節(jié)約法的基本規(guī)定

利用里程節(jié)約法確定配送路線的主要出發(fā)點(diǎn)是，根據(jù)配送方的運(yùn)輸能力及其到客戶之間的距離和各客戶之間的相對距離來制定使配送車輛總的周轉(zhuǎn)量達(dá)到或接近最小的配送方案。（二）節(jié)約法的基本思想方案a）的配送路線為p0→pi→p0→pj→p0,配送距離為da=d0i+d0j方案b)配送路線p0→pi→pj→p0,配送距離為db=.d0i+d0j+dij顯然，da不等于db，我們用sij表示里程節(jié)約量，即方案b)比方案a)節(jié)約的配送里程：四、節(jié)約里程的線路設(shè)計(jì)案例分析例：某一配送中心p0向10個(gè)客戶pj(j=1,2,…,10)配送貨物，其配送網(wǎng)絡(luò)如圖11-9所示。圖中括號內(nèi)的數(shù)字表示客戶的需求量（T），線路上的數(shù)字表示兩節(jié)點(diǎn)之間的距離。配送中心有2t和4t兩種車輛可供使用，試制定最優(yōu)的配送方案。第一步：計(jì)算最短距離。根據(jù)配送網(wǎng)絡(luò)中的已知條件，計(jì)算配送中心與客戶及客戶之間的最短距離，結(jié)果見表11-11。第二步：計(jì)算節(jié)約里程sij,結(jié)果見表11-12。第三步：將節(jié)約sij,進(jìn)行分類，按從大到小的順序排列，得表11-13第四步：確定物流線路。從分類表中，按節(jié)約里程大小順序，組成線路圖（1）初始方案：對每一客戶分別單獨(dú)派車送貨，結(jié)果如圖11-10。

修正方案4

（二）步驟例：下圖所示為某配送中心的配送網(wǎng)絡(luò)，圖中P點(diǎn)為配送中心，A——J為配送客戶共10位客戶，括號內(nèi)為配送貨物噸數(shù)，線路上的數(shù)字為道路距離，單位為公里。步驟1：計(jì)算網(wǎng)絡(luò)結(jié)點(diǎn)之間的最短距。步驟2：計(jì)算各客戶之間的可節(jié)約的運(yùn)行距離：a+b+c

其中a為P點(diǎn)至各點(diǎn)距b為P點(diǎn)至各點(diǎn)距c為兩點(diǎn)間最小距步驟3：對節(jié)約里程按大小順序進(jìn)行排列。步驟4：組成配送路線圖假定本配送企業(yè)有額定載重量分別為2噸和4噸的貨車，每車每次運(yùn)行距離不超過30公里。1．初始方案：行程148公里，需要2噸車10輛。2．二次解：連接AB、AJ、BC，同時(shí)連接PA、PJ，則里程為7+4+4+5+7=27KM0.6+0.7+1.5+0.8=3.6噸，需4噸車一輛；3．三次解：連接DE、EF、FG，同時(shí)連接PD、PG，則里程為8+6+7+6+3=30KM0.4+1.4+1.5+0.6=3.91噸，需4噸車一輛；4．四次解：連接HI，同時(shí)連接PI、PH，則里程為4+9+10=23KM0.8+0.5=1.3噸，需2噸車一輛。則共行駛27+30+23=80KM，共需4噸車二輛，2噸車一輛，比初始方案節(jié)約里程148—80=68KM作業(yè)：求節(jié)約里程的線路設(shè)計(jì)，假定該公司有2T和4T車，每次運(yùn)行距離不超過60KM。五．掃描法路線設(shè)計(jì)中的掃描法很簡單，即使問題規(guī)模很大，也可以通過手工計(jì)算得出結(jié)果。掃描法可闡述如下：（1）在地圖或方格圖中確定所有站點(diǎn)（含倉庫）的位置。（2）自倉庫始沿任一方向向外劃一條直線。沿順時(shí)針或逆時(shí)針方向旋轉(zhuǎn)該直線直到與某站點(diǎn)相交?？紤]：如果在某線路上增加該站點(diǎn)，是否會超過車輛的載貨能力？如果沒有，繼續(xù)旋轉(zhuǎn)直線，直到與下一個(gè)站點(diǎn)相交。再次計(jì)算累計(jì)貨運(yùn)量是否超過車輛的運(yùn)載能力（先使用最大的車輛）。如果超過，就剔除最后的那個(gè)站點(diǎn)，并確定路線。隨后，從不包含在上一條路線中的站點(diǎn)開始，繼續(xù)旋轉(zhuǎn)直線以尋找新路線。繼續(xù)該過程直到所有的站點(diǎn)都被安排到路線中。（3）排定各路線上每個(gè)站點(diǎn)的順序使行車距離最短。排序時(shí)可以使用“水滴”法或求解“流動推銷員”問題的任何算法。例6.4某公司用廂式貨車從貨主處補(bǔ)貨，圖6-4(a)是一天的取貨量，單位是件。廂式貨車的載貨量是10000件。完成所有取貨任務(wù)需一天時(shí)間。公司需要多少條運(yùn)輸路線（即多少部車），每條路線上應(yīng)該經(jīng)過哪些站點(diǎn)，每條路線上的站點(diǎn)怎樣排序。首先，向北畫一條直線，進(jìn)行逆時(shí)針方向“掃描”。這些都是隨機(jī)決定的。逆時(shí)針旋轉(zhuǎn)該直線，直到裝載的貨物能裝上一輛載重10000件的卡車，同時(shí)又不超載。一旦所有的站點(diǎn)都分派有車輛，就可以利用“水滴”法安排經(jīng)過各站點(diǎn)的順序，圖6-4(b)是所列出的最終的路線設(shè)計(jì)。(a)(b)圖6-4掃描法設(shè)計(jì)行車路線六、表上作業(yè)法（一）原理前提：供需平衡，總運(yùn)費(fèi)最小?？傔\(yùn)費(fèi)=運(yùn)量×單位運(yùn)價(jià)（已經(jīng)考慮距離）（二）步驟1．給定初始方案——最小元素法運(yùn)價(jià)最小優(yōu)先供應(yīng)得出下表初始基本可行解為總運(yùn)費(fèi)：4×3+3×10+3×1+1×2+6×4+3×5=86百元2．最優(yōu)解的判別——位勢法（1）造初始方案運(yùn)價(jià)表（黑體）初始方案運(yùn)價(jià)表初始方案運(yùn)量表

（2）作位勢法（見上圖紅、黑體表），UI+VJ=單位運(yùn)價(jià)第三列：U1+V3=30+V3=3則V3=3第四列：U1+V4=100+V4=10，則V4=10第三列：V3+U2=23+U2=2，則U2=-1第四列：V4+U3=510+U3=5則U3=-5第一列：U2+V1=1-1+V1=1，則V1=2第二列：U3+V2=4-5+V2=4則V2=9（3）行列勢+列位勢=單位運(yùn)價(jià)，將運(yùn)價(jià)填入空格（見蘭體