1、-PAGE . z.2012年第九屆北數(shù)學(xué)建模聯(lián)賽承 諾 書我們仔細(xì)閱讀了第九屆北數(shù)學(xué)建模聯(lián)賽的競賽規(guī)則。我們完全明白，在競賽開場后參賽隊(duì)員不能以任何方式包括、電子、網(wǎng)上咨詢等與本隊(duì)以外的任何人包括指導(dǎo)教師研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其它公開的資料包括網(wǎng)上查到的資料，必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們愿意承當(dāng)由此引起的一切后果。我們的參賽報(bào)名號為： 2394參賽組別研究生或本科或?qū)？疲罕究平M參賽隊(duì)員 (簽名) ：隊(duì)員

2、1：鞠珊隊(duì)員2：夏逸凡隊(duì)員3：胡思想獲獎證書郵寄地址：工程學(xué)院數(shù)理學(xué)院教2-5132012年第九屆北數(shù)學(xué)建模聯(lián)賽編 號 專 用 頁參賽隊(duì)伍的參賽：請各個(gè)參賽隊(duì)提前填寫好：競賽統(tǒng)一編號由競賽組委會送至評委團(tuán)前編號：競賽評閱編號由競賽評委團(tuán)評閱前進(jìn)展編號：題目 快遞公司送貨策略摘要本文針對快遞公司送貨策略的優(yōu)化問題進(jìn)展研究，重點(diǎn)放在給該快遞公司提供一個(gè)合理的送貨策略；在一些特殊條件的限制下，給該公司提供一個(gè)費(fèi)用最省的送貨策略。對于問題一，我們通過運(yùn)送總距離最短目標(biāo)函數(shù)首先建立了模型0-1整數(shù)線性規(guī)劃模型。在給定送貨地點(diǎn)和給定送貨量和送貨時(shí)間的約束條件下，結(jié)合最近插入法和最正確匹配的原理，將送貨點(diǎn)抽

3、象為一個(gè)點(diǎn)頂點(diǎn)，由于街道和坐標(biāo)軸平行，即任意兩頂點(diǎn)之間都有路，且任意兩點(diǎn)間的距離為這兩點(diǎn)橫縱坐標(biāo)差的絕對值之和。如兩點(diǎn)，則權(quán)值為。在此根底上,運(yùn)用矩形，將整個(gè)區(qū)域分成5個(gè)區(qū)域，以選擇的點(diǎn)的送貨質(zhì)量之和小于25kg且距離盡可能小的點(diǎn)的集合作為一個(gè)區(qū)域。依次來分配業(yè)務(wù)員的送貨地點(diǎn)。通過我們的計(jì)算，在不考慮時(shí)間的情況下，我們求得一個(gè)人完成任務(wù)的運(yùn)送路線為8條，由于工作時(shí)間的限制，求出了完成任務(wù)所需的最少業(yè)務(wù)員為5人，最短總路程為。對于問題二，我們借助于問題一求解出來的路線，運(yùn)用圖論中最小生成樹的原理，以費(fèi)用最省為目標(biāo)函數(shù)建立數(shù)學(xué)模型。通過TSP模型在滿足約束條件的前提下求出最短距離，再對所求解方案進(jìn)

4、展優(yōu)化修改，從而我們求得問題二的最省費(fèi)用為。關(guān)鍵詞 0-1整體線性規(guī)劃 最近插入法 最小生成樹TSP模型 e*cel一、問題重述1.1背景分析目前，快遞行業(yè)正蓬勃開展，為我們的生活帶來更多方便。一般地，所有快件到達(dá)*地后，先集中存放在總部，然后由業(yè)務(wù)員分別進(jìn)展派送；對于快遞公司，為了保證快件能夠在指定的時(shí)間送達(dá)目的地，必須有足夠的業(yè)務(wù)員進(jìn)展送貨，但是，太多的業(yè)務(wù)員意味著更多的派送費(fèi)用。1.2問題重述假定所有快件在早上7點(diǎn)鐘到達(dá)，早上9點(diǎn)鐘開場派送，要求于當(dāng)天17點(diǎn)之前必須派送完畢，每個(gè)業(yè)務(wù)員每天平均工作時(shí)間不超過6小時(shí)，在每個(gè)送貨點(diǎn)停留的時(shí)間為10分鐘，途中速度為25km/h，每次出發(fā)最多能帶

