快遞公司送貨策略數(shù)學(xué)模型論文

1、快遞公司送貨策略快遞公司送貨策略模型摘要本文是關(guān)于快遞公司送貨策略的優(yōu)化設(shè)計(jì)問(wèn)題，即在給定送貨地點(diǎn)和給定設(shè)計(jì)規(guī)劃的前提下，確定所需的業(yè)務(wù)員人數(shù)，每個(gè)業(yè)務(wù)員的行程路線，總的運(yùn)行公里數(shù)及費(fèi)用最省的策略。在問(wèn)題一中，在考慮業(yè)務(wù)員工作時(shí)間及載重限制的兩方面因素的情況下，尋求路程最短的路線優(yōu)化組合，建立TSP（旅行商問(wèn)題）模型，采用最近鄰算法，以原點(diǎn)（配送中心）為起點(diǎn)，通過(guò)距離矩陣依次尋找距離最近的未服務(wù)送貨點(diǎn)，運(yùn)用MATLAB軟件求解出最優(yōu)的路線組合。并根據(jù)遺傳算法的思想，提出了模型優(yōu)化的方案，得到了一個(gè)相對(duì)較優(yōu)的策略，模型結(jié)果為：共需6名送貨員，所需總路程為536千米，所需總時(shí)間為26.44小時(shí)。對(duì)

2、于問(wèn)題二，以業(yè)務(wù)員酬金最少為目標(biāo)，選取最優(yōu)路線時(shí)應(yīng)盡量避免快件回送現(xiàn)象，同樣建立TSP（旅行商問(wèn)題）模型，依次尋找費(fèi)用最小的點(diǎn)的組合，由此尋找最優(yōu)路線組合，優(yōu)化模型結(jié)果為：總路程是620千米，所花總時(shí)間是31.43小時(shí)，共需要送貨員8人，所需最少費(fèi)用為16189.9元。對(duì)于問(wèn)題三，業(yè)務(wù)員工作時(shí)間增加2小時(shí)，以尋找業(yè)務(wù)員人數(shù)最小的路線分配為目標(biāo)，并盡量保證時(shí)間和路程的相對(duì)均衡。由于業(yè)務(wù)員工作時(shí)間對(duì)總的運(yùn)行路線影響較小，所以只需對(duì)業(yè)務(wù)員數(shù)量和各業(yè)務(wù)員送貨線路進(jìn)行調(diào)整，調(diào)整后將業(yè)務(wù)員人數(shù)減少到4人。關(guān)鍵字：TSP（旅行商問(wèn)題） 最近鄰法 交叉算子一、問(wèn)題重述目前，快遞行業(yè)正蓬勃發(fā)展，為我們的生活帶來(lái)

3、更多方便。一般地，所有快件到達(dá)某地后，先集中存放在總部，然后由業(yè)務(wù)員分別進(jìn)行派送；對(duì)于快遞公司，為了保證快件能夠在指定的時(shí)間內(nèi)送達(dá)目的地，必須有足夠的業(yè)務(wù)員進(jìn)行送貨，但是，太多的業(yè)務(wù)員意味著更多的派送費(fèi)用。假定所有快件在早上7點(diǎn)鐘到達(dá)，早上9點(diǎn)鐘開(kāi)始派送，要求于當(dāng)天17點(diǎn)之前必須派送完畢，每個(gè)業(yè)務(wù)員每天平均工作時(shí)間不超過(guò)6小時(shí)，在每個(gè)送貨點(diǎn)停留的時(shí)間為10分鐘，途中速度為25km/h，每次出發(fā)最多能帶25千克的重量。為了計(jì)算方便，我們將快件一律用重量來(lái)衡量，平均每天收到總重量為184.5千克，公司總部位于坐標(biāo)原點(diǎn)處（如圖2），每個(gè)送貨點(diǎn)的位置和快件重量見(jiàn)下表，并且假設(shè)送貨運(yùn)行路線均為平行于坐標(biāo)

4、軸的折線。（1）請(qǐng)你運(yùn)用有關(guān)數(shù)學(xué)建模的知識(shí)，給該公司提供一個(gè)合理的送貨策略（即需要多少業(yè)務(wù)員，每個(gè)業(yè)務(wù)員的運(yùn)行線路，以及總的運(yùn)行公里數(shù)）；（2）如果業(yè)務(wù)員攜帶快件時(shí)的速度是20km/h，獲得酬金3元/km×kg；而不攜帶快件時(shí)的速度是30km/h，酬金2元/km，請(qǐng)為公司設(shè)計(jì)一個(gè)費(fèi)用最省的策略；（3）如果可以延長(zhǎng)業(yè)務(wù)員的工作時(shí)間到8小時(shí)，公司的送貨策略將有何變化？二、模型假設(shè)1.假設(shè)每個(gè)快遞員由派送中心出發(fā)，可連續(xù)工作6小時(shí)，中途不休息，且送貨完畢后必須返回派送中心報(bào)到；2.假設(shè)每個(gè)快遞員獨(dú)立工作，送貨過(guò)程相互不影響；3.假設(shè)每個(gè)送貨點(diǎn)只能由一個(gè)業(yè)務(wù)員送貨且只需經(jīng)過(guò)一次，路線確定后不

