全國(guó)數(shù)學(xué)建模優(yōu)秀論文

1、承諾書我們仔細(xì)閱讀了中國(guó)人學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng) 上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的，如果引用別人的成果或其他公開的 資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在止文引用處和參 考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如冇違反競(jìng)賽規(guī) 則的行為，我們將受到嚴(yán)肅處理。我們授權(quán)全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽組委會(huì)，可將我們的論文以任何形式進(jìn)行公開展 示（包括進(jìn)行網(wǎng)上公示，在書籍、期刊和其他媒體進(jìn)行正式或非

2、正式發(fā)表等）。我們參賽選擇的題號(hào)是（從a/b/c/d中選擇一項(xiàng)填寫）：衛(wèi)我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話人 j2019所屈學(xué)校（請(qǐng)?zhí)顚懲暾娜簠①愱?duì)員（打卬并簽名）：1.2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）：日期：2013年9月16_日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）:編號(hào)專用頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）:賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱吋使用）:評(píng)閱人評(píng)分rrorooro備 注oooooo全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）:送貨路線設(shè)計(jì)問(wèn)題摘要木文針對(duì)送貨路線優(yōu)化設(shè)計(jì)問(wèn)題進(jìn)行研究，建立了求

3、最小ham訂ton圈模型。借助 mat lab, lingo, vc6. 0軟件，利用c語(yǔ)言、floyd算法、窮舉法、最遠(yuǎn)送貨點(diǎn)優(yōu)先法、 最近送貨優(yōu)先法求解，較好的實(shí)現(xiàn)了送貨路線的設(shè)計(jì)優(yōu)化。首先,針對(duì)將30號(hào)貨物以最快時(shí)間送達(dá)問(wèn)題，將此問(wèn)題簡(jiǎn)化為tsp問(wèn)題，即尋 找一個(gè)最小hamilton圈。利用floyd算法求出任意兩點(diǎn)間距離，借助matalb、lingo 軟件求解最小的hamilton圈，求出最優(yōu)路線如下：0>2621>17>14>16>23 >32>35>38>36>38>43>42>49>42>4

4、5>4>34>31>27>39 >27>31>24> 19> 13> 18>0。其次，在問(wèn)題一的基礎(chǔ)上，考慮到送達(dá)點(diǎn)的時(shí)間的要求，我們按照送貨時(shí)間的限制, 將送達(dá)點(diǎn)分四個(gè)階段，在每個(gè)階段內(nèi)利用窮舉法求解每一階段的最佳路徑，并判斷其總 的送貨時(shí)間是否滿足指定的時(shí)間。最終求出最優(yōu)路線如下： 0->18->13->19->24->31->27->27->39->27->31->31->34->40->45->45->45->42

5、->49-> 42->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26->26->0o最后，針對(duì)將100件貨物以最快時(shí)間送達(dá)的問(wèn)題，選擇一條最優(yōu)的路徑，我們分別 采用最遠(yuǎn)送貨點(diǎn)優(yōu)先法和最近送貨點(diǎn)優(yōu)先兩種方法，分別得出兩種方案，最后將兩種方 案進(jìn)行比較，方案一優(yōu)于方案二，因此，在考慮載重量及載重休積情況下，完成100件 送貨任務(wù)，我們選擇最遠(yuǎn)送貨點(diǎn)優(yōu)先法，即方案一。關(guān)鍵詞：送貨路線優(yōu)化設(shè)計(jì) 最小hami

6、lton圈floyd算法 最遠(yuǎn)送貨點(diǎn)優(yōu)先mat lab 軟件一、問(wèn)題重述現(xiàn)今社會(huì)網(wǎng)絡(luò)越來(lái)越普及，網(wǎng)購(gòu)已成為一種常見的消費(fèi)方式，隨z物流行業(yè)也漸漸 興盛，每個(gè)送貨員需要以最快的速度及時(shí)將貨物送達(dá)，而且他們往往一人送多個(gè)地方， 要設(shè)計(jì)方案使其耗時(shí)最少。現(xiàn)有一快遞公司，庫(kù)房在圖1中的o點(diǎn)，一送貨員需將貨物送至城市內(nèi)多處，請(qǐng)?jiān)O(shè) 計(jì)送貨方案，使所用時(shí)間最少。該地形圖的示意圖見圖1,各點(diǎn)連通信息見表3,假定 送貨員只能沿這些連通線路行走，而不能走其它任何路線。各件貨物的相關(guān)信息見表1, 50個(gè)位置點(diǎn)的處標(biāo)見表2。假定送貨員最大載重50公斤，所帶貨物最大體積1立方米。送貨員的平均速度為 24公里/小時(shí)。假定

