送货路线设计模型 

 

 

一.摘要：

 

 为了解决最佳送货路线一系列问题，建立了一系列模型。在第一问中送货的售货员出从O出发把货运到每一个点后的最短路径（即巡回路线最短）。这个问题可以转化为经典的旅行商问题（TSP）来解决，可以利用Floyd算法，我们用matlab软件求出该问题中其他21个点与0点的最小距离。并在相应的约束条件下利用lingo软件对该目标函数进行求得最优路线：

 

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

 

第二问要求我们在约束时间内求出最短距离。因此，我们采用简单的节约矩阵法，先使用用Flod算法求解，求出该问题中其他21个点与0点的最小距，然后把相同的时间进行分区优化；再联合题目的时间限制和第一问的最优解，得出最后结论：

 

O-18-13-19-24-31-34-40-45-42-49-42-43-38-36-27-39-27-31-26-21-17-14-

 

16-23-32  (单向路线)

 

第三问要把100件货物送达，总体积和重量至少要2次，可以用射线扫描法分3个区域用分三区, 对各区域计算其汉密尔顿回路, 求出最佳送货路线如下：

 

I区：0-21-17-23-16-14-9-10-7-1-6-1-8-3-4-2-5-15-22-20-22-29-25-

 

19-13-12-11-13-18-0

 

II区：0-21-17-23-32-35-38-43-42-49-42-45-36-27-31-26-0

 

III区：0-26-31-24-19-25-29-22-30-28-33-46-48-44-41-37-40-47-40-50-40-

 

34-31-27-39-27-31-26-0

 

第四问先利用最短路径算法得最远是点33，从而得到货物一次性送完的最短时间0.77h；从此点开始依次向两边囊括尽可能多的点，计算H-回路耗时，找出路线。

 

 

 

 

关键字：旅行商问题（TSP） Floyd算法  matlab  射线扫描法 汉密尔顿回路

 

 

 

 

 

 

 

二.问题重述:

 

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

 

现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。

 

 假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。

 

现在送货员要将100件货物送到50个地点。请完成以下问题。

 

1. 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。

 

2. 假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。

 

3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。

 

4. 要是公司派出多名送货员，并且保证在最短时间内送完，同时又要合理节约劳动力，求出要派出多少人，以及所要走的路径？

 

三．基本假设：

 

1． 忽略因自然原因及人为等因素造成的交通堵塞的可能。

 

2． 假设送货员回到出发点O后取货时间不计。

 

3． 在每到达一送货地点后停留时间一定，不会出现特殊情况而延误时间；

 

4． 假设货物在存放中，货物与货物之间无空隙.

 

5． 两点之间的通路既是两点之间的连线。

 

6． 送货员在所有路线上的速度恒定，均为24公里/小时

 

7． 假定每件货物交接花费3分钟，同一地点有多件货物也简单按照每件3分钟交接计算。

 

                   四．符号说明：

 

1．前30件货物总质量M；

 

2．前30件货物总体积V1；

 

3. 送货需要的总时间T;

 

4. 点i到点j的距离权值dij;

 

5.  送货员能否直接从节点i直接到达节点j;

 

6.  最短路径min Z;

 

7.  最短时间min t;

 

8.  最短路距离矩阵B(i,j);

 

9.  节约矩阵S（i,j）;

 

 

                  五．问题分析

 

第一问，求将1—30号货物送到指定地点并返回要求最短时间；经计算得前30号货物的重量是M=48.5公斤< 50公斤体积为V1=0.88立方米< 1立方米 ，因此只需要一圈就能送完。本题可转化为一个TSP路径问题，根据每个点的坐标，由folyd算法得出最短路径权值矩阵，并运用类似于最优树问题的解决方法，建立目标函数：寻找一条从起点0到各节点再到节点0的最短距离。

 

第二问，在第一问的基础上加了时间这样一个限制条件，根据问题提供的约束条件（路线信息图），由folyd求出的最短距离，然后建立节约矩阵,由据约束时间、最短距离、节约矩阵的限制，再参照问题一的最优解进行优化。

 

第三问，此题可转化为多个旅行售货员的最佳旅行售货问题，不存在多项式时间内的精确算法，而且图中节点数较多，为51个。故我们寻求一种较合理的划分准则，根据题目的约束条件和实际工作的经验在划分区域时应遵循如下准则:        

 

