2022年送货线路优化模型 .pdf
《2022年送货线路优化模型 .pdf》由会员分享,可在线阅读,更多相关《2022年送货线路优化模型 .pdf(37页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、最优送货路线设计问题日期: 7 月 27 日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 37 页 - - - - - - - - - 1 最优送货路线设计问题摘要现今社会,网购已成为一种常见的消费方式,本文巧妙地解决了由网购的普及而造成的物流行业的兴盛情况,即货机如何以最快的时间, 最短的路程以及最少花费将货物送达到目的地的最优路线方案问题。我们先建立 0-1 规划模型,利用 Floyd 算法根据 MATLAB 编程处理数据到两省辖市间最短路径。问题一:我们可以建立
2、20 个省辖市之间的单旅行售货员模型(TSP ) ,利用二边逐次修正法算法, 通过 LINGO得到最优送货路线, 即得出该单旅行售货员模型(TSP )的最短路程 16400公里,用时 62.22 小时,最优送货路线为北京上海台湾福建江苏宁夏甘肃青海广西海南湖南香港重庆河南云南西藏新疆内蒙古黑龙江吉林北京。问题二:考虑到货机最大载重和最大体积限制,由题知总需求量为114 件,即货机不能一次携带所需, 需中途返回北京,根据最大载重我们可将其分为三组,即此问题可等价于为多旅行商售货员问题(MTSP) 。 我们利用 LINGO同步实现分组和最优送货路线,得到三组最优送货路线,将其加和,得到总的最优送货
3、路线。即得出该多旅行商售货员问题(MTSP) 的最短路程为 21900公里, 用时 74.34 小时。即北京上海台湾上海福建江苏宁夏甘肃青海新疆北京新疆西藏云南河南重庆广西海南湖南香港北京吉利黑龙江内蒙古黑龙江吉林北京。问题三:考虑到使花费最少, 且对问题一和问题二分别有所用时间最少,即我们建立双目标规划模型, 利用 LINGO求解出最少花费和最优送货路线。得到针对问题一的最少花费为584750元,路线为北京吉林黑龙江内蒙古台湾上海福建江苏宁夏甘肃青海新疆西藏云南河南重庆广西海南湖南香港北京。最后,最后我们进行模型的优缺点评价及改进和推广,使得模型能更加广泛地应用到其他领域。关键字 :0-1
4、规划模型TSP Floyd 算法二边逐次修正法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 37 页 - - - - - - - - - 2 一、问题重述现今社会网络越来越普及, 网购已成为一种常见的消费方式,随之物流行业也渐渐兴盛,每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位,现有实业公司, 该实业公司生产专业生产某专用设备产品,专用设备产品该每件重达 5 吨(其长 5 米,宽 4 米,高 6 米) ,该实业公司库房设在北京,所有货物均由一货机送货,该
5、机种飞机翼展88.40 米(机身可用宽20 米) ,机长 84米(可用长 50 米) ,机高 18.2 米(可用 14米) ,最多可装载 250 吨货物,起飞全重达 600 吨,平均速度为900 公里 / 小时)将货物送至全国各个省辖市(图1所示红色圆点,除北京之外共 19 个省辖市), 假定货机只能沿这些连通线路飞行,而不能走其它任何路线; 但由于受重量和体积限制, 货机可中途返回取货。 经过的各个省市都要一定的停靠费用和停靠时间(停靠时间为常量2 小时) ,假设经过某个省市的停靠费用为:停靠费用=5000元该省市的消费指数;表 1 省辖市新疆: 青海宁夏云南北京湖南海南福建台湾吉林需求量(
6、件)1 3 5 4 0 10 3 4 9 8 消费指数1.2 1.1 1.05 1.3 1.9 1.4 1.7 1.6 1.9 1.2 省辖市甘肃西藏重庆内 蒙古河南广西香港江苏上海黑龙江需求量(件)7 9 12 5 4 5 6 9 7 3 消费指数1.3 1.0 1.5 1.2 1.3 1.2 1.8 1.5 1.8 1.3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 37 页 - - - - - - - - - 3 202311281796812112284210
7、201212212422715344315图 1 问题 1:若图示中 19 个省辖市每个省辖市只要一件产品请设计送货方案,使所用时间最少,标出送货线路。问题 2:若图示中 19 个省辖市需求量见表1,请设计送货方案, 使所用时间最少。问题 3:若该实业公司为了花费最少,针对问题1 和问题 2 分别求出花费、标出送货线路。二、问题分析根据题目的要求我们可知,这是典型的旅行售货员问题(TSP ) 。先建立 0-1 规划模型,利用 Floyd 算法根据 MATLAB 编程得到两省辖市间最短路径矩阵。以下各问都在最短路径矩阵上实现的。问题一要求将货机去往每一个省辖市送一件产品,所耗时间最少的路线, 即
8、为单旅行售货员问题( TSP ) 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 37 页 - - - - - - - - - 4 问题二要求将各个省辖市的所需产品送去,因受重量和体积的限制, 货机不能载全部的产品去送货,必须返回北京取货,所以转化为多旅行售货员问题(MTSP) 。需要对省辖市进行分组, 求得每一次送货的最短路线,使路径之和最小,即为所用时间最少。问题三要求花费最少且所用时间最短,即我们可以建立双目标规划模型。三、模型假设1、货机的速度与其携带的货物重量
9、、体积、天气等因素均无关,为恒定的900公里/ 小时。2、某些送货点关联一个以上的货物,认为这些货物一次全部交接,无需分次交接,且停靠时间均为 2小时。3、货机只能沿图中的连通线路飞行,不能走其它任何路线。无连通的,货机需中转。4、假设在货机送货过程中, 库房的工作人员已经将下一批送货点货物准备完毕,货机刚回库房便可拿到货物开始下一批运送,这个过程不需要额外的时间。5 、如果中途回去取货一定是回到北京,如果货物不是送达目的地,决不卸货,即不考虑可以中途将货物寄存在除北京之外的点之后再返回去取的情况。6、一些省市之间没有航班,需要中转,假设中转过程不需要花费额外时间和费用(除航班费用外)。四、符
10、号说明符号含义2020D20 个点中任意两点之间的最短距离矩阵ijx0-1 决策变量ijh弧( ,)ij的长短( ,1, 2,)ijn2020H20 个省辖市两两之间的弧长矩阵名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 37 页 - - - - - - - - - 5 ijd点i和j之间的最短距离( ,1, 2,)ijnijQ从第i个省辖市到第j个省辖市时,第j个省辖市的消费指数ijW从第个i省辖市到第j个省辖市的权值五、模型建立与求解5.1 最短路径矩阵的计算根据这
11、一送货路线设计问题,首先需要得到库房(北京)与其它19 个目的地之间的最短距离矩阵。20 个省辖市之间并非两两连通,对于可以相互到达的点,二者之间的距离需要对经过的中间点之间的欧式距离求和而得。这一问题可以归结为图论模型中最短路问题。可以采用0-1 规划法寻求 20个省辖市两两之间的最短路径,设立0-1 决策变量ijx,其数学意义是:0,1,ijijxij最 短 路 不 经 过 弧 ()最 短 路 经 过 弧 ()用ijh表示弧( ,)ij的长短 ( 路程)。若i与j直接连通,则ijh为两点之间的欧氏距离,若i与不j直接连通 , 意义是从i不可直接抵达j, 则将ijh的值赋为 100 。则通过
12、对坐标计算可以得到20 个点两两之间的弧长矩阵2020H。设起点为 1,终点为k. 对于除了起点和终点以外的任一点i,11kijjx是从起点到终点的最短路径经过点i的充分必要条件 , 若点i在最短路上,那么从其他顶点到点i的弧中必有一条在最短路上,即有11kijjx;若10kijjx,说明最短路径不过点i,因而也有10kijjx,最短路径有且只有一条,这两种情况可以和写成111,1,2,20kkijjijjxxi。必须从 1点出发,即需满足111kjjx,最后必须名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -
13、- - - - - - 第 6 页,共 37 页 - - - - - - - - - 6 抵达终点k,即需满足11kjkjx。目标函数是最短路径上的所有弧长度之和最小,最短路问题用0-1 规划的数学模型描述如下:2 02 011minijijijzh x 2020112020120111,. .1,1,0,1ijjiijjijiijxxs txxx根据以上建立的模型,我们利用Floyd 算法根据 MATLAB 编程求解出 20个省辖市之间的最短路径距离矩阵2020D如下:20200232826272124121382831202112262316910230649112623353631518
14、142022212839323128605417201740413656148262015224437372612602326231421272201432262128101725271117530363439403555122531153238433637262620D52360338393454341246215242353629231755343041423757319432125453839122620143733360720163428302435354319133327214034377021234133322539361142183133273529322021029392813
15、203431171722810422124211623290181230241926121927318145712343143443959022282729364740392014846251293233284822034127143629302120263631424330321338283403341442628111222203815212124252040271233019232821222721155332523940355529741190743363724282250382536373252361445237040333416221610333633411171230242628
16、3138071592923173630333417193729282135327017103131253731341921227393011223633151705.2 问题一5.2.1 问题分析:本问要求货机从北京出发,往每一个省辖市去一次,最终回到北京,要耗时最少。一共 19 件产品,每件重达5 吨,长 5 米,宽 4 米,高 6 米,即总共重名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 37 页 - - - - - - - - - 7 95 吨,体积 2280立方
17、米,在飞机所能容纳的范围内。故我们可知所耗时间最少就等价于送货路程最短。于是问题转化为寻找一条能遍历指定的19 个省辖市的最短路线,即为出发点(北京)与其他19 个省辖市之间的单旅行售货员问题(TSP )。5.2.2模型建立:在得到了一个最短路径矩阵2020D之后,考虑该送货员一次携带需要配送的19件货物从北京出发送往指定的19个地点 , 为了寻求一条能遍历这 19个省辖市并最终回到出发点的最短路径,即实现所用总时间最短的目标, 必须合理安排送货顺序,此问题可以归结为一个运筹学中的单旅行售货员问题(TSP ) 。 北京和 19 个省辖市组成一个有限的无向图, 将任意两个省辖市之间的最短路径作为
18、二者之间的权。引入 0-1 决策变量ijx,其数学意义是:0,1,iji jxi j最 短 路 不 经 过 弧 ()最 短 路 经 过 弧 ()在本问题中,对于任意一点j,有且仅有一条路通往该点,即需满足条件20111, 2,20ijixj; 同时,对任意一点i,从该点出发的路有且仅有一条,即需满足条件20111,2,20ijjxj. 然而对于 TSP 问题这两个条件只是必要条件,即使满足了前两个约束条件, 仍无法避免可能出现的 TSP 子圈问题,为了过滤这一种情况,需要增加“不含子圈”的约束,采用文献3 介绍的方法,增加变量(1, 2,20)iui,并附加约束条件:1,1, 2, 20,1,
19、 2, 20,ijijuunxnijij且式中iu和ju均为非负实数。目标是从北京出发送完 19件货物再次回到北京所用的总时间最短,也即经过的总路程最短。建立 TSP 问题数学模型如下:202011minijijijzd x 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 37 页 - - - - - - - - - 8 20120111. .011ijiijjijijijxxs txuunxn或52.3 二边逐次修正法修正算法的设计及实现:定义设(,)GVE是连通无向图
20、,包含图G的每个顶点的路称为G的哈密尔顿路 (H am ilton路或H路). H am ilton含图 G 的每个顶点的圈 , 称为G的哈密尔顿圈 ( 或 Hamilton 圈或H圈). 含H am ilton圈的图称为哈密尔顿图( 或H am ilton图或H图). 在一个赋权完全图中 , 找出一个最小权的H圈, 称这种圈为最优圈 . 一个可行的办法是先求一个H圈, 然后适当修改 , 以得到具有较小权的另一个H圈。设找到一个初始H圈121.nCv vv v,则对所有适合11ijv的i和j, 总可得到一个新的H圈:1211121ijijjijjnCv vv v vvvvv v, 它是由C删去
21、边1iiv v和1jjv v,以及添加边ijv v和11ijvv而得到,如下图所示 . 定义若对于某一对 i 和 j ,有1111()()()()ijijiijjw v vw vvw v vw v v则圈 Cij将是圈 C 的一个改进 . 在接连进行一系列修改之后 , 最后得一个圈 , 不能再用此方法改进了, 这个最后的圈可能不是最优的但是它是比较好的,为了得到更高的精度, 这个程序可以重复几次, 每次都以不同的圈开始 . 这种方法叫做二边逐次修正法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -
22、- - - 第 9 页,共 37 页 - - - - - - - - - 9 5.2.4 模型求解:根据以上模型,利用 Lingo9.0 编程求得全局最优解 , 即为本问题的最佳售货员回路。最佳路线如下表所示:1640090022262.22所 用 时 间小 时。表 2 送 19 件产品至 19 个目标点的最快路线路线总路线长度所用时间北京上海台湾福建江苏宁夏甘肃青海广西海南湖南香港重庆河南云南西藏新疆内蒙古黑龙江吉林北京16400 公里62.22 小时绘制出路线图如图2、图 3 所示:5101520468101214161820模型一送货路线新疆西藏云南青海甘肃宁夏内蒙古吉林黑龙江上海福建台
23、湾香港海南湖南广西重庆北京河南江苏8121186202311281517434241521151220124722392212名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 37 页 - - - - - - - - - 10 图 2 用 MATLAB 求得的最短路径图图 3 直观路线图5.3问题二5.3.1问题分析:本问要求货机将表中各个省辖市的需求产品送到,即总共114 件产品配送到 19 个指定地点,所用时间最短的送货路径。因为114件产品重达 570 吨,体积达
24、13680 立方米,已超过飞机所能容纳的重量, 所以货机不可能一次携带全部的产品从出发点去往各个省辖市,必然要返回公司库房 (北京) 取货。于是问题可等价为多个货机从北京出发分送产品到各个目的地再回到出发点的情况,要求时间最少,即为求货机走过的路程之和的最小值,可归结为一个多旅行商售货员问题(MTSP) 问题。解决这一问题, 我们首先要对所有的送货点进行分组,使其转化为多个单旅行售货员问题, 然后再对每一组的路径进行优化,由题重量限制可知我们可以将其分为三组,使其每个路径最短,总体所耗时间最少。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -
25、 - - - 名师精心整理 - - - - - - - 第 11 页,共 37 页 - - - - - - - - - 11 5.3.2模型建立:北京和 19 个省辖市组成一个有限的无向图,将任意两个省辖市之间的最短路径作为二者之间的权。引入 0-1 决策变量ijx,其数学意义是:0,1,iji jxi j最 短 路 不 经 过 弧 ()最 短 路 经 过 弧 ()在本问题中,对于任意一点j,有且仅有一条路通往该点,即需满足条件20111, 2,20ijixj; 同时,对任意一点i,从该点出发的路有且仅有一条,即需满足条件20111,2,20ijjxj. 然而对于 MTSP 问题这两个条件只是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年送货线路优化模型 2022 送货 线路 优化 模型
限制150内