倉(cāng)儲(chǔ)與配送管理第十章.ppt

1、倉(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)是要求得的路徑路程為所有路徑之中的最小值。,10.1 制定配送計(jì)劃的方法 10.1.1 TSP與VRP,中國(guó)郵遞員問(wèn)題（Chinese Postman Problem CPP） 在中國(guó)還有另一個(gè)描述方法：一個(gè)郵遞員從郵局

2、出發(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)的所有排列的集合，大小為（n-1）！?？梢孕蜗蟮匕呀饪臻g看成是一個(gè)無(wú)窮大的丘陵地帶，各山峰或山谷的

3、高度即是問(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ò)它們，在滿足一定的約束條件下，如貨物需求量、發(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ē)或一條路徑滿足不了客戶(hù)的需求，必須是多輛交通工具以及運(yùn)輸工具的行車(chē)順序兩個(gè)問(wèn)題的求解。相對(duì)于TSP問(wèn)題，

4、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è)往返式

5、子回路；在剩下的節(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ì)比較滿意的解。,節(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)化。

6、優(yōu)化過(guò)程分為并行方式和串行方式兩種。,10.2.1 配送路線的確定方法,10.2 配送路線與車(chē)輛調(diào)度,一：配送路線確定原則：成本低、效益高、路線短、噸公里小、勞動(dòng)耗少、運(yùn)力運(yùn)用合理等。 二：配送路線確定的限制條件：用戶(hù)對(duì)貨物品種、規(guī)格、路量的要求，滿足用戶(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)題

7、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,在該圖

8、中，從任一點(diǎn)出發(fā)，能否通過(guò)每條線段一次且僅僅一次后又回到原來(lái)的出發(fā)點(diǎn),圖1和圖2當(dāng)中哪一個(gè)圖滿足：從圖中任何一點(diǎn)出發(fā)，途徑每條邊，最終還能回到出發(fā)點(diǎn)？ 由此試想一下：一個(gè)圖應(yīng)該滿足什么條件才能達(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)重合的一

9、筆畫(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(xiāng)

10、(e)=街道的長(zhǎng)度,V中某一個(gè)頂點(diǎn)為郵局，其余為街道的交叉點(diǎn),1、若G中的頂點(diǎn)均為偶點(diǎn),，即G中存在歐拉回路，,則該回路過(guò)每條邊一次且僅一次，,此回路即為所求的投遞路線,郵路問(wèn)題的圖論描述：,在無(wú)向連通賦權(quán)G =（V，E）上找一個(gè)圈，,該圈過(guò)每邊至少一次，且圈上所有邊的權(quán)和最小,2、G中有奇點(diǎn)：,不存在歐拉回路,投遞路線：至少有一街道要重復(fù)走一次或多次,即不存在每條街道走一次且只走一次的投遞路線,分析：,重復(fù)邊,結(jié)論： 選擇最佳投遞路線=選擇重復(fù)邊的權(quán)和最小的路線,反之，對(duì)郵路圖G，,對(duì)該鏈上的每一條邊增加一條重復(fù)邊,投遞路線,歐拉圖,結(jié)論：,對(duì)任意一個(gè)含奇點(diǎn)的郵路圖G，由于奇點(diǎn)的個(gè)數(shù)為偶數(shù)個(gè)

11、，把每?jī)蓚€(gè)配成一對(duì)，由于G為連通圖，每對(duì)奇點(diǎn)之間至少存在一條鏈，對(duì)該條鏈上的每一條邊增加一條重復(fù)邊，可得一歐拉圖，該歐拉圖對(duì)應(yīng)一條投遞路線,尋找最佳投遞路線方法：,在原郵路圖上增加一些重復(fù)邊得一個(gè)歐拉圖，在所得歐拉圖上找出一條歐拉回路。計(jì)算重復(fù)邊的權(quán)和，重復(fù)邊權(quán)和最小歐拉回路既為所求的最佳投遞路線,管梅谷奇偶點(diǎn)圖上作業(yè)法,奇偶點(diǎn)圖上作業(yè)法：,例：求解右圖所示的郵路問(wèn)題,第一步：確定一個(gè)初始可行方案,方法：,檢查圖G中是否有奇點(diǎn),無(wú)奇點(diǎn)：,，找出一條以v1為 起點(diǎn)的歐拉回路,，該回路就是最佳投遞路線,有奇點(diǎn)：,圖G已是歐拉圖,把所有奇點(diǎn)兩兩配成一對(duì)，每對(duì)奇點(diǎn)找一條鏈，在該條鏈上的每一條邊增加一條

