建模送貨策略

《建模送貨策略》由會(huì)員分享，可在線閱讀，更多相關(guān)《建模送貨策略（29頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、29 快遞公司送貨策略 一 摘要： 本文是關(guān)于快遞公司送貨策略的優(yōu)化設(shè)計(jì)問(wèn)題，即在給定送貨地點(diǎn)和給定設(shè)計(jì)規(guī)范的條件下，確定所需業(yè)務(wù)員人數(shù)，每個(gè)業(yè)務(wù)員的運(yùn)行線路，總的運(yùn)行公里數(shù)，以及費(fèi)用最省的策略。 本文主要從最短路經(jīng)和費(fèi)用最省兩個(gè)角度解決該問(wèn)題，建立了兩個(gè)數(shù)據(jù)模型。模型一：利用“圖”的知識(shí)，將送貨點(diǎn)抽象為“圖”中是頂點(diǎn)，由于街道和坐標(biāo)軸平行，即任意兩頂點(diǎn)之間都有路。在此模型中，將兩點(diǎn)之間的路線權(quán)值賦為這兩點(diǎn)橫縱坐標(biāo)之和。如A（x1，y1），B（x2，y2）兩點(diǎn)，則權(quán)值為D=|x2-x1|+|y2-y1|。并利用計(jì)算機(jī)程序?qū)σ陨辖Y(jié)果進(jìn)行了校核。模型二：根據(jù)題意，建立動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型。然后

2、用動(dòng)態(tài)規(guī)劃的知識(shí)求得最優(yōu)化結(jié)果。根據(jù)所建立的兩個(gè)數(shù)學(xué)模型，對(duì)滿足設(shè)計(jì)要求的送貨策略和費(fèi)用最省策略進(jìn)行了模擬，在有標(biāo)尺的坐標(biāo)系中得到了能夠反映運(yùn)送最佳路線的模擬圖。最后，對(duì)設(shè)計(jì)規(guī)范的合理性進(jìn)行了充分和必要的論證。 二 關(guān)鍵詞： 快遞公司送貨 最優(yōu)化 圖模型 多目標(biāo)動(dòng)態(tài)規(guī)劃 TSP模型 三 問(wèn)題重述： 在快遞公司送貨策略中，確定業(yè)務(wù)員人數(shù)和各自的行走路線是本題的關(guān)鍵。這個(gè)問(wèn)題可以描述為:一中心倉(cāng)庫(kù)(或配送調(diào)度中心) 擁有最大負(fù)重為25kg的業(yè)務(wù)員m人, 負(fù)責(zé)對(duì)30個(gè)客戶進(jìn)行貨物分送工作, 客戶i 的快件量為已知 , 求滿足需求的路程最短的人員行駛路徑,且使用盡量少的人數(shù),并滿足

3、以下條件: 1) 每條送快件的路徑上各個(gè)客戶的需求量之和不超過(guò)個(gè)人最大負(fù)重。 2) 每個(gè)客戶的需求必須滿足, 且只能由一個(gè)人送貨. 3）每個(gè)業(yè)務(wù)員每天平均工作時(shí)間不超過(guò)6小時(shí)，在每個(gè)送貨點(diǎn)停留的時(shí)間為10分鐘，途中速度為25km/h。 4）為了計(jì)算方便，我們將快件一律用重量來(lái)衡量，平均每天收到總重量為184.5千克。 表一為題中所給的數(shù)據(jù)： 表一 最大載重量 25kg 重載時(shí)速 20km/h 途中的平均速度 25km/h 重載酬金 3元/km*kg 業(yè)務(wù)員工作時(shí)間上限 6h 空載時(shí)速 30km/h

4、每個(gè)送貨點(diǎn)停留時(shí)間 10min 空載酬金 2元/km 備注 1、快件一律用重量來(lái)衡量 2、假定街道方向均平行于坐標(biāo)軸 處于實(shí)際情況的考慮, 本研究中對(duì)人的最大行程不加限制.本論文試圖從最優(yōu)化的角度，建立起滿足設(shè)計(jì)要求的送貨的數(shù)學(xué)模型，借助于計(jì)算機(jī)的高速運(yùn)算與邏輯判斷能力，求出滿足題意要求的結(jié)果。 四 問(wèn)題分析： 從公司總部配出一個(gè)人，到任意未配送的送貨點(diǎn)，然后將這個(gè)人配到最近的未服務(wù)的送貨點(diǎn)范圍之內(nèi)的鄰居，并使送貨時(shí)間小于6小時(shí)，各送貨點(diǎn)總重量不超過(guò)25kg。繼續(xù)上述指派，直到各點(diǎn)總重量超過(guò)25kg，或者送貨時(shí)間大于6小時(shí)。最后業(yè)務(wù)員返回總部，記錄得到的可行行程（即路線）。

