快遞公司送貨策略數(shù)模

1、承 諾 書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從A/B/C中選擇一項(xiàng)填寫）： C 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）： 所屬學(xué)院（請(qǐng)?zhí)顚懲暾娜?/p>

2、）： 自動(dòng)化 參賽隊(duì)員 (打印并簽名) ：1. 2. 3. 日期： 2013 年 8 月 23 日評(píng)閱編號(hào)(教師評(píng)閱時(shí)填寫)：快遞公司送貨策略摘要： 本文是關(guān)于如何優(yōu)化快遞公司送貨策略的問題,即在給定送貨地點(diǎn)和給定設(shè)計(jì)規(guī)范的條件下，確定所需業(yè)務(wù)員人數(shù)，每個(gè)業(yè)務(wù)員的運(yùn)行線路，總的運(yùn)行公里數(shù)，以及費(fèi)用最省的策略。 本文主要從最短路經(jīng)和費(fèi)用最省兩個(gè)角度解決該問題。針對(duì)問題一，利用單目標(biāo)0-1規(guī)劃模型和最佳匹配的原理，將送貨點(diǎn)抽象為頂點(diǎn)，由于街道和坐標(biāo)軸平行，即任意兩頂點(diǎn)之間都有路。在此模型中，將兩點(diǎn)之間的距離為這兩點(diǎn)橫縱坐標(biāo)差的絕對(duì)值之和。比如A（x1，y1），B（x2，y2）兩點(diǎn)，則兩點(diǎn)之間距離為

3、d=|x2-x1|+|y2-y1|。通過多目標(biāo)動(dòng)態(tài)規(guī)劃找出初步路徑，再通過lingo軟件對(duì)各路徑進(jìn)行優(yōu)化。通過分析，其模型結(jié)果為：共需要5名快遞員?？爝f員1： 0-29-28-30-23-15-0；快遞員2： 0-8-26-27-0；快遞員3： 0-19-24-25-0-1-6-5-2-0；快遞員4：0-16-17-18-20-0-3-7-4-0；快遞員5：0-9-11-21-22-10-0-12-13-14-0路程為461km，所需總的時(shí)間為23.44h。針對(duì)問題二,根據(jù)題意，建立單目標(biāo)0-1整數(shù)規(guī)劃的數(shù)學(xué)模型，然后用類似于問題一的方法，建立滿足題意的目標(biāo)函數(shù)以及約束條件，并求得最優(yōu)結(jié)果。最

4、后，對(duì)所求解的方案進(jìn)行修改。所得結(jié)果為：快遞員1走0-1-3-8-13-0-25-26-0；快遞員2走0-2-4-7-14-0；快遞員3走：0-6-5-20-18-30；快遞員4走：0-10-11-21-23-0；快遞員5走：0-16-17-24-28；快遞員6走：0-22-29-0；快遞員7走：0-9-12-19-0-15-27-0；所走路程為616km,最少費(fèi)用為13830.7元。針對(duì)問題三，在問題二的模型基礎(chǔ)上，改變時(shí)間的條件約束，因?yàn)樗枰目倳r(shí)間不變，而每個(gè)業(yè)務(wù)員的工作時(shí)間增加為8小時(shí)，所以對(duì)其工作量重新進(jìn)行安排，得到結(jié)果為：需要4個(gè)快遞員，快遞員1走：0-6-5-20-18-30-

5、0-15-27-0；快遞員2走：0-16-17-24-28-0-25-26；快遞員3走：0-10-11-21-23-0-0-22-29-0；快遞員4走：0-1-3-8-13-0-2-4-7-14-0-9-12-19-0；最后對(duì)論文所建模型進(jìn)行了評(píng)價(jià)與推廣。關(guān)鍵詞：快遞公司送貨 最優(yōu)化 分區(qū)送貨策略模型 TSP模型一、問題重述1.1問題背景：目前，快遞行業(yè)正蓬勃發(fā)展，為我們的生活帶來更多方便。一般地，所有快件到達(dá)某地后，先集中存放在總部，然后由業(yè)務(wù)員分別進(jìn)行派送；對(duì)于快遞公司，為了保證快件能夠在指定的時(shí)間內(nèi)送達(dá)目的地，必須有足夠的業(yè)務(wù)員進(jìn)行送貨，但是，太多的業(yè)務(wù)員意味著更多的派送費(fèi)用。1.2問題

