【正文】 ?????????njQbQbjnjpj,2,111? （ 106 ） 計(jì)算過程如下： 先求初始解 。 （ 105 ） B2 B1 B0 d1,2 d0,2 d0,1 圖 10－ 3 節(jié)約法示意圖 2,12,01,02,1 ddds ???2,12,01,02 ddds ???21，S 二、 節(jié)約法的計(jì)算過程 設(shè)由配送中心 B0向用戶 Bj (j=1, 2, … , n)送貨 ， 各用戶需求量為 bj；配送中心與用戶間的最短距離為 d0,j， 用戶之間的距離為 di,j (i=1, 2, … , n。 當(dāng)用兩臺(tái)車分別對兩個(gè)用戶各自往返送貨時(shí) ， 運(yùn)輸總距離為： ）（ 2,01,01 2 dds ??B2 B1 B0 2d0,2 2d0,1 圖 10－ 2 各用戶分別送貨 如果改用一臺(tái)車巡回送貨 （ 假定汽車能夠負(fù)荷b b2時(shí) ） ， 如圖 10－ 3， 則總運(yùn)輸距離為 后一種方案比前一種方案可節(jié)約運(yùn)輸里程 式 10— 5稱為節(jié)約量公式， 為 B1和 B2之間的節(jié)約量。 節(jié)約法是由克拉克 （ Clarke） 和懷特 （ Wright） 提出來的 ，是一種啟發(fā)式方法 。 課堂練習(xí) v 1 v 2 v 3 v 4 v 5 v 6 3 2 4 4 5 2 6 4 8 配送路線與車輛調(diào)度 單中心配送路線選擇與車輛調(diào)度 一、單中心配送的節(jié)約法原理 單中心配送 ， 是指一個(gè)配送中心向所屬 n個(gè)用戶送貨 ，各用戶的需求量為 bj(j=1,2,… ,n)。圖 5中的任一歐拉圈都是汽車的最優(yōu)配送路線。見圖 5。 第二步：調(diào)整可行方案 ? 在圖 410中，圈（ v2,v3,v4, v9,v2）的總長度為 24，但圈上重復(fù)邊總權(quán)為 14，大于該圈總長度的一半，因此可以做一次調(diào)整，以 [v2,v9]， [v9,v4]上的重復(fù)邊代[v2,v3]， [v3,v4]上的重復(fù)邊，使重復(fù)邊總長度下降為 17。見圖 3 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 4 4 4 3 4 2 3 4 6 9 5 5 圖 3 第二步：調(diào)整可行方案 ? 其次，如果把圖中某個(gè)圈上的重復(fù)邊去掉，而給原來沒有重復(fù)邊的邊上加上重復(fù)邊，圖中仍然沒有奇點(diǎn)。 想一想 ? 這樣的可行方案是不是只有一種呢？ ? 在確定一個(gè)可行方案后，怎么判斷這個(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)的一半。 ? 那么該怎樣添加重復(fù)邊，使得圖中全為偶點(diǎn)呢？ ? 其實(shí)可以通過連接匹配的奇點(diǎn)得到！ 第一步：確定初始可行方案 v1 v3 v2 v4 v8 v7 v6 v5 v9 2 5 4 3 3 9 5 4 6 4 4 4 圖 2 ? 這樣就得到初始方案 .在這個(gè)圖中，沒有奇點(diǎn)，故稱它為歐拉圖。 案例 v1 v3 v2 v4 v8 v7 v6 v5 v9 2 5 4 3 3 9 5 4 6 4 4 4 圖 1 ? 顯然街區(qū)圖上有奇點(diǎn)（ 4個(gè) ），不滿足 “ 一筆畫 ” 的條件，則必然有一些街道要被重復(fù)走過（ 添加重復(fù)邊 ）才能回到原出發(fā)點(diǎn)。計(jì)算重復(fù)邊的權(quán)和，重復(fù)邊權(quán)和最小歐拉回路既為所求的最佳投遞路線 管梅谷 —— 奇偶點(diǎn)圖上作業(yè)法 奇偶點(diǎn)圖上作業(yè)法 ： 例：求解右圖所示的郵路問題 第一步：確定一個(gè)初始可行方案 方法： 檢查圖 G中是否有奇點(diǎn) 無奇點(diǎn)： ，找出一條以 v1為 起點(diǎn)的歐拉回路 ，該回路就是最佳投遞路線 有奇點(diǎn)： 圖 G已是歐拉圖 把所有奇點(diǎn)兩兩配成一對，每對奇點(diǎn)找一條鏈，在該條鏈上的每一條邊增加一條重復(fù)邊，得一個(gè)歐拉圖 G1， 由 G1所確定的歐拉回路即為一個(gè)可行方案 v2 ， v8 ， v4 ， v6 G中有奇點(diǎn)： 取 v2到 v4的一條鏈： v2v1v6v7v8v9v4 取 v6到 v8的一條鏈： v6v1v2v3v4v9v8 )( 1為郵局vG ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 4 G1 顯然 G1不是最佳方案 G1是歐拉圖， 第二步：調(diào)整可行方案， 使重復(fù)邊權(quán)和下降 重復(fù)邊權(quán)和 = 若圖中某條邊有兩條或多于兩條的重復(fù)邊 同時(shí)去掉偶數(shù)條， G2 使圖中每一條邊最多有一條重復(fù)邊 G2的重復(fù)邊權(quán)和 = ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 步驟 可得到重復(fù)邊權(quán)和較小的歐拉圖 4 G2 ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 4 51 21 ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 G2是歐拉圖， 重復(fù)邊權(quán)和 =21 G2 4 使圖中每個(gè)初等圈重復(fù)邊的 權(quán)和不大于該圈權(quán)和的一半 9個(gè)初等圈 ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 G2 4 3 G3是歐拉圖， 重復(fù)邊權(quán)和 =17 G3 ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 4 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 ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 4 G4 ?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 4 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 ?1v√ （ 6） v2v3v4v9v8v5v2 32 4 √ （ 8） v6v5v4v9v8v7v6 （ 7） v1v2v3v4v5v6v1 28 11 √ 22 4 √ （ 9） v1v2v3v4v9v8v7v6v1 36 7 √ G4是最佳方案 最佳投遞路線：16785894561254321 vvvvvvvvvvvvvvvvv奇偶點(diǎn)圖上作業(yè)法 ： 第一步：確定一個(gè)初始可行方案 方法： 檢查圖 G中是否有奇點(diǎn)。 ? 這個(gè)問題就是一筆畫問題。 中國郵遞員問題 ? 一個(gè)郵遞員送信，要走完他負(fù)責(zé)投遞的全部街道，投完后回到郵局，應(yīng)該怎樣走，使所走的路程最短？ ? 這個(gè)問題是我國管梅谷同志 1962年首先求出來的，因此在國際上通稱為中國郵遞員問題。始點(diǎn)與終點(diǎn) 重合 的一筆畫問題，奇點(diǎn)的個(gè)數(shù)必是 0。 ?A ? B ?C ?D 在該圖中，從任一點(diǎn)出發(fā)，能否通過每條線段一次且僅僅一次后又回到原來的出發(fā)點(diǎn) b c a 圖 1 v2 v3 v1 v4 圖 2 ? 圖 1和圖 2當(dāng)中哪一個(gè)圖滿足： 從圖中任何一點(diǎn)出發(fā)，途徑每條邊，最終還能回到出發(fā)點(diǎn)？ ? 由此試想一下：一個(gè)圖應(yīng)該滿足什么條件才能達(dá)到上面要求呢？ 一筆畫問題： 從某一點(diǎn)開始畫畫，筆不離紙，