選擇運(yùn)輸線路起止點(diǎn)不同的單一問題：最短路徑法多起點(diǎn)問題：表上作業(yè)法圖上作業(yè)法節(jié)約里程法選擇運(yùn)輸線路起止點(diǎn)不同的單一問題：最短路徑法1最短路徑法練習(xí)AFEDCB50409080405030最短路徑法練習(xí)AFEDCB504090804050302

表上作業(yè)法是單純形法在求解運(yùn)輸問題的一種簡(jiǎn)化方法，尋求運(yùn)費(fèi)最少的調(diào)運(yùn)方案。解題思路是：

首先依據(jù)已知問題列出貨物的供需平衡表及運(yùn)價(jià)表；然后使用左上角法或者最小元素法或伏格爾法確定初始的調(diào)運(yùn)方案；最后根據(jù)一個(gè)判定法則判斷初始方案是不是最優(yōu)方案，如果不是最優(yōu)方案，要借助調(diào)出變量調(diào)整調(diào)配方案，再判斷，直到判定為最優(yōu)方案為止。表上作業(yè)法是單純形法在求解運(yùn)輸問題的一種簡(jiǎn)化方法3初始方案容易找

利用左上角法尋找初始方案，基本思路從運(yùn)價(jià)表元素中左上角的元素開始，集中供應(yīng)，依次安排調(diào)運(yùn)量，直到得到一個(gè)可行方案。

利用最小元素法尋找初始方案，基本思路就近運(yùn)輸，也就是從運(yùn)價(jià)表中找到最小的運(yùn)價(jià)，優(yōu)先滿足運(yùn)價(jià)最小的調(diào)運(yùn)，然后在剩下的供需狀態(tài)中，尋找次小的運(yùn)價(jià)，滿足此供需路徑，再重復(fù)尋找剩下的最小的運(yùn)價(jià)給與滿足，直到給出初始方案為止。這種方法找到的方案，雖然每次都找的是運(yùn)價(jià)最低的路徑優(yōu)先調(diào)運(yùn)，但為了節(jié)省一個(gè)節(jié)點(diǎn)的費(fèi)用，有時(shí)會(huì)造成其他節(jié)點(diǎn)費(fèi)用的大幅增加，所以進(jìn)行判定最優(yōu)解時(shí)，會(huì)比較麻煩。初始方案容易找4伏格爾法，一個(gè)調(diào)運(yùn)地如果不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有了一個(gè)差額，差額越大，說明不按最小運(yùn)費(fèi)供應(yīng)，越不合理，運(yùn)費(fèi)增加越多，所以應(yīng)優(yōu)先采用最小運(yùn)費(fèi)調(diào)運(yùn)。伏格爾法，一個(gè)調(diào)運(yùn)地如果不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)5例3-1某公司有3個(gè)倉庫，分別是A、B、C，供應(yīng)量分別是7噸、4噸、9噸，每天向4個(gè)配送中心送貨，分別是甲、乙、丙、丁，需求量分別是10噸，3噸、2噸和5噸。單位運(yùn)價(jià)表如圖7-2所示，請(qǐng)確定初始可行方案。

單位運(yùn)價(jià)表單位：元/噸銷地產(chǎn)地甲乙丙丁A2376B1326C3548例3-1某公司有3個(gè)倉庫，分別是A、B、C，供應(yīng)量分別是76解：第一步建立貨物的供需平衡表及運(yùn)價(jià)表如表所示。平衡表銷地產(chǎn)地甲乙丙丁供應(yīng)量（噸）A23767B13264C35489需求量（噸）1032520解：銷地甲乙丙丁供應(yīng)量（噸）A23767B1327第二步，利用最小元素法尋找初始方案第二步，利用最小元素法尋找初始方案8最小元素法確定的初始方案表