7、每件貨物交接花費(fèi)3分鐘，為簡(jiǎn)化起見，同一地點(diǎn)冇多件貨物也簡(jiǎn) 單按照每件3分鐘交接計(jì)算。現(xiàn)在送貨員要將100件貨物送到50個(gè)地點(diǎn)。我們對(duì)以下問(wèn)題做出研究。1. 若將130號(hào)貨物送到指定地點(diǎn)并返冋。設(shè)計(jì)最快完成路線與方式。給出結(jié)果。要 求標(biāo)出送貨線路。2. 假定該送貨員從早上8點(diǎn)上班開始送貨，要將130號(hào)貨物的送達(dá)時(shí)間不能超過(guò)指 定時(shí)間，請(qǐng)?jiān)O(shè)計(jì)最快完成路線與方式。要求標(biāo)出送貨線路。3. 若不需要考慮所有貨物送達(dá)時(shí)間限制（包括前30件貨物），現(xiàn)在要將100件貨物全部 送到指定地點(diǎn)并返回。設(shè)計(jì)最快完成路線與方式。要求標(biāo)出送貨線路，給出送完所有快 件的時(shí)間。由于受重量和休積限制，送貨員可屮途返回取貨。可

8、不考慮中午休息時(shí)間。二、問(wèn)題分析2. 1問(wèn)題一由附表1可以得到30個(gè)包裹的總重量不超過(guò)（m3° = £>m）50kg,且總體積 /=130（v30 = £ v（）超過(guò)1加，則送貨員可一次攜帶30個(gè)包裹送貨到指定地點(diǎn)并返回。對(duì)于問(wèn)題一，耍求送貨員以最快的方式將130貨物送達(dá)指定的地點(diǎn)并返回。因此, 可以將問(wèn)題簡(jiǎn)化為tsp （旅行商）進(jìn)行求解（本題可以重復(fù)經(jīng)過(guò)某頂點(diǎn)），因此最佳運(yùn) 送方案等價(jià)于找出一個(gè)遍歷所有目的頂點(diǎn)并返冋出發(fā)點(diǎn)的最短路線，送達(dá)的頂點(diǎn)間的最 短路徑及距離，即尋找一個(gè)最小的hamilton圈。2.2問(wèn)題二問(wèn)題二中耍求將130號(hào)貨物的送達(dá)時(shí)間不能超過(guò)

9、指定時(shí)間，考慮到所到的點(diǎn)的時(shí)間 的要求是否滿足題意即采用多次分區(qū)域的假設(shè)模型從而找出最優(yōu)的解。由題口所給的附表1可知，根據(jù)指定時(shí)間的先后，分四個(gè)階段去送貨（劃分見附錄 2）。從而最佳運(yùn)送方案是找出每個(gè)階段的起點(diǎn)到終點(diǎn)以（距離下一個(gè)區(qū)域最近的點(diǎn)） 的最短路徑，即尋找出每個(gè)階段的最短路徑。應(yīng)用局部全排列窮舉法求解每一塊的最佳 路徑。2.2問(wèn)題三在不考慮送貨吋間限制的情況下，將體積與重量?jī)蓚€(gè)因素考慮在內(nèi)，允許送貨員可以往返取貨，要求送貨員以最快的方式將貨物送達(dá)指定地點(diǎn)并返冋。由于所有100個(gè)包 #100 <=100裹物體的總重量是mkx)=$> = 14%g，總體積為皿=£&g

10、t; = 2.曲，送貨員的最大載貨 1=1 1=1量為50kg,最大載貨體積為1加彳，所以送貨員會(huì)往返三次取貨，因此可以將所有的送 貨地點(diǎn)分為三塊。對(duì)于所有送貨地點(diǎn)的分塊，可以采用2種方案尋找離始發(fā)點(diǎn)最遠(yuǎn) 的點(diǎn)，逐次加入次遠(yuǎn)點(diǎn)，直至達(dá)到送貨員的最大載貨量；尋找離始發(fā)點(diǎn)最近的點(diǎn)，逐次 加入次近點(diǎn)，直至達(dá)到送貨員的最大載貨量。三、基本假設(shè)和符號(hào)說(shuō)明3. 1基本假設(shè)1假設(shè)送貨員的行進(jìn)速度與所送貨物的重量無(wú)關(guān)，速度均為24公里/小時(shí)；2. 假設(shè)送貨員只能沿如圖路線圖行駛，不能走其他的任何路線。且在聯(lián)通路線中，送 貨員可自由選擇；3. 假設(shè)送貨員保持24km/h,不考慮堵車及發(fā)生意外的情況；4. 送貨員