5、對(duì)另一個(gè)業(yè)務(wù)員重復(fù)上述安排，直到?jīng)]有未服務(wù)的送貨點(diǎn)。對(duì)得到的可行的行程安排解中的每一條路徑，求解一個(gè)旅行商問(wèn)題，決定訪問(wèn)指派給每一條行程的業(yè)務(wù)員的順序，最小化運(yùn)輸總距離。得到可行解的行程安排解后退出。 根據(jù)題意的要求，每個(gè)人的工作時(shí)間不超過(guò)6小時(shí)，且必須從早上9點(diǎn)鐘開(kāi)始派送，到當(dāng)天17點(diǎn)之前（即在8小時(shí)之內(nèi)）派送完畢。且，故至少需要8條路線。表二列出了題中任意兩配送點(diǎn)間的距離。 表二：任意兩點(diǎn)間的距離矩陣 因?yàn)榫嚯x是對(duì)稱的，即從送貨點(diǎn)i到送貨點(diǎn)j的距離等于從j到i的距離。記作：dij. 表三給出了客戶的需求，為了完成送快遞的任務(wù)，每個(gè)人在工作時(shí)間范圍內(nèi)，可以承擔(dān)兩條甚至更多的線路。

6、表中給出了送貨點(diǎn)序號(hào)，送貨點(diǎn)編號(hào)，快件量T，以及送貨點(diǎn)的直角坐標(biāo)。 表三 序號(hào) 送貨點(diǎn) 快件量T 坐標(biāo)（km） 序號(hào) 送貨點(diǎn) 快件量T 坐標(biāo)（km） x y x Y 1 1 8 3 2 16 16 3.5 2 16 2 2 8.2 1 5 17 17 5.8 6 18 3 3 6 5 4 18 18 7.5 11 17 4 4 5.5 4 7 19 19 7.8 15 12 5 6 3 0 8 20 15 3.4 19

7、 9 6 5 4.5 3 11 21 32 6.2 22 5 7 7 7.2 7 9 22 22 6.8 21 0 8 8 2.3 9 6 23 23 2.4 27 9 9 9 1.4 10 2 24 24 7.6 15 19 10 10 6.5 14 0 25 25 9.6 15 14 11 11 4.1 17 3 26 26 10 20 17 12 12 12.7 14 6 27 27 12 21 13 13 13 5.8 12 9 28

8、 28 6.0 224 20 14 14 3.8 10 12 29 29 8.1 25 16 15 20 4.6 7 14 30 30 4.2 28 18 五 模型假設(shè)： （1）街道方向均平行于坐標(biāo)軸，且在該前提下，業(yè)務(wù)員可以任意選擇路線。 （2）無(wú)塞車現(xiàn)象，即業(yè)務(wù)員送快遞途中不受任何外界因素影響，且業(yè)務(wù)員的休息時(shí)間不包括在最大工作時(shí)間6個(gè)小時(shí)內(nèi)。 （3）業(yè)務(wù)員人數(shù)不限制。 （4）每個(gè)業(yè)務(wù)員的路線一旦確定，便不再更改。 （5）每個(gè)業(yè)務(wù)員送快遞是獨(dú)立的，每人之間互不影響。 （6）業(yè)務(wù)員到某送貨點(diǎn)后必須把該送貨點(diǎn)的快件送完。

9、 （7）每個(gè)業(yè)務(wù)員每天的工作時(shí)間不超過(guò)6個(gè)小時(shí)。 （8）業(yè)務(wù)員回到快遞公司后停留一個(gè)小時(shí)。 六 主要符號(hào)說(shuō)明： Ti：序號(hào)為i的送貨點(diǎn)的快件重量 （xi ，yi）序號(hào)為i的送貨點(diǎn)的坐標(biāo) M重：業(yè)務(wù)員送貨總重載費(fèi)用 M空：業(yè)務(wù)員送貨總空載費(fèi)用 M總：業(yè)務(wù)員送貨總費(fèi)用 N：業(yè)務(wù)員送貨的總次數(shù) m：業(yè)務(wù)員人數(shù) mj：第j個(gè)業(yè)務(wù)員送貨的次數(shù) 七 模型建立與求解： 7.1問(wèn)題一模型 本模型考慮用多目標(biāo)動(dòng)態(tài)規(guī)劃求解。由于問(wèn)題一中只要求給出一個(gè)合理的方案，且未涉及到業(yè)務(wù)員工資問(wèn)題，故只要滿足條件——業(yè)務(wù)員的工作時(shí)間上限是6個(gè)小時(shí)以及每條路線的最大載重量不大于25k