5、25千克的重量。為了計(jì)算方便，我們將快件一律用重量來衡量，平均每天收到總重量為184.5千克，公司總部位于坐標(biāo)原點(diǎn)處如圖2，每個(gè)送貨點(diǎn)的位置和快件重量見下表，并且假設(shè)送貨運(yùn)行路線均為平行于坐標(biāo)軸的折線。問題1：請你運(yùn)用有關(guān)數(shù)學(xué)建模的知識，給該公司提供一個(gè)合理的送貨策略即需要多少業(yè)務(wù)員，每個(gè)業(yè)務(wù)員的運(yùn)行線路，以及總的運(yùn)行公里數(shù)；問題2：如果業(yè)務(wù)員攜帶快件時(shí)的速度是20km/h，獲得酬金3元/kmkg；而不攜帶快件時(shí)的速度是30km/h，酬金2元/km，請為公司設(shè)計(jì)一個(gè)費(fèi)用最省的策略。送貨點(diǎn)快件量T(kg)坐標(biāo)(km)送貨點(diǎn)快件量T(kg)坐標(biāo)(km)*y*y1832163.521628.2151

6、75.86183654187.5111745.547197.815126308153.419954.5311216.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818點(diǎn)的分布如下列圖：二、問題分析2.1對于問題一的分析問題一，我們以運(yùn)送總距離最短為目標(biāo)函數(shù)建立01規(guī)劃數(shù)學(xué)模型。對于本問題，有時(shí)間和重量兩個(gè)約束條件，我們優(yōu)先考慮重量。，所以至少要有8

7、個(gè)區(qū)域。表中數(shù)據(jù)的分析最大載重量重駛時(shí)速地中的平均速度重駛酬金業(yè)務(wù)員工作時(shí)間上限空駛時(shí)速每個(gè)送貨點(diǎn)停留時(shí)間空駛酬金備注1.快件一律用重量來衡量2.假定街道方向平行于坐標(biāo)軸然而，從題目中我們很明顯的能夠得知一個(gè)業(yè)務(wù)員要運(yùn)送很屢次，而運(yùn)送每次的路線即是我們所要確立的對于完成該任務(wù)運(yùn)送路線。由于每個(gè)業(yè)務(wù)員的工作量有時(shí)間限制，于是我們又將時(shí)間考慮在，此時(shí)就需要增加業(yè)務(wù)員去完成任務(wù)，在此條件下所需的業(yè)務(wù)員就是完成該任務(wù)所需的最少業(yè)務(wù)員。對于運(yùn)送路線確實(shí)定，我們主要分兩步進(jìn)展，一是每條路線上的目的地，二是經(jīng)過這些目的地的先后順序。對于每條路線上的目的地確實(shí)定，我們根據(jù)實(shí)際情況的需要，定義了最近插入法在滿足

8、約束條件的前提下，在一次運(yùn)送過程中，下一目標(biāo)點(diǎn)確實(shí)定要離上一目標(biāo)點(diǎn)最近。經(jīng)過我們的分析，我們分別考慮了從最近點(diǎn)和最遠(yuǎn)點(diǎn)出發(fā)的送貨路線，經(jīng)過我們的求解比擬可知，從最近點(diǎn)出發(fā)的送貨路線較優(yōu)，于是我們選擇了從最近點(diǎn)出發(fā)的送貨路線。在此方法下我們通過MATLAB編程，找出了每條路線所經(jīng)過的目的地。對于經(jīng)過每條路線中目的地的先后順序，我們采用了TSP算法，借助于計(jì)算機(jī)輔助計(jì)算，通過MATLAB編程找出了經(jīng)過它們的最短路，也就是經(jīng)過他們的先后順序，使業(yè)務(wù)員用最少的時(shí)間完成一次運(yùn)送，為下一次的運(yùn)送節(jié)約了時(shí)間，可是業(yè)務(wù)員的工作時(shí)間最大化，從而只需較少的業(yè)務(wù)員即可完成任務(wù)。2.2問題二的分析問題二，業(yè)務(wù)員的速度

