关于送货路线设计问题的分析.doc

送货路线设计问题分析摘要 本文是关于送货员需要以最快的速度及时送达货物的问题，可看作是类货担问题。 第一问中，我们采用最近点插入模型，得到了30个货物的送货方案及路线时间，并且应用局部全排列穷举法将上面得到的路线进行优化，得到最终路线为：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分。 第二问中，根据时间优先的原则，将所有货物送达点进行分块分组，即优先送达时间要求紧的货物，并且利用穷举法列举出每一块中货物送达点的任意排列顺序，求出其中耗时最短的路线即为所需结果，最终路线为：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分。第三问中，由于货物重量和体积的限制，送货员需中途取货。我们采用最远点优先送货和最近点优先送货两种方案进行路线的分划，并根据最终求得结果的比较，得出前者方案更优，因此选用第一种方案送货。最终路线为：第一趟：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,第二趟：0-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分。关键字：快递公司送货 货郎担问题 最近邻点插入 全排列穷举法 1 问题重述在物流行业中，送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方。现有一快递公司，一送货员要按图1中的路径需将货物送至城市内多处，要求设计送货方案，使所用时间最少。假定送货员只能沿图中那些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。每件货物交接花费3分钟，并假定，同一地点有多件货物按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1. 若将130号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2. 假定该送货员从早上8点上班开始送货，要将130号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。不考虑中午休息时间。2 问题分析对于送货员从快递公司库房O点出发将货物送到城市内制定地点问题，可以转换为图论中的最短路径求解问题，我们将城市内的各送货地点看做是图中的顶点，各地点之间送货所需的时间看做是该边上的权值，由题目表3所给的各地点之间的联通性构建无向图。对于问题一，要求送货员以最快的方式将130货物送达指定的地点并返回。因此，可以将问题简化为货郎担问题进行求解。对于问题二，要求送货员从早上8点出发，将货物在指定的时间内以最快的方式送达目的地，由题目已知可以根据时间将130号货物所对应的地点分为4块，即8：00至9:00、9:00至9:30、9:30至10:15、10:15至12：00四个时间段。再对每个时间段内的送货地点进行穷举，得到最佳路径，评价各个时间段的结果。对于问题三，在不考虑送货时间限制的情况下，将体积与重量两个因素考虑在内，允许送货员可以往返取货，要求送货员以最快的方式将货物送达指定地点并返回。由于所有物体的总重量是148公斤，总体积为2.98立方米，送货员的最大载货量为50公斤，最大载货体积为1立方米，所以送货员会往返三次取货，因此可以将所有的送货地点分为三块。对于所有送货地点的分块，可以采用三种方案寻找离始发点最远的点，逐次加入次远点，直至达到送货员的最大载货量；寻找离始发点最近的点，逐次加入次近点，直至达到送货员的最大载货量；人为的分块，直至达到送货员的最大载货量；对此三种方法进行评价，得出分析结果。3 模型假设(1) 送货员只能走题目中给定的联通路线，不能走其他的任何路线；(2) 假定送货员最大载重50公斤，所带货物最大体积1立方米；(3) 假定送货员的平均速度为24公里/小时；(4) 假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算； (5) 送货员在送货期间无塞车现象，即业务员送快递途中不受任何外界因素影响；(6) 送货员送货期间不考虑中午休息时间；(7) 假设送货员到达送货点后就将此站点上的所有货物交付；4 模型的建立与求解4.1 各站点路径求解模型在计算机中通过编程可得到坐标系中各站点的点号以及130号货物所对应的站点号，如图11所示：图11 所有送货站点及前30各送货点的标号由题目已知条件可将送货问题看做是图论求解最佳路径问题，将送货站点看做是图中的顶点，送货站点之间的路径看做边，将送货站点之间的距离作为图中边的权值，构成图 ，其中定点数n=50；因此有 算法求解图中任意两站点直间的最短路径，设图中权矩阵为 ，其中 为 到 的距离。 当 ；= 其他算法基本步骤为：(1) 输入权矩阵 。(2) 计算 ， ，其中 (3) 中元素 就是 到 的最短路长。4.2 问题一模型的建立于求解一、最近邻点插入模型：本题考虑应用货郎担问题，由于货郎担问题还没有一个精确的算法，加之前30个货物的运送共涉及到22个站点数据量较大，故我们采用最邻近点插入模型进行近似求解。其基本的思想为：以O点为起始点，纳入到集合 中，依次计算剩余点到集合 的距离，取其中最小距离所对应的站点作为集合 中下一个待插入点，依次计算此点插入到集合 各元素间时所对应的距离，将其中最小距离所对应的位置作为此点在集合 中的插入位置。依次类推，直到所有站点遍历结束。最邻近插入法实现步骤为：（设 是带权无向图，共有n个结点，其中n=22）(1) 以O点为初始点计作 ，建立有序集合（集合元素排列顺序即为最佳路径） = ，并由其余的n-1个点建立集合 = ，计算 集合中每一个元素到集合 中各个元素的距离，取集合 中每一个元素到集合 中每一个元素的最小距离作为其对应与集合 的距离，比较集合 中各个元素到集合 的距离，取距离最小所对应的元素作为集合 的待纳入元素，将其分别插入到集合 各个元素之间，计算其距离， 取最短距离所对应的插入点作为该元素在集合 中的最终位置，得到最终的有序集合 。（2）假设集合 = ， = ，求出集合 中元素 分别到集合 中元素 之间的距离，依次即为 ，比较 的大小，取其中最小的值作为 到集合 的距离；再求集合 中元素 分别到集合 中元素 之间的距离，依次即为 ，比较 的大小，取其中最小的值作为 到集合 的距离；依次类推，求出集合 中各元素到集合 的距离。比较集合 的各个元素到集合 距离的大小，取其中距离最小的元素为待插入集合 的元素，为了便于理解这里我们假设此元素为 ，然后计算 插入到集合 元素 ， ， 以及 后所得路径的总距离，取其中距离最小的一组作为 的插入点，得到集合 。 (3) 依次类推，直到所有的点遍历一遍，得到的集合 即为最佳路径。由程序可得其最佳路径为：O-21-17-14-16-23-32-35-38-36-38-43-42-49-42-45-40-34-31-18-13-19-24-31-27-39-27-31-26-0总的时间为：230.83分。二、局部全排列穷举法模型前30个货物的运送共涉及到22个站点数据量较大，直接采用全排列穷举法难以实现，因此我问现将其分块，并在每块内部采用局部全排列穷举法得到局部最佳路径，在通过固定每一块路径的起始点的方法是所有块的路径连接成一个整体。（具体模型算法见下文问题二）最佳路径为：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-26-O总的时间为：228.18分。由此两种模型的结果比较明显可得分块后利用穷举法得到的结果优于前者，因此，前30个货物的送货路径选择局部全排列穷举法：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分。路径如图12所示：图12 前30个货物的最佳运输路线图4.3 问题二模型的建立于求解本题利用分块思想，应用局部全排列穷举法求解每一块的最佳路径。由于考虑到送货时间运输限制，我们优先考虑送货时间，即以送货时间对所有货物进行分块，并在每一块内部采用局部全排列穷举法求取路径，并判断其总的送货时间是否满足指定的时间。其基本步骤为：(1) 第一时间段为8:009:00之间送到的站点为：13、18、39、27、24、27，不计重复站点，总共有5个站点，利用穷举法比较 次得到最佳路径为：18-13-24-27-39，考虑交货时间在内总时间为57.1分。(2) 第二时间段为9:009:30之间送到的站点为：31、31、34、40、45、45、45，不计重复站点，总共有4个站点，利用穷举法比较 次得到最佳路径为：31-34-40-45, 考虑交货时间在内总时间为46.05分。(3) 第三时间段为9:3010:15之间送到的站点为：42、49、43、43、38，不计重复站点，总共有4个站点，利用穷举法比较 次得到最佳路径为：42-49-43-43-38, 考虑交货时间在内总时间为39.58分。(4) 第四时间段为10:1512:00之间送到的站点为：36、32、23、16、14、17、21、26，不计重复站点，总共有8个站点，利用穷举法比较 次得到最佳路径为：36-32-23-16-14-17-21-26, 考虑交货时间在内总时间为81.97分。因此，根据题目所给的时间段分块所得结果如表1所示：站点分块表第一时间段货物号送达地点重量体积时间最佳路径时间（含交货时间）/分1132.50.03169:001857.12180.50.03549:001313392.560.05959:002419272.450.05459:002720242.930.0529:002722272.250.00189:0039第二时间段3311.180.02689:303146.0511451.10.02879:303114452.280.05019:303421310.80.01089:304024342.80.01039:304525402.140.01559:304526450.680.06829:3045第三时间段10381.330.031910:154239.5812430.950.022810:154915422.850.01910:154316431.70.078210:154327491.350.014410:1538第四时间段4261.560.03512:003685.455212.150.037712:00326141.720.0112:00327171.380.010912:00328231.40.042612:00239320.70.048112:002317320.250.051212:001618361.790.018412:001423261.570.02112:001728320.520.00212:002129232.910.058712:002630161.20.042912:0026由表1可知其送货路线为：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-26-O，总时间为：228.18分。考虑时间限制时的最佳路线图见如下图所示：图13 考虑时间限制时前30个货物的最佳运输路线图4.4 问题三模型的建立于求解在考虑送货员所载货物重量及体积限制，不考虑送货时间限制的前提下，设计将货物最快送到指定地点的往返路线。由于所有物体的总重量是148公斤，总体积为2.98立方米，送货员的最大载货量为50公斤，最大载货体积为1立方米，所以送货员会往返三次取货，因此最少要将所有的送货地点分为三块。本题我们采用两种分块方案，分别为：(1) 最远送货点优先法：寻找离始发点O点最远的点，以此点为中心寻找周围离其最近的点，直至达到送货员的最大载货量和最大载货体积，在剩余点钟再以距离O的次远点为中心寻找其周围的点，直至达到送货员的最大载货量和最大载货体积，直到所有货物运送结束为止。 有题目数据计算可得，距离O点最远点为2号点，因此以2号点为中心的一组送货点分块数据为：2、3、4、5、8、15、15、1、6、7、7、11、11、12、12、13、13、10、10、18、18、20、20、22、25、25、25、29、30、28、9、33、33、14、14，共35个站点，送货员运送的总重量为48.54公斤，总体积为0.9857立方米，不计重复站点，共有23个送货点，将前12个站点作为一部分，后11个站点作为一部分，利用穷举法得到其最佳路径为：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,其总时间为167.48分。 除去此23个站点，由计算可知，距离O点最远的点为48号点，以此点为中心的一组送货点数据为：48、44、46、46、46、41、41、50、47、40、40、37、37、34、34、19、19、24、24、45、45、45、45、31、31、31、27、27、27、39、39，共31个站点，送货员运送的总重量为50公斤，总体积为0.9573立方米，不计重复站点，共有15个送货点，将前11个站点作为一部分，后4个站点作为一部分，利用穷举法得到其最佳路径为：19-24-31-34-40-47-40-37-41-46-48-44-50-45-36-27-39，其总时间为141.82分 出去前两部的站点后，经计算的离O点最远的站点时17号点，以此点为中心的一组送货点数据为：16、16、17、17、17、23、23、23、23、32、32、32、32、32、32、35、38、38、38、36、36、36、21、21、43、43、43、42、42、49、49，共31个站点，送货员运送的总重量为45.07公斤，总体积为0.9751立方米，不计重复站点，共有11个送货点，利用穷举法得到其最佳路径为：17-23-16-23-32-35-38-43-42-49-42-43-38-36-21，其总时间为78.04分。 最后以26、26、26为一组送回点数据，共3个站点，送货员运送的总重量为4.39公斤，总体积为0.0619立方米，不计重复只有1个站点，其总时间为6.96分。综合此四块的数据可知，总的运送时间为394.3分。 (2) 最近送货点优先法：寻找离始发点最近的点，逐次加入次近点，直至达到送货员的最大载货量和最大载货体积，再在剩余点中寻找距离O点最近的点直至达到送货员的最大载货量和最大载货体积，直到所有货物运送结束为止。 有题目数据计算可得，距离O点最近点为26号点，因此以26号点为起始心的一组送货点分块数据为：26、26、26、18、18、21、21、23、23、23、23、27、27、27、31、31、31、34、34、36、36、36、39、39、24、24、17、17、17、17、11，共31个站点，送货员运送的总重量为45.77公斤，总体积为0.936立方米，不计重复只有11个站点，利用穷举法得到其最佳路径为：26-21-17-23-36-27-39-31-34-24-18,总时间为81.12分。 出去此11个站点外，由计算可得，剩余点中离O点最近的点为25号点，以此点为起始心的一组送货点分块数据为：25、25、25、37、37、42、42、43、43、43、50、1、47、3、6、15、15、29、22、30、49、49、41、41、28、20、20、44、4、4、4、4、20，总共有33个点，送货员运送的总重量为44.55公斤，总体积为0.8004立方米，不计重复只有20个站点，将前12个站点作为一部分，后8个站点作为一部分，利用穷举法得到其最佳路径为：25-29-22-30-33-28-20-15-4-3-1-6-47-37-41-44-50-49-42-43,总时间为219.5分。 除去此31个点外，由计算可得，剩余的点中距离O点最近的点位38号点，以此点为起始点的一组分块数据为：38、38、38、9、11、11、12、12、13、13、14、14、16、16、19、19、32、32、32、32、32、32、35、40、40、45、45、45、45、45、8、10、10、7、7、15，总共有35个点，送货员运送的总重量为48.73公斤，总体积为0.9839立方米，不计重复只有15个站点，将前10个站点作为一部分，后5个站点作为一部分，利用穷举法得到其最佳路径为：19-13-11-12-8-7-10-9-14-16-32-35-38-45-40,总时间为：125.35 剩余点中，由计算可得2号点距离O点最近，依此点作为起始点的一组分块数据为：2、5、48、46、46、46，共6个站点，送货员运送的总重量为8.95公斤，总体积为0.2597立方米，不计重复只有4个站点，利用穷举法得到其最佳路径为：2-5-48-46,总时间为：125.55分。综合