10、g即可，本模型中追加兩個(gè)目標(biāo)——路程最短和人員最少?？梢酝ㄟ^(guò)以下兩種方法實(shí)現(xiàn)：（1）每一個(gè)行程的第一個(gè)送貨點(diǎn)是距離總部最近的未服務(wù)的送貨點(diǎn)。用這種方法，即可得到一組運(yùn)行路線，總的運(yùn)行公里數(shù)，以及總費(fèi)用。（2）每一個(gè)行程的第一個(gè)送貨點(diǎn)是距離總部最遠(yuǎn)的未服務(wù)的送貨點(diǎn)。然后以該點(diǎn)為基準(zhǔn)，選擇距它最近的點(diǎn)，加上約束條件，也可得到一組數(shù)據(jù)。然后比較兩組結(jié)果，通過(guò)函數(shù)擬合即可得到最優(yōu)化結(jié)果。 本模型中以滿足需求的路程最短的人員行駛路徑,且使用盡量少的人數(shù)，即 且 約束條件為： ① 時(shí)間約束： ② 載重量約束： 方法一：每一個(gè)行程的第一個(gè)送貨點(diǎn)是距離總部最近的未服務(wù)的送貨點(diǎn)

11、。 開(kāi)始 找離原該點(diǎn)最近的點(diǎn)v，且該點(diǎn)的訪問(wèn)標(biāo)志設(shè)為被訪問(wèn)，該點(diǎn)快遞重量為w，輸出該點(diǎn)。 找點(diǎn)v最近的點(diǎn)，快遞重量為w1，且w1+w<25，當(dāng)其不成立時(shí)找次遠(yuǎn)點(diǎn)。 N Y 找不到符合條件的點(diǎn) 時(shí) 找到符合條件的點(diǎn)，且不止一個(gè)時(shí)選擇快遞重量最重的那個(gè)點(diǎn)，訪問(wèn)標(biāo)志設(shè)為被反問(wèn)，并輸出該點(diǎn)，賦值給v，且w=w+w1； 第一條行程中訪問(wèn)了節(jié)點(diǎn)0-1-3-4-5-0，是因?yàn)?距離原點(diǎn)最近，因此由1出發(fā)，3是距離1點(diǎn)最近的點(diǎn)，而且兩處快件量之和為14kg，小于每個(gè)人最大負(fù)重量，可以繼續(xù)指配。接著，4是距離3最近的點(diǎn)，而且三處快件量之和為19.

12、5kg，仍小于25kg,還可以繼續(xù)指配。在剩下的未服務(wù)送貨點(diǎn)中，5距離4最近（其實(shí)距離4最近的點(diǎn)有2，5，6，7四個(gè)點(diǎn)，然后考慮該點(diǎn)需求的快件量，將其從大到小依次排列，快件量需求大者優(yōu)先，但超過(guò)25kg上限的點(diǎn)舍去。這里2，7被舍去，故選擇了5）總快件量之和為24kg。再繼續(xù)擴(kuò)充，發(fā)現(xiàn)就會(huì)超出“25kg”這個(gè)上限，因此選擇返回，所以0-1-3-4-5就為第一條路線所含有的送貨點(diǎn)。 用該算法得到的各路線為： （1）0 1 3 4 5 0 （2）1 2 6 7 13 0 （3）9 8 12

13、 10 0 （4）0 16 17 20 14 15 23 0 （5）0 11 22 32 19 0 （6）0 27 26 0 （7）0 18 24 25 0 （8）0 29 28 30 0 現(xiàn)在0-1-3-4-5這四個(gè)送貨點(diǎn)之間的最優(yōu)訪問(wèn)路徑安排就

14、是一個(gè)典型的單回路問(wèn)題?？梢酝ㄟ^(guò)單回路運(yùn)輸模型-TSP模型求解。一般而言，比較簡(jiǎn)單的啟發(fā)式算法求解TSP模型求解有最鄰近法和最近插入法兩種。由RosenkrantzStearns等人在1977年提出的最近插入法，能夠比最近鄰點(diǎn)法，取得更滿意的解。由于0-1-3-0 已經(jīng)先構(gòu)成了一個(gè)子回路，現(xiàn)在要將節(jié)點(diǎn)4 插入，但是客戶4有三個(gè)位置可以插入，現(xiàn)在分析將客戶4插入到哪里比較合適: 1.插入到（0，1）間，C總= 7+4+5+1+4+9=30。 2.插入到（1，3）間，C總=5+6+4+9=24。 3.插入到（3，0）間，C總=5+4+4+11=24。 比較上述三種情況的增量，插入到（3，0