12、重復(fù)邊，得一個(gè)歐拉圖G1， 由G1所確定的歐拉回路即為一個(gè)可行方案,v2,，v8,，v4,，v6,G中有奇點(diǎn)：,取v2到v4的一條鏈：,v2v1v6v7v8v9v4,取v6到v8的一條鏈：,v6v1v2v3v4v9v8,G,G1,顯然G1不是最佳方案,G1是歐拉圖，,第二步：調(diào)整可行方案， 使重復(fù)邊權(quán)和下降,重復(fù)邊權(quán)和=,若圖中某條邊有兩條或多于兩條的重復(fù)邊,同時(shí)去掉偶數(shù)條，,G2,使圖中每一條邊最多有一條重復(fù)邊,G2的重復(fù)邊權(quán)和=,步驟1、,可得到重復(fù)邊權(quán)和較小的歐拉圖,4,51,21,G2是歐拉圖，,重復(fù)邊權(quán)和=21,2、使圖中每個(gè)初等圈重復(fù)邊的 權(quán)和不大于該圈權(quán)和的一半,9個(gè)初等圈,G3

13、,G3是歐拉圖，,重復(fù)邊權(quán)和=17,G3,6,（1）v1v2v5v6v1,16,7,（2）v6v5v8v7v6,14,10,（3）v2v3v4v5v2,24,4,（4）v5v4v9v8v5,16,G3的初等圈,權(quán)和,重復(fù)邊權(quán)和,13,（5）v1v2v5v8v7v6v1,24,G4,G4,7,（1）v1v2v5v6v1,16,4,（2）v6v5v8v7v6,14,4,（3）v2v3v4v5v2,24,8,（4）v5v4v9v8v5,16,G4的初等圈,權(quán)和,重復(fù)邊權(quán)和,11,（5）v1v2v5v8v7v6v1,24,（6）v2v3v4v9v8v5v2,32,4,（8）v6v5v4v9v8v7v6

14、,（7）v1v2v3v4v5v6v1,28,11,22,4,（9）v1v2v3v4v9v8v7v6v1,36,7,G4是最佳方案,奇偶點(diǎn)圖上作業(yè)法：,第一步：確定一個(gè)初始可行方案,方法：,檢查圖G中是否有奇點(diǎn)。,無(wú)奇點(diǎn)：,，找出一條以v0為起點(diǎn)的,歐拉回路，該回路就是最佳投遞路線,有奇點(diǎn)：,圖G已是歐拉圖,把所有奇點(diǎn)兩兩配成一對(duì)，每對(duì)奇點(diǎn)找一條鏈，在該條鏈上的每一條邊增加一條重復(fù)邊,第二步：調(diào)整可行方案，使重復(fù)邊權(quán)和下降,1、使圖中每一條邊最多有一條重復(fù)邊,若圖中某條邊有兩條或多于兩條的重復(fù)邊， 同時(shí)去掉偶數(shù)條,2、使圖中每個(gè)初等圈重復(fù)邊的權(quán)和該圈權(quán)和的一半,若圖中某初等圈重復(fù)邊的權(quán)和大于該圈

15、權(quán)和的一半,去掉圈中的重復(fù)邊同時(shí)將圈中沒(méi)有重復(fù)邊的邊加上重復(fù)邊,車(chē)輛從某配送中心（v1）出發(fā)，給街道邊上的超市（v2,v3,v4,v5,v6,v7,v8,v9）送貨，如圖4-8所示。,案例,顯然街區(qū)圖上有奇點(diǎn)（4個(gè)），不滿足“一筆畫(huà)”的條件，則必然有一些街道要被重復(fù)走過(guò)（添加重復(fù)邊）才能回到原出發(fā)點(diǎn)。此時(shí)得到的圖就無(wú)奇點(diǎn)。 那么該怎樣添加重復(fù)邊，使得圖中全為偶點(diǎn)呢？ 其實(shí)可以通過(guò)連接匹配的奇點(diǎn)得到！,第一步：確定初始可行方案,這樣就得到初始方案.在這個(gè)圖中，沒(méi)有奇點(diǎn)，故稱(chēng)它為歐拉圖。對(duì)應(yīng)于這個(gè)可行方案，重復(fù)邊總權(quán)為51。,想一想,這樣的可行方案是不是只有一種呢？ 在確定一個(gè)可行方案后，怎么判斷

