試談快遞公司送貨策略分析

1、. .30/30快遞公司送貨策略一 摘要：本文是關(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è)客戶(hù)進(jìn)行貨物分送工作,客戶(hù)i的快件量為已知 ,求滿足需求的路程最短的人員行駛路徑,且使用盡量少的人數(shù),并滿足以下條件:1)每條送快件的路徑上各個(gè)客戶(hù)

3、的需求量之和不超過(guò)個(gè)人最大負(fù)重。2)每個(gè)客戶(hù)的需求必須滿足,且只能由一個(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每個(gè)送貨點(diǎn)停留時(shí)間10min空載酬金2元/km備注1、快件一律用重量來(lái)衡量 2、假定街道方向均平行于坐標(biāo)軸處于實(shí)際情況的考慮,本研究中對(duì)人的最大行程不加限制.本論文試圖從最優(yōu)化的

4、角度，建立起滿足設(shè)計(jì)要求的送貨的數(shù)學(xué)模型，借助于計(jì)算機(jī)的高速運(yùn)算與邏輯判斷能力，求出滿足題意要求的結(jié)果。四 問(wèn)題分析：從公司總部配出一個(gè)人，到任意未配送的送貨點(diǎn)，然后將這個(gè)人配到最近的未服務(wù)的送貨點(diǎn)圍之的鄰居，并使送貨時(shí)間小于6小時(shí)，各送貨點(diǎn)總重量不超過(guò)25kg。繼續(xù)上述指派，直到各點(diǎn)總重量超過(guò)25kg，或者送貨時(shí)間大于6小時(shí)。最后業(yè)務(wù)員返回總部，記錄得到的可行行程（即路線）。對(duì)另一個(gè)業(yè)務(wù)員重復(fù)上述安排，直到?jīng)]有未服務(wù)的送貨點(diǎn)。對(duì)得到的可行的行程安排解中的每一條路徑，求解一個(gè)旅行商問(wèn)題，決定訪問(wèn)指派給每一條行程的業(yè)務(wù)員的順序，最小化運(yùn)輸總距離。得到可行解的行程安排解后退出。根據(jù)題意的要求，每個(gè)

5、人的工作時(shí)間不超過(guò)6小時(shí)，且必須從早上9點(diǎn)鐘開(kāi)始派送，到當(dāng)天17點(diǎn)之前（即在8小時(shí)之）派送完畢。且，故至少需要8條路線。表二列出了題中任意兩配送點(diǎn)間的距離。表二：任意兩點(diǎn)間的距離矩陣因?yàn)榫嚯x是對(duì)稱(chēng)的，即從送貨點(diǎn)i到送貨點(diǎn)j的距離等于從j到i的距離。記作：dij.表三給出了客戶(hù)的需求，為了完成送快遞的任務(wù)，每個(gè)人在工作時(shí)間圍，可以承擔(dān)兩條甚至更多的線路。表中給出了送貨點(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）xyxY1183216163.5216228.21517175.86183365418187.51117445.5

6、4719197.815125630820153.4199654.531121326.2225777.27922226.8210882.39623232.4279991.410224247.6151910106.514025259.6151411114.11732626102017121212.7146272712211313135.812928286.02242014143.8101229298.1251615204.671430304.22818五 模型假設(shè)：（1）街道方向均平行于坐標(biāo)軸，且在該前提下，業(yè)務(wù)員可以任意選擇路線。（2）無(wú)塞車(chē)現(xiàn)象，即業(yè)務(wù)員送快遞途中不受任何外界因素影響，且業(yè)務(wù)員

7、的休息時(shí)間不包括在最大工作時(shí)間6個(gè)小時(shí)。（3）業(yè)務(wù)員人數(shù)不限制。（4）每個(gè)業(yè)務(wù)員的路線一旦確定，便不再更改。（5）每個(gè)業(yè)務(wù)員送快遞是獨(dú)立的，每人之間互不影響。（6）業(yè)務(wù)員到某送貨點(diǎn)后必須把該送貨點(diǎn)的快件送完。（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)題一中