15、）間和（1，3）間增量最小，考慮到下一節(jié)點(diǎn)插入時(shí)路程最小問(wèn)題，所以應(yīng)當(dāng)將4插入到送貨點(diǎn)3和總部0之間。接下來(lái)，用同樣的方法，將5插到4和0之間，能使該條路線總路程最小，該路線總路程為32km，歷時(shí)1.9467h。結(jié)果子回路為T={0-1-3-4-5-0}.因?yàn)榻值榔叫杏谧鴺?biāo)軸方向，所以它就是最優(yōu)化路線。 第二條行程這中，由于所剩下節(jié)點(diǎn)中，2距離0點(diǎn)最近，因此由2出發(fā)，就可以找到最近點(diǎn)13，接著是7，然后6.這樣，第二條優(yōu)化路線0-2-13-7-6-0就確定了。用這種方法，依次可確定以下剩余六條路線。 得到總的送貨路線為： （1）0 1 3 4 5 0 （2）0 2

16、13 7 6 0 （3）0 10 12 8 9 0 （4）0 16 17 20 14 15 23 0 （5）0 19 11 32 22 0 （6）0 18 24 25 0 （7）0 27 26 0 （8）0 29 30 28 0 運(yùn)輸員序號(hào) 所經(jīng)站數(shù) 最近點(diǎn) 所用時(shí)間 (小時(shí)) 總載重（kg）

17、總路程（km） 1 4 1（3，2） 1.9467 24 32 2 4 2（1，5） 2.3467 24.2 42 3 4 9（10，2） 1.8664 22.9 30 4 6 16（2，16） 4.6000 23.5 90 5 4 11（17，3） 4.2134 24.9 72 6 3 18（11，17） 3.7500 24.7 68 7 2 27（21，13） 3.7067 22 76 8 3 29（25，16） 4.8400 18.3 96 合計(jì) 30 28.2699 184.5

18、 506 改進(jìn)前和改進(jìn)后的路程，時(shí)間比較如下： 然后，根據(jù)所經(jīng)歷的時(shí)間進(jìn)行劃分，確定運(yùn)送人數(shù)。在工作時(shí)間小于6小時(shí)的前提下，最終只需要六名運(yùn)輸員，第一條線路和第二條線路有一人完成，第三條和第七條線路由一人完成，則各運(yùn)輸員到達(dá)各站點(diǎn)時(shí)間的情況如下： 路線 站點(diǎn) 編號(hào) 到各站 點(diǎn)時(shí)間 出發(fā)時(shí)間 路線 站點(diǎn) 編號(hào) 到各站點(diǎn)時(shí)間 出發(fā)時(shí)間 1 1 9：12 9：00 5 19 10：05 9：00 3 9：32 11 10：41 4 9：52 32 11：08 5 10：14 22 11：32

19、2 2 12：02 11：58 6 18 10：07 9：00 13 12：48 24 10：31 7 13：10 25 10：53 6 13：39 7 27 13：45 12：23 3 10 9：34 9：00 26 14：07 12 9：58 8 29 10：38 9：00 8 10：20 30 11：00 9 10：44 28 11：24 4 16 9：43 9：00 17 10：07 20 10：29 14 10：51 15

20、11：30 23 11：59 路徑為： 方法二：每一個(gè)行程的第一個(gè)送貨點(diǎn)是距離總部最遠(yuǎn)的未服務(wù)的送貨點(diǎn)。 分析方法如一： 得到的路徑為： （1）0 30 29 28 23 15 0 （2）0 26 27 8 0 （3）0 24 25 14 9 0 （4）0 18 17 20 16 6 0 （5）0

21、32 22 11 10 0 （6）0 19 13 7 0 （7）0 12 4 3 0 （8）0 5 2 1 0 同方法一，用最近插入法修改路徑可以得到更優(yōu)的解，改進(jìn)后的路徑為： （1） 0 28 30 29 23 15 0 （2） 0 26 27 8 0 （3） 0 24 25 14 9 0

22、（4） 0 20 18 17 16 6 0 （5） 0 11 32 22 10 0 （6） 0 19 13 7 0 （7） 0 4 12 3 0 （8） 0 2 5 1 0 運(yùn)輸員序號(hào) 所經(jīng)站數(shù) 最遠(yuǎn)點(diǎn) 所用時(shí)間（小時(shí)） 總載重（km） 總路程（km） 1 5 30（28，18） 4.8333 24.1 100 2 3 26（20，17） 3.5400

23、 24.3 76 3 4 24（15，19） 3.3867 22.4 68 4 5 18（11，17） 3.1530 24.4 58 5 4 32（22，5） 2.8267 23.6 54 6 3 19(15, 12 ) 2.6600 20.8 54 7 3 12(14, 6 ) 2.1800 24.2 42 8 3 5 (3, 11) 1.6200 20.7 28 合計(jì) 30 24.1997 184.5 480 改進(jìn)前后路程和時(shí)間的比較如下：然后，根據(jù)所經(jīng)歷的時(shí)間進(jìn)行劃分，確定運(yùn)送人數(shù)。在工作時(shí)

