送貨線路設計問題標準答案

14送貨路線設計問題的答案1、問題重述現(xiàn)今社會網絡越來越普及，網購已成為一種常見的消費方式，隨之物流行業(yè)也漸漸興盛，每個送貨員需要以最快的速度及時將貨物送達，而且他們往往一人送多個地方，請設計方案使其耗時最少。現(xiàn)有一快遞公司，庫房在圖1中的O點，一送貨員需將貨物送至城市內多處，請設計送貨方案，使所用時間最少。該地形圖的示意圖見圖1，各點連通信息見表3，假定送貨員只能沿這些連通線路行走，而不能走其它任何路線。各件貨物的相關信息見表1，50個位置點的坐標見表2。假定送貨員最大載重50公斤，所帶貨物最大體積1立方米。送貨員的平均速度為24公里/小時。假定每件貨物交接花費3分鐘，為簡化起見，同一地點有多件貨物也簡單按照每件3分鐘交接計算?，F(xiàn)在送貨員要將100件貨物送到50個地點。請完成以下問題。1若將130號貨物送到指定地點并返回。設計最快完成路線與方式。給出結果。要求標出送貨線路。2假定該送貨員從早上8點上班開始送貨，要將130號貨物的送達時間不能超過指定時間，請設計最快完成路線與方式。15要求標出送貨線路。3若不需要考慮所有貨物送達時間限制包括前30件貨物，現(xiàn)在要將100件貨物全部送到指定地點并返回。設計最快完成路線與方式。要求標出送貨線路，給出送完所有快件的時間。由于受重量和體積限制，送貨員可中途返回取貨?？刹豢紤]中午休息時間。2、問題分析送貨路線問題可以理解為已知起點和終點的圖的遍歷問題的合理優(yōu)化的路線設計。圖的遍歷問題的指標路程和到達的時間，貨物的質量和體積，以及最大可以負載的質量和體積。在路線的安排問題中，考慮所走的路程的最短即為最合理的優(yōu)化指標。對于問題二要考慮到所到的點的時間的要求是否滿足題意即采用多次分區(qū)域的假設模型從而找出最優(yōu)的解對于問題三則要考慮到體積和質量的雙重影響，每次到達后找到達到最大的體積和質量的點然后返回，再依次分析各個步驟中可能存在的不合理因素達到模型的進一步合理優(yōu)化得到最合理的解。3、模型假設與符號說明1631、模型的假設（1）、到同一地點的貨物要一次拿上，即不考慮再以后又經過時再帶些貨物（2）、要求達到不超過的時間不包括此次在該點交易的時間。（3）、所用的距離數(shù)據(jù)都精確到米而時間則精確到00001H（4）、同一地點有多件貨物也簡單按照每件3分鐘交接計算。32、符號說明其中I，J1、2、350并且M50KGV134、模型的建立及求解模型一模型二模型三模型四最短路徑模型圖的遍歷模型多區(qū)域最短路多階段最短路17模型一11模型的建立我們?yōu)榱饲蟪龈鱾€點的之間的最短的路徑，使用DIJSTRA算法求解。DIJKSTRA算法是圖論中非常有名的一個算法。圖采用鄰接矩陣的形式描述，W（I,J）表示結點I到結點J間的最短距離，如果沒有直接連通，則為無窮大，計算機中可以用一個很大的數(shù)據(jù)代替（如MATLAB中的INF）。但DIJKSTRA算法只能求出從結點I到其它各結點的最短路徑。算法引入這樣兩個集合S和T，S是那些已經確定了到I結點的最短路徑的結點，T為全集U和S的差集，即那些還未確定最短路徑的結點。而且S的初值是I，T的初值是UI。另外再引入一個標記數(shù)組DN，其中在某一步DK表示當前從I到K的較短路徑，DK的初值為W（I，K）。整個算法過程如下、在T中選擇一個DK最小的結點K，將K并入S，并從任意兩點之間的最短路距離由起始點遍歷路徑回到原點多區(qū)域無返回起點的最短路多階段有返回起點的最短路18T中去掉，如果T為則轉到；、用K結點和T中其余結點進行一遍比較，如果DIDKMKI，則用DKMKI取代原來的DI，重復；、算法結束，此時DK中保存的就是從I到K結點的最短路徑。算法就以這樣非常簡單的形式完成了求解，時間復雜度是ON2，確定了從I到其余各結點的最短路徑。12模型的求解根據(jù)算法和相鄰的點的距離可以用DIJKSTRA求出任意兩點的最短路徑。19圖1相鄰的點的距離使用循環(huán)的結構求出150各個點之間的最短距離。程序1見附錄21可以求出W和AA為最短路徑是的所過的的地點如從O開始到其余50個點的A0074831511812141813131821122321024220291731190313025222623283138214036273437433841364140464240要從O點到16點則要先到23即02316要從O點到23點則要先到17即0172316要從O點到17點則要先到21即021172316而O可以直接到21所以從0到16的最優(yōu)路徑是021172316最短的距離是W（0,16）7493M模型二對于問題一的求解21模型的建立由前30件貨物可以到達的地點可以知道I，J13、14、16、17、18、21、23、24、26、27、31、32、34、36、38、39、40、42、43、45、49。20圖2需要達到的點（紅點標注的）其中共經過21個點，運送30件貨物該30件貨物473KG1，到45點時必須在9點半之前到達而1741215故分成兩個階段不成功，所以分四個階段，求出各個階段的最短距離和到達時的時間即可。目標函數(shù)V0約束條件是T到個點的時間最大值32模型的求解25圖44個階段的圈圖對四個階段分別求出到達的時間，由程序4（附錄24）可知分4個階段1從0出發(fā)經過13、18到24。滿足TLUWU,ILILUWU,IZIUENDENDENDENDLLLFORI1NFORJ1KIFISJLLILLIELSELLIINFENDENDENDLVINFFORI1NIFLLI50|V1BREAKENDNIXXT1DISPT1,M,VA,TINFENDSUMSUMVP,1DISP順序為DISPX,0DISP總路程是64DISPSUMTSUM/1000/243I/60DISP所用時間是DISPTDISP第二階段P1X0M0V0A,PINFFORI150S,TMINAP,MMWT1,2VVWT1,3SUMSUMSIFM50|V1BREAKENDNN1PTXXT1DISPT1,M,VA,TINF65ENDDISP順序為DISPX,0DISP總路程是DISPSUMTSUM/1000/243I/60DISP所用時間是DISPTDISP第三階段P1X0M0V0A,PINFFORI150NS,TMINAP,MMWT1,2VVWT1,3SUMSUMSIFM50|V1BREAKEND66PTXXT1DISPT1,M,VA,TINFNN1ENDSUMSUMVP,1DISP順序為DISPX,0DISP總路程是DISPSUMTSUM/1000/243I/60DISP所用時間是DISPTDISP第四階段P1X0M0V0A,PINFFORI150NS,TMINAP,MMWT1,267VVWT1,3SUMSUMSIFM50|V1BREAKENDPTXXT1A,TINFNN1ENDSUMSUMVP,1DISP順序為DISPX,0DISP總距離是DISPSUMTSUM/1000/243I/60DISP總時間是DISPT26、問題三的優(yōu)化CLCCLEARALLLOADWTXTAWLOADXTXTWX68P1X0M0V0SUM0VAA,PINFFORI150S,TMINAP,MMWT1,2VVWT1,3SUMSUMSPTIFM50|V1BREAKENDNIXXT1DISPT1,M,VA,TINFENDSUMSUMVP,1DISP順序為69DISPX,0DISP總路程是DISPSUMTSUM/1000/243I/60DISP所用時間是DISPTDISP第二階段P1X0M0V0A,PINFFORI150S,TMINAP,MMWT1,2VVWT1,3SUMSUMSIFM50|V1BREAKENDNN1PTXXT170DISPT1,M,VA,TINFENDSUMSUMVP,116304SUMSUMVP,1DISP順序為DISPX,0DISP總路程是DISPSUMTSUM/1000/243I/60DISP所用時間是DISPTDISP第三階段P1X0M0V0A,PINFFORI150NS,TMINAP,MMWT1,2VVWT1,3SUMSUMS71IFM50|V1BREAKENDPTXXT1DISPT1,M,VA,TINFNN1IFT46BREAKENDENDSUMSUMVP,1SUMSUMVP,1DISP順序為DISPX,0DISP總路程是DISPSUMTSUM/1000/243I/60DISP所用時間是DISPTDISP