精选文档快递员的送货策略问题

2015高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）．我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题．我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出．我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性．如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理．我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）．我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A 我们的参赛报名号为（如果赛区设置报名号的话）：A06007001所属学校（请填写完整的全名）：北华大学参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名．以上内容请仔细核对，提交后将不再允许做任何修改．如填写错误，论文可能被取消评奖资格．）日期：2015年9月日赛区评阅编号（由赛区组委会评阅前进行编号）：2015高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：快递员的送货策略问题摘要 在货物运输的过程中，合理的选择货物路线很重要，他不仅可以加快配送速度，提高服务质量，还可以降低配送成本，增加经济效益．本文构建货物路线的规划模型，运用图论思想，Dijkstra算法，经典Floyd算法，利用lingo与MATLAB进行编程求解，给出了最佳的送货路线，另外将货物的分配问题转化成旅行商推销问题，进行编程求解；根据运输路线策略中的成组法，用射线旋转法进行区域划分，以送货员最大承受力为50公斤，货物体积不大于1立方米为依据，利用整体规划进行区域规划，从而得到最优化模型．问题一以最快完成送货任务并返回仓库的路线与方式，分析题知尽可能地缩短路径可以达到尽快完成任务的目标．在题目所给的各个点的坐标基础上，为确定最短路径，先应用Dijkstra算法求解出任意两点的直线距离，运用Floyd算法，借用MATLAB求出任意两点之间的最短距离，应用lingo软件进行优化求解，求得遍历路程结果为125499.5m，时间为493.7min．问题二在问题一的前提下进行了对送货时重量和体积的约束，经过分析，快递员需要在送货途中返回一次仓库，进行补货．根据问题一中最小生成树，根据聚集原则，将区域分成两部分，进行分次求解，第一部分路程为67554.8m,时间为261.9min，第二部分路程为66624.56m，时间为246.8min．关键字：Dijkstra算法；经典Floyd算法；0-1规划法；最小距离一、问题重述小张是某快递公司送货员，其负责送货的区域如图，该区域包含50个送货地点，仓库在图中O点处．送货时，小张只能沿图中的道路行进，没有其他道路可选．送货时，小张的平均行进速度为24公里/小时，每件货物交接时间3分钟（如同一地点有多件货物，交接时间也按每件3分钟计算）．根据某天小张的送货清单，请你们帮助他解决下列问题：设计最快完成送货任务并返回仓库的路线与方式，给出结果并注明送货路线．实际上小张每次送货时，只能装载重量不超过50公斤，体积不超过1立方米的货物．这样，小张不能将全天的货物一次取走，只能中途返回仓库取货．在这种情况下，设计最快完成送货任务并返回仓库的路线与方式，给出结果并注明送货路线．以上两种情况都不考虑中午休息时间．图1送货地点示意图表1：送货地点坐标编号X坐标（米）Y坐标（米）0775050001124558150215430873031456559204112015115515500681567925717577645152208744032309895563510861518351184044251213475884013623515435146135134201563655140166475115651717655085184935872019563511652069451235219401297022590066052367579902415005133802513320215526716513800276045144352813720597529550056153015440145553166708210321080083703337007655341785182035129504065361533012265374390208538783510145392350110704011815941541510014750421855273543106752595444490959045395064904645853610471450826548462569549150013670501002513875问题分析在日常生活中购物送货问题，如何在有效的时间内送到货物且能最大限度的节约成本，合理规划过程中的最短路线．我们需要在考虑题的过程中重点分析各个点的路径问题，送货员能承受的重量体积等因素条件下，规划处最优路线．首先我们利用excel处理数据，求出总重量，总体积等数据，在求出每条路的总距离，对于送货员能承受的重量等情况，我们利用射线旋转法进行划分，0-1型规划法对问题进行巧妙的转化，从而求解．对于问题一：不考虑装载重量和物体体积，最佳运送方案就为找出一条走遍所有送货点然后返回出发点的最短路线．根据表1和表2所给出的送货点位置信息即可计算出所有直通点的距离．根据以上数据即可利用Floyd算法算出任意两点间的距离矩阵．然后运用lingo软件就可以得到最优路线．对于问题二：由于质量和体积的约束，综合总的质量与体积得出送货员将货物的分配问题转化成旅行商推销问题，进行编程求解，根据运输路线策略中的成组法，用射线旋转法进行区域划分，以送货员最大承受力为50公斤，货物体积不大于1立方米为依据，利用整体规划进行区域规划，从而得到最优化模型．三、问题假设假设送货员只能沿如图路线图行驶，不能走其他的任何路线．在联通线路中，送货员可自由选择路口．交接货物只需要3分钟，行进速度总是24公里/小时，路上行进畅通无意外阻碍．如果要从任意一点出发前往另一点，送货员必然选择最短路径．送货员路程中都是匀速行走．不考虑送货员中午休息及中途休息．四、符号说明表示送货点i到送货点j之间的距离表示最短距离和表示矩阵中任意的位置，0-1决策变量,表示送货的路线表示经过路程所花费的总时间表示路程表示从个点到点运送货物的质量表示从个点到点运送货物的体积五、模型建立与求解5.1模型分析不考虑装载重量和物体体积，所以最佳运送方案就为找出一条走遍所有送货点然后返回出发点的最短路线．根据表1和表2所给出的送货点位置信息即可计算出所有直通点的距离．（程序见附录3）根据以上所得数据，即可采用0-1规划模型寻找送货点间的最短路径．图2坐标点之间的关系5.2模型的建立利用图论思想，将已连接的送货点一一标明，送货点抽象为下列图的顶点．任意两顶点间都有通路．讲两点之间的路线权值赋为，两坐标间的距离．这样送货点的分布图就构成了加权网络图见图（2）．问题就转化为在给定加权网络图中寻找从原点0出发满足做给约束条件下，行遍所有顶点，并再回到0点，使得总权最小．设假最佳送货路线问题由送货点1，2，3…,n组成，W表示送货点i到送货点j之间的距离决策变量定义为：1，选择从送货点i到送货点j,X=0,否则，其线性（整数）规划模型为：引入0-1决策变量xij=0，最短路经过弧（i,j），xij考虑最短路径唯一和，必须从O点出发并反回O作为约束条件．目标函数是路径上所有弧长度之和最小，我们建立0-1规划模型： 1.上式目标函数（1）给出了送货路线的总长度．2.约束（2）保证由送货点i到送货点j，3.约束（3）保证i只能到一个送货点．4.（4）式保证了经过全部送货点．在以上约束下用MATLAB和lingo软件求解最佳路线．5.3模型的求解（1）求任意两点之间的直线距离：根据Dijkstra算法，并运用MATLAB，可求出任意两点间的直线距离（程序见附录3，结果见附录4）．从中选出可行解：序号地点1地点2距离1062182.022081796.9430151392.0641401417.6852121958.0962363536.417351294.3184212152.549521916.28105122863.78116222103.69127261948.93138101823.91148152191.74158464775.74169202197.641710201774.511811233568.811911421971.382012401756.772113411325.682214261097.862316141885.92416381966.222516394154.592617233102.762717422351.722818331630.782919201311.8730194811143120101774.51322142152.543321234987.053422151537.033522182324.753623333043.493724301252.943824505004.543925351945.514025432681.354126271287.494227131017.894327394997.62442851968.25452865917.944629221067.76473077823.324830362292.64493122178056513263113.465232383455.75333173217.015433181630.785534372618.44563565909.555735282059.375836302292.645937461537.426038312258.646139212366.036239442601.926339492735.426440165756.576540321456.796640504805.786741131325.696841493758.516942111971.38704234917.6771436534273734392607.687443102195.727544332090.057645291779.927746173182.467846292203.927947332331.228048371409.73814941494.138250164235.48350262860.98（2）求任意两点间的最短距离：运用经典Floyd算法，并借助MATLAB，可解出任意两点间的最短距离（程序见附录5，结果见附录6）．（3）求快递员遍历的最短距离：lingo是一种用来解规划的常用软件，故本问采用lingo进行求解（程序见附录7）．由lingo计算出的结果可以给出送货路线如下：0→15→8→10→20→9→19→48→37→46→17→34→42→11→23→33→47→44→18→22→29→45→31→38→16→14→7→26→41→13→17→50→24→30→36→2→5→3→12→32→1→40→21→4→49→39→43→25→35→28→6→0总路程为125499.5m,时间为493.7min5.4问题二模型的建立与求解模型建立：;;;；；；；模型的求解：送货员将60个包裹最快送到50个指定地点，经过计算60个包裹的总质量为87.73公斤，总体积为1.7588立方米，送货员每次携带货物质量不能超过50公斤，体积不能超过1立方米，可以将路线分成两个片区根据最小生成树，和聚集原则还有根据分组，我们在每一个最短区域根据分动态线性规划寻找最短最佳路线，根据运筹学中满载率的规定为80%-90%，为使用时时间最短，两个子区域区域区分如下：区域10，4，8，9，10，11，15，17，18，19，20，21，22，23，29，31，33，34，37，39，42，43，44，45，46，47，48，49区域20，1，2，3，5，6，7，12，13，14，16，24，25，26，27，28，30，32，35，36，38，40，41，50根据遍历程序，解得区域一的最短遍历路径，即路径1为：0→15→8→10→43→9→20→19→48→37→46→17→42→34→42→11→23→21→4→49→39→44→33→47→33→18→22→29→45→29→22→31→22→15→0；第一区域路程为67554.8m，用时261.9min．解得区域二的最短路径，即路径2为：0→6→35→25→35→28→5→3→5→2→36→30→24→50→26→7→26→27→13→41→13→27→26→14→16→38→32→40→12→40→1→32→6→0第二区域路程为66624.56m，时间为243.8min．六、模型的优缺及评价6.1模型的评价在现实的物流配送中，人们多数是按照经验去制定送货路线．而此模型在运用满载率原理对送货区域进行合理化而科学划分的基础上，用0-1整数规划的方法对路线进行优化，得到最优的送货路线和最优的分配方案，非常贴近生活实际．对现实的物流派送有较强的指导意义．以此，物流公司或其他机构可以根据这个采用划分区域，进行线性规划的方法提高自己的送货情况的路径优化，可以提高自己的效率，降低成本，提高企业竞争率．有利于降低社会交易话的成本．6.2模型优点1、模型是从简单到复杂一步一步的进行的，使得更加贴近实际2、本文模型简单，算法直观，容易编程．3、本文注重数据的处理和储存方式，大大提高了规划效率．6.3模型缺点在建模和编程过程中，使用数据只是现实数据的一种近似值因而得出的可能与现实有一定差距，不过差强人意，理论要求强计算比较复杂，这个模型在现实中运用可能还有一些其他因素影响，所以实际运用中需进一步考虑．七、参考文献1．杨丹,赵海滨.MATLAB从入门到精通[M].北京:中国铁道出版社,2013.2.谢金星,薛毅编.优化建模与lingo[M].北京:清华大学出版社,20053.薛毅.数学建模[M].北京:北京工业大学出版,20044.张杰.运筹学模型与实验[M].北京:中国电力出版社,20075.赵静.数学建模与数学实验[M].北京:高等教育出版社,20036.龚劬.图论与网络最优化算法[M].重庆:重庆大学出版,2009附录附录1：表2：道路连通信息序号地点1地点210620830154140521262367358421952105121162212726138101481515846169201710201811231911422012402113412214262316142416382516392617232717422818332919203019483120103221433212334221535221836233337243038245039253540254341262742271343273944285452864629224730748303649312250321513265232385333175433185534375635657352858363059374660383161392162394463394964401665403266405067411368414969421170423471436724387343974431075443376452977461778462979473380483781494825016835026附录2表3：送货清单序号送货地点重量（公斤）体积（立方米）113.090.0145221.900.0332320.460.0133421.960.0406531.340.0043640.900.0339751.420.0462861.670.0559971.280.05571081.730.03481191.340.043112101.730.011413110.580.029914110.990.024015121.450.020616132.790.030317141.220.034418151.230.039919161.420.005120171.820.034821181.200.059022191.190.025023200.900.030024211.590.005525221.650.025226231.450.008027240.940.031228251.620.049229262.130.037930271.110.026631271.030.049732281.550.020933291.770.029034291.990.002935301.710.004236311.120.019137321.180.028638331.400.045739341.520.011840352.330.015641351.300.042042360.480.048643361.370.027144371.140.002445381.360.018346390.870.004147401.700.049148411.710.014449421.170.016050430.060.050751442.370.030352451.180.013353460.900.034554461.310.024855472.050.059156482.510.025757491.110.042958491.550.058659501.770.056660502.120.0093附录3： x=[7750,12455,15430,14565,1120,15500,7925,7645,7440,8955,8615,840,13475,6235,6135,6365,6475,1765,4935,5635,6945,940,5900,675,15005,13320,7165,6045,13720,5500,15440,6670,10800,3700,1785,12950,15330,4390,7835,2350,11815,5100,1855,10675,4490,3950,4585,1450,4625,1500,10025];y=[5000,8150,8730,5920,15115,6815,7175,15220,3230,635,1835,4425,8840,15435,13420,5140,11565,5085,8720,1165,1235,12970,6605,7990,13380,2155,13800,14435,5975,5615,14555,8210,8370,7655,1820,4065,12265,2085,10145,11070,9415,14750,2735,2595,9590,6490,3610,8265,695,13670,13875];distance=zeros(length(x));fori=1:length(x)distance(i,:)=sqrt((x-x(i)).^2+(y-y(i)).^2);end附录405662.1138537.8746876.81812094.22……10687.919161.9465662.11303031.0113070.01613303.89……12267.136219.3678537.8743031.01102940.12315669.85……147807462.2426876.8183070.0162940.123016288.53……15190.689159.34612094.2213303.8915669.8516288.530……1494.138990.9197959.6943324.7931916.2791294.31416603.45……15588.178934.1612182.0294633.7387664.4016757.56110457.13……9135.9547021.39610220.548551.08210135.411592.086525.845……6337.472733.7571796.9427025.4279700.0057615.88613460.89……12011.5410954.374528.2728290.06810366.037707.35516463.83……15016.2713283.173281.0757390.8619694.5997217.32115249.05……13809.0712122.286933.88212197.715211.8713806.1810693.67……9268.52913178.276893.5641231.4631958.0923116.80913857.19……12912.386103.58310544.49579.12411380.0312646.115125……5053.2614098.58573.4848228.93110411.211283.395293.699……4641.7373916.521392.0586793.2479749.9918237.01411269.9……9819.8339470.7886687.6646886.4099393.0439864.7926424.837……5402.0044235.3985985.60411120.7214142.7812827.2110050.72……8589.08912061.994665.0437541.5711049510028.87446.492……6025.0917244.4554379.5499762.30612376.2410117.0614662.46……13170.9213446.793850.0978841.79411321.238945.03415052.74……13574.8813009.8410483.1812483.0915097.6115340.92152.539……896.43749129.9642449.1896734.6169764.0428692.0349760.558……8323.1148358.7397680.86711781.0914773.5414043.47138.883……5739.60111047.8811084.25818.5394669.3827472.96513992.98……13508.115004.546254.5126057.0836905.2683965.50817798.92……16501.7512174.388819.4237739.9359696.1410809.926186.376……5666.4912860.9839587.8188977.15610982.9512045.564971.723……4608.9324019.2046049.0932516.1183242.549846.78815565.98……14440.968721.4122332.5367402.58410407.129070.1310461.09……8993.4999418.23912265.167066.4175825.0098679.21914330.95……13968.065457.5293386.8135785.3118775.428220.4098858.98……7519.3426583.9394545.2611669.5584643.9754491.96211798.2……10704.25559.2854842.6778768.98211779.1611002.667893.542……6404.7038870.9656759.70612406.3615294.9113421.5613311.62……11853.4314602.085283.3914114.8825283.242459.52216188……14945.1810236.7810499.365019.8463536.4146390.95114492.98……13901.185543.9274448.23810091.0112885.5610873.7213434.05……11940.0313067.415145.7025032.3387725.6887946.298354.168……7249.6794325.398124.3410518.4313287.6613256.274227.875……2735.4168171.5156001.3711417.6833679.3274447.19312119.12……11158.154805.79910103.719882.10611956.1412944.313996.702……3758.515002.1256315.1611903.0314839.8313102.9912401.8……10940.7613814.793786.7735833.2177761.9755117.39415749.55……14381.811298.715629.8938094.12310973.7510722.626471.671……5058.316999.8184081.6798665.48511696.510630.299077.418……7586.4959562.6283456.789085.62111992.8510243.8512015.46……10522.411617.397095.78911005.613987.73133236857.944……5405.23110247.085319.64810811.3813465.1111229.6114839.86……13346.0214243.3310687.9112267.131478015190.681494.13……08527.4649161.9466219.3677462.2429159.3468990.919……8527.4640附录5：a=long;%调用附录3的建立的long表格n=size(a,1);d=a;fork=1:nfori=:nforj=1:nifd(i,k)+d(k,j)<d(i,j)d(i,j)=d(i,k)+d(k,j);endendendenddisp(d);附录6：012093.115595.217795.212647.9……11153.813169.412093.105132.67332.65936.2……7430.36223.515595.25132.603210.68233.4……9727.58520.717795.27332.63210.6010433.4……11927.510720.712647.95936.28233.410433.40……1494.19324.316500.96038.31916.31294.39139.1……10633.29426.4218211267.714769.816969.812173.6……10679.51234413416.710403.412700.614900.610382.6……8888.54179.91796.912892.716394.818594.810851……9356.9139697492.915375.317672.519872.59439.1……794513599.63620.814716.617260.519460.59027.1……753313187.61172212339.514636.716836.710708.3……12202.415727.613637.13174.51958.14158.16275.3……7769.46562.614223.211209.913507.115707.16578.3……5084.24986.410819.98977.411357.413557.49981.6……8487.53778.91392.11070114203.116403.113042.7……11548.611777.389347091.59471.511671.58384.1……68904235.47859.611873.514170.716370.710242.3……11736.415261.65253.811488.714990.817190.811813.8……13307.9125656707.216496.819998.922198.912113.5……10619.4162745395.316491.1190352123510801.6……9307.514962.114246.33783.76080.98280.92152.5……3646.67171.82929.1916412666.114866.113469.7……12783.210240.39928.18770.711067.913267.97139.5……8633.612158.818173.9112287081.910292.514328.8……15075.15004.58497.815448.917746.119946.19512.7……8018.613673.211917.88904.511201.713401.78883.7……7389.6268113205.31019212489.214689.27596.2……6102.13968.58099.917185.620687.722887.713517.6……12023.517678.13996.910231.813733.915933.914537.5……1385111308.119426.810961.658299039.614062.4……15556.56257.44709.27383.9108861308611689.6……11114.88460.210423.51669.65171.77371.75975.3……7469.46262.66884.611814.214111.416311.410183……11677.114195.88832.915142.917440.119640.113511.7……15005.817667.88091.517177.219691.621891.611458.2……9964.115618.719131.686693536.4674711769.8……13263.985506214.513973.117475.219675.214637.2……13143.115049.46967.85125.38627.410827.49431……8856.26201.68418.410165.712462.914662.94229.5……2735.4839011880.31417.73714.95914.94518.5……6012.64805.814912.311188.813486156865252.6……3758.56312.19750.614225.216522.418722.412594……14088.117613.35816.512767.615064.817264.86831.4……5337.310991.99215.814145.416442.618642.612514.2……14008.316527577612010.9155131771316316.6……15630.113087.24677.112435.715937.818137.813424.8……12237.1135129215.814145.416442.618642.612514.2……14008.3165277624.215382.818884.921084.913227.5……11733.416459.111153.87430.39727.511927.51494.1……010070.613169.46223.58520.710720.79324.3……10070.60附录7：MODEL

:

SETS:

city/1

..51

/:u;

link(city,city):w,x;

endsets

data:

w=@OLE('C:\distance.xls','w');

enddata

n=@size(city);

min=@sum(link:w*x);

@for(city(k):

@sum(city(i)|i

#ne#

k:

x(i,k))=1;

@sum(city(j)|j

#ne#

k:

x(k,j))=1;

);

@for(link(i,j)|i

#gt#

1

#and#

j

#gt#

1

#and#

i

#ne#

j:

u(i)-u(j)+n*x(i,j)<=n-1;

);

@for(link:

@bin(x));

END

附件8（部分结果）

：路径可行值路程值X(1,16)1.0000001392.100X(2,41)1.0000001417.700X(3,6)1.0000001916.300X(4,13)1.0000004158.100X(5,50)1.0000001494.100X(6,4)1.0000001294.300X(7,1)1.0000002182.000X(8,27)1.0000001498.900X(9,11)1.0000001823.900X(10,20)1.0000003409.500X(11,21)1.0000001774.500