24、間小于6小時(shí)的前提下，最終只需要五名運(yùn)輸員，第三條線路和第八條線路由一人完成 第四條線路和第七條線路由一人完成，第五條線路和第六條線路由一人完成，則各運(yùn)輸員到達(dá)各站點(diǎn)時(shí)間的情況如下： 路線 站點(diǎn)編號(hào) 到各站點(diǎn)時(shí)間 出發(fā)時(shí)間 路線 站點(diǎn)編號(hào) 到各站點(diǎn)時(shí)間 出發(fā)時(shí)間 1 28 10：46 9：00 5 11 9：48 9：00 30 11：11 32 10：15 29 11：33 22 10：39 23 12：05 10 11：06 15 12：34 6 19 13：55 12：50

25、 2 26 10：29 9：00 13 14：31 27 10：51 7 14：53 8 11：47 7 4 13：36 13：10 3 24 10：22 9：00 12 14：12 25 10：44 3 14：48 14 11：11 8 2 13：48 13：34 9 11：45 5 14：07 4 20 9：50 9：00 1 14：39 18 10：17 17 10：41 16 11：07 6 11：41 路徑圖為： 由上面得圖表

26、知改進(jìn)后的方法二的路線的總的距離為480km，時(shí)間為24.1997；比改進(jìn)后的方法一的距離短，時(shí)間短，所以若是只考慮時(shí)間和路程，改進(jìn)后的方法二為最優(yōu)解。 7.2 問(wèn)題二模型 問(wèn)題二中由于業(yè)務(wù)員所得的費(fèi)用是最主要的，業(yè)務(wù)員安排、路線選擇都是為了總費(fèi)用的最小化提供條件，所以應(yīng)首先考慮路費(fèi)，之后再考慮業(yè)務(wù)員的安排。為了使總能夠費(fèi)用最少，總的思路是先送貨給離快遞公司最近切塊間最重的送貨點(diǎn)，以此類推，在保證時(shí)間、載重量有限的前提下，沿途把快遞送完，最終讓業(yè)務(wù)員最遠(yuǎn)點(diǎn)空載返回。根據(jù)這一思路，全部路線業(yè)務(wù)員的重載費(fèi)用可表示為： 從上式可以看出，業(yè)務(wù)員的重載費(fèi)用是恒定的，又由于總費(fèi)用為重載與空載費(fèi)用

27、之和，所以總費(fèi)用的確定就可以轉(zhuǎn)化為滿足一定條件下的各路線的最遠(yuǎn)點(diǎn)的選擇問(wèn)題。某路線業(yè)務(wù)員經(jīng)過(guò)的路徑選擇應(yīng)遵循以下原則：一是，近者優(yōu)先原則。某業(yè)務(wù)員最近起始送貨點(diǎn)的選擇直接關(guān)系到費(fèi)用的多少，所以該業(yè)務(wù)員在沿途往送貨終點(diǎn)站中應(yīng)盡量把較近點(diǎn)的快件送完，不讓下一條路線再把較近點(diǎn)作為起始送貨站。二是，不走冤枉路原則。一方面，離原點(diǎn)（快遞公司）較遠(yuǎn)的送貨點(diǎn)坐標(biāo)應(yīng)分別大于離原點(diǎn)較近送貨點(diǎn)的坐標(biāo)，在各個(gè)坐標(biāo)上均不走回頭路，即按圖（a）中的①②路線前進(jìn)，而不按③路線前進(jìn)： 圖（a）業(yè)務(wù)員行走路線約定 另一方面，由于在路途相等的條件下，重載費(fèi)用要比空載費(fèi)用大得多，因此，盡量讓業(yè)務(wù)員空載行走。三是，坐標(biāo)貼近原則

28、。在同一條路線中，離原點(diǎn)較近送貨點(diǎn)的坐標(biāo)僅次于較遠(yuǎn)點(diǎn)的坐標(biāo)。四是，路線較少原則。路線多，一方面，相對(duì)最遠(yuǎn)點(diǎn)的選擇多，跑的空路多，費(fèi)用就多；另一方面，過(guò)分地強(qiáng)調(diào)短暫效益，出動(dòng)路線多，會(huì)引起業(yè)務(wù)員的反感，不利于以后的人員控制。 根據(jù)上述分析及基本假設(shè)，業(yè)務(wù)員送貨的費(fèi)用可以表示如下： 重載費(fèi)用： 空載費(fèi)用： 總費(fèi)用： 應(yīng)該滿足以下要求： ① 時(shí)間約束： ② 載重量約束: ③ 路線約束： 根據(jù)路線約束條件③以及表二知：送貨點(diǎn)1（3，2）、2（1，5）首先必須作為某路線的最近起始送貨點(diǎn)，再結(jié)合時(shí)間約束條件①、載重量約束條件②以及上述分析的有關(guān)內(nèi)容，依次選出各路線的次近點(diǎn)，并做統(tǒng)籌