8、只要求給出一個(gè)合理的方案，且未涉與到業(yè)務(wù)員工資問(wèn)題，故只要滿足條件業(yè)務(wù)員的工作時(shí)間上限是6個(gè)小時(shí)以與每條路線的最大載重量不大于25kg即可，本模型中追加兩個(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í)間約

9、束：載重量約束：方法一：每一個(gè)行程的第一個(gè)送貨點(diǎn)是距離總部最近的未服務(wù)的送貨點(diǎn)。開(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+w25，當(dāng)其不成立時(shí)找次遠(yuǎn)點(diǎn)。NY找不到符合條件的點(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.5kg

10、，仍小于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）013450 （2）0 2 6 7 13 0（3）0 9 8 12 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

11、18 24 25 0（8）0 29 28 30 0 現(xiàn)在0-1-3-4-5這四個(gè)送貨點(diǎn)之間的最優(yōu)訪問(wèn)路徑安排就是一個(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 插入，但是客戶(hù)4有三個(gè)位置可以插入，現(xiàn)在分析將客戶(hù)4插入到哪里比較合適:1.插入到（0，1）間，C總= 7+4+5+1+4+9=30。2.插入到（1，3）間，C總=5+6+4+9=24

12、。3.插入到（3，0）間，C總=5+4+4+11=24。比較上述三種情況的增量，插入到（3，0）間和（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(mén)=0-1-3-4-5-0.因?yàn)榻值榔叫杏谧鴺?biāo)軸方向，所以它就是最優(yōu)化路線。第二條行程這中，由于所剩下節(jié)點(diǎn)中，2距離0點(diǎn)最近，因此由2出發(fā)，就可以找到最近點(diǎn)6，接著是7，然后13.這樣，第二條優(yōu)化路線0-2-6-7-13-0就確定了。用這種方法，依次可確定以下剩余六條路線。得到總的

13、送貨路線為：（1）013450（2）0 2 6 7 13 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）總路程（km）141（3，2）1.94672432242（1，5）2.506724.246349（10，2）1.866422.9304616（2，16）4.600023.5905411（17，3）4.213424.9726318（11，17）3.750024.7687227（21，13

14、）3.706722768329（25，16）4.840018.396合計(jì)3028.2699184.5506改進(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í)間119：129：0051910：059：0039：321110：4149：523211：08510：142211：322212：0211：5861810：079：001312：482410：317

15、13：102510：53613：3972713：4512：233109：349：002614：07129：5882910：389：00810：203011：00910：442811：244169：439：001710：072010：291410：511511：302311：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 32 22 11 10 0（6）0 19 13 7 0（7）0 12

16、 4 3 0（8）0 5 2 1 0同方法一，用最近插入法修改路徑可以得到更優(yōu)的解，改進(jìn)后的路徑為：（1） 02830292315 0（2） 0 26 27 8 0（3） 0 24 25 14 9 0（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）1530（28，18）4.833324.11002326（20，17）3.540024.3763424（15，19）3.386722.4684518（11，17）3.1

17、53024.4585432（22，5）2.826723.6546319(15, 12 )2.660020.8547312(14, 6 )2.180024.242835 (3, 11)1.620020.728合計(jì)3024.1997184.5480改進(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í)間12810：469：005

18、119：489：003011：113210：152911：332210：392312：051011：061512：3461913：5512：5022610：299：001314：312710：51714：53811：477413：3613：1032410：229：001214：122510：44314：481411：118213：4813：34911：45514：074209：509：00114：391810：171710：411611：07611：41路徑圖為：由上面得圖表知改進(jìn)后的方法二的路線的總的距離為480km，時(shí)間為24.1997；比改進(jìn)后的方法一的距離短，時(shí)間短，所以若是只考慮時(shí)間

19、和路程，改進(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)，以此類(lèi)推，在保證時(shí)間、載重量有限的前提下，沿途把快遞送完，最終讓業(yè)務(wù)員最遠(yuǎn)點(diǎn)空載返回。根據(jù)這一思路，全部路線業(yè)務(wù)員的重載費(fèi)用可表示為：從上式可以看出，業(yè)務(wù)員的重載費(fèi)用是恒定的，又由于總費(fèi)用為重載與空載費(fèi)用之和，所以總費(fèi)用的確定就可以轉(zhuǎn)化為滿足一定條件下的各路線的最遠(yuǎn)點(diǎn)的選擇問(wèn)題。某路線業(yè)務(wù)員經(jīng)過(guò)的路徑選擇應(yīng)遵循以下原則：一是，近者優(yōu)先原則

20、。某業(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)貼近原則。在同一條路線中，離原點(diǎn)較近送貨點(diǎn)的坐標(biāo)僅次于較遠(yuǎn)點(diǎn)的坐標(biāo)。四是，路線較少原則。路線多，一方面，相對(duì)最遠(yuǎn)點(diǎn)的選擇多，跑的空路多

21、，費(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)容，依次選出各路線的次近點(diǎn)，并做統(tǒng)籌兼顧，一直到滿足約束條件的最大值為止。隨后又選出6（0，8）、9（10，2）、10（14，0）、16（2，16）、22（21，0）、15（19，9）、25（15，14）為某條路線的最近點(diǎn)，

22、分別確定次近點(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（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ā)線返

23、回線第七條路線：快遞公司22（21，0）29（25，16）出發(fā)線返回線第八條路線：快遞公司15（19，9）27（21，13）出發(fā)線返回線第九條路線：快遞公司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)用（元）141（3，2）2.4166722.1792.9242（1，5）2.524.7969.5356（0，8）4.6666723.81852.4439（10，2）2.7