11、在送貨期間無(wú)塞車現(xiàn)象，即業(yè)務(wù)員送快遞途中不受任何外界因素影響；送貨的每一條路、每個(gè)地點(diǎn)可以重復(fù)經(jīng)過(guò)。3. 2符號(hào)說(shuō)明符號(hào)符號(hào)說(shuō)明i，j送貨點(diǎn)的標(biāo)號(hào)jfw30個(gè)包裹的總重量jfwo100個(gè)包裹的總重量fn30個(gè)包裹的總體積fw>100個(gè)包裹的總體積w從0開始回到0的總路線t從o開始冋到o的總路線四、模型的建立與求解4.1模型準(zhǔn)備1)根據(jù)已知點(diǎn)的坐標(biāo)和連接情況，使用matlab做出齊點(diǎn)位置如圖所示:160001400012000100008000600040002000°!圖1送貨地點(diǎn)示意圖2）根據(jù)已知各點(diǎn)坐標(biāo)，利用c語(yǔ)言編程求得圖屮相鄰連通點(diǎn)間的距離如下表（附 錄一）3）利用fl

12、oyd算法求出任意兩個(gè)頂點(diǎn)vi,vj之間的距離（附錄一）:4. 2問(wèn)題一模型的建立與求解4.2. 1模型的建立30m 30 = / m i由附表1可以得到30個(gè)包裹的總重量不超過(guò)（ 臺(tái) ）50kg,且總體積30（-）不超過(guò)1加3,則送貨員可一次攜帶30個(gè)包裹送貨到指定地點(diǎn)并返冋。30個(gè)包裹的送達(dá)地點(diǎn)總共有22個(gè),分別為：13 14 16 17 18 21 23 24 26 27 31 32 34 36 38 3940 42 43 45 49；4. 2. 2模型的求解利用vc6.0編程，先計(jì)算岀相鄰頂點(diǎn)（vi, vj） z間的距離（附錄一），并賦為邊的 權(quán)值，然后floyd算法求出任意兩點(diǎn)間最短

13、路徑（附錄二）。構(gòu)造連接各頂點(diǎn)的哈密爾頓 圈（附錄三），求出最優(yōu)解送貨路線如下：0>26>21 > 17> 14> 16>23>32>35>38>36>38>43>42>49>42>45>40>34>31 >27>39>27>31 >24> 19> 13> 18>0 如圖所示：從而，得到最短送貨路線的總長(zhǎng)d=54707.47m4. 3問(wèn)題二模型的建立與求解4.3.1模型的建立曲于考慮到送貨時(shí)間運(yùn)輸限制，我們優(yōu)先考慮送貨時(shí)間。根據(jù)

14、指定時(shí)間的先后，分 四個(gè)階段去送貨，應(yīng)用局部全排列窮舉法求解每一-塊的最佳路徑。即以送貨時(shí)間對(duì)所冇 貨物進(jìn)行分塊，并在每一塊內(nèi)部采用局部全排列窮舉法求取路徑，并判斷其總的送貨時(shí) 間是否滿足指定的時(shí)間。4. 3. 2模型的求解基本步驟如下：(1) 第一時(shí)間段為8:009:00之間送到的站點(diǎn)為：13、18、39、27、24、27,不計(jì) 重復(fù)站點(diǎn)，總共有5個(gè)站點(diǎn)，利用窮舉法比較次得到最佳路徑為:18->13->24->27->39, 考慮交貨吋間在內(nèi)總吋間為57.1分。(2) 第二時(shí)間段為9:009:30之間送到的站點(diǎn)為:31、31、34、40、45、45、45, 不計(jì)重復(fù)站

15、點(diǎn)，總共有4個(gè)站點(diǎn)，利用窮舉法比較次得到最佳路徑為：31->34->40->45, 考慮交貨時(shí)間在內(nèi)總時(shí)間為46.05分。(3) 第三時(shí)間段為9:3010:15之間送到的站點(diǎn)為:42、49、43、43、38,不計(jì)重復(fù) 站點(diǎn)，總共有4個(gè)站點(diǎn)，利用窮舉法比較次得到最佳路徑為：42->49->43->43->3&考慮 交貨時(shí)間在內(nèi)總時(shí)間為39.58分。(4) 第四時(shí)間段為10:1512:00之間送到的站點(diǎn)為：36、32、23、16、14、17、21、 26,不計(jì)重復(fù)站點(diǎn)，總共有8個(gè)站點(diǎn)，利用窮舉法比較次得到最佳路徑為：36->32->23