16、這個(gè)方案是否為最優(yōu)方案？ 若不是最優(yōu)方案，如何調(diào)整這個(gè)方案？,第二步：調(diào)整可行方案,最優(yōu)方案必須滿足以下（1）（2）兩個(gè)條件： （1）在最優(yōu)方案中,圖的每一邊最多有一條重復(fù)邊 （2）在最優(yōu)方案中,圖中每個(gè)圈上的重復(fù)邊的總權(quán)不大于該圈總權(quán)的一半。 為什么?,第二步：調(diào)整可行方案,首先，去掉多余的重復(fù)邊，使圖中每一邊最多有一條重復(fù)邊。見(jiàn)圖3,圖3,第二步：調(diào)整可行方案,其次，如果把圖中某個(gè)圈上的重復(fù)邊去掉，而給原來(lái)沒(méi)有重復(fù)邊的邊上加上重復(fù)邊，圖中仍然沒(méi)有奇點(diǎn)。因而如果在某個(gè)圈上重復(fù)邊的總權(quán)數(shù)大于這個(gè)圈的總權(quán)數(shù)的一半，像上面所說(shuō)的那樣做一次調(diào)整，將會(huì)得到一個(gè)總權(quán)下降的可行方案。,第二步：調(diào)整可行方案

17、,在圖4-10中，圈（v2,v3,v4, v9,v2）的總長(zhǎng)度為24，但圈上重復(fù)邊總權(quán)為14，大于該圈總長(zhǎng)度的一半，因此可以做一次調(diào)整，以v2,v9，v9,v4上的重復(fù)邊代v2,v3，v3,v4上的重復(fù)邊，使重復(fù)邊總長(zhǎng)度下降為17。見(jiàn)圖4,圖4,檢查圖4中圈（v1,v2, v9, v6,v7, v8,v1）的總長(zhǎng)度為24，但圈上重復(fù)邊總權(quán)為13，大于該圈總長(zhǎng)度的一半，因此可以做一次調(diào)整，使重復(fù)邊總長(zhǎng)度下降為15。見(jiàn)圖5。,圖5,檢查圖5，均滿足條件（1）和（2），于是得到最優(yōu)方案。圖5中的任一歐拉圈都是汽車(chē)的最優(yōu)配送路線。 如：v1-v2-v9-v8-v1-v8-v7-v6-v5-v4-v9-

18、v6-v9-v4-v3-v2-v1是汽車(chē)的一條最優(yōu)配送路線。,課堂練習(xí),10.2 配送路線與車(chē)輛調(diào)度,單中心配送路線選擇與車(chē)輛調(diào)度,一、單中心配送的節(jié)約法原理 單中心配送，是指一個(gè)配送中心向所屬n個(gè)用戶(hù)送貨，各用戶(hù)的需求量為bj(j=1,2,n)。假定以汽車(chē)作為配送車(chē)輛，配送車(chē)按其載重量的大小不同有p種，載重量為QK(K=1,2p)的發(fā)送車(chē)有xK臺(tái),QK-1QK,且 （61） 解決這類(lèi)配送問(wèn)題的一種有效方法節(jié)約法。節(jié)約法是由克拉克（Clarke）和懷特（Wright）提出來(lái)的，是一種啟發(fā)式方法。,節(jié)約法的基本原理,如圖102，由物流網(wǎng)點(diǎn)B0向兩個(gè)用戶(hù)B1、B2送貨，B0至各用戶(hù)的最短運(yùn)輸距離分

19、別為d0,1和d0,2；用戶(hù)需求量各為b1，b2；兩用戶(hù)之間的最短運(yùn)輸距離為d1,2。當(dāng)用兩臺(tái)車(chē)分別對(duì)兩個(gè)用戶(hù)各自往返送貨時(shí)，運(yùn)輸總距離為：,圖102 各用戶(hù)分別送貨,如果改用一臺(tái)車(chē)巡回送貨（假定汽車(chē)能夠負(fù)荷b1、b2時(shí)），如圖103，則總運(yùn)輸距離為 后一種方案比前一種方案可節(jié)約運(yùn)輸里程 式105稱(chēng)為節(jié)約量公式， 為B1和B2之間的節(jié)約量。 顯然，將節(jié)約量大的兩個(gè)用戶(hù) 連接起來(lái)采用巡回方式送貨， 則可獲得較大的節(jié)約。,（10-5）,圖103 節(jié)約法示意圖,二、節(jié)約法的計(jì)算過(guò)程,設(shè)由配送中心B0向用戶(hù)Bj (j=1, 2, , n)送貨，各用戶(hù)需求量為bj；配送中心與用戶(hù)間的最短距離為d0,j，

