数学建模的题目：送货路线设计问题

佛自业障

五 模型假设

（1）假设送货车辆不会在半路抛锚，半路无塞车现象，即送货员送快递途中不受任何外界因素影响，且无需考虑送货员的工作时间与休息时间。

（2）送货员到某送货点后必须把该送货点的快件送完。

（3）假定送货员最大载重50公斤，所带货物最大体积1立方米。

（5）假设每个送货点的货物一次被送到，不会出现分批送到的情况。

（6）假定每个业务员都的按照，送货员的平均速度为24公里/小时和每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。

（7）假设数据整理后无其他错误。

# o1 m! n" ?& [( K

六 主要符号说明

Ti：序号为i的货物号的快件重量

Ni：表示为i个货物号

vi：表示第i个送货地点（xi ，yi）序号为i的送货点的坐标

ei：表示两个送货点的关系（见附录表3-1.）

G=<V,E>：是一个简单图，V=ív0,v1,v2,…,vny集合V是图顶点集(代表系统的个体)，E=íe1,e2,…,eny集合E是图的边集（代表系统个体之间的关系）

A(G)=( ) n×n：称A(G)为G的邻接矩阵。简记为A。

, J2 S, [( S/ X# Z" M% X  F; ~5 G2 t

其中：

i,j=1,…,n

Wi：表示第i件货物的重量。

Bi：表示第i件货物的体积

MaxW：表示能够承受的最大的总重量，即MaxW=50公斤

MaxB：表示能够承受的最大的总体积，即MaxB=1立方米

K：表示人送货员在送货的过程中返回快递公司的次数

七 模型建立与求解

7.1.问题一：

分析：由于表3-3可以知道，前30件货物的重量和体积都不会超过送货员所承受的最大载重，所以假设送货一次性把30件货物都带上。

11.

例如：（为了计算的方面先用一些较小和较少的数据代替）

有如下的v0~v16的送货点，其中ei表示两个送货点之间的关系。

1-1：Dijkstra算法

是求最短路径最常用也是最有效的方法，但是它只能求从某一顶点到其余各顶点的最短路径。而实际生活中的送货往往出现由某一快递公司送往多个送货地点后再返回快递公司的情况，对于这种情况，就得重复多次用Dijkstra算法，计算起来比较复杂。1962年Floyd提出了求任意两点间最短距离的算法，但是当地址比较多时，也是比较复杂的，而且也很难计算出回路的最短距离。通过研究对这类由快递公司到多个送货点然后返回原地的最短路径选取作简单的探讨。由于图1可以知道：

1)求出v0到v7的最短距离为7．6千米， v0到v9的最短距离为6.6千米，v0到v12的最短距离为9.1千米，v0到v15的最短距离为11.5千米。

2)仍用Dijkstra算法计算到v7到v9、v12、v15的最短距离；然后再求到v7最短距离的点(v9、v12、v15中的点)到其他两点的距离，然后求剩下两点的最短距离。

3)根据排列组合原理计算从v0到路经各站点回到原点的最短距离。

同样的道理，把50个送货点看做是题目中的V(v1,v2---v50)，由附录表3-1.可以得到E（e1，e2.----e76）。

用同样的方法计算，可以明显看到计算量超级大，无法计算得到。这是因为此算法用于求给定两点间的最短距离比较方便，例如送快递过程中只要将货物从快递公司送到指定送货点然后返回，但对于多个送货点最短路径的求解就比较繁琐了，本研究过程涉及了30个送货站。

所以不单独采用Dijkstra算法。

2-2用Kruskal算法计算：

Kruskal算法的要点是在与已选取的边中不构成回路的边选取最小者，图2黑线部分即为最小生成树。

计算过程见表l：

此时恰巧必经站点在一条通路上，根据抄近路法连接，根据抄近路法连接v14、v15，如图2即走v0，v2v6v7v13v14v15v12v8v9v5v3v0全程共长27．1千米。

Kruskal算法计算起来比Dijkstra算法要简单的多，但是误差比较大

如图2即走全程共长27．1千米。

所以也不适合直接采用Kruskal算法来计算。

3--3采用“D-J模型”指的是：

Dijkstra算法和Kruskal算法相结合求解

3-1算法步骤：

1)求出到v0，v9，v12，v15的最短距离和次最短距离点，此时v0到v9 的最短距离为6．6千米，到v7 的最短距离为7．2千米，分别为最短距离点和次最短距离点，从而确定起始第一站和最后一站。并且根据表2可得应走v0,v1,v7和v9, v5,v3, v0.

2)将图1划分成两部分，如图3，在下版图中只有只有v7,v8,v9,v11,v12,v13,v14,v15,v16等9个点，因为v15是必经点，故以v15为起始点，根据Kruskal算法制造一棵最小生成树如图4，此时根据实际情况有两种选择方案。

（1）根据抄近路法连接V14，v15，则所走的路径为v0，v1，v7，v13，v14，v15，v12，v8，v9，v5，v3，v0，总长为6.6+7.2+13.7=26.7千米。

（2）选择走回头路，因为v12，v15都为必经点，又是临近点，故可以考虑走回头路，即v0，v1，v7，v13，v14，v15，v12，v8，v9，v5，v3，v0，总长为6.6+7.2+12.9=26.7千米。

按照路径较短应选（1）就是应该走v0，v1，v7，v13，v14，v15，v12，v8，v9，v5，v3，v0，总长为26.7千米。事实上，从v0经过v7，v9，v12，v15返回的过程中最短的路线就是v0，v1，v7，v13，v14，v15，v12，v8，v9，v5，v3，v0，故此误差最小，几乎为0.且把图划分为两部分后，计算起来就简单多了。

用同样的方法计算出最短的路线为：

因此，送货员所走过的总路程：56271.14573米

行走所需要的时间：2.3446小时

货物交接总时间：1.5小时

送完全部货物所需时间：3.8446小时

1.2利用“分析&递推模型”

1-1：要送前30件物品时，由表3-3可以知，最起码只要经过固定的送货点。

Step1：分析：这样如果只是从这些固定点出发，这样可以避免了浪费无关的送货点的时间。这样把从表面上看，送货员所走的路程花的时间会相对短些。但是如果只是这些固定点有没有可能构成一个通路呢？

Step2：如果满足Step1，才进行Step3的；否则就没有必要进行下去。

Step3：利用递推的方法，如果要走完所有的送货点，只要每个都是最短的，那么就能满足。若F(n-1)[表示前n个ei的和是最小的]，同时en（表示n条边的长度）也是最小的，那么F(n)就必然是最小的。

由于表3-3可以知道，推算一下就可以很快的得出路线：

送货员所走过的总路程：60045.52405米

行走所需要的时间：2.501896835小时

货物交接总时间：1.5小时

送完全部货物所需时间：4.001896835小时

综合以上模型可以得出，需要的最短时间为：3.8446小时

, g5 H( q- k( I# o& ^3 f3 J