16、-> 16-> 14-> 17->21 ->26,考慮交貨時(shí)間在內(nèi)總時(shí)間為81.97分。 按照時(shí)間分段得到站點(diǎn)分塊表，如下表所示：表1站點(diǎn)分塊表第時(shí)間段貨物號(hào)送達(dá)地 點(diǎn)重量體積時(shí)間最佳路 徑時(shí)間（含 交貨時(shí) 間）/分1132.50.03169:001857.12180.50.03549:001313392.560.05959:002419272.450.05459:002720242.930.0529:002722272.250.00189:0039第時(shí)間段3311.180.02689:303146.0511451.10.02879:303114452.280.0

17、5019:303421310.80.01089:304024342.80.01039:304525402.140.01559:304526450.680.06829:3045第三吋間段10381.330.031910:154239.5812430.950.022810:154915422.850.01910:154316431.70.078210:154327491.350.014410:1538第 四 時(shí) 冋 段4261.560.03512:003685.455212.150.037712:00326141.720.0112:00327171.380.010912:00328231.40.0

18、42612:00239320.70.048112:002317320.250.051212:001618361.790.018412:001423261.570.02112:001728320.520.00212:002129232.910.058712:002630161.20.042912:0026因此，由以上時(shí)間段得到的路徑各時(shí)間分段路線圖，如下:綜上得到最佳路徑為：0->18->13->19->24->31->27->27->39->27->31->31->34->40->45->45->4

19、5->42- >49->42->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26->26 ->0 4. 4問(wèn)題三模型的建立與求解4. 3.1模型的建立在考慮送貨員所載貨物重量及體積限制，不考慮送貨時(shí)間限制的前提下，設(shè)計(jì)將貨 物最快送到指定地點(diǎn)的往返路線。由于所有物體的總重量是148公斤，總體積為2.98立方 米，送貨員的最大載貨量為50公斤，最大載貨體積為1立方米，所以送貨員會(huì)往返三次 取貨，因

20、此最少要將所有的送貨地點(diǎn)分為三塊。本題我們采用兩種分塊方案，分別為最 遠(yuǎn)送貨點(diǎn)優(yōu)先法和最近送貨點(diǎn)優(yōu)先法；4. 3. 2模型的求解(1) 最遠(yuǎn)送貨點(diǎn)優(yōu)先法尋找離始發(fā)點(diǎn)o點(diǎn)最遠(yuǎn)的點(diǎn)，以此點(diǎn)為中心尋找周圍離其最近的點(diǎn)，直至達(dá)到送貨 員的最大載貨量和最大載貨體積，在剩余點(diǎn)鐘再以距離o的次遠(yuǎn)點(diǎn)為屮心尋找其周圍的 點(diǎn)，直至達(dá)到送貨員的最大載貨量和最大載貨體積，直到所有貨物運(yùn)送結(jié)束為止。有題目數(shù)據(jù)計(jì)算可得，距離0點(diǎn)最遠(yuǎn)點(diǎn)為2號(hào)點(diǎn)，因此以2號(hào)點(diǎn)為中心的一組送貨點(diǎn) 分塊數(shù)據(jù)為：2、3、4、5、8、15、15、1、6、7、7、11、11、12、12、13、13、10、 10、18、18、20、20、22、25、2

21、5、25、29、30、28、9、33、33、14、14,共35個(gè)站 點(diǎn)，送貨員運(yùn)送的總重量為48.54公斤，總體積為0.9857立方米，不計(jì)重復(fù)站點(diǎn)，共有23 個(gè)送貨點(diǎn)，將前12個(gè)站點(diǎn)作為一部分，后11個(gè)站點(diǎn)作為一部分，利用窮舉法得到其最佳 路徑為：18- >13->11->12-> 15->25->29->22->20->22->30->28->33->28->30->22-> 15->5->2->4 ->3->8-> 1 ->6-> 1 ->

22、7-> 10->9-> 14,其總吋間為 167.48分。除去此23個(gè)站點(diǎn)，由計(jì)算可知，距離o點(diǎn)最遠(yuǎn)的點(diǎn)為48號(hào)點(diǎn)，以此點(diǎn)為中心的一組 送貨點(diǎn)數(shù)據(jù)為：48、44、46、46、46、41、41、50、47、40、40、37、37、34、34、19、 19、24、24、45、45、45、45、31、31、31、27、27、27、39、39,共31 個(gè)站點(diǎn)，送貨 員運(yùn)送的總重量為50公斤，總體積為0.9573立方米，不計(jì)重復(fù)站點(diǎn)，共有15個(gè)送貨點(diǎn)， 將前11個(gè)站點(diǎn)作為一部分，后4個(gè)站點(diǎn)作為一部分，利用窮舉法得到其最佳路徑為：19- >24->31 ->34->