銷地產(chǎn)地甲乙丙丁供應(yīng)量（噸）A617B44C2259需求量（噸）1032520最小元素法確定的初始方案表銷地甲乙丙丁供應(yīng)量（噸9第三步判定最優(yōu)方案第三步判定最優(yōu)方案10位勢(shì)法首先在初始方案中找到運(yùn)量分配最多的行或列，確定其所在行或列的位勢(shì)為零，然后根據(jù)有調(diào)運(yùn)量的格所對(duì)應(yīng)的運(yùn)價(jià)等于行位勢(shì)加上列位勢(shì)之和，依次求出各行和列的位勢(shì)，再根據(jù)下列公式求空格所對(duì)應(yīng)的檢驗(yàn)數(shù)。Aij＝Cij—（Ui+Vj）公式中的Aij表示空格所對(duì)應(yīng)的檢驗(yàn)數(shù)，Cij表示空格所對(duì)應(yīng)的運(yùn)價(jià)，Ui表示行位勢(shì)，Vj表示列位勢(shì)，i表示運(yùn)價(jià)表的行數(shù)，j表示運(yùn)價(jià)表的列數(shù)。位勢(shì)法11最小元素法確定的初始方案表

銷地產(chǎn)地甲乙丙丁供應(yīng)量（噸）A617B44C2259需求量（噸）1032520最小元素法確定的初始方案表銷地甲乙丙丁供應(yīng)量（噸12最小元素法確定的初始方案的檢驗(yàn)數(shù)

銷地產(chǎn)地甲乙丙丁供應(yīng)量（噸）A6（0）1（0）（5）（0）7B4（0）（1）（1）（1）4C（-1）2（0）2（0）5（0）9需求量（噸）1032520最小元素法確定的初始方案的檢驗(yàn)數(shù)銷地甲乙丙丁供應(yīng)13最后判斷，如果所有的檢驗(yàn)數(shù)均大于等于零，則判斷的方案最優(yōu)。當(dāng)檢驗(yàn)數(shù)有至少一個(gè)負(fù)數(shù)時(shí)，說明該方案不是最優(yōu)的方案，運(yùn)輸成本還有調(diào)整的空間，對(duì)負(fù)數(shù)檢驗(yàn)數(shù)絕對(duì)值最大的所在的閉回路進(jìn)行調(diào)整。Aij>=0，初始方案最優(yōu)；有一個(gè)Aij<0，則不是最優(yōu)，需要調(diào)整負(fù)數(shù)中|Aij

|值最大的所在閉合回路。最后判斷，如果所有的檢驗(yàn)數(shù)均大于等于零，則判斷的方案最優(yōu)。當(dāng)14閉合回路基本思路是從任意一個(gè)空格（沒有安排調(diào)運(yùn)量的格）出發(fā)，沿著行或列尋找的一條除此空格之外其余頂點(diǎn)均為有數(shù)字格（安排有調(diào)運(yùn)量的格）的閉合回路。找出某一空格的閉合回路；從該空格開始在閉合回路上給各個(gè)頂點(diǎn)進(jìn)行“+”、“-”間隔標(biāo)號(hào)；對(duì)負(fù)數(shù)檢驗(yàn)數(shù)絕對(duì)值最大的所在的閉回路進(jìn)行調(diào)整:標(biāo)有負(fù)號(hào)頂點(diǎn)中對(duì)應(yīng)的最小運(yùn)量作為調(diào)入運(yùn)量，標(biāo)有“+”的頂點(diǎn)所對(duì)應(yīng)的運(yùn)量加上調(diào)入運(yùn)量，標(biāo)有“—”的頂點(diǎn)所對(duì)應(yīng)的運(yùn)量減去調(diào)入運(yùn)量；形成新的調(diào)運(yùn)方案，再判斷和調(diào)整直到得到最優(yōu)方案為止。閉合回路15例7-2某公司有3個(gè)倉庫，分別是A、B、C，供應(yīng)量分別是7噸、4噸、9噸，每天向4個(gè)配送中心送貨，分別是甲、乙、丙、丁，需求量分別是10噸，3噸、2噸和5噸。單位運(yùn)價(jià)表如圖所示，請(qǐng)確定最優(yōu)方案。單位運(yùn)價(jià)表單位：元/噸產(chǎn)地銷地甲乙丙丁A2376B1326C3548例7-2某公司有3個(gè)倉庫，分別是A、B、C，供應(yīng)量分別是716銷地產(chǎn)地甲乙丙丁供應(yīng)量（噸）A（1）3（5）47B2（0）2（0）4C8（0）（0）19需求量（噸）1032520銷地甲乙丙丁供應(yīng)量（噸）A（1）3（5）47B2（0）17運(yùn)輸線路決策ppt課件18運(yùn)輸線路決策ppt課件19運(yùn)輸線路決策ppt課件20

Aij