20、用戶(hù)之間的距離為di,j (i=1, 2, , n; j=1, 2, , n)；配送車(chē)按其載重量的大小不同有p種，載重量為QK(K=1,2p)的發(fā)送車(chē)有xK臺(tái)，QK-1QK。 假定：,（10-6）,計(jì)算過(guò)程如下：,先求初始解。 假定載重量最小的汽車(chē)臺(tái)數(shù)是無(wú)限多的，即x1=。對(duì)每一用戶(hù)各派一臺(tái)最小的車(chē)往返送貨，得一初始可行方案。顯然這一方案的運(yùn)輸效率是很低的，而且x1=的假設(shè)實(shí)際也不存在。,然后迭代求滿意解。 計(jì)算每?jī)蓚€(gè)用戶(hù)之間的節(jié)約量，按節(jié)約法原理對(duì)方案進(jìn)行修正。修正時(shí)，以節(jié)約量的大小為順序，從大到小依次將節(jié)約量大的用戶(hù)連接到巡回路線中，并考慮汽車(chē)載重量和各種車(chē)輛臺(tái)數(shù)的約束。反復(fù)進(jìn)行這樣的修正

21、，直至再?zèng)]有可連接的用戶(hù)時(shí)為止。 整個(gè)計(jì)算過(guò)程可在節(jié)約量表上進(jìn)行。 下面用例子說(shuō)明計(jì)算過(guò)程。,例：由配送中心B0向12個(gè)用戶(hù)Bj (j=1,2,12)送貨，各點(diǎn)之間的運(yùn)輸里程和各用戶(hù)的需求量見(jiàn)表10-1。表10-2為可供調(diào)度的車(chē)輛數(shù)目及其載重量。,表10-1 各點(diǎn)之間里程表（單位：公里） 表10-2 可供調(diào)度的汽車(chē),解：由表10-1中的數(shù)據(jù)，按節(jié)約量公式（10-5）計(jì)算每?jī)捎脩?hù)之間的節(jié)約量Si,j 列于表10-3，稱(chēng)節(jié)約量表。,表6-3 節(jié)約量表（單位：公里）,如:S1,2d0,1+d0,2d1,2 9145 18,S2,4d0,2+d0,4d2,4 142317 20,設(shè)ti,j(i=0,1

22、,12; j=1,2,12；ij )表示i、j兩點(diǎn)是否連接在一起的決策變量，并對(duì)其取值作如下定義： ti,j=1 表示i、j用戶(hù)連接，即在同一巡回路線中； ti,j=0 表示i、j用戶(hù)不連接，即不在同一巡回路線中； t0,j=2 表示j用戶(hù)只與配送中心B。連接，由一臺(tái)車(chē)單獨(dú)送貨。 根據(jù)以上定義，對(duì)任一用戶(hù)j,有以下等式成立：,j=1, , n （6-7）,迭代求解：,第一步，求初始解 每用戶(hù)各派一臺(tái)車(chē)單獨(dú)送貨，得初始方案如表104。表中B0列中的數(shù)字為ti,j的取值。此方案的總行程為728公里。 按表104的初始方案，所用汽車(chē)臺(tái)數(shù)如表105所列。,表10-4 初始方案 表105 初始方案所用汽

23、車(chē)臺(tái)數(shù),第二步，按下述條件在初始方案表中尋找具有最大節(jié)約量的用戶(hù)i、j,（1）t0,i、t0,j0ij； （2）Bi、Bj尚未連接在一條巡回路線中； （3）考慮車(chē)輛臺(tái)數(shù)和載重量的約束。 如果最大節(jié)約量有兩個(gè)或兩個(gè)以上相同時(shí)，可隨機(jī)取一個(gè)。 按此條件，在初始方案表104中尋到具有最大節(jié)約量的一對(duì)用戶(hù)為：i=11,j=12，其節(jié)約量為92公里。將11和12兩用戶(hù)連接到一個(gè)運(yùn)輸回路中，并在對(duì)應(yīng)的格中記上t11,12的值，用“1）”表示。,第三步，按ti,j的定義和公式107修正ti,j的值。,B11與B12連接，即令t11,12=1，由公式107得： t0,11=1 t0,12=1 其他不變。,第四