23、;40->47->40->37->41 ->46->48->44->50->45->36->27->39,其總時(shí) 間為141.82分。除去前兩部的站點(diǎn)后，經(jīng)計(jì)算的離o點(diǎn)最遠(yuǎn)的站點(diǎn)時(shí)17號(hào)點(diǎn)，以此點(diǎn)為中心的一組 送貨點(diǎn)數(shù)據(jù)為：16、16、17、17、17、23、23、23、23、32、32、32、32、32、32、35、 38、38、38、36、36、36、21、21、43、43、43、42、42、49、49,共31 個(gè)站點(diǎn)，送貨 員運(yùn)送的總重量為45.07公斤，總體積為0.9751立方米，不計(jì)重復(fù)站點(diǎn)，共冇11個(gè)送貨點(diǎn),

24、利用窮舉法得到其最佳路徑為：17->23-> 16->23->32->35->38->43->42->49->42->43->38->36->21,其總時(shí)間為78.04 分。最后以26、26、26為一-組送回點(diǎn)數(shù)據(jù)，共3個(gè)站點(diǎn)，送貨員運(yùn)送的總重量為4.39公斤, 總體積為0.0619立方米，不計(jì)重復(fù)只有1個(gè)站點(diǎn)，其總吋間為6.96分。綜合此四塊的數(shù)據(jù)可知，總的運(yùn)送時(shí)間為394.3分。(2) 最近送貨點(diǎn)優(yōu)先法尋找離始發(fā)點(diǎn)最近的點(diǎn)，逐次加入次近點(diǎn)，直至達(dá)到送貨員的最大載貨量和最大載 貨體積，再在剩余點(diǎn)屮尋找距離o點(diǎn)

25、最近的點(diǎn)直至達(dá)到送貨員的最大載貨量和最大載貨 體積，直到所有貨物運(yùn)送結(jié)束為止。由題目數(shù)據(jù)計(jì)算可得，距離o點(diǎn)最近點(diǎn)為26號(hào)點(diǎn)，因此以26號(hào)點(diǎn)為起始心的一組送 貨點(diǎn)分塊數(shù)據(jù)為:26、26、26、18、18、21、21、23、23、23、23、27、27、27、31、 31、31、34、34、36、36、36、39、39、24、24、17、17、17、17、11,共31 個(gè)站點(diǎn)， 送貨員運(yùn)送的總重量為45.77公斤，總體積為0.936立方米，不計(jì)重復(fù)只有11個(gè)站點(diǎn)，利 用窮舉法得到其最佳路徑為：26->21 -> 17->23->36->27->39->31

26、 ->34->24-> 18,總時(shí)間為81.12分。除去此11個(gè)站點(diǎn)外，由計(jì)算可得，剩余點(diǎn)中離o點(diǎn)最近的點(diǎn)為25號(hào)點(diǎn)，以此點(diǎn)為起 始心的一組送貨點(diǎn)分塊數(shù)據(jù)為:25、25、25、37、37、42、42、43、43、43、50、1、 47、 3、 6、 15、 15、 29、 22、 30、 49、 49、 41、 41、 28、 20、 20、 44、 4、 4、 4、 4、 20, 總共有33個(gè)點(diǎn)，送貨員運(yùn)送的總重量為44.55公斤，總體積為0.8004立方米，不計(jì)重復(fù)只 有20個(gè)站點(diǎn)，將前12個(gè)站點(diǎn)作為一部分，后8個(gè)站點(diǎn)作為一部分，利用窮舉法得到其最 佳路徑為：25->

27、;29->22->30->33->28->20-> 15->4->3-> 1 ->6->47->37->41 >44->50->49->42->43, 總時(shí)間為219.5分。除去此31個(gè)點(diǎn)外，由計(jì)算可得，剩余的點(diǎn)中距離o點(diǎn)最近的點(diǎn)為38號(hào)點(diǎn)，以此點(diǎn)為 起始點(diǎn)的一組分塊數(shù)據(jù)為：38、38、38、9、11、11、12、12、13、13、14、14、16、 16、 19、 19、 32、 32、 32、 32、 32、 32、 35、 40、 40、 45、 45、 45、 45、 45、 8