≥0，得到最優(yōu)解x13=5,x14=2,x21=3,x24=1,

x32=6,x34=3,其余xij=0;

最優(yōu)值：

f*=3×5+10×2+1×3+8×1+4×6+5×3=85Aij≥0，得到最優(yōu)解x13=5,21例某地區(qū)有3個(gè)煤礦，所產(chǎn)煤炭全部銷往兩座火力發(fā)電廠。各礦產(chǎn)量、電廠需求量及單位運(yùn)價(jià)表如表所示，問如何安排運(yùn)輸可使總運(yùn)費(fèi)最??？例某地區(qū)有3個(gè)煤礦，所產(chǎn)煤炭全部銷往兩座火力發(fā)電廠。各礦產(chǎn)量22運(yùn)價(jià)電廠煤礦B1B2煤產(chǎn)量A1355000A24211000A3698000需求量1000014000運(yùn)價(jià)電廠B1B2煤產(chǎn)量A1355000A24223練習(xí)題:某商品產(chǎn)地：A、B、C、D銷地：a、b、c、d、e供應(yīng)量分別為：100、300、600、800，需求量分別為：250、300、350、400、500，請(qǐng)確定最優(yōu)方案。單位運(yùn)價(jià)表abcdeABCD3020305030303010304070804020205040707080練習(xí)練習(xí)題:某商品產(chǎn)地：A、B、C、D銷地：a、b、c、d、e供24供需不平衡的物資調(diào)運(yùn)問題1、供應(yīng)量大于需求量2、需求量大于供應(yīng)量處理：引入一個(gè)虛設(shè)的需求點(diǎn)，令其的需求量等于實(shí)際問題中供應(yīng)量與需求量之差。實(shí)際中，相當(dāng)于在某個(gè)供應(yīng)點(diǎn)的倉庫里將多余部分儲(chǔ)存起來了。因此，可視其相應(yīng)運(yùn)價(jià)為。零處理：引入一個(gè)虛設(shè)的供應(yīng)點(diǎn)，令其的供應(yīng)量等于實(shí)際問題中需求量與供應(yīng)量之差。實(shí)際中，相當(dāng)于在某個(gè)需求點(diǎn)內(nèi)設(shè)立一個(gè)倉庫，將不足部分另找出路供應(yīng)好，預(yù)先儲(chǔ)存起來了。相應(yīng)運(yùn)價(jià)為零。供需不平衡的物資調(diào)運(yùn)問題1、供應(yīng)量大于需求量處理：引入一個(gè)虛25例:某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？例:某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B126解：增加一個(gè)虛設(shè)的銷地運(yùn)輸費(fèi)用為0解：增加一個(gè)虛設(shè)的銷地運(yùn)輸費(fèi)用為027例:某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？例:某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B28解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為0解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為029圖上作業(yè)法圖上作業(yè)法30圖上作業(yè)法：利用商品產(chǎn)地和銷地的地理分布和交通路線示意圖，采用科學(xué)規(guī)劃的方法，制定出商品合理的運(yùn)輸方案，來求得商品運(yùn)輸最小噸公里的方法。它適用于交通線路為線狀、圈狀，而且對(duì)產(chǎn)銷地點(diǎn)的數(shù)量沒有嚴(yán)格限制的情況。如果沒有對(duì)流和迂回，就是一個(gè)運(yùn)輸力最省的最優(yōu)方案。

