送货路线设计问题的分析

1、1 / 21送货路线设计问题分析摘要本文是关于送货员需要以最快的速度及时送达物资的问题， 可看作是类货担问题。第一问中， 我们采纳最近点插入模型， 得到了 30 个物资的送货方案及路线时刻， 同时应用局部全排列穷举法将上面得到的路线进行优化，得到最终路线为：O-18-13-19-24-31-27-27-39-27-31-31-34-40-45-45-45-426-14-17-21-26-O ，总用时为（包括交货时刻）： 228.18-49-42-43-43-38-36-38-35-32-32-32-23-23-12 / 21分。第二问中，依照时刻优先的原则，将所有物资送达点进行 分块分组， 即

2、优先送达时刻要求紧的物资， 同时利用穷举法列举 出每一块中物资送达点的任意排列顺序， 求出其中耗时最短的路 线即为所需结果，最终路线为：O-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-O ，总用时为（包括交货时刻）： 228.18 分。第三问中，由于物资重量和体积的限制，送货员需中途取货。我 们采纳最远点优先送货和最近点优先送货两种方案进行路线的 分划，并依照最终求得结果的比较，得出前者方案更优，因此选 用第一种方案送货。最终路线

3、为：第一趟：0-18-13-11-12-15-25-29-22-20-22-30-28- 33-28-30第二趟：-22-15-5-2-4-3-8-1-6-1-7-10-9-14-18-0,3 / 210-26-31-19-24-31-34-40-47-40-37-41-46-48-44-50-45-36-27-39-27-31-26-0第三趟：0-21-17-23-16-23-32-35-38-43-42-49-42-43-38-36-21-0第四趟： 0-26-26-26-0总时刻为： 394.3 分。4 / 21关键字： 快递公司送货 货郎担问题 最近邻点插入 全排列穷举法1 问题重述在

4、物流行业中，送货员需要以最快的速度及时将物资送达，而且他们往往一人送多个地点。现有一快递公司， 一送货员要按图 1 中的路径需将物资送至 都市内多处，要求设计送货方案，使所用时刻最少。假定送货员 只能沿图中那些连通线路行走， 而不能走其它任何路线。 各件物 资的相关信息见表 1，50 个位置点的坐标见表 2。假定送货员最大载重 50 公斤，所带物资最大体积 1 立方米。 送货员的平均速度为 24 公里/小时。每件物资交接花费 3 分钟， 并假定，同一地点有多件物资按照每件 3 分钟交接计算。现在送货员要将 100 件物资送到 50 个地点。请完成以下问题。1. 若将 130 号物资送到指定地点

5、并返回。 设计最快完成路 线与方式。给出结果。要求标出送货线路。2.假定该送货员从早上 8 点上班开始送货， 要将 130 号物资的送达时刻不能超过指定时刻，请设计最快完成路线与方式。要求标出送货线路。5 / 213.若不需要考虑所有物资送达时刻限制 （包括前 30 件物资） ，现在要将 100 件物资全部送到指定地点并返回。设计最快完成路线与方式。 要求标出送货线路， 给出送完所有快件的时刻。由于受重量和体积限制， 送货员可中途返回取货。 不考虑中午休息时刻。2 问题分析关于送货员从快递公司库房 0 点动身将物资送到都市内制定地点问题， 能够转换为图论中的最短路径求解问题， 我们将都市 内的

6、各送货地点看做是图中的顶点， 各地点之间送货所需的时刻 看做是该边上的权值， 由题目表 3 所给的各地点之间的联通性构 建无向图。关于问题一，要求送货员以最快的方式将 130 物资送达指定的地点并返回。因此，能够将问题简化为货郎担问题进行求解。关于问题二，要求送货员从早上 8 点动身，将物资在指定的时刻内以最快的方式送达目的地，由题目已知能够依照时刻将130 号物资所对应的地点分为 4 块，即 8：00 至 9:00 、9:00 至 9:30 、9:30 至 10:15 、 10:15 至 12：00 四个时刻段。再对每个 时刻段内的送货地点进行穷举， 得到最佳路径， 评价各个时刻段 的结果。

7、关于问题三，在不考虑送货时刻限制的情况下，将体积与重6 / 21量两个因素考虑在内， 同意送货员能够往返取货， 要求送货员以最快的方式将物资送达指定地点并返回。 由于所有物体的总重量是 148 公斤，总体积为 2.98 立方米，送货员的最大载货量为 50公斤，最大载货体积为 1 立方米，因此送货员会往返三次取货，因此能够将所有的送货地点分为三块。关于所有送货地点的分块，能够采纳三种方案查找离始发点最远的点， 逐次加入次远点，直至达到送货员的最大载货量；查找离始发点最近的点，逐次加入次近点，直至达到送货员的最大载货量；人为的分块，直至达到送货员的最大载货量； 对此三种方法进行评价， 得出分析结果

8、。3 模型假设(1)送货员只能走题目中给定的联通路线， 不能走其他的任何路 线；(2)假定送货员最大载重 50 公斤，所带物资最大体积 1 立方米；(3)假定送货员的平均速度为 24 公里 /小时；(4)假定每件物资交接花费 3 分钟，为简化起见， 同一地点有多件物资也简单按照每件 3 分钟交接计算；(5)送货员在送货期间无塞车现象， 即业务员送快递途中不受任何外界因素阻碍；(6)送货员送货期间不考虑中午休息时刻；(7) 假设送货员到达送货点后就将此站点上的所有物资交付；4 模型的建立与求解4.1 各站点路径求解模型在计算机中通过编程可得到坐标系中各站点的点号以及130 号物资所对应的站点号，如图 1 1 所示：图 1 1 所有送货站点及前 30 各送货点的标号由题目已知条件可将送货问题看做是图论求解最佳路径问题，将送货站点看做是图中的顶点， 送货站点之间的路径看做边，7 / 21将送货站点之间的距离作为图中边的权值，构成图 ，其中定点数 n=50；因此有 算法求解图中任意两站点直间的最短路径，设图中权矩阵为 ，其中 为 到 的距离。当；其他算法差不多步骤为：(1)输入权矩阵 。(2)计算 ， ，其中(3)中元素 确实是 到 的最短路长。4.2 问题一模型的建立于求解 一、最近邻点插入模型： 本题考虑应用货郎担问题， 由于货郎担