送货路线设计问题111.docVIP

送货路线设计问题 摘要 我们建立了相应的模型来解决最优路径问题，使送货员耗时最少，路程最短。并讨论了在最大载重和最大带货体积一定情况下的有时间限制和无时间限制的最优路径问题。 问题一，根据题中所给数据可求出30件货物质量之和为49.5公斤、体积之和为0.99立方米，故在问题一的模型建立中我们不用考虑质量、体积的约束。本文可以将该问题转化为TSP（旅行商）问题（本题可以重复经过某顶点），建立了求最小Hamilton 圈模型,先利用Floyd 算法求出任意顶点间最短路，构造连接各顶点的一个无向赋权完全图。再寻找该完全图中的最小Hamilton 圈。本文用LINGO 软件寻找该完备图中的最小Hamilton 圈，从而得到问题一的最优解。依据程序运行结果，最后得出具体路径为：O—26—21—17—14—16—23—32—35—38—36—38—43—42—49—42—45—40—34—31—27—39—27—31—24—19—13—18—O且得到最短送货路线的总长d=54600m，总的时间为：226.50分钟。 问题二中增加了“时间”这一约束条件，而没有要求返回出发点。所以我们必须在满足各点的时间要求前提下，寻找一条最优的路径。我们根据时间优先的原则, 即优先送货到时间要求较紧的地点，将所有货物送达点进行分块分组，我们将22个节点按时间限制划分为四个阶段：9:00、9:30、10：15、12:00四个阶段 。分阶段后，由于各阶段所要求进过的地点个数较少，故在此问题中采用穷举法比较出其中耗时最短的路线，即为所求结果，最佳路线为：-18-13-19-24-31-27-27-39-27-31-31-34-40-45-45-45-42 -49-42-43-43-38-36-38-35-32-32-32-23-23-16-14-17-21-26， 总路程：53208米，总用时为（包括交货时间）：223.02分钟。 问题三中由于考虑到送货员送货受到包裹最大重量和最大体积的限制，因此送货员必须返回原点取货，根据题中所给数据可求出100件货物质量之和为148公斤、体积之和为2.98立方米，因此送货员最少要三次返回O点取货，故我们首先将最小生成树的枝节点靠近主干划分为三个区域，在每个区域中求出最优Hamilton 回路，从而得到最短送完所有货物的线路图的满意解，并标出送货路线。三个区域总路程和为最短路程为133509m，总时间为633.78分钟。其中： 红色线路区域最短回路为：0→26→31→27→39→27→36→45→40→47→40→50→49→42→43→38→35→32→23→17→21→0；路径长：42173米。 绿色线路区域最短回路为：0→26→31→34→40→37→41→44→48→46→33→28→30→22→20→22→29→25→19→24→31→26→0；路径长：39895米。 橙色线路区域最短回路为：0→21→17→23→16→14→9→10→7→1→6→1→8→3→4→2→5→15→12→11→13→18→0。路径长：51441米。 即有：总路线长 总时间 关键词：送货路线、最优路径、Floyd算法、TSP问题、 穷举法 一 、问题重述 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。 现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。 假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。 现在送货员要将100件货物送到50个地点。请完成以下问题。 1. 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。标出行走路线。 2. 假定该送货员从早上8点上班开始送货，要1~30号货物还需要按照预定时间内完成，请设计最快完成路线与方式。标出行走路线。 3. 若将100件货物全部送到指定地点并返回。设计最快完成路线与方式。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。 二 、问题假设 1．假设送货员只能沿如图路线图行驶，不能走其他的任何路线 2．在联通路线中，送货员可自由选择 3．送货员交接货物只需三分钟，同一地点多次交接也以三分钟计，且同一地区的货物只一次即可全部送达，无需再次回O点取货。交接完毕立即前往下一处，不会出现特殊情况而延误时间 4