送货路线论文.doc

送货路线设计问题
摘要
本问题是货物运送路线的优化设计问题,要求我们在给定的送货地点,送货时间,综合考虑货物最大载重和体积这些限制条件下找到最快运送完货物的路线。
先利用两点坐标公式,把送达地点的具体位置标出,并求出可达点之间的直接距离,。
对于第一个问题,首先用Floyd算法求解出任意两点间最短距离。 公里,
对于第二个问题,在第一问得到的最优解的基础上,进行模型进一步优化操作,使得满足时间限制,最终得到了优化路线以及对应的总路程、总耗时。,。
对于第三个问题,我们使用节约矩阵和三分法,,
关键词:最佳路线 TSP Floyd算法时间约束节约矩阵三分法
1、问题重述
现今社会网络越来越普及,网上购物已成为一种常见的消费方式,随之物流行业也渐渐兴盛,每个送货员需要以最快的速度及时将货物送达,而且他们往往一人送多个地方,请设计方案使其耗时最少。
现有一家快递公司,库房在图1中的O点,一位送货员需将货物送至城市内多处,请设计送货方案,使所用时间最少。该地形图的示意图见图1,各点连通信息见表3,假定送货员只能沿着这些连通线路行走,而不能走其它任何路线。各件货物的相关信息见表1,50个位置点的坐标见表2。
假定送货员最大载重50公斤,所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟,为简化起见,同一地点有多件货物也简单按照每件3分钟交接计算。
现在送货员要将100件货物送到50个地点。请按以下要求设计最快完成任务的路线,并且给出路线图和完成时间。
1. 若将1~30号货物送到指定地点并返回。
2. 假定该送货员从早上8点上班开始送货,要将1~30号货物的送达时间不能超过指定时间。
3. 若不需要考虑所有货物送达时间限制(包括前30件货物),现在要将100件货物全部送到指定地点并返回。由于受重量和体积限制,送货员可中途返回取货。可不考虑中午休息时间。
图1 快递公司送货地点示意图
O点为快递公司地点,O点坐标(11000,8250),单位:米
2、条件假设
为简化问题,作如下假设:
送货员只能沿可连通线路行走,而不能走其它任何路线。
送货员最大载重50公斤,所带货物最大体积为1立方米。
每件货物交接时间均为3分钟,同一地点有多件货物也简单按照每件3分钟交接计算,不会出现特殊情况而延误时间。
送货员保持匀速行驶,速度为24公里/小时,不考虑堵车等意外情形。
3、符号说明
,
送达地点
第组货物的总重量
最大载重量
第组货物的总体积
最大体积
C
邻接赋权矩阵,即任意两点间的最短路径的距离矩阵
任意两点间最短距离
两点间的节约距离
到点的最短距离
到点的最短距离
到的最短距离
4、问题分析、建模及求解
1、问题一
问题分析
利用Excel对附表2(各货物信息表)对前30好货物进行数据处理分析,可知前30号货物的总重量为<最大载重,总体积为<最大体积,均没有超过最大载重和体积限制,所以可以确定送货员一次就能把货物送完,不需返回。因此,求解货物运送路线问题也就转变成了从一点出发,遍历区内所有指定地点,最后回到起点的最短路径问题。显然,这是一个类TSP问题。
模型建立与求解
该问是一个特殊的哈密尔顿回路,为了历遍所有送货点,它可能会经过一些额外点。我们将首先用MATLAB编程求出相互之间可直接到达点的距离,然后利用求得的可达点间的距离,用MATLAB Floyd算法程序求出各点间的最短路径,构造出带权邻接矩阵。
我们可以根据Floyd算法算出对于第一问所必过的22点(包括零点)的赋权矩阵:
0 ……
0
0
0


……
引入0-1整数变量,表示路线从到,表示不走到路线,则TSP模型可表示为
运用Lingo求解得,得X(1,10)= X(2,6)= X(3,4)= X(4,8)= X(5 3)= X(6,1)= X(7,5)= X(8,13)= X(9,2)= X(10,7)= X(11,17)= X(12,11)= X(13,15)= X(14,12)= X(15,16)= X(16,20)= X(17,9)= X(18,14)= X(19,21)= X(20,22)= X(21,18)= X(22,19)=