9、改變，分成攜帶快件和不攜帶兩種情況下的具有不同的速度，分別為20km/h,30km/h,且業(yè)務(wù)員的薪酬與其工作過程中的行走的總路程有關(guān)。我們借助于第一問求解出送貨路線的根底上，以運(yùn)費(fèi)最省為目標(biāo)函數(shù)建立數(shù)學(xué)模型。由于問題一我們運(yùn)送路線的安排都是最短的，而問題二只是對于速度這一約束條件進(jìn)展了改變，運(yùn)行的路線是沒有變化的，所以我們根據(jù)時(shí)間要求，在問題一的根底上，對業(yè)務(wù)員的送貨路線進(jìn)展了調(diào)整。經(jīng)過我們的分析，以費(fèi)用最省建立目標(biāo)函數(shù)，建立動態(tài)規(guī)劃數(shù)學(xué)模型，每人工作時(shí)間不超過6小時(shí)且每次出發(fā)最多只帶25千克的重量，列出目標(biāo)函數(shù)和約束條件，來找出每條路線的送貨點(diǎn)。三、模型假設(shè)結(jié)合此題的實(shí)際，為了確保模型求解

10、的準(zhǔn)確性和合理性，我們排除了一些位置因素的干擾，提出以下幾點(diǎn)假設(shè)：1、每個(gè)業(yè)務(wù)員每天的工作時(shí)間不超過6個(gè)小時(shí)，且送完貨后必須再回公司報(bào)到。2、假設(shè)以送貨運(yùn)行路線均為平行于坐標(biāo)軸的折線而不是直線。3、運(yùn)貨途中快件沒有任何損壞，并且業(yè)務(wù)員的運(yùn)送過程也十分平安，沒有堵車、天氣等問題，即送貨過程非常順利。4、如果離*一點(diǎn)最近的點(diǎn)不止一個(gè)，這時(shí)我們要從快件的量出發(fā)，選取加上此快件量最接近25千克而不能超過25千克的目的地。5、各個(gè)業(yè)務(wù)員之間的快件運(yùn)送過程是相互獨(dú)立的，互不影響。6、假設(shè)每個(gè)人的路線一旦確定，再不更改。四、符號說明為了便于問題的求解，我們給出以下符號說明：符號說明兩質(zhì)點(diǎn)的橫縱坐標(biāo)一個(gè)區(qū)域經(jīng)

11、過的地方數(shù)一個(gè)區(qū)域所用的時(shí)間min總的所用的工作時(shí)間min兩質(zhì)點(diǎn)之間的距離總的路程km業(yè)務(wù)員每天送貨的平均速度v=km/min1 在第i條路線上業(yè)務(wù)員向第j個(gè)送貨點(diǎn)送快件0 在第i條路線上業(yè)務(wù)員不向第j個(gè)送貨點(diǎn)送快件1 第i條路線上選擇第j個(gè)送貨點(diǎn)是最遠(yuǎn)點(diǎn)0 第i條路線上選擇第j個(gè)送貨點(diǎn)不是最遠(yuǎn)點(diǎn)第j個(gè)送貨點(diǎn)坐標(biāo)第j個(gè)送貨點(diǎn)所需快件重量五、模型的建立與求解經(jīng)過以上的分析和準(zhǔn)備，我們將逐步建立以下數(shù)學(xué)模型，進(jìn)一步闡述模型的實(shí)際建立過程。5.1問題一的模型建立與求解問題一我們分兩步來完成，首先將30個(gè)點(diǎn)進(jìn)展分組，使每組總的數(shù)之和盡量接近25kg，即一個(gè)郵遞員的最大載重量。分組時(shí)我們采用先找兩個(gè)可行

