数学建模-送货线路设计模型.docVIP

送货线路设计模型 摘要：针对题目所给关于货物配送的一系列问题，通过已知起点和终点的图的遍历问题来建立合理优化的路线设计，使送货员耗时最少，路程最短，并讨论了在最大载重和最大带货体积一定情况下的有时间限制和无时间限制的最优路径问题。 对于问题一，根据题中数据计算30件货品的总质量与体积，得出的结果不超过送货员的最大载重量，在此我们只考虑最短路径问题，我们利用Floyd算法求出任意顶点间的最短路径距离，最后利用Matlab﹑Lingo 软件得出从O点出发经过各节点又回到O点的最短路径。 对于问题二，在第一问的基础上加入时间限制，根据不同的地点到达的时间不同，对整个路线图进行阶段划分，然后对于不同的阶段转化为一个新的求最短路径的问题。 对于问题三，没有时间限制，但是基于重量和体积的要求，论文类比第二问中所用方法对总路线按照体积与重量的限制进行了划分片区（3个区域），在根据地理位置进行优化。 关键词：送货路线 最优路径 Floyd算法 区域划分 一﹑问题重述 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。 现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。 假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。 现在送货员要将100件货物送到50个地点。请完成以下问题。 1. 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。标出行走路线。 2. 假定该送货员从早上8点上班开始送货，要1~30号货物还需要按照预定时间内完成，请设计最快完成路线与方式。标出行走路线。 3. 若将100件货物全部送到指定地点并返回。设计最快完成路线与方式。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。 以上各问尽可能给出模型与算法。 图1 快递公司送货地点示意图 O点为快递公司地点，O点坐标(11000,8250) 表1 各货物号信息表 货物号 送达地点 重量(公斤) 体积(立方米) 不超过时间 1 13 2.50 0.0316 9：00 2 18 0.50 0.0354 9：00 3 31 1.18 0.0268 9：30 4 26 1.56 0.0350 12：00 5 21 2.15 0.0377 12：00 6 14 1.72 0.0100 12：00 7 17 1.38 0.0109 12：00 8 23 1.40 0.0426 12：00 9 32 0.70 0.0481 12：00 10 38 1.33 0.0319 10：15 11 45 1.10 0.0287 9：30 12 43 0.95 0.0228 10：15 13 39 2.56 0.0595 9：00 14 45 2.28 0.0501 9：30 15 42 2.85 0.0190 10：15 16 43 1.70 0.0782 10：15 17 32 0.25 0.0512 12：00 18 36 1.79 0.0184 12：00 19 27 2.45 0.0545 9：00 20 24 2.93 0.0520 9：00 21 31 0.80 0.0108 9：30 22 27 2.25 0.0018 9：00 23 26 1.57 0.0210 12：00 24 34 2.80 0.0103 9：30 25 40 2.14 0.0155 9：30 26 45 0.68 0.0682 9：30 27 49 1.35 0.0144 10：15 28 32 0.52 0.0020 12：00 29 23 2.91 0.0587 12：00 30 16 1.20 0.0429 12：00 31 1 1.26 0.025 32 2 1.15 0.0501 33 3 1.63 0.0483 34 4 1.23 0.0006 35 5 1.41 0.0387 36 6 0.54 0.0067 37 7 0.70 0.0129 38 8 0.76 0.0546 39 9 2.14 0.0087 40 10 1.07 0.0124 41 11 1.37 0.051