送货路线设计问题讲解.docx

资源描述

送货路线设计问题讲解.docx

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

送货路线设计问题讲解.docx

送货路线设计问题讲解

期末数学建模

报告（A）题

120540214

120610317

姓名：

李飞专业：

功能材料学号：

姓名：

谭秀松专业：

自动化学号：

2014-6-7

送货路线设计问题

摘要

现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，针对一个送货员要去城市多处送货并返回，该图为一个网络图，如何设计线路使送货员所用时间最少。

因为速度是恒定的，并且货物交换时间也相同，所以把求时间最短问题转化为求路径最短的问题，采用Floyd算法思想、借助矩阵、MATLAB软件和编程，求出最短距离矩阵和最短路径矩阵。

再通过数据的分析、筛选和计算，从而可在图上标出送货员到各个点的最短路径，得到最优解。

针对问题一：

采用“D-J模型”。

在此模型中，运用Floyd算法求解,然后套用此模型可以得到最优的结果是：

送货员所走过的总路程：

54707.5米。

针对问题二：

采用“分析&递推模型”。

在此模型中利用分析法和递归的思路建立动态的方法求得最优化结果来相结合求解,然后套用此模型可以得到最优的结果是：

送货员所走过的总路程：

52004.37米送完全部货物所需时间：

3小时37分01秒。

针对问题三：

分区送货策略模型”。

通过对送货点的分成不同的区域，在对其继续单独的利用模型二计算，得到最优的结果为：

关键词：

分析&递推模型Floyd算法Kruskal算法最短路径最小生成树法

一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方。

所以在快递公司送货策略中，确定合理的行走路线是关键的问题。

问题

（1）在送货员送货路线设计问题中，送货员从图1中的起点O出发，将1~30件货物送到指定目的地并返回，要求所用时间最短。

此时送货员可将30件货物一次性带上，因为这30件货物的总重量48.5kg、总体积0.88m3并没有超过送货员的最大载重和所带货物的最大体积。

问题

（2）送货员从早上8点开始送货，要将1到30货物送到指定地点并且不超过指定时间。

而且他们往往要去很多地方，如果在路线上选择不合理的话，不仅不能按时将货物送到指定地点，反会浪费更多的时间。

这样不仅要考虑将货物送到而且要满足不超过指定时间。

问题（3）送货的数量增加由30件增加到100件，不考虑时间限制。

但是要考虑送货员的最大载重和所带货物的最大体积。

很明显送货员不可能一次性将货物带完，必须把货物分批送到，还要满足所走的路线最短。

2.问题分析

（1）题目中只从快递公司派出一个送货员，到任意未配送的送货点，然后

将这个送货派到最近的未服务的送货点范围之内，且最大载重不超过50kg，货

物体积不超过1立方米。

在问题二中还必须使每一件货物在指定时间内送达。

继续上述指派，直到各点总重量超过50kg或者体积超过1立方米。

最后业务员返回快递公司，记录得到的可行行程（即路线）。

对得到的可行的行程安排解中的每一条路径，计算路线是否最短，时间是否最少。

即得到所需的最短路线。

（2）为此我们必须制定合理的送货策略———一个合理的送货策略是指送货员每天在有限的时间内，尽量多送货，使日送货量达到最大，让送货员在几个指定的送货点能最有效率的完成送货任务。

每天要将所有的货物全部送到指定点，不能出现每天有未接到服务，而货品在邮局积压的情况。

送货公司要尽量节约人力成本，从而使自己的利益最大化。

送货安排要合理，不要出现送货点混乱和兜弯路的情况。

根据这些合理性原则，我们需要给送货公司制定出在固定的送货点上安排好每个送货员的送货和运行线路，以及总的运行公里数，而且是需要的送货员尽可能少，总路线尽可能短。

（3）快递行业正蓬勃发展，为我们的生活带来更多方便。

为了保证快件能够在指定的时间内和规范的条件下送达目的地，设计最快完成路线与方式成为了快递公司的首要之需。

快递公司不但要求每一件货物需要在指定的时间内送达，

而且还要使每个送货员送货的路线最短，因此，如何用最少的时间准时完成所有的任务是最重要的。