12、解，然后將兩可行解比擬擬合得到最優(yōu)解的方法。其次，確立組數(shù)之后求每組最優(yōu)路線，通過計(jì)算時(shí)間，將郵遞員分到相應(yīng)的組。模型一的建立與求解兩質(zhì)點(diǎn)的橫縱坐標(biāo)，各自的差的絕對值的和等價(jià)于兩質(zhì)點(diǎn)之間的距離，即兩點(diǎn)間距離： d都是使用用e*cel得到的距離,即a矩陣見附錄一個(gè)區(qū)域所用時(shí)間為：所用總時(shí)間：根據(jù)各個(gè)送貨點(diǎn)的分布，以矩形把整個(gè)區(qū)域分成5個(gè)區(qū)域，在區(qū)域或區(qū)域周圍找出送貨質(zhì)量和小于25KG且距離盡可能小的點(diǎn)的集合，為一個(gè)送貨區(qū)域，由一位業(yè)務(wù)員負(fù)責(zé)送貨。由此，畫出送貨區(qū)域成折線距離的如下列圖：將質(zhì)量大的進(jìn)展分組，在不超過25KG的同時(shí)將前面質(zhì)量小的分?jǐn)偨o后面質(zhì)量大的，將其缺乏25KG的局部補(bǔ)足。形成8條

13、路線。行進(jìn)次序送貨路線12345678業(yè)務(wù)員的送貨路線、送貨區(qū)域、送貨的路程及時(shí)間通過e*cel可得行進(jìn)次序送貨路線問題一路程km時(shí)間min170168258139.234198.4456134.453379.262867.273788.8842100.8總計(jì)365876模型二的建立與求解考慮一個(gè)目標(biāo)：總運(yùn)行公里數(shù)最短?？梢杂靡韵路椒ǎ合燃僭O(shè)每條線路由不同的業(yè)務(wù)員來完成，即需要8名業(yè)務(wù)員來完成運(yùn)送快遞；然后在人數(shù)不變的情況下，此題先從最遠(yuǎn)點(diǎn)開場出發(fā)，依次查找臨近點(diǎn)，并考慮總重量小于25kg，以此來劃分區(qū)域，最后利用最近插入法來尋求最優(yōu)解，最后根據(jù)表中的時(shí)間的約束，對業(yè)務(wù)員人數(shù)安排進(jìn)展重新調(diào)整。

14、根據(jù)題意每個(gè)業(yè)務(wù)員工作時(shí)間不超過6小時(shí)，又因?yàn)?84.5/25=7.38；即派送這些快件至少需要8個(gè)業(yè)務(wù)員。因此問題一只需滿足兩個(gè)條件即可：業(yè)務(wù)員工作時(shí)間不超過6小時(shí)；每條線路上最大載重不超過25kg。由于快遞員從公司出發(fā)最多只能載25kg，因此: 1 在每一條線路上，每一個(gè)送貨點(diǎn)只能選擇一次，因此： 2在每條線路上只有一個(gè)最遠(yuǎn)點(diǎn)，即： 3一條線路上至少有一個(gè)貨點(diǎn)， 4業(yè)務(wù)員在每個(gè)貨點(diǎn)停留10min，而業(yè)務(wù)員每天工作不超過6小時(shí)，因此： 6因此，此模型滿足路程最短目標(biāo)函數(shù)，建立如下模型：約束條件為：因?yàn)?0這個(gè)點(diǎn)距原點(diǎn)最遠(yuǎn)，因此假設(shè)先從30出發(fā)，29是距離30最近的送貨點(diǎn)，而且兩點(diǎn)的快件重量和

15、為12.3kg小于每個(gè)人的最大負(fù)重，可以繼續(xù)指配。接著28是距離29最近的點(diǎn)，此時(shí)三點(diǎn)的快件重量和為18.3kg仍小于25還可以繼續(xù)指配，剩余送貨點(diǎn)中23距離28最近其實(shí)距離28最近的點(diǎn)有23,24,26,27四個(gè)點(diǎn)，但是結(jié)合快遞重量，將其從小到大依次排列，快遞重量大者先選，但需滿足總重量要求，綜合考慮選擇23，同理確定下一個(gè)點(diǎn)選擇15，再繼續(xù)擴(kuò)大，會超出最大限載重，故返回原點(diǎn)，該路線總送貨重量為24.1，所以第一條路線為。用該算法得到的所有路線一?，F(xiàn)在這五個(gè)送貨點(diǎn)之間的最優(yōu)訪問路徑的是一個(gè)典型單回路問題。可以根據(jù)單回路運(yùn)輸模型TSP求解。一般而言，用比擬法求解TSP模型求解有最鄰近法和最近插