圖上作業(yè)法：31圖上作業(yè)法交通圖畫法1、交通圖的符號(hào)：發(fā)點(diǎn)用“”表示，并將發(fā)貨量記在里面，收點(diǎn)用“”表示，并將收貨量記在里面。兩點(diǎn)間交通線的長(zhǎng)度記在交通線旁邊。2、調(diào)運(yùn)物資的流向圖：物資調(diào)運(yùn)的方向（流向）用“”表示，并把“”按調(diào)運(yùn)方向畫在交通線的右邊，把調(diào)運(yùn)物資的數(shù)量記在“”的右邊并加上括號(hào)。圖上作業(yè)法交通圖畫法32例1：調(diào)運(yùn)線路呈線狀。依據(jù)“就近調(diào)空”原則，只要不出現(xiàn)對(duì)流情況，即是最優(yōu)方案。設(shè)產(chǎn)地A、D、F，產(chǎn)量為10、3、9，銷地B、C、E、G，需求為2、5、11、4，試求合理的運(yùn)輸方案。例1：調(diào)運(yùn)線路呈線狀。33第一步，編制商品產(chǎn)銷平衡表需供BCEG產(chǎn)量A10D3F9銷量2511422第一步，編制商品產(chǎn)銷平衡表需BCEG產(chǎn)量A10D3F34第二步，繪制交通線路示意圖A10B-2-5C3DE-11F9G-4第二步，繪制交通線路示意圖AB-5C3DEFG35第三步，按交通路線示意圖進(jìn)行圖上作業(yè)。就近調(diào)空，首先從各端開始就近調(diào)運(yùn)，在進(jìn)行調(diào)整。A10B-2-5C3DE-11F9G-4第三步，按交通路線示意圖進(jìn)行圖上作業(yè)。就近調(diào)空，首先從各端開36第四步，將結(jié)果填入商品調(diào)運(yùn)平衡表。需供BCEG產(chǎn)量A22610D33F549銷量2511422第四步，將結(jié)果填入商品調(diào)運(yùn)平衡表。需BCEG產(chǎn)量A237例有某物資17萬噸，由A1，A2，A3，A4發(fā)出，發(fā)量分別為5，2，3，7（單位：萬噸），運(yùn)往B1，B2，B3，B4，收量分別為8，1，3，5，收發(fā)量是平衡的，它的交通路線如圖所示，問應(yīng)如何調(diào)運(yùn)，才能使運(yùn)輸噸·千米最小。例有某物資17萬噸，由A1，A2，A3，A4發(fā)出，發(fā)量分別為3852378135A1A2B1A3B2B3A4B452378135A1A2B1A3B2B3A4B439例2：調(diào)運(yùn)線路呈圈狀。設(shè)有產(chǎn)地，銷地,其距離及供需量見書，求最優(yōu)運(yùn)輸線路。它的原則可歸納為：流向劃右方，對(duì)流不應(yīng)當(dāng)；里圈、外圈分別算，要求不過半圈長(zhǎng)；如若超過半圈長(zhǎng)，應(yīng)甩運(yùn)量最小段；反復(fù)求算最優(yōu)方案。例2：調(diào)運(yùn)線路呈圈狀。設(shè)有產(chǎn)地，銷地,其距離及供需量見書，求40第一步，在每個(gè)圈中，去掉一段距離最長(zhǎng)的線路，用虛線表示，變成線狀，再根據(jù)線路不含圈的情況作出初始調(diào)運(yùn)方案。第二步，檢查有無迂回現(xiàn)象。第三步，調(diào)整流向。第四步將結(jié)果填入平衡表。第一步，在每個(gè)圈中，去掉一段距離最長(zhǎng)的線路，用虛線表示，變成41

［例］調(diào)運(yùn)線路成圈狀例。設(shè)有某商品發(fā)運(yùn)點(diǎn)A、B、C、D等四處，接收點(diǎn)a、b、c、d位于圈狀，其距離及供需量如表所示，試求最優(yōu)運(yùn)輸路線。

42

解：具體作業(yè)步驟如下：

A．首先假定里程最長(zhǎng)的一段沒有貨流通過，使圈狀線路變成非圈線狀，其B應(yīng)甩去。

B．進(jìn)行合理運(yùn)輸，即從B運(yùn)150噸到a，再從a運(yùn)20噸到A，A運(yùn)100噸到d。另一方面，從D運(yùn)10噸到d。此外，從D運(yùn)90噸到e，C地運(yùn)70噸到e，同時(shí)運(yùn)100噸到b地。解：具體作業(yè)步驟如下：43

C．根據(jù)圖中虛線簡(jiǎn)示．將內(nèi)外圈貨流里程匯總．檢查是否超過全圈長(zhǎng)的一半C．根據(jù)圖中虛線簡(jiǎn)示．將內(nèi)外圈貨流里程匯44運(yùn)輸線路決策ppt課件45運(yùn)輸線路決策ppt課件46運(yùn)輸線路決策ppt課件47運(yùn)輸線路決策ppt課件48