在约束条件下，应确定圆满完成每天的送货，保证货物不因延误时间而耽误到客户的需要，这些都是我们需要考虑的问题。

（4）通过以上分析，我们建立了“D-J模型”，“分析&递推模型”，“分区送货策略模型”。

3.模型基本假设

1．假设送货员在送货的过程中没有出现把货物弄丢等意外情况，全部货物都能准确送到；

2.假设送货员在送货的过程中不考虑天气等突变因素影响送货员行进的因素；

3．假设送货员在送货的过程中没有退货情况，所有的货物都能全部送出；

4．假设送货员在送货的过程中全部把货送到位，忽略把货物送错重送的情况；

5.假设送货员在送货的过程中不考虑路途中的交通堵塞问题，随时保持速度恒定不变；

6.假设数据整理后无其他错误。

4.符号说明

Inf：

表示相应两点不能直接到达

dij：

各个点之间的坐标距离

pij：

各点之间在有权图上的最短距离矩阵

qij：

各点之间在有权图上的最短路径矩阵

cij：

表示此题例图的权矩阵

M1：

1—30号货物的总重量

100

M2：

1—100号货物的总重量

M31：

第三问第一次携带货物的总重量

M32：

第三问第二次携带货物的总重量

M33：

第三问第三次携带货物的总重量

V1：

1—30号货物的总体积

100

V2：

1—100号货物的总体积

V31：

第三问第一次携带货物的总体积

V32：

第三问第二次携带货物的总体积

V33：

第三问第三次携带货物的总体积

S1：

第1问的最短路程

S2：

第2问的最短路程

S3：

第3问的最短路程

T：

第2问所用的总时间

5.模型建立与求解

深度探索

此题共有50个目标点，加上出发点原点O共51个点，要求将货物送往目标点，且用的时间最短，则必须知道目标点和原点O的距离（令O点为第51个点），及各个点之间的坐标距离dij。

此图并不是每个点都相连，有些点不能直接到达，所以要先列出此题的权矩阵cij，然后求出它们之间的最短距离pij和最短路径

qij。

则模型规划如下：

51515151

dij=xixj2yiyj2，pij=cijxixj2yiyj2

i1j1i1j1

i=1,⋯,51；j=1,⋯,51。

利用MATLAB软件进行计算，编程结果得：

dij取值情况如下表所示

⋯

7740.2

1916.3

5452.7

⋯

16603

14854

14871

7959.7

7740.2

5825

2292.6

⋯

14331

17770

16159

12265

1916.3

5825

3536.4

⋯

15670

15212

14774

8537.9

5452.7

2292.6

3536.4

⋯

14493

16475

15266

10499

6583.6

1252.9

4669.4

1161.4

⋯

13993

16758

15310

11084

1294.3

8679.2

2940.1

6391

⋯

16289

13806

14043

6876.8

1968.2

8750.7

3242.5

6492.8

⋯

15566

12973

13200

6049.1

∶

⋯

∶

15588

13968

14780

13901

⋯

1494.1

9268.5

5739.6

10688

14125

15339

13988

14445

⋯

6857.9

3888.1

822.34

7095.8

16603

14331

15670

14493

⋯

10694

7138.9

12094

14854

17770

15212

16475

⋯

10694

3568.8

6933.9

14871

16159

14774

15266

⋯

7138.9

3568.8

7680.9

7959.7

122658

537.91

499

⋯

12094

6933.9

7680.9

cij得取值情况如下表

⋯

Inf

1916.3

Inf

⋯

Inf

2292.6

1252.9

⋯

Inf

1916.3

Inf

3536.4

Inf

⋯

Inf

2292.6

3536.4

Inf

⋯

Inf

1252.9

Inf

⋯

Inf

⋯

Inf

⋯

Inf

3568.

Inf

3568.

Inf

⋯

Inf

此表中的Inf表示相应两点不能直接到达，数值表示两点间可以直接到达的

距离值，0表示自身到自身的距离

利用Floyd算法求得pij，pij取值情况如下表所示

⋯

7745.3

1916.3