16、入法兩種。由最近插入法比最近鄰點(diǎn)法得到的結(jié)果更好，由于已經(jīng)構(gòu)成一個(gè)子回路，但現(xiàn)在要將28插入，但是28送貨點(diǎn)有3個(gè)位子可以插入：1、插入到0和30之間2、插入到30和29之間3、插入到29和0之間。分析比擬，得出插入到0和30之間，增量最小。同理將23和15用最近插入法，可以得出最優(yōu)化路線為。用這種方法可以依次對剩下的七條路線進(jìn)展優(yōu)化，進(jìn)而得出所有的優(yōu)化送貨路二。優(yōu)化后優(yōu)化前每個(gè)業(yè)務(wù)員每天工作不超過6小時(shí)的最正確匹配方案，又考慮每個(gè)業(yè)務(wù)員所經(jīng)過工作站之間的距離，即：業(yè)務(wù)員3和業(yè)務(wù)員8的工作可以合并為一個(gè)人來做；業(yè)務(wù)員4和業(yè)務(wù)員7的工作可以合并為一個(gè)人來做。業(yè)務(wù)員5和業(yè)務(wù)員6的工作可以合并為一個(gè)

17、人來做。由此得出每位快遞員的送貨路線為：所得列表如下：業(yè)務(wù)員編號過站數(shù)所用時(shí)間小時(shí)總載重量千克總路程千米154.8324.1100233.5424.37634+33.39+1.6322.4+20.768+2845+33.15+2.1824.4+24.258+4254+32.83+2.6623.6+20.854+54合計(jì)3024.211845480下列圖為各條路線優(yōu)化前與優(yōu)化后所用時(shí)間比擬下列圖為各條路線優(yōu)化前與優(yōu)化后經(jīng)過路程比擬5.2問題二的模型建立與求解問題一是以路程作為劃分的界限，而問題二就是考慮以費(fèi)用為主，費(fèi)用最主要的因素就是重量和路程，根據(jù)題意，每個(gè)送貨點(diǎn)的送貨的質(zhì)量是確定的，在確定送

18、貨路線的時(shí)候，需要考慮每個(gè)業(yè)務(wù)員每次的載重量不得超過25Kg，且每個(gè)業(yè)務(wù)員每天工作量少于6小時(shí)即滿足上面論述中需要注意的一些限制條件。要使得快遞公司支出費(fèi)用最少，則在安排業(yè)務(wù)員的路線的時(shí)候，需要盡可能使路線短，且載重量在離原點(diǎn)近的時(shí)候可以卸載快件。根據(jù)問題一的模型一的求解方法，首先把快件的重量按從大到小的順序排列，將排序的前八個(gè)送貨點(diǎn)記為重貨點(diǎn)，其次八個(gè)為中等點(diǎn)，其余的記為輕貨點(diǎn)。顯然每個(gè)送貨點(diǎn)的信件量的大小的分布是隨機(jī)分布的。在此，我們考慮到它的總酬金越少則總費(fèi)用越省，在考慮到重量的根底上，我們建立了以下的模型，來進(jìn)展改良。因此我們轉(zhuǎn)向討論它是滿載還是空載的情況。所以*業(yè)務(wù)員路線的選擇應(yīng)遵循