24、步，按以下原則修正bi、bj,（1）t0,i或t0,j等于0時(shí)，令bi或bj等于0； （2）t0,i或t0,j等于1時(shí)，令bi或bj等于所在巡回路線中所有用戶(hù)需求量之和，以此代替原bi或bj,因此 b11=b12=1.1+1.7=2.8（噸） 得改進(jìn)方案（表10-6、表10-7）。 改進(jìn)后的方案比原方案少一臺(tái)發(fā)送車(chē)，總發(fā)送距離減少92公里。,表6-6 第一次迭代方案 表6-7 該方案所用汽車(chē)臺(tái)數(shù),重復(fù)第二步，按下述條件在第一次迭代方案表66中尋找具有最大節(jié)約量的用戶(hù)i、j,（1）t0i、t0j0ij； （2）Bi、Bj尚未連接在一條巡回路線上； （3）考慮車(chē)輛臺(tái)數(shù)和載重量的約束。 如果最大節(jié)約

25、量有兩個(gè)或兩個(gè)以上相同時(shí)，可隨機(jī)取一個(gè)。 按此條件，在表66中尋得具有最大節(jié)約量的用戶(hù)有兩對(duì)，分別為：i=10,j=11和i=10,j=12 ，其節(jié)約量均為84公里，任取一對(duì)i=10, j=11，將其連接到一個(gè)回路中。,重復(fù)第三步，按ti,j的定義和公式67修正ti,j的值。,B10與B11連接，則t10,11=1，由公式67得： t0,11=0 t0,10=1 其他不變。,重復(fù)第四步，按以下原則修正bi、bj,（1）t0,i或t0,j等于0時(shí)，令bi或bj等于0； （2）t0,i或t0,j等于1時(shí)，令bi或bj等于所在巡回路線中所有用戶(hù)需求量之和，以此代替原bi或bj,因此 b10=b12=

26、2.81.6=4.4（噸） b11=0 得第二次迭代方案（表6-8、表6-9）。 第二次迭代方案比第一次迭代方案又少一臺(tái)配送車(chē)，只需10臺(tái)，其中一臺(tái)為5噸車(chē)；總發(fā)送距離比前一方案減少84公里。,表6-8 第二次迭代方案 表6-9 該方案所用汽車(chē)臺(tái)數(shù),表6-10 第三次迭代方案 表6-11 該方案所用汽車(chē)臺(tái)數(shù),為什么不選B10B9、B10B8？,可否將B11與B7連接？,得到第一條配送路線：B0B7B10B11B12B0，行程112公里，用6噸車(chē)配送，載重5.6噸； 開(kāi)始下一條配送路線的選擇，過(guò)程如何？,表6-12 第四次迭代方案 表6-13 該方案所用汽車(chē)臺(tái)數(shù),表6-14 第五次迭代方案 表6

27、-15 該方案所用汽車(chē)臺(tái)數(shù),得到二條配送路線：B0B6B8B9B0，行程80公里，用6噸車(chē)配送，載重5.1噸； 再開(kāi)始下一條配送路線的選擇，過(guò)程與前相同。,反復(fù)進(jìn)行第二第四步，直至沒(méi)有可連接的用戶(hù)時(shí)為止，得最終滿意配送方案如表6-16，表6-17。 表6-16 滿意配送方案 表6-17 最終方案所用汽車(chē)臺(tái)數(shù),滿意配送方案有四條配送路線，它們是：,B0B7B10B11B12B0，行程112公里，用6噸車(chē)配送，載重5.6噸； B0B6B8B9B0，行程80公里，用6噸車(chē)配送，載重5.1噸； B0B5B0，行程44公里，用4噸車(chē)配送，載重1.7噸； B0B1B2B3B4B0，行程54公里，用6噸車(chē)配送，載重5.8噸； 滿意方案共用四臺(tái)車(chē)配送，總行程290公里。,第三節(jié) 多中心配送路線選擇與車(chē)輛調(diào)度,一、制定多中心配送方案的基本思想 多中心配送與單中心配送不同的是，制定配送計(jì)劃時(shí)，不僅要選擇配送路線和調(diào)度車(chē)輛，還要確定各配送中心所服務(wù)的用戶(hù)對(duì)象。 所以，制定多中心配送的配送計(jì)劃，首先將所有用戶(hù)按一定的方法分派給各配送中心，形成每個(gè)配送中心的服務(wù)區(qū)，然后用上一節(jié)討論的節(jié)約法在各配送中心的服務(wù)區(qū)選擇配送路線和調(diào)度車(chē)輛。,10.3 配送的質(zhì)量管理,10.3.1 配送服務(wù)概述,一、配送服務(wù)的含義和要素 （一）配送服務(wù)的含義 配送服務(wù)就是物流配送過(guò)程中為滿足客戶(hù)需求所實(shí)施的一系列配送活動(dòng)過(guò)程及