送货路线设计问题111

《送货路线设计问题111》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、送货路线设计问题摘要我们建立了相应的模型来解决最优路径问题，使送货员耗时最少，路程最短。并讨论了在最大载重和最大带货体积一定情况下的有时间限制和无时间限制的最优路径问题。问题一，根据题中所给数据可求出30件货物质量之和为49.5公斤、体积之和为0.99立方米，故在问题一的模型建立中我们不用考虑质量、体积的约束。本文可以将该问题转化为TSP（旅行商）问题（本题可以重复经过某顶点），建立了求最小Hamilton圈模型，先利用Floyd算法求出任意顶点间最短路，构造连接各顶点的一个无向赋权完全图。再寻找该完全图

2、中的最小Hamilton圈。本文用LINGO软件寻找该完备图中的最小Hamilton圈，从而得到问题一的最优解。依据程序运行结果，最后得出具体路径为：0—>2—>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—>0且得到最短送货路线的总长d=54600m，总的时间为：226.50分钟。问题二中增加了’时间〃这一约束条件，而没有要求返回出发点。所以我们

3、必须在满足各点的时间要求前提下，寻找一条最优的路径。我们根据时间优先的原则，即优先送货到时间要求较紧的地点，将所有货物送达点进行分块分组，我们将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->4

4、3->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26,总路程：53208米，总用时为（包括交货时间）：223.02分钟。问题三中由于考虑到送货员送货受到包裹最大重量和最大体积的限制，因此送货员必须返回原点取货，根据题中所给数据可求出100件货物质量之和为148公斤、体积之和为2.98立方米，因此送货员最少要三次返回0点取货，故我们首先将最小生成树的枝节点靠近主干划分为三个区域，在每个区域中求出最优Hamilton回路，从而得到最短送完所

5、有货物的线路图的满意解，并标出送货路线。三个区域总路程和为最短路程为133509m,总时间为63378分钟。其中：红色线路区域最短回路为：0->26->引->27t39t27t36t45t40t47t40t50t49t42t43t38t35t32t23->17t21t0;路径长：42173米。绿色线路区域最短回路为：0t26t31t34t40t37t41t44t48t46t33t28t30t22t20t22t29t25t19t24t31t26t0;路径长：39895米。橙色线路区域最短回路为：0t21t1

6、7t23t16t14t9t10t7t1t6t1t8t3t4t2->5->15->12->11->13->18->0o路径长：51441米。即有：总路线长W=vv,+W2+W3=133509米总时间T二W*+3x“633.78分钟关键词：送货路线、最优路径、Floyd算法、TSP问题、穷举法一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛,每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图I中的0点，

7、一送货员需将货物送至城市内多处，请设计送货方案，使所用吋间最少。该地形图的示意图见图1,各点连通信息见表3,假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1,50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小吋。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1.若将「30号货物送到指定地点并返回。设计最快完成路线与方

8、式。给出结杲。标出行走路线。2.假定该送货员从早上8点上班开始送货，要广30号货物还需要按照预定时间内完成，请设计最快完成路线与方式。标出行走路线。3.若将100件货物全部送到指定地点并返回。设计最快完成路线与方式。由于受重量和体积限制，送货员可中途返冋取货。可不考虑中午休息时间。二、问题假设1.假设送货员只能沿如图路线图行驶，不能走其他的任何路线2.在联通路线中，送货员可自由选择3.送货员交接货物只需三分钟，同一地点多次交接