19、：近者優(yōu)先，即應(yīng)使盡量多的路線的最遠(yuǎn)點(diǎn)靠近原點(diǎn)，則必須同時(shí)考慮貨物的重量和路程，先把貨物重且近的送貨點(diǎn)送完，依次篩選，最后送貨物輕及遠(yuǎn)的，因此我們得到優(yōu)化方案，即以貨物的輕重做參考由近到遠(yuǎn)依次篩選。因此，所有業(yè)務(wù)員每天的總酬金：可建立動態(tài)規(guī)劃模型如下：我們接下來用問題一的模型進(jìn)展求解可以求得以下的的路線，同時(shí)我們對路線進(jìn)展進(jìn)一步的優(yōu)化, 從而可以進(jìn)展一次優(yōu)化前后比照。從比照分析中我們對詞的前后變動進(jìn)展分析，通過簡單的軟件進(jìn)展推斷，再參加限制條件。1、近者優(yōu)先原則。*業(yè)務(wù)員最近起始送貨點(diǎn)的選擇直接關(guān)系到費(fèi)用的多少，所以該業(yè)務(wù)員在沿途往送貨終點(diǎn)站中應(yīng)盡量把較近點(diǎn)的快件送完，不讓下一條路線再把較近點(diǎn)

20、作為起始送貨站。2、少走重復(fù)路原則。由于在路途相等的條件下，重載費(fèi)用要比空載費(fèi)用大得多，因此，盡量讓業(yè)務(wù)員空載行走。3、坐標(biāo)貼近原則。在同一條路線中，離原點(diǎn)較近送貨點(diǎn)的坐標(biāo)僅次于較遠(yuǎn)點(diǎn)的坐標(biāo)。4、路線較少原則。路線多，一方面，相對最遠(yuǎn)點(diǎn)的選擇多，跑的空路多，費(fèi)用就多；另一方面，過分地強(qiáng)調(diào)短暫效益，出動路線多，會引起業(yè)務(wù)員的反感，不利于以后的人員控制。根據(jù)這一思路，全部路線業(yè)務(wù)員的重載費(fèi)用可表示為：根據(jù)上述分析及根本假設(shè)，業(yè)務(wù)員送貨的費(fèi)用可以表示如下：重載費(fèi)用：空載費(fèi)用：根據(jù)題意可知，業(yè)務(wù)員在第i條線路運(yùn)送與不運(yùn)送貨物，所需時(shí)間：所以總約束條件為：時(shí)間約束：載重量約束:路線約束：；優(yōu)化前優(yōu)化后路

21、線編號經(jīng)過站點(diǎn)所用時(shí)間小時(shí)總負(fù)載載重量千克負(fù)重路程空載路程總路程千米費(fèi)用142.566724.8301242687.6253.324.8401454937333.066724.63820581659.8444.266724.65624801761.6543.133314.944852817.6634.424.45436902665.273523.74644902711.5844.922.76628942326.4合計(jì)30 = sum(C2:C9) * MERGEFORMAT 30.6334 = sum(D2:D9) * MERGEFORMAT 184.5 = sum(E2:E9) * MERG

22、EFORMAT 374 = sum(F2:F9) * MERGEFORMAT 186560 = sum(H2:H9) * MERGEFORMAT 13586.7由以上分析知，第一條路線和第二條路線可以由一名業(yè)務(wù)員來完成，其余每條路線分別由一名業(yè)務(wù)員運(yùn)送，所以總共需要7名業(yè)務(wù)員。在以上方案中，公司每天付給業(yè)務(wù)員的總薪金為：13586.7。六、模型的評價(jià)與改良6.1模型的優(yōu)點(diǎn)1、模型一給出了業(yè)務(wù)員的調(diào)配方案，便于指導(dǎo)工作。2、兩個(gè)問題中所建的模型將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)0-1規(guī)劃問題求解，減少了運(yùn)算量。3、此模型在業(yè)務(wù)員的調(diào)配中利用了最有匹配原理，減少了問題的時(shí)間復(fù)雜度。4、此模型的方法和思想

23、對其他類型也適，便于推廣到其他領(lǐng)域。5、問題中的模型都通過最近插入法，來進(jìn)展優(yōu)化，以改變其條件，從而到達(dá)最優(yōu)解。6、問題一中所建兩個(gè)模型，來進(jìn)展比照，從而找出更加簡單且更好的結(jié)果。6.2模型的缺點(diǎn)1、本模型問題二沒有充分利用問題一的結(jié)論進(jìn)展相關(guān)的靈敏度分析，而是重新建立相對穩(wěn)定的模型求解，因此增加了問題的繁瑣程度。2、模型給出的約束條件也有不太現(xiàn)實(shí)的地方，對街道的方向和客戶的快件量的假設(shè)也有待進(jìn)一步改良。3、各個(gè)業(yè)務(wù)員的工作時(shí)間安排不甚合理，這需要進(jìn)一步改良。七、模型的推廣1、本模型不但適合于快遞公司送貨問題，還是用于一般的送貨以及運(yùn)輸問題只需要稍微改動模型即可。 2、建模的方法和思想可以推廣

