送貨線路設(shè)計問題標(biāo)準(zhǔn)答案

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