送货路线设计问题模型.docx

送货路线设计问题模型.docx

《送货路线设计问题模型.docx》由会员分享，可在线阅读，更多相关《送货路线设计问题模型.docx（47页珍藏版）》请在冰点文库上搜索。

送货路线设计问题模型

送货路线设计问题模型

摘要：

本题是求解送货员如何选取最佳行驶线路问题。

对于问题一：

方法一：

运用图论中关于最佳送货路径问题与最佳哈密顿圈（H圈）问题的有关结论建立基于前30号货物所需送至地点的完备图，通过矩阵翻转法和二边逐次修正法将求解最佳送货员的路径问题转化为求解最佳哈密顿圈（H圈）问题。

通过编程实现最佳哈密顿圈（H圈）的求解。

最后将最佳哈密顿圈（H圈）的解与实际路线相结合，得出最优解。

方法二：

进行观测判断。

由于前30号货物共需送到21个位置，交接时间可随之确定，所以直接观测判断可以得出几组较优路线，最后择优。

对于问题二，引入了时间问题，使解题有了时间约束。

方法一：

根据各个货物的不同时间限制和送往地点，观察图形知与问题一通过编程实现最佳哈密顿圈（H圈）得出的路线的逆路线十分接近。

运用问题一中方法一的最佳路线，将它与实际条件结合，得出最优解。

方法二：

进行观测判断。

由各个货物的送货不超过时间来确定其行驶路线，得出几组较优路线，最后择优。

对于问题三，100件货物的总重量为148公斤，总体积为2.8立方米。

为满足他送货的重量和体积限制，故将所有送货地点分成以库房（O点）为公共点的3个区域（建模原理同问题一的方法一），使送货员以O点为起始逐一通过每个区域。

建立3个区域地点的完备图，建立哈密顿圈（H圈），通过MATLAB实现最佳哈密顿圈（H圈）的求解。

最后分别三个最佳解与相对应的实际路线结合，得出每个的最优解（解题原理同问题一的解题原理）。

做后将每个的最优解以O点为中心合并在一起，就是最终的最优解。

关键字：

两边逐次修正法型矩阵翻转法最佳哈密顿圈（H圈）最优路线

送货路线设计问题模型

一、问题重述

随着现今社会网络越来越普及，网购已成为一种常见的消费方式，流行业也随之渐渐兴盛。

每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，我们需要设计方案使其耗时最少。

现有一家快递公司（库房在图1即所给图中的O点），一名送货员需将货物送至城市内多个地点，他只能沿这些连通线路行走，而不能走其它任何路线。

题目要求我们设计出最佳送货方案，使送货员所用时间最少。

（题目已给各件货物的相关信息，50个位置点的位置坐标及各位置点相互到达信息）其中假定送货员的最大载重为50公斤，所带货物的最大体积为1立方米，送货员的平均速度为24公里/小时，并假定每件货物交接花费3分钟（为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算）。

1、若送货员要从库房（O点）将1~30号货物送到指定地点并返回库房（O点）。

要求设计最快完成路线与交接方式，并给出结果，标出送货线路。

2、假定该送货员从早上8点上班从库房（O点）开始送货，要使1~30号货物的送达时间不能超过每个货物的指定时间，不需返回要求设计最快完成路线与交接方式，标出送货线路。

3.、若不考虑所有货物送达的时间限制，现要将100件货物从库房（O点）全部送到指定地点并返回库房（O点）。

由于受重量和体积限制，送货员可中途返回取货。

可不考虑中午休息时间。

要求设计最快完成路线与交接方式，标出送货线路，并给出送完所有货物的时间。

二、模型假设与符号说明

2.1模型假设

1、送货员行驶的速度一定，为24公里/小时；

2、送货员每次交接的时间一定，为3分钟，不会出现特殊情况而延误时间。

3、对于问题三，送货员中午不休息。

2.2符号说明

S：

路线的总路程

t：

送货员送货所需时间

V：

送货员行驶的速度；

T0：

送货员每次交接的时间；

（Xi,Yi）：

各个送货地点的坐标；

Vi：

H圈各顶点

N：

货物所需到达的地点总数