5452.7

8998.3

⋯

16277

18761

20306

16989

10068

7745.3

5829.1

2292.6

1252.9

⋯

22427

18002

26325

22757

16296

1916.3

5829.1

3536.4

7082

⋯

16676

17856

20705

17388

10467

5452.7

2292.6

3536.4

3545.6

⋯

20212

20295

24242

20924

14004

8998.3

1252.9

7082

3545.6

⋯

21174

16749

25073

21504

16563

16277

22427

16676

20212

21174

⋯

11253

8943.5

5374.7

9215.

18761

18002

17856

20295

16749

⋯

11253

10708

7139.6

15806

20306

26325

20705

24242

25073

⋯

8943.5

10708

3568.8

11722

16989

22757

17388

20924

21504

⋯

5374.7

7139.6

3568.8

9928.

10068

16296

10467

14004

16563

⋯

9215.8

15806

11722

9928.1

（1）从起点51出发，行遍每一个地点并且要把30件货物送到指定目的地并返回，要

求所用时间最短。

由题意得：

1—30号货物的总重量为：

M148.550；总体n1

积为：

V10.881，所以一次性可将货物全部带完。

行走路线如下：

路线

51（O）262117141623323538363843

路程

1392.1+2191.7+1823.9+2195.7+2607.7+2097.6+1311.9+1114+1409.7+1537.4+1537.4+

路线

4249424540343127392731241913

路程

2618.4+917.67+1971.4+1971.4+2351.7+3217+1630.8+2324.7+1067.8+1779.9+1779.9+

路线

1851（O）

路程

1067.8+1780.1+2258.6+3455.7+3113.5+2182=54707.5最（短路程）

最短路程:

S1=54707.5（米）

2）5.1问题一：

在第一题的基础上，第二题加了限制条件（将货物在指定时间内

送到指定地点），送货员还是可以将货物全部携带，但没有限制必须返回，所以行走路线如下：

24公里/小时=400米/分

1阶段

路线

51（O）18131924

路程

2182+3113.5+3455.7+2258.6

2阶段

路线

2431344045

路程

1780.1+2324.7+1630.8+3217

3阶段

路线

454249424338

路程

2351.7+1971.4+1971.4+917.67+2618.4

4阶段

路线

3836383532231614172126312739

路程

1537.4+1537.4+1409.7+1114+1311.9+2097.6+2607.7+2195.7+1823.9+2191.7+1537+1067.8+1779.9

1阶段用时：

（2182+3113.5+3455.7+2258.6）/400+3*2+3=36.5242min=36分31秒此时刻时间为：

36:

31<9:

00:

00满足条件

2阶段用时：

（1780.1+2324.7+1630.8+3217）/400+5*3+3=43.382min=43分23秒一二阶段共用时:

36分31秒+43分23秒=79分54秒此时刻时间为：

19:

54<9:

30:

00满足条件

3阶段用时：

（2351.7+1971.4+1971.4+917.67+2618.4）/400+4*3+3=39.5672min=39分34秒

前三阶段共用时:

79分54秒+39分34秒=119分28秒此时刻时间为：

59:

28<10:

15:

00满足条件

4阶段用时：

（1537.4+1537.4+1409.7+1114+1311.9+2097.6+2607.7+2195.7+1823.9+2191.7+1537+1067.8+1779.9）/400+13*3+3=97.5483min=97分33秒总共用时为:

119分28秒+97分33秒=217分01秒=3小时37分01秒此时刻时间为：

11:

37:

01<12:

00:

00满足条件

全程总走过的路程为：

S2=52004.37（米）

全程总用时为：

T=3小时37分01秒

（3）要将100件货物送到指定地点，无时间要求，并要求返回，求最短路径。

由题意得：

1—100号货物的总重量为：

M214850；总体积为：

V22.81，所以至少要三次性才可将货物全部带完。

行走路线如下：

第1次从O出发

路线

51（O）181311121552438161

7109141623172151（O）

路程

2182+3113.5+1669.6+1417.7+4805.8+5004.5+1252.9+2292.6+3536.4+