准则一: 每个区域里的送货总量小于送货员的最大载重;准则二: 每个区域里的送货总体积小于送货员所带最大的体积;准则三: 尽量将相邻的点分在同一区域;

 

     运用射线扫描法，计算并进行区域划分，划分后对各区域计算其汉密尔顿回路，然后优化求出最短路径。

 

     第四问，送货最短时间即送货到最远点所需时间，鉴于分组数量无限制，则可以此时间为上限设计送货分组路线，与实际情况相结合，分组数量须相对少，从最远从点开始依次向两边囊括尽可能多的点，若超出则减小囊括范围、并沿途搜索此H-回路所遍历的点，若包含未被囊括的点则将此点从单圈H-回路中删去，这样进行下去得到所需的分组。

 

 

 

               六．模型的建立与求解：

 

1、 问题一的模型建立及求解

 

在不考虑时间的前提下送前，我们首先用excel对各货物号信息表的前30件货物数据进行了汇总；

 

最大载重量M=48.5公斤，最大体积V1=0.88立方米

 

均未超出最大限度，即送货员可往复一次将所要求货物送完。

 

    有附件可知前30个货物的目的地如下表（把起点O也包含在内）：

 

 

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

我们用Flod算法求解最短路距离矩阵。其中i,j的值取上表的22个数。

 

1) 先根据题目数据给初始矩阵赋值，其中没有给出距离的赋给一个很大的值，以便于更新。

 

2)进行迭代计算。对任意两点，若存在，使，则更新

 

3)直到所有点的距离不再更新停止计算。则得到最短路距离矩阵 。

 

由旅行售货员问题(TSP)建立矩阵, =22;其中表示点i到点j的距离权值。为对称矩阵，令=0。现求节点0到各节点再到节点0的最短距离，要求各线路上的权值最小。设立变量, 其关系如下:

 

当节点和节点连通，=1；当节点和节点不连通，=0；目标函数为寻找一条从起点0到各节点再到节点0的最短距离，要求各线路上的权值和最小，故目标函数为：最短路径         

 

      （1） 对起始点0至少有一条路径出去，故有 

 

 

      （2） 对其余各节点，恰有一条路径进去，故有

 

 

      （3） 所有节点不出现闭合回路，约束为；

 

 总的线性规划模型为  ：

 

 

(1)

 

(2)

 

约束条件s.t.  (3) 

 

(4)

 

利用lingo软件和图论软件，计算出:

 

min Z= 54.7071(km)，min t =2.2741 + 1.1= 3.3741（h）

 

送货线路为：

 

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

 

若按照问题一的最优解，45号送货点和49不连通，通过对其优化，因此得出最短路线为：   

 

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

 

图如右：

 

 

2、 问题二的模型建立及求解：

 

     在满足约束时间限制的条件下求出最短设计路线，由问题一知1-30号货物的总质量为48.5公斤  总体积为0.88立方米，所以可以不考虑质量和体积对送货的影响。

 

（1）首先建立节约矩阵：节约矩阵是指货物依次送到，两个送货点所节约的距离：

 

    =  其中表示送货中心到送货点的最短距离,表示送货中心和送货点点的最短距离,表示送货点和送货点的最短距离。(节约矩阵数据见附表)

 

  （2）根据约束时间、最短距离、节约矩阵的限制，再参照问题一的最优解：

 

  0—18—13—(18)—31—27—39—(27)—(31)—24—(31)—34—40—45—49—42—43—38—(35)—32—23—16—14—17—21—26—0

 

其中最短路径  minZ和所用时间 min t为：

 

 

min Z= 53.7771()，min t== 3.3407（）

 

 

若按照问题一的最优解，45号送货点不能按时到达，通过对其优化，兼顾时间的要求，因此得出最短路线为：   

 

   0—18—13—18—31—24—31—34—40—45—42—49—42—

 

43—38—35—32—23—16—14—17—21—36—27—39—27—31—26—0

 

图如下：

 

 

3、问题三的模型建立及求解

 

题目给定了货物总重量为148公斤，总体积2.8立方米，送货员每次送货的最大载重为50公斤，最大体积为1立方米，50×3>148 （公斤）; 1×3>2.8（分钟） ;故估计把整个网络分为三个区域。为此，现决定采用射线扫描法，其具体步骤如下：

 

一、在线路图中以o为顶点大致设定3条射线将图形分成大致相等三个区域

 

二、计算其中送货总重及及总体积，若超出限制条件则调整射线角度；直至三区域中送货满足限制条件

 

最终分区如下

 

组名	需送货地点	总重量   （公斤）	总体积   (立方米)
Ⅰ	1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、22	49.99	0.9529
Ⅱ	21、23、26、32、35、36、38、42、43、45、49	49. 24	0.9040
Ⅲ	24、25、27、28、29、30、31、33、34、37、39、40、41、44、46、47、48、50	48.77	0.9431

