西工大最优送货路线.doc

最优送货路线摘要：建立了最优送货路线的模型，使物流公司在满足一定的社会效益（如按时送达）和获得最大经济效益（如较少的人力物力、较短的时间）的前提下，可以给出理想的送货方案与路线。对问题一，采用了两种模型求解：在模型一中，首先给出三十件货物送达地点的一个完全图，再利用二边逐次修正法的思想，利用Matlab随机产生10000个初始圈并生成哈密顿圈，通过程序自动比较可以很近似地得到本问题的最优路线，得出其最优路线的总路程为54708米。模型二建立了整数规划模型，该模型可以得出本问题的最优路线，其总路程为54707.63米，结果和模型一相差无几，由此也可看出模型一在解决本问题时不失为一个好模型。针对问题二，化繁为简，将截止送货时间和交接货物所用时间等约束条件统一转化为路程约束，于是问题二就转化为判断以下问题：问题一中每次产生的哈密顿圈的每个节点是否满足其路程约束。不满足则跳出继续判断下一个哈密顿圈，如若满足，通过逐次比较各个符合条件的哈密顿圈即可得出最优路线，通过该模型得到的最优路线的总路程为56277米。问题三可以采用多旅行商问题的解决思路，先根据普里姆算法计算出最小生成树，再结合各点的位置坐标和得到的最小生成树，将其分为三组，于是问题三就转化为在满足重量和体积要求的前提下求该送货员三次送货的总时间（送货员在路上花费的时间+送货员交接货物花费的时间）最短的送货路线。分组后的算法和问题一类似，求得其最短送货时间为11.187小时。关键字：图论、哈密顿圈、完全图、最小生成树、分组、规划 一、问题的提出现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，这不仅对于送货公司的效益来说是非常重要的而且对于送货员的薪酬多少等也是至关重要,所以对于路线的优化设计是很有必要的！现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，合理地设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点，需要分别解决以下问题：问题（1） 若将130号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。问题（2） 假定该送货员从早上8：00上班开始送货，要将130号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。问题（3） 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。 问题（4） 在上述关于交接时间t和运货速度v的假定下，如果送货人员足够多，完成送货的最短时间是多少？送货路线给出在这种最短时间完成送货的要求下，如何射界运送路线认为最佳？ 二、符号约定v 速度常量24000米/小时a（i，j） i点与j点的最短距离距离，（51=i=51， 51=j=51）S1，S2，S3 分别表示三个分组的路程（问题三）51 O点maxw 最大载重50公斤maxv 最大体积1立方米w1 三十件货物总重量v1 三十件货物总体积w2 一百件货物总重量v2 一百件货物总体积b（i,1） 第i个地点交接货物所花时间转化的路程，（1=i=21）b（i,2） 第i个地点交接货物截止时间距离早上八点的时间间隔（小时）（1=i=21）b（i,3） 第i个地点交接货物截止时间距离早上八点的时间间隔转化的路程（1=i= m（i）这一条件,就得到了一组可行路径，多条路径经过比较可得出最优解。 哈密顿圈路径符合时间要求输出路径与路程对比多组找出最优解说明：程序简明流程图对问题三的分析： 现在要将100件货物全部送到指定地点并返回，这里不需要考虑所有货物送达时间限制(包括前30件货物)，但一百件货物的总重量w2为148公斤，总体积v2为2.8立方米，超出了最大载重maxw和最大体积maxv。由于w2/maxw3,v2/maxv0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)a(c1(m),c1(m+1)+a(c1(n),c1(n+1) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end endendif sum=0for i=1:L-1 sum=sum+a(c1(i),c1(i+1);end circle=c1; sum=sum+a(c1(L),22);else sum1=0; for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1); end sum1=sum1+a(c1(L),22);if sum1sum sum=sum1; circle=c1;endendendcircle,sum%13-1 14-2 16-3 17-4 18-5 21-6 23-7 24-8 26-9 27-10 31-1132-12 34-13 36-14%38-1539-1640-1742-1843-1945-2049-2151-22 节点和数组序号对应表，前面是节点号 后为对应的数组中的序号附录3clc,cleara=0.008455.6411063.328916.343113.467092.4310690.865714.346687.556284.915217.1612002.737541.908488.8310026.248064.839172.6913562.3612644.6911671.2815533.745295.498455.640.002607.682195.725342.183296.733970.248805.655488.478093.257025.505282.119350.256176.917714.339873.1810981.0311250.4510332.779359.3713221.825093.6811063.322607.680.003872.167949.865696.072097.6411204.987887.819674.579424.833409.5111749.587470.655933.2411454.4913380.369469.368551.6810653.1111440.737493.018916.342195.723872.160.005802.881823.911774.517332.824015.656620.435552.683086.387877.424704.095610.118400.359508.219146.238228.557886.5411117.603620.853113.465342.187949.865802.880.003978.977577.403883.843574.093171.452103.698889.264428.445375.366912.784951.376059.2210448.909531.238557.8212420.282182.037092.433296.735696.071823.913978.970.003598.425508.912191.744796.523728.774910.296053.512880.184417.596576.447684.307953.717036.046062.639925.091796.9410690.863970.242097.641774.517577.403598.420.009107.345790.167576.937327.191311.879651.945373.013835.609356.8511282.727371.716454.048555.479343.095395.375714.348805.6511204.987332.823883.845508.919107.340.003317.172847.901780.159112.964104.895051.826589.244627.825735.6810125.359207.688234.2712096.734709.236687.555488.477887.814015.653574.092191.745790.163317.170.002604.781537.037102.033861.774808.706346.114384.705492.569882.238964.567991.1511853.611392.066284.918093.259674.576620.433171.454796.527576.932847.902604.780.001067.756265.063392.502203.923741.331779.925023.287277.456359.785386.379248.833996.845217.167025.509424.835552.682103.693728.777327.191780.151537.031067.750.007332.822324.753271.674809.092847.683955.538345.217427.536454.1310316.582929.0812002.735282.113409.513086.388889.264910.291311.879112.967102.036265.067332.820.009657.564061.142523.738044.9810460.616059.845142.177243.608031.226707.247541.909350.2511749.587877.424428.446053.519651.944104.893861.773392.502324.759657.560.005596.427133.845172.421630.787199.518117.184847.798243.095253.838488.836176.917470.654704.095375.362880.185373.015051.824808.702203.923271.674061.145596.420.001537.423983.846399.465073.534155.863182.467044.914677.1210026.247714.335933.245610.116912.784417.593835.606589.246346.113741.334809.092523.737133.841537.420.005521.267936.883536.122618.444719.875507.496214.548064.839873.1811454.498400.354951.376576.449356.854627.824384.701779.922847.688044.985172.423983.845521.260.006803.219057.378139.707166.3011028.755776.769172.6910981.0313380.369508.216059.227684.3011282.725735.685492.565023.283955.5310460.611630.786399.467936.886803.210.005568.736486.403217.016612.316884.6113562.3611250.459469.369146.2310448.907953.717371.7110125.359882.237277.458345.216059.847199.515073.533536.129057.375568.730.00917.672351.721971.389750.6512644.6910332.778551.688228.559531.237036.046454.049207.688964.566359.787427.535142.178117.184155.862618.448139.706486.40917.670.003269.402889.058832.9811671.289359.3710653.117886.548557.826062.638555.478234.277991.155386.376454.137243.604847.793182.464719.877166.303217.012351.723269.400.004323.107859.5815533.7413221.8211440.7311117.6012420.289925.099343.0912096.7311853.619248.8310316.588031.228243.097044.915507.4911028.756612.311971.382889.