一般來說，利用圖上作業(yè)法尋求商品最優(yōu)運(yùn)輸方案，可以按運(yùn)輸噸公里最小原則，也可以從運(yùn)送時(shí)間最短或運(yùn)費(fèi)最省等角度來分別計(jì)算，只要商品在圖上沒有對(duì)流，內(nèi)外圈長(zhǎng)都不大于半圈長(zhǎng)，該運(yùn)輸方案就是最優(yōu)運(yùn)輸方案。一般來說，利用圖上作業(yè)法尋求商品最49練習(xí)3131132A1A2B1A3B2B3B475344432練習(xí)3131132A1A2B1A3B2B3B4753444350在實(shí)際運(yùn)輸活動(dòng)中，各流向上的物資是不平衡的，如進(jìn)多出少或進(jìn)少出多，就會(huì)出現(xiàn)有時(shí)車輛卸貨后空載，如何調(diào)運(yùn)才能使空車行駛里程最少。練習(xí)在實(shí)際運(yùn)輸活動(dòng)中，各流向上的物資是不平衡的，51貨名發(fā)貨點(diǎn)收貨點(diǎn)里程運(yùn)量XXGB1669XXGH571XXIH13210XXJH759XXAD16710XXAB785XXKB749XXFD416XXEB1449XXCD5713貨名發(fā)貨點(diǎn)收貨點(diǎn)里程運(yùn)量XXGB1669XXGH571XXI52運(yùn)輸線路決策ppt課件53節(jié)約法確定路徑的基本原理車輛運(yùn)行計(jì)劃法(VSP，VehiclesSchedulingProgram)又稱里程節(jié)約法（VSP方法）。適用于實(shí)際工作中為求得較優(yōu)解或最優(yōu)的近似解時(shí)采用。它的基本原理是三角形的一邊之長(zhǎng)必定小于另外兩邊之和。如圖所示。節(jié)約法確定路徑的基本原理車輛運(yùn)行計(jì)劃法(VSP，Vehicl54為實(shí)現(xiàn)所節(jié)約里程?？筛鶕?jù)用戶要求、道路條件等設(shè)計(jì)幾種巡回方案，再計(jì)算節(jié)約里程，以其中節(jié)約里程最大者為優(yōu)選的方案。VSP方法可對(duì)所有需求地點(diǎn)計(jì)算其節(jié)約里程，按節(jié)約量的大小順序，優(yōu)選確定路線。為實(shí)現(xiàn)所節(jié)約里程。可根據(jù)用戶要求、道路條件等設(shè)計(jì)幾種巡回方案55如圖所示交通網(wǎng)絡(luò)圖。由起始點(diǎn)P向A、B、C、D、E等五個(gè)用戶送物品。圖中連線上的數(shù)字表示公路里程（km）。圖中靠近各用戶括號(hào)里的數(shù)字，表示對(duì)貨物的需求量（t）。起始點(diǎn)備有2t和4t載質(zhì)量的汽車，且汽車一次巡回行駛里程不能超過30km。求解滿意的送貨方案。如圖所示交通網(wǎng)絡(luò)圖。由起始點(diǎn)P向A、B、C、D、E等五個(gè)用戶56PABCDEP-831087A-817159B-91110C-713D-6E--ABCDEA-3116B-400C-114D-9E-序號(hào)路程節(jié)約數(shù)額1C-D112D-E93A-E64B-C45C-E46A-B37A-C18A-D1

節(jié)約里程數(shù)額排序表節(jié)約里程表最短距離表PABCDEP-831087A-817159B-91110C57從圖中可以看出，依次確定的3條路徑均符合約束條件。最后選擇的方案是：使用2輛4t車，1輛2t車，行駛里程共52km。其中：路徑1：4t車，載貨量3.5t，行駛里程30km；路徑2：2t車，載貨量1.5t，行駛里程16km；路徑3：4t車，載貨量3t，行駛里程6km。在環(huán)形的線路起點(diǎn)，可以通過計(jì)算實(shí)載率的思路確定。總之，這一方法用計(jì)算機(jī)計(jì)算將變得非常簡(jiǎn)單。從圖中可以看出，依次確定的3條路徑均符合約束條件。最后選擇的58練習(xí)：有一配送中心（Q）要向10個(gè)用戶配送，配送距離（公里）和需用量（噸）。采用最大載重量2t、4t、8t三種汽車，并限定車輛一次運(yùn)行距離50km。練習(xí)：有一配送中心（Q）要向10個(gè)用戶配送，配送距離（公里）59第一步，從配送網(wǎng)絡(luò)圖中列出配送中心至用戶及用戶相互間的最短距離。第二步：從最短距離中，計(jì)算用戶相互間的節(jié)約里程。第三步：將節(jié)約里程按大小順序排列分類。第四步：按節(jié)約里程大小順序，組成配送路線第一步，從配送網(wǎng)絡(luò)圖中列出配送中心至用戶及用戶相互間的最短距60第一步：做出最短距離第一步：做出最短距離61例如：C-d之間的節(jié)約里程為：