三、对各区域计算其汉密尔顿回路，然后优化并得到最短路径如下：

 

 

组名	路线	行驶时间	总时间
Ⅰ	0-21-17-23-16-14-9-10-7-1-6-1-8-3-4-2-5-15-22-20-22-29-25-19-13-12-11-13-18-0	155.8895	660.3554
Ⅱ	0-21-17-23-32-35-38-43-42-49-42-45-36-27-31-26-0	71.11230
Ⅲ	0-26-31-24-19-25-29-22-30-28-33-46-48-44-41-37-40-47-50-40-34-31-27-39-27-31-26-0	133.3536

图如下：（I路线用红色，II路线用青色，III路线用黑色）

 

 

 

 

4 、问题四的模型建立及求解

 

对整个送货路线计算汉密尔顿单圈回路

 

利用最短路径算法得最远点为33（距离为17.3322km）  ；

 

送货时间上限Tmax = 0.722175+0.05=0.77h；

 

从此点开始依次向两边囊括尽可能多的点，计算H-回路耗时t，

 

即求MAX(n)；在约束条件 Tmax下

 

若超出则减小囊括范围、并沿途搜索此H-回路所遍历的点，若包含未被囊括的点则将此点从单圈H-回路中删去，这样进行下去，得分组

 

总计32   组

 

 

 

 

 

 

 

 

 

七．模型评价

 

7.1模型优缺点

 

优点: 

 

    （1）本文思路清晰，模型恰当，结果合理.由于附件所给数据的繁杂，给数据的整理带来了很多麻烦，故我们利用Excel排序本文成功地对0—1变量进行了使用和约束，简化了模型建立难度，同时给出了在各种约束条件下的最短路径的计算方法，具有较强的实用性和通用性，在日上生活中经常可以用到。

 

   （2）建立的模型通过利用folay算法来求出最短路径，把原图变为完全图，利用全局线性规划法充分发挥lingo软件包求最优解功能。这种算法不仅精确的算出最短所走的路线，而且还利用matlab软件程序来求，既方便又准确。

 

 

 

缺点：

 

   （1）对程序的要求很高，尽管经过了检验，但结果依然比较粗糙，有待进行进一步的改进。

 

   （2）在问题中节点过多，限制时间多，会在算法中并不一定能保证两点能够连同，因此需要对所得的结果进行优化处理。

 

   （3）本问题中所建立的模型，是舍弃了某些影响因素的结果，尽管这些因素的影响很小，但会使所求结果与实际生活中实际结果产生偏差。

 

 

 

 

八．参考文献

 

[1]姜启源 谢金星 叶俊，《数学模型（第三版）》，北京：高等教育出版社，2003。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

附录：

 

Floyd算法：

 

function [D,path]=floyd(a)

 

n=size(a,1);

 

D=a;

 

path=zeros(n,n);

 

for i=1:n

 

    for j=1:n

 

        if D(i,j)~=inf

 

            path(i,j)=j;

 

        end

 

    end

 

end

 

for k=1:n

 

    for i=1:n

 

        for j=1:n

 

            if D(i,k)+D(k,j)<D(i,j)

 

                D(i,j)=D(i,k)+D(k,j);

 

                path(i,j)=path(i,k);

 

            end

 

        end

 

    end

 

end

 

!旅行售货员问题;

 

model:

 

sets:

 

  city / 1.. 5/: u;

 

  link( city, city):

 

       dist,  ! 距离矩阵;

 

          x;

 

endsets   

 

   n = @size( city);

 

data:   !距离矩阵，它并不需要是对称的;

 

  dist =    ;  !这里输入最短距离;

 

enddata

 

  !目标函数;

 

  min = @sum( link: dist * x);

 

 

 

  @FOR( city( K):

 

    !进入城市K;

 

    @sum( city( I)| I #ne# K: x( I, K)) = 1;

 

 

 

    !离开城市K;

 

    @sum( city( J)| J #ne# K: x( K, J)) = 1;

 

  );

 

 

 

  !保证不出现子圈;

 

  @for(city(I)|I #gt# 1:

 

    @for( city( J)| J#gt#1 #and# I #ne# J:

 

      u(I)-u(J)+n*x(I,J)<=n-1);

 

  );

 

  

 

  !限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解;

 

  @for(city(I) | I #gt# 1: u(I)<=n-2 );

 

  !定义X为0\1变量;

 

  @for( link: @bin( x));

 

end