29、兼顧，一直到滿足約束條件的最大值為止。隨后又選出6（0，8）、9（10，2）、10（14，0）、16（2，16）、22（21，0）、15（19，9）、25（15，14）為某條路線的最近點(diǎn)，分別確定次近點(diǎn)等，最后確定各路線如圖（b）所示： 第一條路線： 快遞公司 1（3，2） 3（5，4） 8（9，6） 13（12，9） 出發(fā)線 返回線 第二條路線： 快遞公司 2（1，5） 4（4，7） 7（7，9） 14（10，12） 出發(fā)線 返回線 第三條路線： 快遞公司 6（0，8） 5（3，11） 20（7，14） 18（11，17） 出發(fā)線

30、返回線 30（28，18） 第四條路線： 快遞公司 9（10，2） 12（14，6） 19（15，12） 出發(fā)線 返回線 第五條路線： 快遞公司 10（14，0） 11（17，3） 32（22，5） 23（27，9） 出發(fā)線 返回線 第六條路線： 快遞公司 16（2，16） 17（6，18） 24（15，19） 28（24，20） 出發(fā)線 返回線 第七條路線： 快遞公司 22（21，0） 29（25，16） 出發(fā)線 返回線 第八條路線： 快遞公司 15（19，9） 27（21，13） 出發(fā)線 返回線

31、 第九條路線： 快遞公司 25（15，14） 26（20，17） 出發(fā)線 返回線 圖（b）業(yè)務(wù)員行走路線 根據(jù)上面確定的路線，把個(gè)業(yè)務(wù)員所經(jīng)過(guò)的送貨點(diǎn)數(shù)、最近點(diǎn)、所用時(shí)間、總載重量進(jìn)行歸納，并用C++編程求出各業(yè)務(wù)員送貨所得費(fèi)用以及總費(fèi)用，如下表： 路線號(hào) 所經(jīng)送貨點(diǎn)數(shù) 最近送貨點(diǎn) 所用時(shí)間（小時(shí)） 總載重量（kg） 費(fèi)用（元） 1 4 1（3，2） 2.41667 22.1 792.9 2 4 2（1，5） 2.5 24.7 969.5 3 5 6（0，8） 4.66667 23

32、.8 1852.4 4 3 9（10，2） 2.75 21.9 1498.2 5 4 10（14，0） 3.66667 19.2 1352.4 6 4 16（2，16） 4.33333 22.9 2261.8 7 2 22（21，0） 3.75 14.9 1506.7 8 2 15（19，9） 3.16667 15.4 1577.6 9 2 25（15，14） 3.42667 19.6 2019.2 合計(jì) 30 184.5 13830.7 根據(jù)時(shí)間約束，最少要8個(gè)業(yè)務(wù)員送快件，其

33、中把路線1和2合并，讓業(yè)務(wù)員A執(zhí)行任務(wù)，其余的分別由其他7個(gè)業(yè)務(wù)員送貨。同時(shí)，為了便于統(tǒng)籌業(yè)務(wù)員，可以得出各業(yè)務(wù)員到各送貨點(diǎn)的時(shí)間（各業(yè)務(wù)員的出發(fā)時(shí)間為0）以及各路線從快遞公司出發(fā)的參考時(shí)間（從9：00開(kāi)始工作）。 第一個(gè)人：0-1-3-8-13-0和0-2-4-7-14-0 第二個(gè)人：0-6-5-20-18-30-0 第三個(gè)人：0-9-12-19-0 第四個(gè)人：0-10-11-32-23-0 第五個(gè)人：0-16-17-24-28-0 第六個(gè)人：0-22-29-0 第七個(gè)人：0-15-27-0 第八個(gè)人：0-25-26-0 根據(jù)上述分析，得到各路線的行走路線如下圖所示

34、： 若根據(jù)問(wèn)題一的求解方法，可得以下8條路線： 第一條路線： 快遞公司 1（3，2） 3（5，4） 4（4，7） 5（3，11） 出發(fā)線 返回線 第二條路線： 快遞公司 2（1，5） 13（12，9） 7（7，9） 6（0，8） 第三條路線： 快遞公司 10（14，0） 12（14，6） 8（9，6） 9（10，2） 第四條路線： 快遞公司 16（2，16） 17（6，18） 20（7，14） 14（10，12） 第五條路線： 快遞公司 22（21，0） 32（22，5） 23（27，9） 15（19