6、提出：假定所有快件在早上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ā)最多能帶25千克的重量。為了計(jì)算方便，我們將快件一律用重量來衡量，平均每天收到總重量為184.5千克，公司總部位于坐標(biāo)原點(diǎn)處（如圖2），每個(gè)送貨點(diǎn)的位置和快件重量見下表，并且假設(shè)送貨運(yùn)行路線均為平行于坐標(biāo)軸的折線。圖一送貨點(diǎn)快件量T坐標(biāo)(km)送貨點(diǎn)快件量T坐標(biāo)(km)xyXy1832163.521628.215175.86183654187.5111745.547197.815126308153.4

7、19954.5311326.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818（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)為公司

8、設(shè)計(jì)一個(gè)費(fèi)用最省的策略；（3）如果可以延長業(yè)務(wù)員的工作時(shí)間到8小時(shí)，公司的送貨策略將有何變化？圖二二、基本假設(shè)(1) 假設(shè)送貨運(yùn)行路線均為平行于坐標(biāo)軸的折線(2) 無塞車現(xiàn)象，即業(yè)務(wù)員送快遞途中不受任何外界因素影響，且業(yè)務(wù)員的休息時(shí)間不包括在最大工作時(shí)間6個(gè)小時(shí)內(nèi)。（3）假設(shè)在問題一中若其中一個(gè)業(yè)務(wù)員跑多條路線時(shí)，中間返回總部后取快（將快件裝上車）所花費(fèi)的時(shí)間不計(jì)(4) 在問題一中假設(shè)空載時(shí)的速度和有貨物時(shí)的速度是相同的都是（5）每個(gè)業(yè)務(wù)員送快遞是獨(dú)立的，每人之間互不影響。（6）不走冤枉路原則（即送貨時(shí)只能向上或者向右走）。三、符號(hào)說明符號(hào)說明單位第j個(gè)送貨點(diǎn)的所需的快件重量kg業(yè)務(wù)員攜帶快件

9、時(shí)，按第i條路線派送快件所需時(shí)間h業(yè)務(wù)員不攜帶快件時(shí)，按第i條路線派送快件所需時(shí)間h業(yè)務(wù)員按第i條路線所花費(fèi)的總時(shí)間h業(yè)務(wù)員送貨的總次數(shù)四、問題分析問題要求給出快遞公司送貨的策略，要求我們根據(jù)不同情況和要求為快遞公司提供合理的送貨策略，題中給出了實(shí)際送貨點(diǎn)的位置和快件重量表，并且抽象到一個(gè)平面的二維坐標(biāo)系中，題中假設(shè)送貨運(yùn)行路線均為平行于坐標(biāo)軸的折線，則我們可以用平行于坐標(biāo)軸的折線連接兩個(gè)送貨點(diǎn)，它們之間的距離為兩坐標(biāo)差的絕對(duì)值.題中還給出了幾個(gè)已知條件和限制條件：1.每個(gè)業(yè)務(wù)員平均工作時(shí)間不超過6小時(shí)；2.在每個(gè)送貨點(diǎn)停留的時(shí)間為10分鐘；3.途中速度為5.每次出發(fā)時(shí)帶的重量不超過；4.平均