28、、 10、 10、7、7、15,總共冇35個(gè)點(diǎn)，送貨員運(yùn)送的總重量為48.73公斤，總體積為0.9839立方 米，不計(jì)重復(fù)只有15個(gè)站點(diǎn)，將前10個(gè)站點(diǎn)作為一部分，后5個(gè)站點(diǎn)作為一部分，利用 窮舉法得到其最佳路徑為：19-> 13-> 11 -> 12->8->7-> 10->9-> 14-> 16->32->35->38->45->40,總時(shí)間為：125.35剩余點(diǎn)中，由計(jì)算可得2號(hào)點(diǎn)距離o點(diǎn)最近，依此點(diǎn)作為起始點(diǎn)的一組分塊數(shù)據(jù)為： 2、5、48、46、46、46,共6個(gè)站點(diǎn)，送貨員運(yùn)送的總重量為8.95公斤

29、，總體積為0.2597 立方米，不計(jì)重復(fù)只有4個(gè)站點(diǎn)，利用窮舉法得到其最佳路徑為：2->5->48->46,總時(shí)間為:125.55 分。綜合此四塊的數(shù)據(jù)可知其總時(shí)間為：551.52分。綜上所述：有計(jì)算結(jié)果可知：應(yīng)用方案一所得總的送貨時(shí)間為：394.3分；應(yīng)用方案 二所得總的送貨時(shí)間為551.52分，方案一優(yōu)于方案二，因此，在考慮載重量及載重體積 情況卜：完成100件送貨任務(wù)的最優(yōu)路徑為：第一趟0-> 18->13->11->12-> 15->25->29->22->20->22->30->28->3

30、3->28->30->22-> 15->5->2->4 >3->8-> 1 ->6-> 1 ->7-> 10->9-> 14->18->0第二趟：0->26->31 -> 19->24->31 ->34->40->47->40->37->41 ->46->48->44->50->45->36->27->39-> 27->31->26->0第三趟：0-&

31、gt;21 -> 17->23-> 16->23->32->35->38->43->42->49->42->43->38->36->21 ->0 第四趟：0->26->26->26->0總時(shí)間為:394.3分。貝i垸成100件送貨任務(wù)的路線圖如下：1600014000120003210000n.40002000800012030eoco-*85圖4各分段路線圖第一趟0-> 18->13->11->12-> 15->25->29->

32、;22->20->22->30->28->33->28->30->22-> 15->5->2->4 >3->8-> 1 ->6-> 1 ->7-> 10->9-> 14-> 18->0笫二趟：0->26->31 -> 19->24->31 ->34->40->47->40->37->41 >46->48->44->50->45->36->27->

33、39-> 27->31->26->0 第三趟：0->21 -> 17->23-> 16->23->32->35->38->43->42->49->42->43->38->36->21 ->0 第四趟：0->26->26->26->0總時(shí)間為：394.3分。五、模型的評(píng)價(jià)5.1模型的優(yōu)缺點(diǎn)5.1.1模型的優(yōu)點(diǎn)問(wèn)題一建立的單旅行商的模型，是被認(rèn)為解決這類型的通用算法。本模型將最快完 成任務(wù)，轉(zhuǎn)化為尋找最短路徑，借助lingo軟件得到最小hamilto

34、n圈，進(jìn)而得到問(wèn)題的 最優(yōu)解，這種方法有嚴(yán)格的理論基礎(chǔ)，并且更具普遍性。問(wèn)題二在問(wèn)題一的求解基礎(chǔ)上，添加了時(shí)間限制，要尋找到一條路線使得送貨員在 規(guī)定的時(shí)間內(nèi)，完成任務(wù)。我們根據(jù)題口所給定的運(yùn)貨吋間將前30件貨物的運(yùn)達(dá)地點(diǎn)分 為四塊，使得數(shù)據(jù)量減小，因此可以利用窮舉法將每一時(shí)間段的運(yùn)送路徑精確地表示出 來(lái)，再根據(jù)每一吋間段首尾銜接的站點(diǎn)可以得到最終的最佳路徑。根據(jù)問(wèn)題三己知的送貨員最人運(yùn)載量及最人運(yùn)載體積的限制條件，至少要將所有的 貨物分為三組，往返三次送達(dá)最終地點(diǎn)。根據(jù)分組方案的不同得到不同的結(jié)果。本題我 們分兩種方案，即最遠(yuǎn)點(diǎn)優(yōu)先法和最近點(diǎn)優(yōu)先法進(jìn)行計(jì)算，并通過(guò)比較得到結(jié)果，這樣 可使結(jié)果