5、再更改；4.若一個(gè)業(yè)務(wù)員需運(yùn)送多條路線，中間返回總部取快件所花時(shí)間不計(jì)；5.假設(shè)快遞員送貨的公路均平行于所建立的坐標(biāo)軸；6.假設(shè)快遞員在送貨途中不出現(xiàn)堵車(chē)現(xiàn)象，且沒(méi)有其他的事情耽擱；三、符號(hào)說(shuō)明符號(hào)說(shuō)明任意一條路線（1,2n）任意一條路線上具體某一送貨點(diǎn)（1,2m）總的運(yùn)行公里數(shù)每一條最優(yōu)送貨路線的公里數(shù)每條路線上兩個(gè)送貨點(diǎn)之間的距離快件全部送完所花總時(shí)間業(yè)務(wù)員運(yùn)送途中的速度每一條送貨路線的時(shí)間總的送貨點(diǎn)重量之和每一條路線送貨的重量每一條路線上每一個(gè)送貨點(diǎn)的重量任意一位送貨員總的送貨需要多少錢(qián)送貨員攜帶快件時(shí)的酬金送貨員未攜帶快件時(shí)的酬金業(yè)務(wù)員攜帶快件時(shí)途中的運(yùn)行速度業(yè)務(wù)員未攜帶快件時(shí)途中的運(yùn)

6、行速度三角距離函數(shù)四、問(wèn)題分析本題屬于資源分配優(yōu)化問(wèn)題，要求根據(jù)資源限制和約束條件來(lái)建立一個(gè)合理的郵件派送模型。在問(wèn)題一中，要求我們根據(jù)時(shí)間和重量等方面的約束條件，建立合理的郵件派送路徑，使得運(yùn)行線路最短且使用盡可能少的業(yè)務(wù)員。分析題目條件知道影響模型的主要因素有：1.業(yè)務(wù)員每天工作不可超過(guò)6小時(shí)；2.業(yè)務(wù)員每次出發(fā)至多可帶25千克的快件；3.公司需在9:00-17:00間將184.5千克的貨物分送到雜亂無(wú)序的30個(gè)送貨點(diǎn)。因此，我們需要建立最短送貨路徑的數(shù)學(xué)模型，首先，應(yīng)用Dijkstra算法求解出坐標(biāo)原點(diǎn)（公司總部）到各送貨點(diǎn)的最短路距離矩陣D1；利用TSP模型中的最近鄰法確定滿足條件的8

7、條最短路徑并依據(jù)各線路送貨時(shí)間進(jìn)行送貨人員的分配；利用順序插入交叉算子對(duì)模型一提出優(yōu)化方案。問(wèn)題二中，題目增加了業(yè)務(wù)員空載和重載的酬金以及速度的條件，要求公司設(shè)計(jì)一個(gè)費(fèi)用最省的策略。因業(yè)務(wù)員重載的費(fèi)用高于空載費(fèi)用，而模型一僅給出路線最短，不能滿足問(wèn)題二需求，所以對(duì)問(wèn)題二提出費(fèi)用優(yōu)化方案，即根據(jù)費(fèi)用計(jì)算方式，運(yùn)用最近鄰法尋找離原點(diǎn)（配送中心）費(fèi)用最少的點(diǎn)，依次類(lèi)推，找出費(fèi)用最省的路徑組合并計(jì)算出所需費(fèi)用；根據(jù)路徑組合和運(yùn)送時(shí)間，在滿足問(wèn)題一約束條件的基礎(chǔ)上重新分配送貨人員。問(wèn)題三中，將業(yè)務(wù)員的工作時(shí)間延長(zhǎng)到每天8小時(shí)，求解公司的運(yùn)送策略將如何改變。業(yè)務(wù)員工作時(shí)間的調(diào)整對(duì)于總的運(yùn)行路線的影響并不大

8、，只需對(duì)業(yè)務(wù)員的數(shù)量已及各業(yè)務(wù)員的安排路線進(jìn)行調(diào)整即可。五、模型建立與求解5.1問(wèn)題一模型建立與求解5.1.2模型的建立在問(wèn)題一中，要求在每個(gè)業(yè)務(wù)員每天平均工作時(shí)間不超過(guò)6小時(shí)且必須從早上9點(diǎn)開(kāi)始到當(dāng)日17點(diǎn)（8小時(shí)內(nèi)）全部派送完畢;平均每天送貨總重量為184.5千克，每人每次出發(fā)最多可帶25千克。如果將兩點(diǎn)之間的路線距離附為這兩點(diǎn)橫縱坐標(biāo)之和，比如， 這兩點(diǎn)，則次兩點(diǎn)間的距離為： （5.1.1）用此方法結(jié)合MATLAB求出任意兩配送點(diǎn)的距離矩陣如下（圖5.1）：圖5.1 距離矩陣D該問(wèn)題為規(guī)劃模型，根據(jù)題意，結(jié)合距離矩陣D，設(shè)定目標(biāo)函數(shù)為： （5.1.2）即為送貨總路線的最短路程。其約束條件