10、每天收到的貨物總重量為。送貨問題的難點(diǎn)在于當(dāng)運(yùn)輸能力和送貨點(diǎn)一定的情況下，如何選擇最優(yōu)的送貨路線，而最優(yōu)的目標(biāo)有多個(gè):送貨總路程最短,運(yùn)輸時(shí)間最短,所需業(yè)務(wù)員人數(shù)最少或運(yùn)輸成本最低。在大多數(shù)情況下，由于送貨總路程與運(yùn)輸時(shí)間正相關(guān) 與運(yùn)輸成本負(fù)相關(guān)。因此，為了便于敘述和推導(dǎo)，我們直接選取送貨總路程最短和所需業(yè)務(wù)員最少作為我們優(yōu)化送貨線路的最終目標(biāo)由題意可知，平均每天收到總重量為184.5千克，每個(gè)人的最大負(fù)重是25kg，即,則可知至少需要8條路線對(duì)這些郵件進(jìn)行運(yùn)送。對(duì)于問題一的要求，給該公司提供一個(gè)合理的送貨策略。其中所謂“合理”，我們可以理解為業(yè)務(wù)員盡量少，每個(gè)業(yè)務(wù)員的運(yùn)行路線盡量短，完成任務(wù)

11、的時(shí)間盡量短。再以這個(gè)要求為原則進(jìn)行方案設(shè)計(jì)。對(duì)于問題二只是業(yè)務(wù)員的攜帶快件時(shí)的速度與不攜帶時(shí)的不同,并且提到了業(yè)務(wù)員的酬金并且要求費(fèi)用最省,其他條件沒變,我們可以在解決問題一后利用它得到的結(jié)果，對(duì)問題二的最優(yōu)策略進(jìn)行設(shè)計(jì)與安排。對(duì)于問題三，將前面所限定的每個(gè)業(yè)務(wù)員每天最多工作6小時(shí)改成了8小時(shí)。這一條件的改變，對(duì)送貨路徑并沒有太多影響，只是業(yè)務(wù)員工作的分配會(huì)發(fā)生改變，事實(shí)上問題三是問題一和二的衍生。 根據(jù)實(shí)際要求，建立出單目標(biāo)0-1規(guī)劃模型，分別針對(duì)三個(gè)問題列出目標(biāo)函數(shù)和約束條件，然后利用軟件進(jìn)行求解，得出最終結(jié)論，并進(jìn)行相關(guān)的模型評(píng)價(jià)與推廣。五、模型的建立與求解5.1問題15.1.1模型的

12、建立本模型考慮用多目標(biāo)動(dòng)態(tài)規(guī)劃求解。由于問題一中只要求給出一個(gè)合理的方案，且未涉及到業(yè)務(wù)員工資問題，故只要滿足條件業(yè)務(wù)員的工作時(shí)間上限是6個(gè)小時(shí)以及每條路線的最大載重量不大于25kg即可，本模型中追加兩個(gè)目標(biāo)路程最短 和人員最少?？梢酝ㄟ^以下兩種方法實(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é)果，通過函數(shù)擬合即可得到最優(yōu)化結(jié)果。5.1.2模型的求解由題意可知，平均每天

13、收到總重量為184.5千克，每個(gè)人的最大負(fù)重是25kg，即,則可知至少需要8條路線對(duì)這些郵件進(jìn)行運(yùn)送?？梢酝ㄟ^以下兩種方法實(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)確定業(yè)務(wù)員的送貨路線，采取多目標(biāo)動(dòng)態(tài)規(guī)劃法，根據(jù)送貨點(diǎn)的位置和快件的質(zhì)量，我們進(jìn)行送貨點(diǎn)的劃分，劃分時(shí)遵循以下的準(zhǔn)則：1、 兩個(gè)送貨點(diǎn)間距最近；2、 盡量沿這實(shí)際道路的方向選取送貨點(diǎn)；3、 使區(qū)域經(jīng)過盡量多的點(diǎn)4、 經(jīng)過的送貨點(diǎn)快件的總質(zhì)量不超過25kg即：目標(biāo)函數(shù)： 約束條件為：方案一