ΔS=s1＋s2-s3=7＋8—5=10km第二步：從最短矩陣中，計(jì)算用戶相互間的節(jié)約里程如圖所示。例如：C-d之間的節(jié)約里程為：第二步：從最短矩陣中，計(jì)算用戶62第三步：將節(jié)約里程按大小順序排列分類見表第三步：將節(jié)約里程按大小順序排列分類見表63第四步：按節(jié)約里程大小順序，組成配送路線。此方案總路線7條，總行程為109公里，用6輛2噸載重汽車和1輛4噸汽車。按上述方法，逐次取代，優(yōu)化配送路線，得出方案共有兩條路線，線路A和B，總行程70公里，用8噸的載重車1輛（實(shí)際載重6.9噸），最大行程46公里；2噸的載重車1輛（實(shí)際載重1.9噸），最大行程24公里。第四步：按節(jié)約里程大小順序，組成配送路線。此方案總路線7條，64節(jié)約里程法應(yīng)用原則節(jié)約里程法的原則是在約束條件下追求利潤(rùn)最大化。為了使利潤(rùn)最大，可以通過使路程最短，運(yùn)力最優(yōu)，運(yùn)送準(zhǔn)確性最高來實(shí)現(xiàn)。約束條件也就是應(yīng)該注意的事項(xiàng)，例如：①客戶的需要。即客戶對(duì)配送數(shù)量、質(zhì)量、時(shí)間的要求。②應(yīng)充分考慮交通和道路情況。③充分考慮收貨站的停留時(shí)間。④應(yīng)充分考慮運(yùn)載工具的載重量和容積要求及配送中心的配送能力等。節(jié)約里程法應(yīng)用原則65運(yùn)輸線路決策ppt課件66起訖點(diǎn)重合的問題起訖點(diǎn)重合的路徑問題一般被稱為推銷員問題。直覺方法和啟發(fā)式方法是求解這類問題的有效方法。例如，好的路線規(guī)劃中應(yīng)沒有線路交叉，呈凸形或水滴形。起訖點(diǎn)重合的問題67行車路線和時(shí)刻表的制訂原則劃分站點(diǎn)群以分派車輛時(shí)，將距離靠近的站點(diǎn)劃在一起；在安排每天各車的運(yùn)輸線路時(shí)，同樣要使它們的站點(diǎn)群不重疊；從距離倉庫最遠(yuǎn)的站點(diǎn)開始劃分站點(diǎn)群，分派車輛；各卡車的行車路線應(yīng)呈水滴狀，避免交叉；對(duì)于孤立于站點(diǎn)群之外的站點(diǎn)，可采用其它配送方式，如第三方服務(wù)；各站點(diǎn)規(guī)定的取貨/送貨時(shí)間要與行車路線之間協(xié)調(diào)；行車路線和時(shí)刻表的制訂68運(yùn)輸線路決策ppt課件69啟發(fā)式方法啟發(fā)式方法中很多是貪婪方法，例如最近鄰點(diǎn)法，最近插入法等。最近鄰點(diǎn)法就是從某點(diǎn)開始，總是找離目前位置最近的、還未到過的節(jié)點(diǎn)作為下一點(diǎn)，直到所有節(jié)點(diǎn)走完，再回到起點(diǎn)。得到的結(jié)果常常是不理想的。最近插入法要更進(jìn)一步，在選擇下一點(diǎn)時(shí)，不僅僅只考慮當(dāng)前的一點(diǎn)，而是考慮所有已走過的點(diǎn)。另外，它每一步是整個(gè)回路的擴(kuò)張，即從一開始它就考慮回到起點(diǎn)的成本。方法描述如下：（1）

找出離起點(diǎn)最近的節(jié)點(diǎn)，構(gòu)成子回路T。（2）