三、问题分析

3.1问题

（1）的分析

将1~30号货物送到指定地点并返回库房（O点）,要求时间最短。

先将1~30号的送达位置进行标注，得出总共为21个点。

由此可得出总的交接货物时间：

由于假设V恒定（24千米/小时），所以下一步只需求得最短路线。

方法一：

可以引入图论中关于最佳送货路径问题与最佳哈密顿圈（H圈）问题的有关结论，建立基于前30号货物所需送至地点（21个）的完备图，通过矩阵翻转法和二边逐次修正法将最佳送货员的路径问题转化为求解最佳哈密顿圈（H圈）问题，通过MATLAB实现最佳哈密顿圈（H圈）的求解。

最后将得出的最佳解与实际路线情况结合，得出最优解。

方法二：

进行数据分析观测判断。

根据前30号货物所需送到得21个位置，对图进行观测判断，可以得出几组较优路线，最后择优。

3.2问题

（2）的分析

要求将1~30号货物送到所需送往地点并不要求返回库房（O点）。

由于仍是1~30号货物，故交接货物时间仍是：

由于假设V恒定（24千米/小时），所以下一步仍只需求得最短路线。

方法一：

问题中要求送货员从8点开始送货（前1~30号货物），每件货物都有自己的送货不超过时间，对每件货物进行时间标注，可得出每件货物的送达时间限制。

随之就引入了送货时间先后的问题。

由每件货物的送达时间约束可发现约束时间相近或相同的货物所需送至位置相对集中，且与问题一中方法一的逆路线基本相同。

故引用问题一中方法一的结论。

并将结论与实际时间限制情况相结合，得出最优解。

方法二：

进行数据分析观察判断。

由各个货物的送货不超过时间来确定送货员的行驶路线，得出几组较优路线，最后择优。

3.3问题（3）的分析

要求将100件货物送到所需送往地点并返回库房（O点）。

图中50个地点均有货物。

此问无时间限制，但多了重量和体积限制（送货员的最大载重为50公斤，所带货物的最大体积为1立方米）。

故先计算一百件货物的总重量：

148公斤和总体积：

2.8立方米。

所以考虑将货物分成满足像只条件的三组，分成3次送完。

故将所有送货地点分成以库房（O点）为公共点的3个区域，其中每个区域都得满足重量和体积限制。

送货员就以O点为起始逐一通过这3个区域。

下一步就是建立3个区域地点的完备图，通过矩阵翻转法和二边逐次修正法将最佳送货员的路径问题转化为求解最佳哈密顿圈（H圈）问题，通过MATLAB实现最佳哈密顿圈（H圈）的求解。

（利用问题一方法一的建模模型）最后将得出的三个最佳哈密顿圈（H圈）的解与相对应的实际路线结合，得出每个区域的最优解。

最后将每个的最优解以O点为公共点合并在一起，就是最终的最优解。

四、模型建立与求解

4.1模型准备

1、图论中的几个结论：

哈密尔顿图：

设G为所需经过的所有点，经过G的每个点正好一次的圈，称为G的一条哈密尔顿圈，简称H圈；含H圈的图称为哈密顿图或H图。

最佳H圈：

在加权图中，权最小的哈密尔顿圈称为最佳H圈。

由以上结论可知，经过每个顶点至少一次的权最小的闭通路称为最佳H圈及最佳送货员行驶线路。

2、在完备图中寻找最佳H圈，需采用二边逐次修正法和矩阵翻转法来实现。

二边逐次修正法的算法过程如下：

（1）任取初始H圈：

C0=V1,V2,V3,V4,…,Vi,…,Vj,…,Vn,V1

（2）对所有的i,j，1

则在C0中删除边

）和

而加入边

和

，形成新的日圈C=V1,V2,V3,V4,…,Vi,Vj，Vj-1,…,Vi+1,Vj+1,…,Vn,V1

矩阵翻转法的算法过程如下：

矩阵翻转法：

在一个矩阵中，对它的第i行（列）到第j行（列）翻转是以i行（列）和j行（列）的中心位置为转轴、旋转180。

这样：