14、：每一個(gè)行程的第一個(gè)送貨點(diǎn)是距離總部最近的未服務(wù)的送貨點(diǎn)。開始找離原該點(diǎn)最近的點(diǎn)v，且該點(diǎn)的訪問標(biāo)志設(shè)為被訪問，該點(diǎn)快遞重量為w，輸出該點(diǎn)。找點(diǎn)v最近的點(diǎn)，快遞重量為w1，且w1+w<25，當(dāng)其不成立時(shí)找次遠(yuǎn)點(diǎn)。NY找不到符合條件的點(diǎn) 時(shí)找到符合條件的點(diǎn)，且不止一個(gè)時(shí)選擇快遞重量最重的那個(gè)點(diǎn)，訪問標(biāo)志設(shè)為被訪問，并輸出該點(diǎn)，賦值給v，且w=w+w1；取原點(diǎn)為0 點(diǎn)，離最近的送貨點(diǎn)是1點(diǎn)，離1點(diǎn)最近的時(shí)3點(diǎn)，離3點(diǎn)最近的4點(diǎn) ，離 4點(diǎn)最近的是5點(diǎn)，這時(shí)我們發(fā)現(xiàn)離5點(diǎn)最近的是2點(diǎn)，但根據(jù)條件2 點(diǎn)的快件總量為8.2kg，加上1、2、3、4、5點(diǎn)的重量已經(jīng)超過了25kg。而這時(shí)的1，3，4，

15、5 的重量之和為24kg，所以將 1，3，4，5點(diǎn)劃分為一個(gè)區(qū)域 ，同理我們可以按照上面的方法劃分區(qū)域，可以得到如下的送貨路線線路編號(hào)送貨路線路程（公里）負(fù)重站點(diǎn)數(shù)時(shí)間（小時(shí)）線路10-1-3-4-5-0322441.946線路20-2-6-7-13-04424.242.4267線路30-9-8-12-10-04222.942.3467線路40-16-17-20-14-15-23-09023.564.6線路50-11-22-21-19-07424.933.46線路60-27-26-0762223.7067線路70-18-24-25-06824.733.75線路80-29-28-30-09818

16、.334.42總計(jì)524184.53026.6561 現(xiàn)在對(duì)路線進(jìn)行優(yōu)化：由于論文格式問題，舉例選取第一條路線，現(xiàn)在0-1-3-4-5這四個(gè)送貨點(diǎn)之間的最優(yōu)訪問路徑安排就是一個(gè)典型的單回路問題?？梢酝ㄟ^單回路運(yùn)輸模型-TSP模型求解。通過lingo程序（附錄2）解決路線的選擇。得到第一條路線優(yōu)化后的路線為0-1-3-4-5-0。 用以上方法可以得到其它的路線（1）013450（2）0 2 13 7 6 0（3）0 10 12 8 9 0（4）0 16 17 20 14 15 23 0（5）0 11 19 2 1 22 0（6）0 27 26 0（7）0 18 24 25 0（8）0 29 30

17、 28 0則站點(diǎn)數(shù)，所用時(shí)間，總載重（kg），總路程（km）如下：線路編號(hào)送貨路線路程（公里）負(fù)重（千克）站點(diǎn)數(shù)時(shí)間（小時(shí)）線路10-1-3-4-5-0322441.9467線路20-2-6-7-13-04324.242.3866線路30-9-8-12-10-04222.942.3467線路40-16-17-20-14-15-23-09023.564.6線路50-11-22-21-19-07224.933.38線路60-27-26-0762223.7067線路70-18-24-25-06824.733.75線路80-29-28-30-09618.334.34總計(jì)522184.53027.429

18、9優(yōu)化前后的路程和時(shí)間的比較如下 ：時(shí)間比較 由表共有八條路線，其中線路1和線路6累計(jì)時(shí)間不足6小時(shí)，可選派一名快遞員分兩次運(yùn)送。同理，線路2 和3也可以由一名快遞員運(yùn)送。所以整個(gè)過程只需要6名快遞員。快遞員1:線路1，線路6；快遞員2:線路2，線路3；快遞員3:線路 4 ；快遞員4:線路5；快遞員5:線路7；快遞員6: 線路8；方案二：每一個(gè)行程的第一個(gè)送貨點(diǎn)是距離總部最遠(yuǎn)的未服務(wù)的送貨點(diǎn)。分析方法和方案一相似，只不過是從離原點(diǎn)的最遠(yuǎn)端開始優(yōu)化前線路編號(hào)送貨路線路程（公里）負(fù)重站點(diǎn)數(shù)時(shí)間（小時(shí)）線路10-30-29-28-23-15-09624.154.673線路20-26-27-8-075

