【正文】 可以看到 C 點是距 A 點最近的節(jié)點，記為 AC。由于 C 點是惟一選擇，所以它成為已解的節(jié)點。隨后，找出距 A 點和 C 點最近的未解的節(jié)點。只要列出距各個已解的節(jié)點最近點和連接點，有 A—C，D—F，記為第二步。注意，從起點通過已解的節(jié)點到某一節(jié)點所需的時間應該等于到達這個已解點的最短時間加上已解點與未解點之間的時間，也就是說，從 A 點經(jīng)過 C 點到達 D 點的費用為 AC+CD=138+156=294，而從 A 直達 D 的時間為 348?，F(xiàn)在 D 也成了已解的接點。重復上述過程直到到達終點 J，綜合時間限制與最小費用的要求，最優(yōu)路線為： A C D G J 即：其總費用為 492。264．1 背景分析及假設四、 配送方案關(guān)于解決配送的問題，我們選取了案例六和十四作為背景，把要解決的問題抽象成為數(shù)學模型。我們主要分為三個階段來進行優(yōu)化，階段一：安得 P 分公司到一級配送中心的優(yōu)化；階段二：一級配送中心到終端用戶的優(yōu)化，階段三：貫穿于總流程的增值服務。如圖 所示：建立客戶需求的數(shù)據(jù)庫，利用以往客戶需求數(shù)據(jù)模擬出一定時間（24 小時）內(nèi)該區(qū)域的各客戶各產(chǎn)品需求總量運用節(jié)約法，階段三：貫穿于總流程的增值服務階段一：由總的配送中心（蕪湖）集中向各一級配送中心（各城市）運和客戶協(xié)調(diào)溝通，力爭下單時間統(tǒng)階段二：客戶下定單，各一級配送中心根據(jù)定單要求，向所在區(qū)域范圍內(nèi)的各個銷售點配送圖 配送流程圖和 水 滴 狀 規(guī)則 兩 個 方 案來 使 空 載 的路 程 與 時 間縮短通 過 客 戶 的數(shù)據(jù)庫，找出各 個 客 戶 的訂 單 時 間 的規(guī)律運用節(jié)約法，使 空 載 的 路程 與 時 間 縮短274．2 階段一：安得 P 分公司到一級配送中心的優(yōu)化對于階段一我們提出兩個方案，通過比較后選取其中一個作為解決問題的最優(yōu)方案。由于案例提供的數(shù)據(jù)有限，我們作出以下假設：P 公司為安得在蕪湖的分公司，公司年配送業(yè)務 350 萬的主要客戶僅有案例中給出配送城市的 A、C、D、K 組成。根據(jù)案例十五《南京－杭州對流運輸》中的《陳奎文系統(tǒng)數(shù)據(jù)》（），我們估算 P 公司月配送業(yè)務的重量為：3500000/57545*＝3167 噸。案例中提及到的配送城市有：淮北、阜陽、蚌埠、合肥、巢湖、六安、安慶七個。把一個城市中要配送的每個客戶均視為一點，那么據(jù)統(tǒng)計，七個城市里面一共有十八個點。假設每個點的日均配送量相等，即均為：3167/30/18≈6 噸。兩個城市間的距離采用電子地圖的距離。還根據(jù)案例五《運費如此就上升了 20％》，125 車型和 122 車型的運輸費率只差 元/噸公里，而這里的配送屬于短距離，小批量，所以兩種車型的費率可以視為相等。七個城市的地理位置分布以及相關(guān)假設的數(shù)據(jù)如下圖 和表 所示：28圖 ：配送交通示意圖29城市淮北阜陽蚌埠合肥巢湖六安安慶表 . 各城市的相關(guān)數(shù)據(jù)城市所包含客戶A 客戶、C 客戶A 客戶、K 客戶、C 客戶A 客戶、C 客戶A 客戶、K 客戶、C 客戶、D 客戶A 客戶、K 客戶、D 客戶A 客戶、K 客戶A 客戶、C 客戶每日業(yè)務量/噸12181224181212（注：每日業(yè)務量＝6*所包含的客戶數(shù)）3．2．1 方案一：節(jié)約法優(yōu)化配送路線：簡單介紹節(jié)約法：（1）節(jié)約法的基本規(guī)定利用節(jié)約法確定配送線路的主要出發(fā)點是，根據(jù)配送中心的運輸能力（包括車輛的多少和載重量）和配送中心到各個用戶以及各個用戶之間的距離來制訂使總的車輛運輸?shù)?（噸數(shù)乘上公里數(shù)）數(shù)最小的配送方案。為了便于介紹節(jié)約法的基本思想，設：①配送的是一種貨物；②各用戶的坐標（x，y）及需求量均為已知；③配送中心有足夠的運輸能力。利用節(jié)約法制訂出的配送方案除了送總 數(shù)最小外，還滿足以下條件：①方案能滿足所有用戶的要求；②不使任何一輛車超載；③每輛車每天的總運行時間或行駛里程不超過規(guī)定的上限；④能滿足用戶到貨時間要求。（2）節(jié)約法的基本思想如圖 所示，設 po點為配送中心，它分別向用戶 pi和 pj送貨。設 po到 pi和 pj的距離為 doi和 doj，兩個用戶 pi，pj之間的距離為 dij，送貨方案只有兩種，如圖中（a）和（b）所示。pi（a）pjpi（b）pj圖 節(jié)約法的送貨方案圖 （a）方案是從配送中心 po向用戶 pi，pj分別單獨送貨，配送路線為： popjpo總的配送距離為：Da=2doi+2dojpipo30圖 （b）方案是從配送中心向用戶，pj 依次送貨，配送線路為：po或 popjpipo。總的配送距離為：Db=doi+doj+dijpipjpo對比這兩個方案，哪個更合理呢？這就要看 Da 和 Db 哪個最小，配送距離月小則說明方案越合理，由總距離公式可得出：DaDb=doi+dojdi如果把圖 中的 po、pi、pj看成為一個三家性的三個頂點，那么 doi、doj、dij則是這個三角形三條邊的長度。由三角形的幾何性質(zhì)可知，任意兩條邊之和均大于第三邊，因此，可以認定（1）的結(jié)果是大于零的，即：Da＞Db可以看出，（b）方案優(yōu)于（a）方案，這種分析方案優(yōu)劣的思想就是節(jié)約法的基本思想。根據(jù)節(jié)約法的基本思想，如果有一個配送中心分別向 N 個用戶配送貨物，在汽車載重能力允許的前提下，每輛汽車的配送線路上經(jīng)過的用戶個數(shù)越多，則配送線路越合理，總配送距離越小。用節(jié)約法來解決案例安得“P 分公司到一級配送中心”的問題前提條件：⑴ 面計算的點點距離假設為點點的最短距離（下列數(shù)據(jù)由電子地圖得出）表 計算的點宇假設點的最短距離路線蕪湖——淮北蕪湖——蚌埠蕪湖——阜陽蕪湖——合肥蕪湖——六安蕪湖——巢湖蕪湖——安慶安慶——巢湖距離（km）32520129414220879100142表 路線淮北——蚌埠淮北——合肥淮北——阜陽合肥——阜陽阜陽——六安合肥——安慶合肥——巢湖安慶——六安距離（km）12623315817914315063145城市噸數(shù)（t）蚌埠12淮北12阜陽18合肥24六安12巢湖18安慶12⑵P 分公司可供調(diào)配的車型主要為：四軸 125 型 W=35 噸的車（其中核定載重為 25 噸）⑵ 個點每天需要貨物量一定，數(shù)據(jù)具體與方案一一樣31把以上地理圖轉(zhuǎn)化成簡圖如下：圖 安徽省配送網(wǎng)圖（初始解）圖 中實心點為客戶，紅點為配送中心，“（）”內(nèi)的數(shù)字為噸數(shù)，線上的數(shù)字為距離。32運用節(jié)約法得出原先“蕪湖圖 安徽省配送網(wǎng)簡圖（初始解）六安 蕪湖 ” 與 “蕪湖安慶蕪湖”的配送路線可改成“千米里程。如圖所示：蕪湖安慶六安蕪湖”，則只需一輛車，且節(jié)約了 16333圖 安徽省配送網(wǎng)圖（一次解）34圖 安徽省配網(wǎng)送簡圖（一次解）類推，得出最終解如圖：總共需要 5 輛 125 型的車，總共節(jié)約了 563 千米里程。35圖 安徽省配送圖（最終解）36圖 安徽省配送簡圖（最終解）由于巢湖和阜陽每天的貨物量是 18 噸，如果用 125 型的車會造成浪費，所以安得公司可改成 2 輛三軸 122 型 W=27（核定載重為 20 噸）的車?？偨Y(jié)：表 蕪湖→安慶→六安→蕪湖（125 車型）路線蕪湖→安慶安慶→六安六安→蕪湖小計直線路程/km100145208453載重量/噸2412036節(jié)約里程數(shù)163千米路線蕪湖→合肥→蕪湖（125 車型）直線路程/km 載重量/噸節(jié)約里程數(shù)蕪湖→合肥合肥→蕪湖小計142142284蕪湖→巢湖→蕪湖（122 車型）240240千米路線蕪湖→巢