35、，9） 11（17，3） 第六條路線： 快遞公司 19（15，12） 25（15，14） 24（15，19） 第七條路線： 快遞公司 18（11，17） 26（20，17） 28（24，20） 第八條路線： 快遞公司 27（21，13） 29（25，16） 30（28，18） 圖（b）業(yè)務(wù)員行走路線 根據(jù)上面確定的路線，把個(gè)業(yè)務(wù)員所經(jīng)過(guò)的送貨點(diǎn)數(shù)、最近點(diǎn)、所用時(shí)間、總載重量進(jìn)行歸納，并用C++編程求出各業(yè)務(wù)員送貨所得費(fèi)用以及總費(fèi)用，如下表： 路線號(hào) 所經(jīng)送貨點(diǎn)數(shù) 最近送貨點(diǎn) 所用時(shí)間（

36、小時(shí)） 總載重量（kg） 費(fèi)用（元） 1 4 1（3，2） 2.03333 24 767.5 2 4 2（1，5） 2.73333 24.2 1390.6 3 4 10（14，0） 2.56667 22.9 1357.5 4 4 16（2，16） 3.1 17.7 1438.4 5 5 22（21，0） 5.2 22.9 2680.6 6 3 19（15，12） 3.33333 25 2310.2 7 3 18（11，17） 4.16667 23.5 2620 8 3 27（21，13） 4.333

37、33 24.3 2891.9 合計(jì) 30 27.46666 184.5 15456.7 合并則有以下人員分配： 第一個(gè)人：0-1-3-4-5-0和0-19-25-24-0 第二個(gè)人：0-2-13-7-6-0和0-10-12-8-9-0 第三個(gè)人：0-16-17-20-14-0 第四個(gè)人：0-22-32-23-15-11-0 第五個(gè)人：0-18-26-28-0 第六個(gè)人;0-27-29-30-0 八 模型評(píng)價(jià) 1、模型的優(yōu)點(diǎn)： （1）模型系統(tǒng)的給出了業(yè)務(wù)員的調(diào)配方案，便于指導(dǎo)工作實(shí)踐。 （2）模型簡(jiǎn)單明了，容易理解與靈活應(yīng)用。 （3）模型的方法和

38、思想對(duì)其他類型也適合，易于推廣到其他領(lǐng)域。 （4）本模型方便、直觀，易于在計(jì)算機(jī)上實(shí)現(xiàn)和推廣。 2、模型的缺點(diǎn)： （1）模型給出的約束條件可能也有不太現(xiàn)實(shí)的。 （2）對(duì)街道的方向，客戶的快件量的假設(shè)有待進(jìn)一步改進(jìn)。 3、 模型的推廣 （1）本模型不但適合于快遞公司送貨問(wèn)題，還是用于一般的送貨以及運(yùn)輸問(wèn)題，只需要稍微改動(dòng)模型即可。 （2）模型方便、直觀，可以實(shí)現(xiàn)計(jì)算機(jī)模擬。 （3）建模的方法和思想可以推廣到其他類型，如車輛調(diào)度問(wèn)題等。 參考文獻(xiàn)： [1]：姜啟源、謝金星、葉俊編，數(shù)學(xué)模型-3版，北京，高等教育出版社，2003.8 [2]：吳建國(guó)、汪名杰、李虎軍、

39、劉仁云編，數(shù)學(xué)建模案例精編-1版，北京，中國(guó)水利水電出版社，2005.5 [3]：唐煥文、賀明峰編，數(shù)學(xué)模型引論-3版，北京，高等教育出版社，2005.3 注釋：C++源碼 求解路線及其相關(guān)內(nèi)容： 問(wèn)題一之方法一： #include #include #include #define max 1000 using namespace std; struct ver{ int x; int y; int num; float weight; }; bool visited[31]; ver v[

40、31]; int next1(){ int k,min=max,tag=0; float w; for(int i=1;i<31;i++){ if(visited[i]==false&&v[i].x+v[i].yw){ k=i; w=v[i].weight;

41、tag=1; } } if(tag)return k; else return 0; } int next2(int k,float w){ int min=max,tag=0,m,i; for(i=1;i<31;i++){ if(visited[i]==false&&fabs(v[k].x-v[i].x)+fabs(v[k].y-v[i].y)

42、; tag=1; } if(visited[i]==false&&fabs(v[k].x-v[i].x)+fabs(v[k].y-v[i].y)==min&&w+v[i].weight<=25&&v[i].weight>v[m].weight){ m=i;tag=1; } } if(tag)return m; else return 0; } void way(){ int k; float w; k=next1(); while(k!=0){ float time; int nu

43、m_of_station=0,distance,tag; visited[k]=true; w=v[k].weight; distance=v[k].x+v[k].y; time=(v[k].x+v[k].y)/25.0; cout<<'0'<<"->"<"; tag=next2(k,w); while(tag!=0){ num_of_station++; visited[tag]=true; cout<"; w=w+v[tag].weight;

44、 time=time+(fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y))/25.0; if(time+(v[tag].x+v[tag].y)/25.0+(num_of_station+1)/6.0<=6){ distance=distance+fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y); k=tag; tag=next2(tag,w); }else{ time=time-(fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y)

45、)/25.0; break; } } time=time+(v[k].x+v[k].y)/35.0+(num_of_station+1)/6.0; distance=distance+v[k].x+v[k].y; cout<<'0'<<" "<