35、更具說(shuō)服力。5.1.2模型的缺點(diǎn)1.對(duì)于與詼tsp問(wèn)題雖然我們用計(jì)算機(jī)模擬技術(shù)，得到了近似優(yōu)解，但跟實(shí)際存在 的最優(yōu)解直接仍然有一定差距。2對(duì)于求解問(wèn)題中，對(duì)于一些問(wèn)題我們基于一些假設(shè)，但是還是缺少證明，同時(shí)還 應(yīng)該加入-些數(shù)據(jù)修整的優(yōu)化方法。六、參考文獻(xiàn)【1】richard johnsonbaugh, marcus schaefer著,大學(xué)算法教程m,清華大學(xué)出版社 【2】黃厚生，求解tsp問(wèn)題的新方法j,天津大學(xué)碩士學(xué)位論文3 譚永基.數(shù)學(xué)模型.上海：復(fù)旦大學(xué)出版社，20054 姜啟源，數(shù)學(xué)模型，北京：高等教育出版社，2004七、附錄附錄一:序號(hào)位置點(diǎn)1位置點(diǎn)2距離(m)序號(hào)位置點(diǎn)1位置點(diǎn)

36、2距離(in)1131916.284325191966.212182863.784425291885.9032207823.324527311067.754242292.644628331325.695381958.094729221097.866343536.414830281017.897422292.644930414997.6285155004.545031261537.039521252.945131342324.7510611294.315232351114.00117185917.945332231311.8712711968.255433463758.51138121756.7

37、75533281325.69149142681.355634401630.78159101945.515735381409.731610185909.555836453182.46171072059.375936272203.921811121417.686037402090.051912131456.796138361537.422012255756.576239271779.922112154805.806340341630.782213183113.466440453217.012313193455.706541442366.032413111669.566641372601.92251

38、4185342.186741462735.422614162607.68684243917.672714172195.726942491917.382814213296.737043382618.442915222860.987144482152.543015254235.407244504987.103116232097.647345503102.763217231774.517445422351.723318311780167546481494133419242258.647647402331.223520221498.937748442152.543621262191.747849503

39、568.823721362880.187949421917.383821171823.918050403043.493922301287.49810182182.034023171774.51820211796.944124311780.1683o261392.064225414154.59附錄二：求兩點(diǎn)間距離的源程序#include "stdio.h"#include "math.h"void main()int xl,x2,yl,y2,i;double d,m,n;for(i=0;i< 100;i+)printft輸入第一組坐標(biāo)，屮間用空格門；

40、 scanf(,%d%d,&xl,&yl);printfc*輸入第二組坐標(biāo),中間用空格:”); scanf(”d%d”,&x2,&y2); m=pow(x2-xl,2); n=pow(y2-yl,2); d=sqrt(m+n);printfc'%.2fan,d);附錄三：找出包括o點(diǎn)在內(nèi)的22個(gè)點(diǎn)之間任意兩點(diǎn)之間的最短距離的matlab源代碼如下: clear;clc;lianjie=l 31 82 20243834425 15526 17 187 18 129 149 1010 1810 711 1212 1312 2512 1513 1813 191

41、3 1114 1814 1614 17142115 2215 2516 2317 23183119 2420 2221 2621 3621 1722 3023 1724 3125 4125 1925 2927 3128 3329 2230 2830 4131 2631 3432 3532 2333 4633 2834 4035 3836 4536 2737 4038 3639 2740 3440 4541 4441 3741 4642 4342 4943 3844 4844 5045 5045 4246 4847 4048 4449 5049 4250 4051 1851 2151 26;zu

42、obiao=|9185 5001445 5607270 5703735 6702620 99510080 143510025 22807160 252513845 268011935 30507850 35456585 41857630 520013405 53252125 597515365 704514165 73858825 80755855 8165780 835512770 85602200 883514765 90557790 93304435 952510860 963510385 10500565 97652580 98651565 99559395 1010014835 10

43、3651250 109007280 1106515305 1137512390 114156410 1151013915 116109510 120508345 123004930 1365013265 1414514180 142153030 1506010915 142352330 145007735 14550885 1488011575 151608010 1532511000 8250;d,d22=juli(zuobiao,lianjie);其中的d,d22=juli(zuobiao,lianjie)函數(shù) matlab 源代碼如下：%計(jì)算任意兩點(diǎn)間的最短距離與達(dá)到最短距離的路徑表示%