24、521.91498.25410（14，0）3.6666719.21352.46416（2，16）4.3333322.92261.87222（21，0）3.7514.91506.78215（19，9）3.1666715.41577.69225（15，14）3.4266719.62019.2合計(jì)30184.513830.7根據(jù)時(shí)間約束，最少要8個(gè)業(yè)務(wù)員送快件，其中把路線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-

25、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ù)上述分析，得到各路線的行走路線如下圖所示：若根據(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）第四條路

26、線：快遞公司16（2，16）17（6，18）20（7，14）14（10，12）第五條路線：快遞公司22（21，0）32（22，5）23（27，9）15（19，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í)間

27、（小時(shí)）總載重量（kg）費(fèi)用（元）141（3，2）2.0333324767.5242（1，5）2.7333324.21390.63410（14，0）2.5666722.91357.54416（2，16）3.117.71438.45522（21，0）5.222.92680.66319（15，12）3.33333252310.27318（11，17）4.1666723.526208327（21，13）4.3333324.32891.9合計(jì)3027.46666184.515456.7合并則有以下人員分配：第一個(gè)人：0-1-3-4-5-0和0-19-25-24-0第二個(gè)人：0-2-13-7-6-0和0

28、-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）模型的方法和思想對(duì)其他類(lèi)型也適合，易于推廣到其他領(lǐng)域。（4）本模型方便、直觀，易于在計(jì)算機(jī)上實(shí)現(xiàn)和推廣。2、模型的缺點(diǎn)：（1）模型給出的約束條件可能也有不太現(xiàn)實(shí)的。（2）對(duì)街道的方向，客戶(hù)的快件量的假設(shè)有待進(jìn)一步改進(jìn)。3、 模型的推廣（1）本模型不但適合于快遞公司送貨問(wèn)題，還是用于一般的送

29、貨以與運(yùn)輸問(wèn)題，只需要稍微改動(dòng)模型即可。（2）模型方便、直觀，可以實(shí)現(xiàn)計(jì)算機(jī)模擬。（3）建模的方法和思想可以推廣到其他類(lèi)型，如車(chē)輛調(diào)度問(wèn)題等。 參考文獻(xiàn)：1：?jiǎn)⒃础⒔鹦?、葉俊編，數(shù)學(xué)模型-3版，高等教育，2003.8 2：吳建國(guó)、汪名杰、虎軍、仁云編，數(shù)學(xué)建模案例精編-1版，中國(guó)水利水電，2005.53：唐煥文、賀明峰編，數(shù)學(xué)模型引論-3版，高等教育，2005.3 注釋?zhuān)篊+源碼求解路線與其相關(guān)容：?jiǎn)栴}一之方法一：#include#include#include#define max 1000 using namespace std;struct verint x;int y;int num;