9、為：1、每條線路上個(gè)需求點(diǎn)需求量之和不超過(guò)業(yè)務(wù)員的最大負(fù)荷量： （5.1.3）2、每個(gè)業(yè)務(wù)員所有配送路徑來(lái)回的時(shí)間不能超過(guò)業(yè)務(wù)員一天最長(zhǎng)的工作時(shí)間： （5.1.4）3、每一條送貨路線上送貨點(diǎn)數(shù)不超過(guò)總送貨點(diǎn)數(shù)： （5.1.5）4、所有點(diǎn)都能夠被配送到： （5.1.6）5、總的送貨路線不超過(guò)每人送一個(gè)一個(gè)地點(diǎn)： （5.1.7）綜上：最終模型建立如下 （5.1.8） （5.1.9） 為方便快件公司進(jìn)行人員分配和路線選擇，需計(jì)算每天路徑的送貨時(shí)間及派送完所有快件所花總時(shí)間 （5.1.10） （5.1.11）5.1.2利用最近鄰法求最短送貨路徑組合經(jīng)過(guò)分析，本題屬于業(yè)務(wù)員路徑問(wèn)題，即VRP問(wèn)題，從本質(zhì)

10、上說(shuō)，TSP（旅行商問(wèn)題）是VRP的基本問(wèn)題，因此，本文以TSP思想中的一種最近鄰算法為根據(jù)，結(jié)合題目約束條件，利用MATLAB求解出業(yè)務(wù)員工作的最短路徑。TSP問(wèn)題是典型的組合優(yōu)化問(wèn)題，問(wèn)題要求求得一條遍歷所有城市的最短路徑，是一個(gè)易于描述但難于處理的NP-HARD問(wèn)題。TSP問(wèn)題在交通運(yùn)輸、計(jì)算機(jī)網(wǎng)絡(luò)、電路設(shè)計(jì)以及物流配送等領(lǐng)域內(nèi)有著廣泛的應(yīng)用，目前，其主要算法主要有遺傳算法、貪婪算法、模擬退火法及最近鄰法等諸多方法。最近鄰算法是TSP近似算法中最簡(jiǎn)單直觀的一種，其主要思想為：任取一點(diǎn)作為出發(fā)點(diǎn)，每次取最近的一個(gè)點(diǎn)加入到最優(yōu)解中，一直到所有點(diǎn)皆已進(jìn)入解中。首先根據(jù)距離矩陣D找到距離送貨中心

11、最近的一個(gè)未服務(wù)送貨點(diǎn)，則分配一條路線，再找出距離最近的另外一個(gè)未服務(wù)的送貨點(diǎn)，對(duì)每一個(gè)服務(wù)店同理依次尋找出，同時(shí)，每經(jīng)過(guò)一個(gè)服務(wù)點(diǎn)對(duì)該服務(wù)點(diǎn)郵件的重量進(jìn)行累加，即，直到此路線中所經(jīng)過(guò)的所有送貨點(diǎn)的郵件累計(jì)重量，則以上包含的點(diǎn)的組合即為該路線的路徑。依據(jù)上述原理，運(yùn)用MATLAB軟件（程序詳見(jiàn)附件一）可得到8條最短路徑，由此分析配送路線及分配表如下表：表一：模型一路線分配表路線i路徑總時(shí)間(h)總路程(km)總重量(kg)10-1-3-4-51.95 3224.020-2-6-7-8-9-234.52 8824.530-10-11-122.34 4623.340-16-17-20-14-133

12、.23 6023.550-22-21-15-193.39 6824.260-18-24-253.22 6824.770-27-263.37 7622.080-29-28-304.42 9818.3合計(jì)26.44536184.5注：0為配送中心將以上模型求解得到的路線射線圖可用網(wǎng)絡(luò)圖象表達(dá)，如下（圖5.2）：圖5.2 模型一路線射線圖 則每條路徑的具體路線如下（圖5.3）：圖5.3 模型一路線圖在保證所有快件準(zhǔn)時(shí)送達(dá)各個(gè)送貨點(diǎn)的情況下，合理安排路線及送貨員，使得所需送貨員的人數(shù)最少，線路及人員安排情況如下表：表二：模型一人員分配表送貨員R123456合計(jì)路線L24681、53、7-總時(shí)間(h)4