44、zuobiao為已知各頂點(diǎn)的坐標(biāo)，lianjie表示圖中相鄰兩點(diǎn)間有連接的點(diǎn)的序號(hào) %d表示任意兩點(diǎn)間最短路徑%d1表示第一問(wèn)小30件貨物所要到達(dá)的指定地點(diǎn)之間的任意兩點(diǎn)之間的最短距離function d d1 =juli(zuobiao,lianjie)%計(jì)算任意相鄰的兩點(diǎn)間的距離a,b=size(zuobiao);for i=l:afor j=i :ajuli(i,j)=sqrt(zuobiao(i, 1 )-zuobiao(j, 1 )a2+(zuobiao(i,2)-zuobiao(j,2)a2);endend%計(jì)算在lianjie情況下，所應(yīng)該知道的口j到達(dá)點(diǎn)的距離c,d=size(

45、iianjie);e=zeros(a);for i=l:ce(lianjie(i, 1 ),lianjie(i,2)= 1;e(lianjie(i,2),lianjie(i, 1 )= 1;endf,g=find(e-=l);h=length(f)；for i=l:h j=l;juli(f(i),g(j)=inf;endp,o=size(juli);for i=l:pjuli(i,i)=0;end%運(yùn)用floyd算法計(jì)算任意兩點(diǎn)間的最短距離a=juli;n=size(a,l);d=a;path=zeros(n,n);for i=l:nfor j=l:nif d(i,j)=infpath(i,j

46、)=j;endendendfor k=l:nfor i=l:nfor j=l:nifd(i,k)+d(k,j)vd(i,j)d(i,j)=d(i,k)+d(k,j);path(i,j)=path(i,k);endendendendx=13 18 31 26 21 14 17 23 32 38 45 43 39 42 36 27 24 34 40 49 1651;y=sort(x);dl=d(y,y);利用所求得的任意兩點(diǎn)間的最短距離，利用lingo求解最短的hamilton圈的源代碼如2model:sets:city/1.22/:u;link (city,city):dist,x;endset

47、sdata:dist=0 8455.6 11063 8916.3 3113.5 7092.4 10691 5714.3 6687.5 6284.95217.2 12003 7541.9 8488.8 10026 8064.8 9172.7 13562 1264511671 15534 5295.58455.6 0 2607.7 2195.7 5342.2 3296.7 3970.2 8805.6 5488.5 8093.37025.5 5282.1 9350.2 6176.9 7714.3 9873.2 10981 11250 103339359.4 13222 5093.711063 260

48、7.7 0 3872.2 7949.9 5696.1 2097.6 11205 7887.8 9674.69424.8 3409.5 11750 7470.7 5933.2 11454 13380 9469.4 8551.710653 11441 74938916.3 2195.7 3872.2 0 5802.9 1823.9 1774.5 7332.8 4015.7 6620.45552.7 3086.4 7877.4 4704.1 5610.1 8400.4 9508.2 9146.2 8228.67886.5 11118 3620.93113.5 5342.2 7949.9 5802.9

49、 0 3979 7577.4 3883.8 3574.1 3171.42103.7 8889.3 4428.4 5375.4 6912.8 4951.4 6059.2 10449 9531.28557.8 12420 21827092.4 3296.7 5696.1 1823.9 3979 0 3598.4 5508.9 2191.7 4796.53728.8 4910.3 6053.5 2880.2 4417.6 6576.4 7684.3 7953.7 70366062.6 9925.1 1796.910691 3970.2 2097.6 1774.5 7577.4 3598.4 0 91

50、07.3 5790.2 7576.97327.2 1311.9 9651.9 5373 3835.6 9356.9 11283 7371.7 64548555.5 9343.1 5395.45714.3 8805.6 11205 7332.8 3883.8 5508.9 9107.3 0 3317.2 2847.91780.1 9113 4104.9 5051.8 6589.2 4627.8 5735.7 10125 9207.78234.3 12097 4709.26687.5 5488.5 7887.8 4015.7 3574.1 2191.7 5790.2 3317.2 0 2604.8

51、1537 7102 3861.8 4808.7 6346.1 4384.7 5492.6 9882.2 8964.67991.2 11854 1392.16284.9 8093.3 9674.6 6620.4 3171.4 4796.5 7576.9 2847.9 2604.8 01067.8 6265.1 3392.5 2203.9 3741.3 1779.9 5023.3 7277.5 6359.85386.4 9248.8 3996.85217.2 7025.5 9424.8 5552.7 2103.7 3728.8 7327.2 1780.1 1537 1067.80 7332.8 2324.7 3271.7 4809.1 2847.7 3955.5 8345.2 7427.5 6454.110317 2929.112003 5282.1 3409.5 3086.4 8889.3 4910.3 1311.9 9113 7102 6265.17332.8 0 9657.6 4061.1 2523.7 8045 10461 6059.8 5142.2 7243.68031.2 6707.27541.9 9350.2 11750 7877.4 442