重復(fù)（3）直到T包含所有節(jié)點(diǎn)：（3）從子回路T以外的節(jié)點(diǎn)中找出離回路T中節(jié)點(diǎn)最近的節(jié)點(diǎn)v，在T中找到一條邊(a,b)，使av+vb-ab最小，將v插在a,b之間，用av+vb代替(a,b)，構(gòu)成新的回路T啟發(fā)式方法70例如一家面包房每天要向五家零售店送貨，各點(diǎn)之間的行車時(shí)間如下：自

到面包房0零售店1零售店2零售店3零售店4零售店5面包房002450385520零售店122032234518零售店247350152160零售店339271701425零售店457421816042零售店521165721410例如一家面包房每天要向五家零售店送貨，各點(diǎn)之間的行車時(shí)間如下71掃描法方法簡(jiǎn)單，在較快時(shí)間內(nèi)得到一個(gè)合理解。在地圖或方格圖上確定所有站點(diǎn)的位置；劃分站點(diǎn)群：自倉庫向任意方向劃一直線，沿一個(gè)方向（順時(shí)針或逆時(shí)針）旋轉(zhuǎn)，依次根據(jù)一輛車能裝載的站點(diǎn)劃分出所有的站點(diǎn)群；用“水滴法”或其它方法確定每個(gè)站點(diǎn)群的路線計(jì)劃。缺點(diǎn)：在劃分站點(diǎn)群時(shí)，沒有考慮在途總運(yùn)行時(shí)間、各站點(diǎn)的取貨/送貨時(shí)間等?？梢詫?duì)結(jié)果調(diào)整（如：與P.158圖7-8是自相矛盾的）。掃描法72貨郎擔(dān)問題有一個(gè)串村走戶賣貨郎，他從某個(gè)村莊出發(fā)，通過若干個(gè)村莊一次且僅一次，最后仍回到原出發(fā)的村莊，問應(yīng)如何選擇行走路線，能使總的行程最短？貨郎擔(dān)問題有一個(gè)串村走戶賣貨郎，他從某個(gè)村莊出發(fā)，通過若干個(gè)73例：求解四個(gè)城市旅行推銷員問題，其距離矩陣如表。當(dāng)推銷員從1城出發(fā)，經(jīng)過每個(gè)城市一次且僅一次，最后回到1城，問按怎樣的路線走，能使總的行程距離最短？最短距離為多少？距離

ij12341859267354例：求解四個(gè)城市旅行推銷員問題，其距離矩陣如表。當(dāng)推銷員從174中國郵路問題

郵遞員的工作是每天在郵局里選出郵件，然后送到他所管轄的客戶中，再返回郵局。自然地，若他要完成當(dāng)天的投遞任務(wù)，則他必須要走過他所投遞郵件的每一條街道至少一次。問怎樣的走法使他的投遞總行程為最短？這個(gè)問題就稱為中國郵路問題。1、提出問題返回結(jié)束上圖表示從R1-R15個(gè)街道交叉點(diǎn)，街道上的數(shù)字表示該街道的長(zhǎng)度，單位為米。中國郵路問題郵遞員的工作是每天在郵局里選出郵件75首先把這個(gè)實(shí)際問題轉(zhuǎn)換成一個(gè)非負(fù)賦權(quán)圖G，G的頂點(diǎn)代表街與街之間的交叉路口和終端，兩個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)這兩點(diǎn)所對(duì)應(yīng)的路口有直通街道而中間不通過其他路口，每條邊的權(quán)是這條邊所對(duì)應(yīng)街道的長(zhǎng)度。G的通過每條邊至少一次的閉途徑稱為G的環(huán)游。具有最小權(quán)的環(huán)游稱為G的最優(yōu)環(huán)游，則中國郵路問題就是要在賦權(quán)圖G中找一條最優(yōu)環(huán)游。2、分析問題首先把這個(gè)實(shí)際問題轉(zhuǎn)換成一個(gè)非負(fù)賦權(quán)圖G，G的頂76街道結(jié)構(gòu)圖由上構(gòu)造右圖街道結(jié)構(gòu)圖由上構(gòu)造右圖773、解決問題返回結(jié)束尋找Euler圖的最優(yōu)環(huán)游的基本思路：（1）用雙倍邊方法求的一個(gè)Euler賦權(quán)母圖，使達(dá)到最小。（2）用Fleury算法求得的Euler環(huán)游,就是圖的環(huán)游；