30、float weight;bool visited31;ver v31;int next1()int k,min=max,tag=0;float w;for(int i=1;i31;i+)if(visitedi=false&vi.x+vi.yw)k=i; w=vi.weight;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;i31;i+)if(visitedi=false&fabs(vk.x-vi.x)+fabs(vk.y-vi.y)min&w+vi.we

31、ight=25) min=fabs(vk.x-vi.x)+fabs(vk.y-vi.y); m=i; tag=1; if(visitedi=false&fabs(vk.x-vi.x)+fabs(vk.y-vi.y)=min&w+vi.weightvm.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 num_of_station=0,distance,tag; visitedk=true;w=vk.weight;distance

32、=vk.x+vk.y;time=(vk.x+vk.y)/25.0;cout0vk.num;tag=next2(k,w);while(tag!=0) num_of_station+;visitedtag=true;coutvtag.num;w=w+vtag.weight;time=time+(fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y)/25.0;if(time+(vtag.x+vtag.y)/25.0+(num_of_station+1)/6.0=6)distance=distance+fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y);k=tag

33、;tag=next2(tag,w);elsetime=time-(fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y)/25.0;break; time=time+(vk.x+vk.y)/35.0+(num_of_station+1)/6.0;distance=distance+vk.x+vk.y;cout0 time distancekm wendl; k=next1();int main()int i; ifstream infile(1.txt);cout各站點(diǎn)的坐標(biāo)與相關(guān)信息是：endl;for(i=0;ivi.numvi.xvi.yvi.weight; coutvi

34、.num(vi.x,vi.y):vi.weightt;coutendl;coutn各條送快遞的線路 所用時(shí)間 該線路總路程endl; way();return 0;問(wèn)題一之方法二：#include#include#include#define max 1000 using namespace std;struct verint x;int y;int num;float weight;bool visited31;ver v31;int next1()int k,max1,tag=0;float w;for(int i=1;imax1)max1=vi.x+vi.y; k=i; w=vi.wei

35、ght;tag=1; if(visitedi=false&vi.x+vi.y=max1&vi.weightw)k=i; w=vi.weight;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;i31;i+)if(visitedi=false&fabs(vk.x-vi.x)+fabs(vk.y-vi.y)min&w+vi.weight=25) min=fabs(vk.x-vi.x)+fabs(vk.y-vi.y); m=i; tag=1; if(visited

36、i=false&fabs(vk.x-vi.x)+fabs(vk.y-vi.y)=min&w+vi.weight=25&vi.weightvm.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 num_of_station=0,distance,tag; visitedk=true;w=vk.weight;distance=vk.x+vk.y;time=(vk.x+vk.y)/25.0;cout0vk.num;tag=next2(

37、k,w);while(tag!=0) num_of_station+;visitedtag=true;coutvtag.num;w=w+vtag.weight;time=time+(fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y)/25.0;if(time+(vtag.x+vtag.y)/25.0+(num_of_station+1)/6.0=6)distance=distance+fabs(vk.x-vtag.x)+fabs(vk.y-vtag.y);k=tag; tag=next2(tag,w);elsetime=time-(fabs(vk.x-vtag.x)+fab

38、s(vk.y-vtag.y)/25.0;break;time=time+(vk.x+vk.y)/25.0+(num_of_station+1)/6.0;distance=distance+vk.x+vk.y;cout0 time distancekm wendl;k=next1();int main()int i; ifstream infile(1.txt);cout各站點(diǎn)的坐標(biāo)與相關(guān)信息是：endl;for(i=0;ivi.numvi.xvi.yvi.weight; coutvi.num(vi.x,vi.y):vi.weightt;coutendl;coutn各條送快遞的線路 所用時(shí)間 該線路總路程endl; way();return 0;問(wèn)題二：#include#include#include#define M 1000using namespace std;struct nodeint x;int y;int num;float weight;node v31;int mindis31;bool vd31;void create(ifstream &in,int n)int i;for(i=0;ivi.numvi.xvi.yvi.weight; coutvi.num(vi.x,vi.y)