13、.523.233.224.425.345.7126.44總重量(kg)24.523.524.718.348.245.3184.5總路程(km)88606898100122536綜上，可得該模型所構(gòu)建的路線共需6名送貨員，快件完全送完所需總路程為536千米，所需總時(shí)間為26.44小時(shí)。該模型較簡(jiǎn)單直觀，但也存在不足。在路徑選擇時(shí)，當(dāng)其中某一點(diǎn)被路線選定后，該點(diǎn)將不作為接下來(lái)的任意一條路線的備選送貨點(diǎn)，每一條路線均為當(dāng)前條件下的最優(yōu)路線，將所有路線組合后不一定是整體送貨點(diǎn)的最優(yōu)路線，即局部最優(yōu)并非整體最優(yōu)。為提高工作效率，使所走總路程更短、時(shí)間更少，我們對(duì)上述模型進(jìn)行了優(yōu)化。5.1.3利用順序插入

14、交叉算子（OIC）優(yōu)化模型一順序插入交叉算子是針對(duì)TSP問(wèn)題的特點(diǎn)，在遺傳算法的交叉運(yùn)算過(guò)程中設(shè)計(jì)的三角距離差函數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn)，運(yùn)用貪婪策略思想，提出的一種新的交叉算子，該算子有效的利用了局部信息，并且能很好的繼承父代優(yōu)秀的基因。順序插入交叉算子的基本思想是：對(duì)于兩個(gè)待交叉的染色體，將一個(gè)作為基本染色體，另一個(gè)作為參考染色體，按照在參考染色體中的送貨點(diǎn)間的鄰接順序，利用三角距離差函數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn)，運(yùn)用貪婪策略思想，逐步改變基本染色體的編碼順序，從而使經(jīng)過(guò)交叉得到的兩個(gè)子代染色體的適應(yīng)度最高。優(yōu)化思想：利用順序插入交叉算子，我們將模型一中每一條進(jìn)行染色體編碼定義，如，將上述染色體看成一個(gè)環(huán)，染色

15、體的下一個(gè)送貨點(diǎn)是。定義，設(shè)有3個(gè)送貨點(diǎn),，定義三角距離函數(shù)G(a,b,c)如下： （5.1.12）其中，表示送貨點(diǎn)到送貨點(diǎn)的距離。設(shè)待交叉的雙親為和,設(shè)計(jì)交叉算子其求解步驟如下：1. 將父體作為基本染色體，父體作為參考染色體，在中隨機(jī)找到一個(gè)參考城市；2. 在染色體中找到城市，然后對(duì)函數(shù)值進(jìn)行比較，若： （5.1.13）則染色體保持不變，否則，在染色體中刪除城市，然后再與之間插入，得到新染色體3.依次在參考染色體中取參考城市，重復(fù)步驟2，直至生成子代個(gè)體。4.再將作為基本染色體，將作為參考染色體，重復(fù)上述步驟直至得到最優(yōu)搭配方案。5.2問(wèn)題二模型建立與求解5.2.1模型的建立問(wèn)題二要求根據(jù)題

16、給空載和重載的速度與價(jià)格條件，優(yōu)化送貨路線使得送貨費(fèi)用最小。根據(jù)條件，任意一條送貨路線的費(fèi)用可分為兩部分組成：重載情況下到達(dá)最后一個(gè)送貨點(diǎn)通過(guò)該路線將快件從原點(diǎn)送到該路線上任意一點(diǎn)所需要的路程為： 則所需要的費(fèi)用為 由此得到重載情況下到達(dá)最后一個(gè)送貨點(diǎn)的費(fèi)用為 2.空載情況下由最后一個(gè)送貨點(diǎn)返回配送中心： 綜合1、2兩步，得到任意一條送貨路線的費(fèi)用為 則將貨物送達(dá)完畢的費(fèi)用為 可設(shè)定目標(biāo)函數(shù)為： （5.2.1）上式即為送貨總費(fèi)用的最省的線路。1、每條線路上的需求點(diǎn)需求量之和不超過(guò)業(yè)務(wù)員的最大負(fù)荷量，即： （5.2.2）2、每個(gè)業(yè)務(wù)員所有配送路徑來(lái)回的時(shí)間不能超過(guò)業(yè)務(wù)員一天最長(zhǎng)的工作時(shí)間： （5

17、.2.3）3、所有點(diǎn)都能夠被配送到： （5.2.4）4、每一條送貨路線上送貨點(diǎn)數(shù)不超過(guò)總送貨點(diǎn)數(shù)： （5.2.5）5、總的送貨路線不超過(guò)每人送一個(gè)地點(diǎn)： （5.2.6）綜上：最終模型建立如下. （5.2.7） （5.2.8） 為方便快件公司進(jìn)行人員分配和路線選擇，需計(jì)算每條路徑的送貨時(shí)間和派送完所有快件所花總時(shí)間，以及總的費(fèi)用5.2.2模型的求解根據(jù)題意，本題目屬于求解費(fèi)用最小的組合優(yōu)化模型，同樣利用問(wèn)題一種的最近鄰法，結(jié)合送貨時(shí)間及重量的約束條件，利用路線費(fèi)用計(jì)算公式來(lái)尋找費(fèi)用最小的優(yōu)化模型。首先找到距離送貨中心送貨費(fèi)用最少的一個(gè)未服務(wù)送貨點(diǎn)，則分配一條路線，再找出距離送貨費(fèi)用最小的另外一個(gè)

