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

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

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

3、為d=|x2-x1|+|y2-y1|。通過多目標(biāo)動態(tài)規(guī)劃找出初步路徑，再通過lingo軟件對各路徑進行優(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，所需總的時間為23.44h。針對問題二,根據(jù)題意，建立單目標(biāo)0-1整數(shù)規(guī)劃的數(shù)學(xué)模型，然后用類似于問題一的方法，建立滿足題意的目標(biāo)函數(shù)以及約束條件，并求得最優(yōu)結(jié)果。

4、最后，對所求解的方案進行修改。所得結(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,最少費用為13830.7元。針對問題三，在問題二的模型基礎(chǔ)上，改變時間的條件約束，因為所需要的總時間不變，而每個業(yè)務(wù)員的工作時間增加為8小時，所以對其工作量重新進行安排，得到結(jié)果為：需要4個快遞員，快遞員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；最后對論文所建模型進行了評價與推廣。關(guān)鍵詞：快遞公司送貨 最優(yōu)化 分區(qū)送貨策略模型 tsp模型 一、問題重述1.1問題背景：目前，快遞行業(yè)正蓬勃發(fā)展，為我們的生活帶來更多方便。一般地，所有快件到達某地后，先集中存放在總部，然后由業(yè)務(wù)員分別進行派送；對于快遞公司，為了保證快件能夠在指定的時間內(nèi)送達目的地，必須有足夠的業(yè)務(wù)員進行送貨，但是，太多的業(yè)務(wù)員意味著更多的派送費用。1.2

6、問題提出：假定所有快件在早上7點鐘到達，早上9點鐘開始派送，要求于當(dāng)天17點之前必須派送完畢，每個業(yè)務(wù)員每天平均工作時間不超過6小時，在每個送貨點停留的時間為10分鐘，途中速度為25km/h，每次出發(fā)最多能帶25千克的重量。為了計算方便，我們將快件一律用重量來衡量，平均每天收到總重量為184.5千克，公司總部位于坐標(biāo)原點處（如圖2），每個送貨點的位置和快件重量見下表，并且假設(shè)送貨運行路線均為平行于坐標(biāo)軸的折線。圖一送貨點快件量t坐標(biāo)(km)送貨點快件量t坐標(biāo)(km)xyxy1832163.521628.215175.86183654187.5111745.547197.815126308153

7、.419954.5311326.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818（1）請你運用有關(guān)數(shù)學(xué)建模的知識，給該公司提供一個合理的送貨策略（即需要多少業(yè)務(wù)員，每個業(yè)務(wù)員的運行線路，以及總的運行公里數(shù)）；（2）如果業(yè)務(wù)員攜帶快件時的速度是20km/h，獲得酬金3元/kmkg；而不攜帶快件時的速度是30km/h，酬金2元/km，請為公司設(shè)計一個

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

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

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

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

12、型考慮用多目標(biāo)動態(tài)規(guī)劃求解。由于問題一中只要求給出一個合理的方案，且未涉及到業(yè)務(wù)員工資問題，故只要滿足條件業(yè)務(wù)員的工作時間上限是6個小時以及每條路線的最大載重量不大于25kg即可，本模型中追加兩個目標(biāo)路程最短 和人員最少?？梢酝ㄟ^以下兩種方法實現(xiàn)：（1）每一個行程的第一個送貨點是距離總部最近的未服務(wù)的送貨點。用這種方法，即可得到一組運行路線，總的運行公里數(shù)，以及總費用。（2）每一個行程的第一個送貨點是距離總部最遠的未服務(wù)的送貨點。然后以該點為基準，選擇距它最近的點，加上約束條件，也可得到一組數(shù)據(jù)。然后比較兩組結(jié)果，通過函數(shù)擬合即可得到最優(yōu)化結(jié)果。5.1.2模型的求解由題意可知，平均每天收到總重

13、量為184.5千克，每個人的最大負重是25kg，即,則可知至少需要8條路線對這些郵件進行運送?？梢酝ㄟ^以下兩種方法實現(xiàn)：（1）每一個行程的第一個送貨點是距離總部最近的未服務(wù)的送貨點。用這種方法，即可得到一組運行路線，總的運行公里數(shù)，以及總費用。（2）每一個行程的第一個送貨點是距離總部最遠的未服務(wù)的送貨點確定業(yè)務(wù)員的送貨路線，采取多目標(biāo)動態(tài)規(guī)劃法，根據(jù)送貨點的位置和快件的質(zhì)量，我們進行送貨點的劃分，劃分時遵循以下的準則：1、 兩個送貨點間距最近；2、 盡量沿這實際道路的方向選取送貨點；3、 使區(qū)域經(jīng)過盡量多的點4、 經(jīng)過的送貨點快件的總質(zhì)量不超過25kg即：目標(biāo)函數(shù)： 約束條件為：方案一：每一個

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

15、24kg，所以將 1，3，4，5點劃分為一個區(qū)域 ，同理我們可以按照上面的方法劃分區(qū)域，可以得到如下的送貨路線線路編號送貨路線路程（公里）負重站點數(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.334.42總

16、計524184.53026.6561 現(xiàn)在對路線進行優(yōu)化：由于論文格式問題，舉例選取第一條路線，現(xiàn)在0-1-3-4-5這四個送貨點之間的最優(yōu)訪問路徑安排就是一個典型的單回路問題?？梢酝ㄟ^單回路運輸模型-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 28 0則站點

17、數(shù)，所用時間，總載重（kg），總路程（km）如下： 線路編號送貨路線路程（公里）負重（千克）站點數(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總計522184.53027.4299優(yōu)化前后的路

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

19、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總計475184.53025.76同方案一，進行優(yōu)化。優(yōu)化后的路線：線路編號送貨路線路程（公里）負重站點數(shù)時間（小時）線路10-29-28-30-23-15-09124.154.473線路20-8-26-27-07624.333.540線路30-19-24-25-068

20、2533.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總計461184.53023.44優(yōu)化前后比較：同樣共有八條路線，根據(jù)所經(jīng)歷的時間進行劃分，確定運送人數(shù)。在工作時間小于6小時的前提下，最終只需要五名快遞員，第三條線路和第八條線路由一人完成 第四條線路和第七條線路由一人完成，第五條線路和第六條線路由一人完成。快遞員1：線路1；快遞員2：線路2；快遞員3：線路3，線

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

22、，此時即為一種合理的方案。類似于問題一的研究方法，可以將本問題的方法分析如下：問題中由于業(yè)務(wù)員所得的費用是最主要的，業(yè)務(wù)員安排、路線選擇都是為了總費用的最小化提供條件，所以應(yīng)首先考慮路費，之后再考慮業(yè)務(wù)員的安排。為了使總能夠費用最少，總的思路是先送貨給離快遞公司最近切塊間最重的送貨點，以此類推，在保證時間、載重量有限的前提下，沿途把快遞送完，最終讓業(yè)務(wù)員最遠點空載返回。根據(jù)這一思路，全部路線業(yè)務(wù)員的重載費用可表示為：從上式可以看出，業(yè)務(wù)員的重載費用是恒定的，又由于總費用為重載與空載費用之和，所以總費用的確定就可以轉(zhuǎn)化為滿足一定條件下的各路線的最遠點的選擇問題。某路線業(yè)務(wù)員經(jīng)過的路徑選擇應(yīng)遵循以

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

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

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

27、67921852.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累計時間不足8小時，可選派一名快遞員分兩次運送。同理，線路6 和9也可以由一名快遞員運送，線路5和線路7選一名快遞員，線路1和線路4、線路2派一名快遞員。所以整個過程只需要4名快遞員。每個快遞員負責(zé)的路

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

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

30、a: !距離矩陣，它并不需要是對稱的; 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): !進入城市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#include#include#define m 1000using namespace std;struct nodeint x;int y;int num;float weight;node v31;int mindis31;bool v

32、d31;void create(ifstream &in,int n)int i;for(i=0;ivi.numvi.xvi.yvi.weight; coutvi.num(vi.x,vi.y) vi.weightt;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;i31;i+)coutvi.num到各點的距離：n;for(j=0;j31;j+) coutd(vi,vj) ;coutendlendl;int next1()int k,min=m,tag=0;float w;for(in

33、t i=1;i31;i+)if(vdi=false&d(v0,vi)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;i31;i+)if(vdi=false&d(vk,vi)min&w+vi.weightvk.x&vi.yvk.y) min=d(vk,vi); m=i; tag=1; if(vdi=false&d(vk,vi)=min&w+vi.weightvm.weight&vi.xvk.x&vi.yvk.y)m=i;tag=1;if(tag) return m;else return 0;void way()int k;float w;k=n