19、24.333.500線路30-24-25-19-0682533.220線路40-18-17-20-16-06421.443.227線路50-21-22-11-10-9-0522554.673線路60-14-13-12-05222.332.580線路70-7-4-3-03418.731.860線路80-5-6-2-1-03423.742.027總計(jì)475184.53025.76同方案一，進(jìn)行優(yōu)化。優(yōu)化后的路線：線路編號(hào)送貨路線路程（公里）負(fù)重站點(diǎn)數(shù)時(shí)間（小時(shí)）線路10-29-28-30-23-15-09124.154.473線路20-8-26-27-07624.333.540線路30-19-24

20、-25-0682533.22線路40-16-17-18-20-05821.442.987線路50-9-11-21-22-10-0542552.993線路60-12-13-14-05222.332.58線路70-3-7-4-03218.731.78線路80-1-6-5-2-03023.741.867總計(jì)461184.53023.44優(yōu)化前后比較：同樣共有八條路線，根據(jù)所經(jīng)歷的時(shí)間進(jìn)行劃分，確定運(yùn)送人數(shù)。在工作時(shí)間小于6小時(shí)的前提下，最終只需要五名快遞員，第三條線路和第八條線路由一人完成 第四條線路和第七條線路由一人完成，第五條線路和第六條線路由一人完成?？爝f員1：線路1；快遞員2：線路2；快遞員

21、3：線路3，線路8快遞員4：線路4，線路7快遞員5：線路5，線路6；通過以上兩種方法的比較，考慮時(shí)間和路程因素我們可以得出：方案路程（km）時(shí)間（h）方案一52227.4299方案二46123.44方法二更優(yōu)其最優(yōu)路程為461km，所需的總的時(shí)間為23.44h。5.2問題2模型建立在業(yè)務(wù)員送貨次數(shù)為N的情況下，本問題可以轉(zhuǎn)化為利用0-1整數(shù)規(guī)劃對(duì)總的費(fèi)用實(shí)施滿足條件的最小化；再次，對(duì)所建立的單目標(biāo)模型利用Lingo軟件求解，并分析數(shù)據(jù)，列出每條路線上的時(shí)間耗費(fèi)表；最后，根據(jù)上述表中的數(shù)據(jù)，利用最佳匹配的原理，對(duì)業(yè)務(wù)員的人數(shù)安排進(jìn)行重新調(diào)配，得到總行運(yùn)路程最小情況下，快遞公司所需業(yè)務(wù)員人數(shù)最少的

22、策略，此時(shí)即為一種合理的方案。類似于問題一的研究方法，可以將本問題的方法分析如下：問題中由于業(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)用之和，所以總費(fèi)用的確定就可以轉(zhuǎn)化為滿足一定條件下的各路線的最遠(yuǎn)點(diǎn)的選擇問題。某路線業(yè)務(wù)員經(jīng)過的路徑選擇應(yīng)遵

23、循以下原則：（1）近者優(yōu)先原則。某業(yè)務(wù)員最近起始送貨點(diǎn)的選擇直接關(guān)系到費(fèi)用的多少，所以該業(yè)務(wù)員在沿途往送貨終點(diǎn)站中應(yīng)盡量把較近點(diǎn)的快件送完，不讓下一條路線再把較近點(diǎn)作為起始送貨站。（2）不走冤枉路原則（即只能向上或者向右走）。一方面，離原點(diǎn)（快遞公司）較遠(yuǎn)的送貨點(diǎn)坐標(biāo)應(yīng)分別大于離原點(diǎn)較近送貨點(diǎn)的坐標(biāo)，在各個(gè)坐標(biāo)上均不走回頭路，即按圖（a）中的路線前進(jìn)，而不按路線前進(jìn)：另一方面，由于在路途相等的條件下，重載費(fèi)用要比空載費(fèi)用大得多，因此，盡量讓業(yè)務(wù)員空載行走（3）坐標(biāo)貼近原則。在同一條路線中，離原點(diǎn)較近送貨點(diǎn)的坐標(biāo)僅次于較遠(yuǎn)點(diǎn)的坐標(biāo)。四是，路線較少原則。路線多，一方面，相對(duì)最遠(yuǎn)點(diǎn)的選擇多，跑的空路