24、到其他類型。3、模型方便直觀，可以在很多中實(shí)現(xiàn)運(yùn)用。八、參考文獻(xiàn)1啟源 金星 葉俊，數(shù)學(xué)建模第三版，：高等教育，2006年2 基于matlab 動態(tài)規(guī)劃中最短路線的實(shí)現(xiàn)程序J電腦學(xué)習(xí)施益昌、賢斌、自立。3 Lingowenku.baidu./view/3bef9888d0d233d4b14e697e.html4 袁新生、邵大宏、郁時(shí)煉編，LINGO和E*cel在數(shù)學(xué)建模中的應(yīng)用，科學(xué)，2007.1九、附錄附錄問題一中TSP算法求解路線即經(jīng)過目的地的先后順序：%運(yùn)用tsp算法求的任一回路中各點(diǎn)的先后順序，是總和最?。籪unction y=tsp(hl)an=*lsread(3.*ls);m=si

25、ze(hl,2); n=hl;for i=1:m-2for j=i+1:m-1 i0=hl(i);j0=hl(j);i1=hl(i+1);j1=hl(j+1); an1=an(i0,j0)+an(i1,j1); an2=an(i0,i1)+an(j0,j1);if an1an2 n(i+1)=hl(j); n(j)=hl(i+1);n(j+1)=hl(j);endendendy=n;附錄問題二中最省費(fèi)用的計(jì)算：%此程序根據(jù)用TSP算法求出的各條回路中的最短回路共八條；%在第二問的條件下求出各條的路走完所需的時(shí)間及費(fèi)用；%s_t(i)用來表示走完第i條回路所需的時(shí)間；%cost(i)用來表示走完

26、第i條回路的費(fèi)用；w=cell(8,1);w1,1=1 2 4 5 6 1;k(1)=24;w2,1=1 3 14 8 7 1;k(2)=24.2;w3,1=1 11 13 9 10 1 ;k(3)=22.9;w4,1=1 17 18 21 15 1;k(4)=17.7;w5,1=1 23 22 24 16 12 1;k(5)=22.9;w6,1=1 20 26 25 1;k(6)=25;w7,1=1 19 27 29 1;k(7)=23.5;w8,1=1 28 30 31 1;k(8)=24.3;T=*lsread(1.*ls,j3:j33);V=*lsread(3.*ls);for i=1

27、:8 m=size(wi,1,2);an1=0;an2=0;an3=0;an=k(i);for j=1:m-2 s=wi,1(j);t=wi,1(j+1); an1=an1+V(s,t); an2=V(wi,1(1,(m-1),1); t1=1/6*(m-2); t2=an1/20;t3=an2/30; s_t(i,1)=t1+t2+t3; %求得每條的時(shí)間； an=an-T(wi,1(1,j); an3=an3+(an)*3*V(wi,1(1,j),wi,1(1,j+1); s_s(i,1)=an1+an2;end cost(i,1)=an3+an2*2; %求得每條的花費(fèi)；endfor i=1:8 disp (第,num2str(i),條回路為：,num2str(wi,1), 時(shí)間為：,num2str(s_t(i,1), 花費(fèi)為：,num2str(cost(i,1); disp(.);endss_t=sum(s_t);s_c=sum(cost);ss_s=sum(s_s);disp (這八條路線的總時(shí)間為：,num2str(ss_t), 總費(fèi)用為：,num2str(s_c), 總路程為：,num2str(ss_s);送貨點(diǎn)快件量T坐標(biāo)(km)*Y91.4102*82.396*19.8232.4279*6308*153.4199163.5216143.81012