第i行（列）和第j行（列）位置互换，第i+1行（列）和第j-1行（列）位置互换，…

4.2模型的建立与求解：

1、问题

（1）模型的建立与求解

要将1~30号货物送到指定地点并返回库房（O点）,要求时间最短。

先将1~30号的送达位置进行标注，得出总共为21个点。

由此可得出总的交接货物时间：

由于假设V恒定（24千米/小时），所以下一步只需求得最短路线，即将送货员送货时间最小的求解转化为送货员行驶路程最小的求解。

方法一：

（1）、1~30号货物总共送往的地点有21个，以这21个点为顶点建立哈密顿（H圈）。

通过矩阵翻转法和二边逐次修正法求解最佳哈密顿圈。

初始圈为C0=V1，V2，V3，V4，…，V22，V1其对应的位置点为：

O—14—16—17—21—23—32—36—38—43—42—49—45—40—39—34—24—31—27—26—18—13—O

运用excel求得H圈上任意两点的距离：

（见附录）

由确定的初始的哈密顿圈，将其各值录入矩阵中。

最后将所得数据转换成的完备图邻接矩阵如下：

（只摘录前十行和前十列）

e=[

012345678910

00378745283281179738504380345744486760

03787026082196329739705239617463068924

04528260801247300520983362528747907267

03281219612470182417753054440442326830

01797329730051824020552743288032585828

03850397020981775205501312334826935193

04380523933623054274313120266115483905

03457617452874404288033482661015373323

04448630647904232325826931548153702618

…]

将矩阵数据录入编好的程序中（由floyd算法得出，程序在附录给出）

得出的最佳路线为：

V1--V5--V2--V4--V3--V6--V7--V9--V8--V10--V12--V13--V15--V14--V16--V17--V18--V19--V20--V21--V22--V1

对应的位置点为：

O—21—14—17—16—23—32—38—36—43—42—49—45—39—40—34—24—31—27—26—18—13—O

程序得出总路程为：

（对应数据在程序中运行）

43666m

（2）、将程序求得的路线与实际结合

由于程序求得的路线是在任一点都连通的前提下，但实际情况并不是任意点都联通，所以与实际情况有误差。

所以要将程序求得的路线与实际是否连通（是否有路）结合，将调整之前的最佳路线进行调整优化。

结合后所得的最终优化路线为：

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

对应数据：

1392

2192

1824

2196

2608

2098

1312

1114

1410

1537

1537

2618

918

1971

1971

2352

3217

1631

2325

1068

1780

1780

1068

3456

2259

3113

2182

可得总路程为：

52928m

算的总时间为：

（N=21）

=52928/（24*1000）60+3*21

=195min

方便起见化成：

3小时15分

送货路线如图

（1）：

（1）图

方法二：

通过观测判断，根据每个路径的长度，得出3条较优路线：

（1）路线;

O—21—17—14—16—23—32—35—38—43—42—49—42—45—40—34—31—24—19—13—18—31—27—39—27—36—21—26—O

总路程：

57552m

（2）路线：

O—18—13—19—24—31—34—40—45—42—49—42—43—38—35—32—23—16—14—17—21—36—27—39—27—31—26—O

总路程：

54995m

（3）路线：

O—26—21—17—14—16—23—32—35—38—43—42—49—42—45—40—34—31—27—39—27—36—27—31—18—13—18—O

总路程：

57326m

固由这三条路线的值得出最优解：

54995m

算的总时间为：

（N=21）

=54995/（24*1000）60+3*21

=204min

方便起见化成：

3小时24分

2、问题

（2）模型的建立与求解

此问不要求返回O点。

由于仍是1~30号货物，故交接货物时间仍是：

由于假设V恒定（24千米/小时），所以下一步仍只需求得最短路线。

方法一：

送货员从8点开始送货（前1~30号货物），根据每件货物的所需送往地点和送货不超过时间，可以观测出三段送货不超过时间：

9:

00—9:

30、10:

15、12:

00。

且这三段时间各自分布比较集中，分别为：

9:

00—9:

30段时间分布在图上21个点的左下角；

10:

15段时间分布在图上21个点的右上角；

12:

00段时间分布在图上21个点的右下角。

它按送货不超过时间顺序与第一问建模得出的最优路线的逆路线基本吻合。

故直接根据第一问方法得出的最优路线的逆路线确定它的逆路线：

线路（a）

O—18—13—19—24—31—27—39—27—31—34—40—45—42—49—42—43—38—36—38—35—32—23—16—14—17—21—26（可见上图）

当走到31点处，有两种路线可以选择。

1、先走27点2、先走34点

路线（a）是1情况，但当送货员走到38点就已经不能满足该店货物的送货不超过时间，故要2情况，即先走34点即将1情况作下小改进。

改进后所得的最优路线为：

线路（b）

O—18—13—19—24—31—34—40—45—42—49—42—43—38—35—32—23—16—14—17—21—26—31—27—39—27—36

对应数据：

（数据按路线从左到右录入）

2182

3113

3456

2259

1780

2325

1192

3217

2352

1971

1971

918

2618

1410

1114

1312

2098

2608

2196

1824

2192

1537

1068

1780

1780

2204

总路程：

52475m

算得总时间为：

（N=21）

=52475/（24*1000）60+3*21

=194min

方便起见化成：

3小时14分。

送货路线如图

（2）：

（2）图

方法二：

通过观测判断，根据每个路径的长度，得出2条较优路线：

线路（a）

O—18—13—18—31—24—31—24—40—45—42—49—43—38—36—27—39—27—31—26—21—17—14—16—23—32

总路程：

54462m

线路（b）

O—18—13—19—24—31—34—40—45—42—49—42—43—38—35—32—23—16—14—17—21—36—27—39—27—31—26

总路程：

53164m

所以得出方法二最优路线的总路程：

53164m

算得总时间为：

（N=21）

=53164/（24*1000）60+3*21

=196min

方便起见化成：

3小时16分。

3、问题（3）模型的建立与求解

由于100件货物的重量和体积限制（送货员的最大载重为50公斤，所带货物的最大体积为1立方米）。

算得100件货物的总重量为148公斤，总体积为2.8立方米。

所以送货员只能一次拿载重小于50公斤，货物的最大体积小于1立方米的货物。

所以我们让送货员从O往回三次（即从O出发后，还得再返回O两次）我们考虑将所有货物送达地点分成以库房（O点）为公共点的3个区域，将每个区域的送货员最佳路线分别求出，最后将其合并及得送货员的总最佳路线。

现将所有送货地点分成以库房（O点）为公共点的3个区域：

O—26—21—23—16—17—14—9—10—6—1—3—7—8—11—13—O

O—32—35—38—43—42—49—50—47—40—34—39—31—27—O

O—18—24—37—41—44—48—46—33—28—30—29—25—19—22—20—15—12—5—2—4—O

以每个区域的位置点为顶点分别建立3个最佳哈密顿圈（H圈）（方法同第一问解法）。

初始圈：

C1:

V1--V2--V3--V4--V5--V6--V7--V8--V9--V10--V11--V12--V13--V14--V15--V16--V1

C2:

V1--V2--V3--V4--V5--V6--V7--V8--V9--V10--V11--V12--V13--V14--V15--V1

C3:

V1--V2--V3--V4--V5--V6--V7--V8--V9--V10--V11--V12--V13--V14--V15--V16—V17--V18--V19--V20--V21--V1

根据两边逐次修正法型和矩阵翻转法将需要的表格数据录入编好的程序中

（由floyd算法得出，程序在附录给出，同第一问建模过程）

C1：

（1）由程序得出的最佳路线为：

V1--V2--V3--V4--V5--V6--V7--V8--V9--V10—V11--V12--V13--V14--V1

对应的位置点为：

O—38—35----32—27—43—42—40—47—50—49—34—39—31—O

程序得出总路程为：

36358m

（2）将程序求得的路线与实际结合

由于程序求得的路线是在任一点都连通的前提下，而实际并非如此。

故与实际有误差。

所以要将程序求得的路线与实际是否连通（是否有路）结合。

结合后所得的最终优化路线为：