24、多，費(fèi)用就多；另一方面，過分地強(qiáng)調(diào)短暫效益，出動(dòng)路線多，會(huì)引起業(yè)務(wù)員的反感，不利于以后的人員控制。根據(jù)上述分析及基本假設(shè)，業(yè)務(wù)員送貨的費(fèi)用可以表示如下：業(yè)務(wù)員攜帶快件時(shí)公司應(yīng)付費(fèi)用為：由于業(yè)務(wù)員不攜帶快件時(shí)的速度是30千米/小時(shí)，酬金2元/千米，因此，業(yè)務(wù)員不攜帶快件時(shí)，公司應(yīng)付費(fèi)用為：根據(jù)題意，業(yè)務(wù)員攜帶與不攜帶快件時(shí)，按第i條路線派送快件所需時(shí)間分別為因此，本問題的時(shí)間約束可以列為 根據(jù)上述分析及基本假設(shè)，本問題的模型可表示為目標(biāo)函數(shù)：約束條件： 根據(jù)模型，通過C+編程（程序見附錄）可得結(jié)果如下表：線路編號(hào)送貨線路時(shí)間（小時(shí)）路程（公里）費(fèi)用負(fù)重（千克）10-1-3-8-13-02.416

25、6742792.922.120-2-4-7-14-02.544969.524.730-6-5-20-18-30-04.66667921852.423.840-9-12-19-02.75541498.221.950-10-11-21-23-03.66667721352.419.260-16-17-24-28-04.33333882261.822.970-22-29-03.75821506.714.980-15-27-03.16667681577.615.490-25-26-03.41667742019.219.661613830.7線路1和線路9累計(jì)時(shí)間不足6小時(shí)，可選派一名快遞員分兩次運(yùn)送。同

26、理，線路4 和8也可以由一名快遞員運(yùn)送。所以整個(gè)過程只需要7名快遞員?？爝f員1: 線路1，線路9，快遞員2:線路2；快遞員3:線路 3 ；快遞員4:線路5；快遞員5:線路6；快遞員6: 線路7；快遞員7，線路4，85.3問題3模型及其求解由于問題三為問題一和問題二的衍生，所以該模型在問題二的基礎(chǔ)上重新考慮時(shí)間這個(gè)約束條件。因此由問題二的模型即可求得問題三的結(jié)果。該模型條件為: 通過C+語言編程（程序見附錄）可得結(jié)果如下表： 路線時(shí)間路程 費(fèi)用線路10-1-3-8-13-02.41642792.9線路20-2-4-7-14-02.544969.5線路30-6-5-20-18-30-04.6666

27、7921852.4線路40-9-12-19-02.75541498.2線路50-10-11-21-23-03.66667721352.4線路60-16-17-24-28-04.33333882261.8線路70-22-29-03.75821506.7線路80-15-27-03.16667681577.6線路90-25-26-03.41667742019.2由表共有九條路線，其中線路3和線路8累計(jì)時(shí)間不足8小時(shí)，可選派一名快遞員分兩次運(yùn)送。同理，線路6 和9也可以由一名快遞員運(yùn)送，線路5和線路7選一名快遞員，線路1和線路4、線路2派一名快遞員。所以整個(gè)過程只需要4名快遞員。每個(gè)快遞員負(fù)責(zé)的路線分

28、別為：快遞員1: 線路3，線路8，快遞員2:線路6、線路9；快遞員3:線路5、線路7 ；快遞員4:線路1、線路2、線路4。6、 模型的評(píng)價(jià)與推廣6.1模型的優(yōu)點(diǎn)（1）模型系統(tǒng)的給出了業(yè)務(wù)員的調(diào)配方案，便于指導(dǎo)工作實(shí)踐。（2）模型簡單明了，容易理解與靈活應(yīng)用。（3）模型的方法和思想對(duì)其他類型也適合，比如災(zāi)情考察、郵局遞送、車輛運(yùn)輸?shù)?，易于推廣到其他領(lǐng)域。（4）本模型方便、直觀，易于在計(jì)算機(jī)上實(shí)現(xiàn)和推廣。比如災(zāi)情考察、郵局遞送、6.2模型的缺點(diǎn)（1）模型給出的約束條件可能也有不太現(xiàn)實(shí)的。（2）對(duì)街道的方向，客戶的快件量的假設(shè)有待進(jìn)一步改進(jìn)。6.3模型的推廣（1）本模型不但適合于快遞公司送貨問題，還