18、未服務(wù)的送貨點(diǎn)，對(duì)每一個(gè)服務(wù)店同理依次尋找出，同時(shí)，每經(jīng)過(guò)一個(gè)服務(wù)點(diǎn)對(duì)該服務(wù)點(diǎn)郵件的重量進(jìn)行累加，即，直到此路線中所經(jīng)過(guò)的所有送貨點(diǎn)的郵件累計(jì)重量，則以上包含的點(diǎn)的組合即為該路線的路徑。依據(jù)上述原理，運(yùn)用MATLAB軟件（程序詳見(jiàn)附件）可得到9條最短路徑，由此分析配送路線及分配表如下表：表三：模型二路線分配圖路線i路徑總時(shí)間(h)總路程(km)總重量(kg)總費(fèi)用10-9-8-14-20-16-5-6-03.835623.10002234.520-11-10-22-21-03.526623.60002205.630-2-7-13-23-03.67 7223.60001189.8 40-1-3-

19、4-15-03.10 5822.9000858.550-26-03.25 7410.0000118460-12-27-03.17 6824.7000205670-30-28-29-04.72 9818.30002955.180-19-25-02.75 5817.4000152590-17-18-24-03.43 70 20.90001981.4合計(jì)31.43 620184.50016189.9每條路徑的路線圖如下（圖5.4）所示：圖5.4 模型二路線圖根據(jù)送貨路線分配表，合理安排送貨員如下表：表四：模型二業(yè)務(wù)員分配表送貨員R12345678合計(jì)路線L1234，85679-總時(shí)間(h)3.833

20、.523.67 5.853.253.174.723.4331.43 總重量(kg)23.100023.600023.600040.300010.000024.700018.300020.9000184.500總路程(km)56667211674689870 620總費(fèi)用（元）2234.52234.52234.52042.52056205620562056綜上，模型二所建立的優(yōu)化模型的總路程是620千米，所花總時(shí)間是31.43小時(shí)，共需要送貨員8人，所需最少費(fèi)用為16189.9元5.3問(wèn)題三模型建立與求解5.3.1模型的建立與求解由于業(yè)務(wù)員的日常工作時(shí)間由6小時(shí)增加到8小時(shí)，因此，需要根據(jù)每天路

21、徑的運(yùn)送時(shí)間對(duì)模型一的路線重新分配業(yè)務(wù)員。模型三人員分配表如下：表五：模型三業(yè)務(wù)員分配表送貨員R1234合計(jì)路線L1，82，34，56，7-總時(shí)間(h)6.376.866.626.592644總重量(kg)42.347.847.746.7184.5總路程(km)130134128144536綜上，業(yè)務(wù)員工作時(shí)間調(diào)整后，共需業(yè)務(wù)員4人。六、模型的評(píng)價(jià)與改進(jìn)6.1模型的評(píng)價(jià)6.1.1模型的優(yōu)點(diǎn)在模型建立的過(guò)程當(dāng)中，我們將具體問(wèn)題抽象成一個(gè)數(shù)學(xué)目標(biāo)函數(shù)，一方面在結(jié)果上具體分配出了送貨策略，另一方面模型的整個(gè)求解過(guò)程簡(jiǎn)單清晰，便于理解和推廣。在求解分析中將有序路徑問(wèn)題引入到矩陣中，并很好的融合了TSP

22、模型中求最短路徑的思想設(shè)計(jì)出自己的算法，模型的建立簡(jiǎn)單明確，具有針對(duì)性，模型的計(jì)算結(jié)果經(jīng)過(guò)仿真測(cè)試，具有較高的準(zhǔn)確度。最終得出了較為合理的送貨策略并對(duì)模型一提出了基于遺傳算法思想的優(yōu)化理論。6.1.2模型的缺點(diǎn)該模型主要采用TSP（旅行商問(wèn)題）思想中的最近鄰算法，僅在現(xiàn)有條件內(nèi)實(shí)現(xiàn)了局部最優(yōu)，并沒(méi)有達(dá)到整體最優(yōu)的效果，優(yōu)化方案模型不成熟。該模型選擇配送線路不能對(duì)客戶的需求進(jìn)行靈活多變的處理。由于線代的消費(fèi)者的需求傾向于個(gè)性化，引起企業(yè)的生產(chǎn)、銷(xiāo)售和配送也愈來(lái)愈傾向于小批量、多品種、多批次，而該模型更適合需求穩(wěn)定的環(huán)境。參考文獻(xiàn)1 孫海雷，劉瓊蓀，胡上尉。TSP問(wèn)題的順序插入交叉算子J。計(jì)算機(jī)工