1958.1+2863.8+1294.3+1294.3+1968.2+2059.4+1945.5+2681.3+2607.7

+2097.6+1774.5+1823.9+1796.9=51440.5

第2次从O出发

路线

51（O）1831241925292220223028

33464844413740474034312651（O）

路程

2182+2103.7+1780.1+2258.6+1966.2+1885.9+1097.9+1498.9+1498.9+

1287.5+1017.9+1325.7+3758.5+1494.1+2152.5+2366+2601.9+2090.1+

2331.2+2331.2+1630.8+2324.7+1537+1392.1=45913.4

第3次从O出发

路线

51（O）2631273927364550494243

38353223172151（O）

路程

1392+1537+1067.8+1779.9+1779.7+2203.9+3182.5+3102.8+3568.8+1971.4

+917.67+2618.4+1409.7+1114+1311.9+1774.5+1823.9+1796.9=34352.8

红、绿、蓝分别是一条回路，第一次从O点出发，经过18这个地点，但不

带2号，48号货物：

M3149.9950，V31=0.9412<1；第二次从O

点出发经过31，26这两个地点，但不带61号，4号，23号，56号货物

M3249.7350,V32=0.8997<1;第三次从O点出发

M3348.2850,V33=0.9591<1，满足题目要求。

全程总走过的路程为：

S3=51440.5+45913.4+34352.8=131706.7（米）

五、模型评价

A．优点：

1.在模型求解最短距离过程中用了MATLAB软件编程，把大量的运算交给计算机处理，提高了计算的准确性。

2.本模型通过转换的思想，把求时间最短转化为求路径最短，使问题变的简单些，便于求解。

3.定性与定量相结合的方法解决了送货员送货问题。

B.缺点：

1.由于本模型的计算量大，在计算的过程中，存在数据的处理，比如：

四舍五入导致最后的计算数值可能存在误差。

参考文献

【1】陈光亭裘哲勇.数学建模.北京：

高等教育出版社

【2】肖华勇.实用数学建模与软件应用.西安：

西北工业大学出版社2008.11.S1期，2006年

【3】刘承平数学建模方法北京：

高等教育出版社

【4】张秀兰林峰数学建模与实验北京：

化学工业出版社

附录

x=[91851445727037352620100801002571601384511935785065857630134052125153651416588255855780127702200147657790443510860103855652580156593951483512507280153051239064101391595108345493013265141803030109152330773588511575801011000];

y=[5005605706709951435228025252680305035454185520053255975704573858075816583558560883590559330952596351050097659865995510100103651090011065113751141511510116101205012300136501414514215150601423514500145501488015160153258250];

fori=1:

forj=1:

d（i,j）=sqrt（（x（i）-x（j））^2+（y（i）-y（j））^2）;

c（i,j）=inf;

c（i,i）=0;

end

c（01,08）=d（01,08）;c（01,03）=d（01,03）;c（02,20）=d（02,20）;c（02,04）=d（02,04）;c（03,08）=d（03,08）;c（03,04）=d（03,04）;c（05,15）=d（05,15）;c（05,02）=d（05,02）;c（06,01）=d（06,01）;c（07,18）=d（07,18）;c（07

01）=d（07,01）;c（08,12）=d（08,12）;c（09,14）=d（09,14）;c（09,10）=d（09,

10）;

c（10,07）=d（10,07）;c（11,12）=d（11,12）;c（12,13）=d（12,13）;c（12,25）=d（12,25）;c（12,15）=d（12,15）;c（13,18）=d（13,18）;c（13,19）=d（13,19）;c（13,11）=d（13,11）;c（14,18）=d（14,18）;c（14,16）=d（14,16）;c（14,17）=d（14,17）;c（14,21）=d（14,21）;c（15,22）=d（15,22）;c（15,25）=d（15,2）;

c（16,23）=d（16,23）;c（17,23）=d（17,23）;c（18,31）=d（18,31）;c（19,24）=d（19,24）;c（20,22）=d（20,22）;c（21,26）=d（21,26）;c（21,36）=d（21,36）;c（21,17）=d（21,17）;c（22,30）=d（22,30）;c（23

展开阅读全文