29、是用于一般的送貨以及運(yùn)輸題，只需要稍微改動(dòng)模型即可。（2）模型方便、直觀，可以實(shí)現(xiàn)計(jì)算機(jī)模擬。（3）建模的方法和思想可以推廣到其他類型，如車輛調(diào)度問題等。七、參考文獻(xiàn)1姜啟源，謝金星數(shù)學(xué)模 型 .北京:高等教育出版社 2003.2唐煥文，賀明峰編，數(shù)學(xué)模型引論-3版，北京，高等教育出版社，2005.3 .3快遞公司送貨策略, ， 2013.8.16.八、附錄附錄1：各送貨點(diǎn)之間的距離（含原點(diǎn)）附錄2：問題1路線優(yōu)化:model:sets:city / 1. 5/: u; link( city, city): dist, ! 距離矩陣; x;endsets n = size( city);dat

30、a: !距離矩陣，它并不需要是對(duì)稱的; dist=0 70 115 90 95 70 0 46 21 50 115 46 0 30 32 90 21 30 0 48 95 50 32 48 0;enddata !目標(biāo)函數(shù); min = sum( link: dist * x); FOR( city( K): !進(jìn)入城市K; sum( city( I)| I #ne# K: x( I, K) = 1; !離開城市K; sum( city( J)| J #ne# K: x( K, J) = 1; ); !保證不出現(xiàn)子圈; for(city(I)|I #gt# 1: for( city( J)| J

31、#gt#1 #and# I #ne# J: u(I)-u(J)+n*x(I,J)<=n-1); ); !限制u的范圍以加速模型的求解，保證所加限制并不排除掉TSP問題的最優(yōu)解;for(city(I) | I #gt# 1: u(I)<=n-2 ); !定義X為01變量; for( link: bin( x);End附錄3：問題2，3路線求解：#include<iostream>#include<fstream>#include<cmath>#define M 1000using namespace std;struct nodeint x;int

32、 y;int num;float weight;node v31;int mindis31;bool vd31;void create(ifstream &in,int n)int i;for(i=0;i<n;i+)vdi=false;in>>vi.num>>vi.x>>vi.y>>vi.weight; cout<<vi.num<<"("<<vi.x<<","<<vi.y<<") "<<vi

33、.weight<<'t'int d(node a,node b)return (abs(a.x-b.x)+abs(a.y-b.y);void dis()int i,j;for(i=0;i<31;i+)cout<<vi.num<<"到各點(diǎn)的距離：n"for(j=0;j<31;j+) cout<<d(vi,vj)<<" "cout<<endl<<endl;int next1()int k,min=M,tag=0;float w;for(int i=

34、1;i<31;i+)if(vdi=false&&d(v0,vi)<min) min=d(v0,vi); k=i; w=vi.weight;tag=1; if(vdi=false&&d(v0,vi)=min&&vi.weight>w) k=i; w=vi.weight;tag=1; if(tag) return k;else return 0;int next2(int k,float w) int min=M,tag=0,m,i; for(i=1;i<31;i+)if(vdi=false&&d(vk,vi)

35、<min&&w+vi.weight<=25&&vi.x>vk.x&&vi.y>vk.y) min=d(vk,vi); m=i; tag=1; if(vdi=false&&d(vk,vi)=min&&w+vi.weight<=25&&vi.weight>vm.weight&&vi.x>vk.x&&vi.y>vk.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,distance,tag; vdk=true;w=vk.weight;distance=vk.x+vk.y;money=3.0*w*distance;time=(vk.x+vk.y)/20.0;cout<<'0'<<"->"<<vk.num<&l