23、程與應(yīng)用，2007,43（8）。2 張輝。TSP問(wèn)題的算法與應(yīng)用的研究J。計(jì)算機(jī)應(yīng)用與軟件，2009，26（4）。附錄附錄1.模型求解相關(guān)matlab程序關(guān)鍵字： tsp模型 鄰近算法 狀態(tài)選擇模型求解的相關(guān)數(shù)據(jù)文件文件說(shuō)明數(shù)據(jù)類(lèi)文件：Point.xls 文件存入的是以送貨配發(fā)點(diǎn)為原點(diǎn)所建成的坐標(biāo)體系上的各個(gè)點(diǎn)的相對(duì)坐標(biāo)集合st.xls 文件存入的內(nèi)容為各個(gè)配送點(diǎn)的所需貨物的重量以及貨物送達(dá)的狀態(tài)Dis2.xls 文件存入的內(nèi)容為各個(gè)配送點(diǎn)的距離矩陣表gres.xls由問(wèn)題模型一結(jié)果構(gòu)成的路線矩陣Dis3.xls由距離矩陣和單價(jià)表構(gòu)成的距離單價(jià)矩陣（用于問(wèn)題二的模型）程序類(lèi)文件getallDi

24、s.m文件（工具類(lèi)程序文件） 表現(xiàn)：function s = getallDis()主要功能：求出各個(gè)送貨點(diǎn)的距離舉證，并存入dis.txt源代碼：function s = getallDis()%UNTITLED1 Summary of this function goes here% Detailed explanation goes here% author:managerx=xlsread('point.xls','b3:b33');y=xlsread('point.xls','c3:c33');for i=1:31 fo