46、xt"); cout<<"各站點(diǎn)的坐標(biāo)及相關(guān)信息是："<>v[i].num>>v[i].x>>v[i].y>>v[i].weight; cout<

47、 way(); return 0; } 問(wèn)題一之方法二： #include #include #include #define max 1000 using namespace std; struct ver{ int x; int y; int num; float weight; }; bool visited[31]; ver v[31]; int next1(){ int k,max1,tag=0; float w; for(int i=1;i<31;i++){

48、 if(visited[i]==false&&v[i].x+v[i].y>max1){ max1=v[i].x+v[i].y; k=i; w=v[i].weight; tag=1; } if(visited[i]==false&&v[i].x+v[i].y==max1&&v[i].weight

49、,float w){ int min=max,tag=0,m,i; for(i=1;i<31;i++){ if(visited[i]==false&&fabs(v[k].x-v[i].x)+fabs(v[k].y-v[i].y)

50、.y-v[i].y)==min&&w+v[i].weight<=25&&v[i].weight

51、=v[k].x+v[k].y; time=(v[k].x+v[k].y)/25.0; cout<<'0'<<"->"<"; tag=next2(k,w); while(tag!=0){ num_of_station++; visited[tag]=true; cout<"; w=w+v[tag].weight; time=time+(fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y))/25.0; if(time+(v[t

52、ag].x+v[tag].y)/25.0+(num_of_station+1)/6.0<=6){ distance=distance+fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y); k=tag; tag=next2(tag,w); }else{ time=time-(fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y))/25.0; break; } } time=time+(v[k].x+v[k].y)/25.0+(num

53、_of_station+1)/6.0; distance=distance+v[k].x+v[k].y; cout<<'0'<<" "<>

54、v[i].num>>v[i].x>>v[i].y>>v[i].weight; cout< #include #include

55、h> #define M 1000 using namespace std; struct node{ int x; int y; int num; float weight; }; node v[31]; int mindis[31]; bool vd[31]; void create(ifstream &in,int n){ int i; for(i=0;i>v[i].num>>v[i].x>>v[i].y>>v[i].weight; cout<

56、("<

57、 int k,min=M,tag=0; float w; for(int i=1;i<31;i++) { if(vd[i]==false&&d(v[0],v[i])w) { k=i; w=v[i].weight; tag=1; } } if(tag) r

58、eturn k; else return 0; } int next2(int k,float w) { int min=M,tag=0,m,i; for(i=1;i<31;i++) { if(vd[i]==false&&d(v[k],v[i])v[k].x&&v[i].y>v[k].y) { min=d(v[k],v[i]); m=i; tag=1; } if(vd[i]

59、==false&&d(v[k],v[i])==min&&w+v[i].weight<=25&&v[i].weight>v[m].weight&&v[i].x>v[k].x&&v[i].y>v[k].y) { m=i;tag=1; } } if(tag) return m; else return 0; } void way() { int k; float w; k=next1(); while(k!=0) { float time,money; int num_of_station=0,dis

60、tance,tag; vd[k]=true; w=v[k].weight; distance=v[k].x+v[k].y; money=3.0*w*distance; time=(v[k].x+v[k].y)/20.0; cout<<'0'<<"->"<"; tag=next2(k,w); while(tag!=0) { num_of_station++; vd[tag]=true; cout<"; w=w+v[tag].weight;

61、 time=time+(d(v[k],v[tag]))/20.0; if(time+(v[tag].x+v[tag].y)/20.0+(num_of_station+1)/6.0<=6){ distance=distance+d(v[k],v[tag]); money=money+3.0*distance*v[tag].weight; k=tag; tag=next2(tag,w); } else { time=time-(fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y))/20.0;

62、 break;} } time=time+(v[k].x+v[k].y)/30.0+(num_of_station+1)/6.0; distance=distance+v[k].x+v[k].y; money=money+(v[k].x+v[k].y)*2.0; cout<<'0'<<" "<