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