O—26—31—27—39—27—31—40—47—40—50—45—42—49—42—38—35—32—23—17—21—O

对应数据：

（数据按路线从左到右录入）

1392

1537

1068

1780

1780

1068

2438

2331

2331

3043

3103

2352

1971

1971

2617

1410

1114

1312

1775

5489

2449

可得总路程为：

44330m

算得总时间为：

（N=13）

=44330/（24*1000）60+3*13

=150min

方便起见化成：

2小时30分。

见图（3）

（3）图

C2：

（1）由程序得出的最佳路线为：

V1--V2--V3--V4--V5--V6--V7--V8--V9--V10--V11--V12--V13--V14--V15--V16--V17--V1

对应的位置点为：

O—16—26—36—21—23—17—10—6—7—3—1—8—9—14—11—13—O

程序得出总路程为：

35687m

（2）将程序求得的路线与实际结合

由于程序求得的路线是在任一点都连通的前提下，而实际并非如此。

故与实际有误差。

所以要将程序求得的路线与实际是否连通（是否有路）结合。

结合后所得的最终优化路线为：

O—26—21—36—21—17—23—16—14—9—10—7—1—6—1—3—8—12—11—13—18—O

对应数据：

（数据按路线从左到右录入）

1392

2192

2880

2880

1824

1775

2098

2608

2681

1946

2059

1968

1294

1294

1916

1958

1757

1418

1670

3113

2182

程序得出总路程为：

41513m

算得总时间为：

（N=17）

=41513/（24*1000）60+3*17

=158min

方便起见化成：

2小时38分。

见图（4）

（4）图

C3;

（1）由程序得出的最佳路线为：

V1--V5--V2--V4--V3--V6--V7--V9--V8--V10--V12--V13--V15--V14--V16--V17--V18--V19--V20--V21--V1

对应的位置点为：

O—18—24—37—41—46—48—44—30—28—33—11—12—22—13—20—15—12—5—4—2—O

程序得出总路程为：

90115m

（2）将程序求得的路线与实际结合

由于程序求得的路线是在任一点都连通的前提下，而实际并非如此。

故与实际有误差。

所以要将程序求得的路线与实际是否连通（是否有路）结合

结合后所得的最终优化路线为：

O—18—13—12—8—3—4—2—5—15—22—20—22—30—28—33—46—48—44—41—37—41—30—22—29—25—19—13—18—O

对应数据：

（数据按路线从左到右录入）

2182

3113

1457

1757

1958

3536

2293

1253

19163

19140

1499

1499

1287

1018

1326

3759

1494

2153

2366

2602

2602

4998

1287

1098

1886

1966

3456

3113

程序得出总路程为：

97443m

算得总时间为：

（N=20）

=42905/（24*1000）60+3*20

=304min

方便起见化成：

5小时4分。

见图（5）

（5）图

总时间:

t=150+158+304=612min

方便起见化成：

10小时12分。

4.3模型的检验

4.3.1问题一中的模型的检验

由方法一：

运用MATLAB中的程序得出最优路线和最优路线的路程值

和方法二：

进行直接观测计算得出的最优路线和最优路线的路程值可知，

相应对应时间

两个方法互相验证了彼此的正确性，只不过思路不同，但建模由于数据分析。

4.3.2问题二中的模型的检验

由方法一：

由问题一的结果和实际的货物时间限制相结合得出的最优路线和最优路线的路程值和方法二：

进行直接观测计算得出的最优路线和最优路线的路程值可知，

相应对应时间

两个方法互相验证了彼此的正确性，只不过思路不同，但建模由于数据分析。

4.3.3问题三中的模型的检验

问题三我们运用的建模方法是问题一中方法一的建模方法。

经过前两问模型的验证，可得知建模的正确性。

所以问题三是对我问题一得建模的直接应用。

不同的是要将每个的最优解以O点为公共点合并在一起，就是最终的最优解。

五、模型评价

5.1模型优缺点

5.1.1模型优点

本模型运用到了图论知识，即图论中最佳送货员行驶路径问题与最佳哈密顿圈（H圈）中的相关结论。

运用两边逐次修正法型和矩阵翻转法，通过编写相应的程序建立