25、r j=1:31 a(i,j)=abs(x(i)-x(j)+abs(y(i)-y(j); endendfile=fopen('dis.txt','w'); for i=1:31 for j=1:31 % fprintf(file,','); fprintf(file,',%d',a(i,j); if mod(j,31)=0 fprintf(file,'n'); end end end fclose(file);getDis.m文件（工具類(lèi)程序文件） 表現(xiàn)：function k = getDis(i)主要功能：獲取返

26、還距離；源代碼：function k = getDis(i)%UNTITLED1 Summary of this function goes here% Detailed explanation goes hereif i=1 k=xlsread('dis2.xls','a1:a1');endif i=2 k=xlsread('dis2.xls','a2:a2');endif i=3 k=xlsread('dis2.xls','a3:a3');endif i=4 k=xlsread('dis

27、2.xls','a4:a4');endif i=5 k=xlsread('dis2.xls','a5:a5');endif i=6 k=xlsread('dis2.xls','a6:a6');endif i=7 k=xlsread('dis2.xls','a7:a7');endif i=8 k=xlsread('dis2.xls','a8:a8');endif i=9 k=xlsread('dis2.xls','a9:a

28、9');endif i=10 k=xlsread('dis2.xls','a10:a10');endif i=11 k=xlsread('dis2.xls','a11:a11');endif i=12 k=xlsread('dis2.xls','a12:a12');endif i=13 k=xlsread('dis2.xls','a13:a13');endif i=14 k=xlsread('dis2.xls','a14:a14'

29、;);endif i=15 k=xlsread('dis2.xls','a15:a15');endif i=16 k=xlsread('dis2.xls','a16:a16');endif i=17 k=xlsread('dis2.xls','a17:a17');endif i=18 k=xlsread('dis2.xls','a18:a18');endif i=19 k=xlsread('dis2.xls','a19:a19');en

30、dif i=20 k=xlsread('dis2.xls','a20:a20');endif i=21 k=xlsread('dis2.xls','a21:a21');endif i=22 k=xlsread('dis2.xls','a22:a22');endif i=23 k=xlsread('dis2.xls','a23:a23');endif i=24 k=xlsread('dis2.xls','a24:a24');endif i

31、=25 k=xlsread('dis2.xls','a25:a25');endif i=26 k=xlsread('dis2.xls','a26:a26');endif i=27 k=xlsread('dis2.xls','a27:a27');endif i=28 k=xlsread('dis2.xls','a28:a28');endif i=29 k=xlsread('dis2.xls','a29:a29');endif i=30 k

32、=xlsread('dis2.xls','a30:a30');endif i=31 k=xlsread('dis2.xls','a31:a31');endcaldis.m文件（工具類(lèi)程序文件） 表現(xiàn)：function ans = caldis(s,m,n)主要功能：計(jì)算矩陣的整體路徑源代碼：function ans = caldis(s,m,n)%UNTITLED1 Summary of this function goes here% Detailed explanation goes heredis=;tempdis=0;fo

33、r i=1:m tempdis=0; for j=1:n-1 m=j+1; if s(i,m)>0 tempdis=tempdis+GgetbothDis(s(i,j),s(i,m); dismy=GgetbothDis(s(i,j),s(i,m); tempdis else break; end end if s(i,j+1)=0 tempdis=tempdis+GgetbothDis(s(i,j),s(i,1) else tempdis=tempdis+GgetbothDis(s(i,j+1),s(i,1) end dis(i)=tempdis;end ans=dis; gets.m

34、文件（工具類(lèi)程序文件） 表現(xiàn)：function n = gets(i)主要功能：獲取i到各點(diǎn)的距離矩陣源代碼： function n = gets(i)%獲取i到個(gè)點(diǎn)的各個(gè)點(diǎn)的距離舉證if i=1 s=xlsread('dis2.xls','a1:a31'); endif i=2 s=xlsread('dis2.xls','b1:b31'); endif i=3 s=xlsread('dis2.xls','c1:c31'); endif i=4 s=xlsread('dis2.xls'

35、;,'d1:d31'); endif i=5 s=xlsread('dis2.xls','e1:e31'); endif i=6 s=xlsread('dis2.xls','f1:f31'); endif i=7 s=xlsread('dis2.xls','g1:g31'); endif i=8 s=xlsread('dis2.xls','h1:h31'); endif i=9 s=xlsread('dis2.xls','i1:

36、i31'); endif i=10 s=xlsread('dis2.xls','j1:j31'); endif i=11 s=xlsread('dis2.xls','k1:k31'); endif i=12 s=xlsread('dis2.xls','l1:l31'); endif i=13 s=xlsread('dis2.xls','m1:m31'); endif i=14 s=xlsread('dis2.xls','n1:n31&#

37、39;); endif i=15 s=xlsread('dis2.xls','o1:o31'); endif i=16 s=xlsread('dis2.xls','p1:p31'); endif i=17 s=xlsread('dis2.xls','q1:q31'); endif i=18 s=xlsread('dis2.xls','r1:r31'); endif i=19 s=xlsread('dis2.xls','s1:s31');

38、 endif i=20 s=xlsread('dis2.xls','t1:t31'); endif i=21 s=xlsread('dis2.xls','u1:u31'); endif i=22 s=xlsread('dis2.xls','v1:v31'); endif i=23 s=xlsread('dis2.xls','w1:w31'); endif i=24 s=xlsread('dis2.xls','x1:x31'); endi

39、f i=25 s=xlsread('dis2.xls','y1:y31'); endif i=26 s=xlsread('dis2.xls','z1:z31'); endif i=27 s=xlsread('dis2.xls','aa1:aa31'); endif i=28 s=xlsread('dis2.xls','ab1:ab31'); endif i=29 s=xlsread('dis2.xls','ac1:ac31'); end

40、if i=30 s=xlsread('dis2.xls','ad1:ad31'); endif i=31 s=xlsread('dis2.xls','ae1:ae31'); endCloseDis.m文件 （問(wèn)題一基本模型核心文件） 表現(xiàn)：function n = closeDis(i,st,status)主要功能：在選擇狀態(tài)和貨物重量的限制下，求出與參數(shù)i點(diǎn)距離最近的點(diǎn)n并返回；源代碼：%用于計(jì)算和i點(diǎn)距離最近的點(diǎn)，并返回點(diǎn)的下標(biāo)function n = closeDis(i,st,status)%UNTITLED1 Summa

41、ry of this function goes here% Detailed explanation goes here% i表示要尋找的點(diǎn)% st表示當(dāng)前累計(jì)重量% status:所有貨物點(diǎn)的接受狀態(tài)%step1:尋找與i點(diǎn)距離最近的點(diǎn)且累計(jì)重量不超過(guò)25kg%獲得所有貨物點(diǎn)的坐標(biāo)和標(biāo)號(hào)x=xlsread('point.xls','b3:b33');y=xlsread('point.xls','c3:c33');%獲取所有貨物點(diǎn)的重量k=xlsread('st.xls','b1:b31');a=

42、xlsread('st.xls','a1:a31');%獲取i到個(gè)點(diǎn)的各個(gè)點(diǎn)的距離舉證if i=1 s=0,5,6,9,11,8,14,16,15,12,14,20,20,21,22,21,18,24,28,27,28,27,21,36,34,29,37,34,44,41,46; endif i=2 s=5,0,5,4,6,9,9,11,10,7,13,15,15,16,17,16,15,19,23,22,23,22,20,31,29,24,32,29,39,36,41; endif i=3 s=6,5,0,5,5,4,8,10,9,12,18,18,14,15

43、,16,15,12,18,22,21,22,21,25,30,28,23,31,28,38,35,40; endif i=4 s=9,4,5,0,4,9,9,7,6,7,13,13,11,12,13,12,15,15,19,18,19,18,20,27,25,20,28,25,35,32,37; endif i=5 s=11,6,5,4,0,5,5,5,6,11,17,17,11,10,11,10,11,13,17,16,17,20,24,25,23,18,26,23,33,30,35; endif i=6 s=8,9,4,9,5,0,6,8,11,16,22,22,16,13,14,13,1

44、0,16,20,19,20,25,29,28,26,21,29,26,36,33,38; endif i=7 s=14,9,8,9,5,6,0,6,11,16,22,22,16,11,8,7,6,10,14,13,18,25,29,26,20,15,23,20,30,27,32; endif i=8 s=16,11,10,7,5,8,6,0,5,10,16,16,10,5,6,5,12,10,12,11,12,19,23,20,18,13,21,18,28,25,30; endif i=9 s=15,10,9,6,6,11,11,5,0,5,11,11,5,6,7,10,17,15,13,12

45、,13,14,18,21,19,14,22,19,29,26,31; endif i=10 s=12,7,12,7,11,16,16,10,5,0,6,8,8,9,10,15,22,20,16,15,16,15,13,24,22,17,25,22,32,29,34; endif i=11 s=14,13,18,13,17,22,22,16,11,6,0,6,6,11,16,21,28,26,20,13,14,13,7,22,20,15,23,20,30,27,32; endif i=12 s=20,15,18,13,17,22,22,16,11,8,6,0,6,11,16,21,28,26,2

46、0,11,8,7,7,16,18,13,17,14,24,21,26; endif i=13 s=20,15,14,11,11,16,16,10,5,8,6,6,0,5,10,15,22,20,14,7,8,9,13,16,14,9,17,14,24,21,26; endif i=14 s=21,16,15,12,10,13,11,5,6,9,11,11,5,0,5,10,17,15,9,6,7,14,18,15,13,8,16,13,23,20,25; endif i=15 s=22,17,16,13,11,14,8,6,7,10,16,16,10,5,0,5,12,10,6,5,12,19

47、,23,20,12,7,15,12,22,19,24; endif i=16 s=21,16,15,12,10,13,7,5,10,15,21,21,15,10,5,0,7,5,7,10,17,24,28,25,13,8,16,15,23,20,25; endif i=17 s=18,15,12,15,11,10,6,12,17,22,28,28,22,17,12,7,0,6,10,17,24,31,35,32,16,15,19,22,26,23,28; endif i=18 s=24,19,18,15,13,16,10,10,15,20,26,26,20,15,10,5,6,0,6,15,2

48、2,29,33,30,10,13,15,20,20,21,22; endif i=19 s=28,23,22,19,17,20,14,12,13,16,20,20,14,9,6,7,10,6,0,9,16,23,27,24,6,7,9,14,16,15,18; endif i=20 s=27,22,21,18,16,19,13,11,12,15,13,11,7,6,5,10,17,15,9,0,7,14,18,15,7,2,10,7,17,14,19; endif i=21 s=28,23,22,19,17,20,18,12,13,16,14,8,8,7,12,17,24,22,16,7,0,

49、7,11,8,14,9,9,6,16,13,18; endif i=22 s=27,22,21,18,20,25,25,19,14,15,13,7,9,14,19,24,31,29,23,14,7,0,6,9,21,16,14,9,17,14,19; endif i=23 s=21,20,25,20,24,29,29,23,18,13,7,7,13,18,23,28,35,33,27,18,11,6,0,15,25,20,18,13,23,20,25; endif i=24 s=36,31,30,27,25,28,26,20,21,24,22,16,16,15,20,25,32,30,24,1

50、5,8,9,15,0,22,17,15,10,14,9,10; endif i=25 s=34,29,28,25,23,26,20,18,19,22,20,18,14,13,12,13,16,10,6,7,14,21,25,22,0,5,7,12,10,13,14; endif i=26 s=29,24,23,20,18,21,15,13,14,17,15,13,9,8,7,8,15,13,7,2,9,16,20,17,5,0,8,7,15,12,17; endif i=27 s=37,32,31,28,26,29,23,21,22,25,23,17,17,16,15,16,19,15,9,1

51、0,9,14,18,15,7,8,0,5,7,6,9; endif i=28 s=34,29,28,25,23,26,20,18,19,22,20,14,14,13,12,15,22,20,14,7,6,9,13,10,12,7,5,0,10,7,12; endif i=29 s=44,39,38,35,33,36,30,28,29,32,30,24,24,23,22,23,26,20,16,17,16,17,23,14,10,15,7,10,0,5,6; endif i=30 s=41,36,35,32,30,33,27,25,26,29,27,21,21,20,19,20,23,21,15

52、,14,13,14,20,9,13,12,6,7,5,0,5; endif i=31 s=46,41,40,37,35,38,32,30,31,34,32,26,26,25,24,25,28,22,18,19,18,19,25,10,14,17,9,12,6,5,0; end%找到最小值,在正確的狀態(tài)下尋找最小值minnum,num=min(s); while status(num)=1|(k(num)+st)>25 s(num)=inf; minnum,num=min(s); if minnum=inf break; endendif minnum=inf n=0;else n=num;endshowResult.m文件 （問(wèn)題一基本模型核心文件） 表現(xiàn)：function ans = showResult()主要功能：實(shí)現(xiàn)tsp最優(yōu)路徑選擇算法，并顯示路徑矩陣和重量矩陣源代碼：function ans = showResult() %UNTITLED1 Summary of this function goes here % Detailed explanat