【正文】 倉儲與配送管理 天津工業(yè)大學(xué)管理學(xué)院 第十章 配送的組織與管理 ?制定配送計劃的方法 ?配送路線的制定方法 ?配送的經(jīng)營管理與質(zhì)量管理 TSP問題 TSP問題（ Travelling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題 .假設(shè)有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。 ? 制定配送計劃的方法 TSP與 VRP 中國郵遞員問題（ Chinese Postman Problem CPP） 在中國還有另一個描述方法：一個郵遞員從郵局出發(fā)，到所轄街道投遞郵件，最后返回郵局，如果他必須走遍所轄的每條街道至少一次，那么他應(yīng)如何選擇投遞路線，使所走的路程最短？這個描述之所以稱為中國郵遞員問題， 因為是我國學(xué)者管梅古谷教授于 1962年提出的這個問題并且給出了一個解法。 配送路線問題（ Route of Distribution） TSP問題在物流中的描述是對應(yīng)一個物流配送公司，欲將 n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。 TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨于無窮大的復(fù)雜解的空間，搜索空間是n個點的所有排列的集合，大小為（ n1）！?？梢孕蜗蟮匕呀饪臻g看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解 TSP，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程。 多回路運輸問題（ Vehicle Routing Problem, VRP） 回路運輸問題在物流中的解釋是對一系列客戶的需求點設(shè)計適當?shù)穆肪€，使車輛有序地通過它們，在滿足一定的約束條件下，如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛載重量限制、行駛里程限制、時間限制等等，達到一定的優(yōu)化目標，如里程最短、費用最少、時間最短，車隊規(guī)模最少、車輛利用率高。 VRP問題和 TSP問題的區(qū)別在于：客戶群體的數(shù)量大，只有一輛車或一條路徑滿足不了客戶的需求，必須是多輛交通工具以及運輸工具的行車順序兩個問題的求解。相對于 TSP問題， VRP問題更復(fù)雜，求解更困難，但也更接近實際情況。 ? 最近鄰點法（ Nearest Neighbor） 這是一種用于解決 TSP問題的啟發(fā)式算法。方法簡單，但得到的解并不十分理想，可以作為進一步優(yōu)化的初始解。求解的過程一共四步：首先從零點開始，作為整個回路的起點，然后找到離剛剛加入到回路的上一節(jié)點最近的一個節(jié)點，并將其加入到回路中。重復(fù)上一步，直到所有的節(jié)點都加入到回路中，最后，將最后一個加入的節(jié)點和起點連接起來，構(gòu)成了一個 TSP問題的解。 最近插入法（ Nearest Insertion） 最近插入法是另一個 TSP問題的求解方法。它的求解過程也是 4步：首先從一個節(jié)點出發(fā)，找到一個最近的節(jié)點，形成一個往返式子回路；在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點，再在子回路中找到一個弧，使弧的兩端節(jié)點到剛尋找到的最近節(jié)點的距離之和減去弧長的值最小，實際上就是把新找到的節(jié)點加入子回路以后使得增加的路程最短，就把這個節(jié)點增加到子回路中。重復(fù)以上過程，直到所有的節(jié)點都加入到子回路中。最近插入法比最近鄰點法復(fù)雜，但可以得到相對比較滿意的解。 節(jié)約里程法（ Saving Algorithm） 節(jié)約算法是用來解決運輸車輛數(shù)目不確定的 VRP問題的最有名的啟發(fā)式算法。它的核心思想是依次將運輸問題中的兩個回路合并為一個回路，每次使合并后的總運輸距離減小得幅度最大，直到達到一輛車的裝載限制時，再進行下一輛車的優(yōu)化。優(yōu)化過程分為并行方式和串行方式兩種。 配送路線的確定方法 ? 配送路線與車輛調(diào)度 一：配送路線確定原則：成本低、效益高、路線短、噸公里小、勞動耗少、運力運用合理等。 二：配送路線確定的限制條件：用戶對貨物品種、規(guī)格、路量的要求，滿足用戶對貨物發(fā)到時間的要求，在允許通行時間內(nèi)進行配送，車輛載重量和容積的限制，配送能力等。 三：配送路線的確定方法 (一）中國郵遞員問題（ TSP） 利用歐拉圖和歐拉回路求解。 歐拉回路：連通圖 G中，若存在一條回路，經(jīng)過每邊一次且僅一次，稱這條回路為歐拉回路，具有歐拉回路的圖為歐拉圖。而且，連通圖 G為歐拉圖的充要條件是圖中所有點全為偶點。 七橋問題 Seven Bridges Problem ? 18世紀著名古典數(shù)學(xué)問題之一。在哥尼斯堡的一個公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€島以及島與河岸連接起來 (如圖 )。問是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每座橋一次，再回到起點？ 普萊格爾河 ? 歐拉于 1736年研究并解決了此問題， 他用點表示島和陸地，兩點之間的連線表示連接它們的橋，將河流、小島和橋簡化為一個網(wǎng)絡(luò)，把七橋問題化成判斷連通網(wǎng)絡(luò)能否 一筆畫 的問題。之后他發(fā)表一篇論文，證明了上述走法是不可能的。并且給出了連通網(wǎng)絡(luò)可一筆畫的充要條件這一著名的結(jié)論。 用 A、 B表示兩座小島， C、 D表示兩岸， 連線 AB表示 A、 B之間有一座橋。 ?A ? B ?C ?D 在該圖中，從任一點出發(fā)，能否通過每條線段一次且僅僅一次后又回到原來的出發(fā)點 b c a 圖 1 v2 v3 v1 v4 圖 2 ? 圖 1和圖 2當中哪一個圖滿足： 從圖中任何一點出發(fā)，途徑每條邊，最終還能回到出發(fā)點？ ? 由此試想一下：一個圖應(yīng)該滿足什么條件才能達到上面要求呢？ 一筆畫問題： 從某一點開始畫畫，筆不離紙，各條線路僅畫一次，最后回到原來的出發(fā)點。 類似的問題：一筆畫問題 字的一筆畫：如“中、日、口、串”等可一筆畫 而：“田、目”等不能一筆畫 圖的一筆畫： 可一筆畫 不可一筆畫 田 日 中 白 回 不連通 可一筆畫 可一筆畫 不可一筆畫 可一筆畫 可一筆畫 不可一筆畫 不可一筆畫 一筆畫問題 ? 凡是能一筆畫出的圖，奇點的個數(shù)最多有 兩個 。始點與終點 重合 的一筆畫問題，奇點的個數(shù)必是 0。 ? 在一個多重邊的連通圖中，從某個頂點出發(fā)，經(jīng)過不同的線路，又回到原出發(fā)點，這樣的線路必是 歐拉圖 ，即 能一筆畫出的圖必是歐拉圖。 中國郵遞員問題 ? 一個郵遞員送信，要走完他負責(zé)投遞的全部街道，投完后回到郵局，應(yīng)該怎樣走，使所走的路程最短？ ? 這個問題是我國管梅谷同志 1962年首先求出來的，因此在國際上通稱為中國郵遞員問題。在物流活動中，經(jīng)常會遇到這樣的問題，如：每天在大街小巷行駛的垃圾車、灑水車、各售貨點的送貨車等都需要解決一個行走的最短路程問題。 ? 這個問題就是一筆畫問題。 郵路問題的圖論描述： 取一無向賦權(quán)連通圖 G=（ V， E） E中的每一條邊對應(yīng)一條街道 每條邊的非負權(quán) l(e)=街道的長度 V中某一個頂點為郵局，其余為街道的交叉點 若 G中的頂點均為偶點 ，即 G中存在歐拉回路， 則該回路過每條邊一次且僅一次， 此回路即為所求的投遞路線 郵路問題的圖論描述： 在無向連通賦權(quán) G =（ V， E）上找一個圈， 該圈過每邊至少一次，且圈上所有邊的權(quán)和最小 G中有奇點： 不存在歐拉回路 投遞路線：至少有一街道要重復(fù)走一次或多次 為郵局為郵路圖，其中例：設(shè) 1vG不是歐拉圖為奇數(shù) Gvdvd ,)(),( 43?不存在歐拉回路，G?即不存在每條街道走一次且只走一次的投遞路線 14253214563211 vvvvvvvvvvvvvC ：路線 12?權(quán)和1232563542412 vvvvvvvvvvvvC ：路線 11?權(quán)和12 CC 優(yōu)于路線路線分析： ），），（，），（，重復(fù)走過邊：（路線 4132211 vvvvvvC），），（，重復(fù)走過邊：（路線 32422 vvvvC重復(fù)邊 2?重復(fù)邊的權(quán)和結(jié)論： 選擇最佳投遞路線 =選擇重復(fù)邊的權(quán)和最小的路線 3?重復(fù)邊的權(quán)和????1v 2v 3v4v 5v 6v? ?1 1 1 1 1 1 1 1 1 ????1v 2v 3v4v 5v 6v? ?1 1 1 1 1 1 1 1 1 14253214563211 vvvvvvvvvvvvvC ：對路線），），（，），（，重復(fù)邊：（ 413221 vvvvvv1G為歐拉圖，1G 的一條歐拉回路為且 11 GC1232563542412 vvvvvvvvvvvvC ：對路線），），（，重復(fù)邊：（ 3242 vvvv????1v 2v 3v4v 5v 6v? ?1 1 1 1 1 1 1 1 1 2G為歐拉圖，2G 的一條歐拉回路為且 22 GC歐拉圖一條投遞路線對應(yīng)一個條歐拉回路且投遞路線為該圖的一反之，對郵路圖 G， 的一條鏈到任取奇點 34 vv3654 , vvvv如：對該鏈上的每一條邊增加一條重復(fù)邊 G?為歐拉圖G ? 存在歐拉回路即 G ?,CG 對應(yīng)一條投遞路線即 ?????1v 2v 3v4v 5v 6v? ?1 1 1 1 1 1 1 1 1 G?