没有合适的资源?快使用搜索试试~ 我知道了~
92个牛奶配送点的牛奶配送问题
需积分: 39 61 下载量 105 浏览量
2022-02-14
15:27:01
上传
评论 72
收藏 12.17MB PDF 举报
温馨提示
试读
14页
物流配送与我们的生活密切相关,而“最后一公里”是物流中的瓶颈。如何 合理的安排配送任务和设计配送路线是快递公司面临的一个实际难题。 试针对某市区的鲜牛奶配送需求,建立数学模型分析解决下面的问题: (1)附件 1 中给出了某城区 92 个牛奶配送点的坐标、需求量及相互之间的连接道路。假设牛奶站的位置坐标为原点,牛奶配送车的载货量为 400 瓶,速度是 20 公里/小时,每个需求点的下货时间为 1 分钟,配送车辆送完牛奶后需返回牛奶站。请设计一个运输成本最低的配送方案。 (2)由于鲜奶的保鲜要求,需要尽快的完成配送。请在考虑成本的前提下, 设计一个最快的配送方案。
资源详情
资源评论
资源推荐
1
牛奶配送的路径选择
摘要
本文将牛奶配送问题转化为车辆路径问题,建立相应的整数线性规划模型,
结合 Floyd 算法,运用 MATLAB 编写遗传算法进行求解。
针对问题一,我们先根据题目提供的数据,建立邻接矩阵,采用 Floyd 算法,
结合 MATLAB 得到最短距离矩阵和 path 矩阵;然后利用 MATLAB 编写遗传算法求
出在最短路径下的路线图;最后根据路线图和最短距离矩阵以及 path 矩阵得到
实际路线如下:
路
线
一
0-23-13-22-11-
26
-10-
34
-33-8-47-5-49-53-52-51-50-
51
-
52
-56-57-58-59
-6-
47
-7-32-31-15-0
路
线
二
0-70-69-78-
79
-80-18-83-84-85-20-86-87-92-91-88-89-90-82-81-
18
-
80
-
79-19-77-76-0
路
线
三
0-24-25-12-27-26-
10
-34-9-35-45-46-55-54-
55
-3-44-2-40-39-38-
39
-
36
-
37-36-16-14-21-0
路
线
四
0-28-29-30-48-61-60-62-4-63-64-65-66-67-68-75-1-74-73-
74
-71-72-43
-42-17-41-0
求得的最低运输成本为 34.6092.
针对问题二,我们先对租车数小于等于 4 的情况进行考虑,分析问题一的结
论,以租车数,租车成本,运输成本,总成本,总运输时间为表头建表,记录相
关数据。然后根据问题一的模型,用 MATLAB 计算车辆数为 5 时的最优路径,最
后计算租车相关参数并记录在表中。分析表中数据,得到最优方案。在考虑成本
的前提下,得到的最快的配送时间是 42.8096 分钟。
关键词:Floyd 算法;最短距离矩阵;遗传算法;MATLAB;车辆路径问题
2
一、 问题重述
在互联网的快速发展之下,人们越来越追求快速便捷的生活方式,网上购物
的需求量也越来越大,随之而来的是物流产业的快速发展。物流配送与我们的生
活密切相关,而“最后一公里”一直是物流中的瓶颈。如何合理地安排配送任务
和设计配送路线是现阶段快递公司面临的一个实际难题。
现在社会的人不仅追求便捷的生活方式,同时也非常注重身体健康,所以很
多家庭都会订购鲜奶。现针对某市区的鲜奶配送需求,需要建立数学模型解决以
下问题。
问题一:已知某城区 92 个牛奶配送点的坐标、需求量及相互之间的连接道
路。假设牛奶站的位置坐标为原点,牛奶配送车的载货量为 400 瓶,速度是 20
公里每小时,每个需求点的下货时间为 1 分钟,配送车辆送完牛奶后需返回牛奶
站。要求设计一个运输成本最低的配送方案。
问题二:由于鲜奶的保鲜要求,需要尽快地完成配送。请在考虑成本的前提
下,设计一个最快的配送方案。
二、 问题分析
对于问题一,运输成本和行驶的公里数成正比,要使运输成本最低,也就是
牛奶配送车行驶的总距离最短。该问题与车辆路径问题基本一致,可以转化为车
辆路径问题。即在给定的网络中 G(N,A),A 为所有的边集合,N={1,2,…,n}
为节点集合,其中,1 为配送中心,其他节点为需要服务的顾客。车辆路径问题
为希望用 k 辆车配送 n-1 个客户,使得总路线最短。
本题中,n=93,1 为牛奶站,其他节点即为牛奶配送点。因为配送点总的需
求量为 1245 瓶,而牛奶配送车的载货量为 400 瓶。所以我们可以将 k 看成 4,
也就是说,一辆牛奶配送车从牛奶站出发四次回到牛奶站,形成四条回路。我们
的目标就是使得这四条回路的总距离最短。根据车辆路径问题的模型,我们就可
以建立相应的整数线性规划模型。由于本题的数据量过大,我们用 MATLAB 编写
3
遗传算法求解。
对于问题二,成本由租车成本和运输成本构成,考虑成本就是考虑租车数还
有牛奶配送车该如何行驶使得总路程最短。在这两个基础之上,选择一个最快的
配送方案。该题的模型与问题一类似,只是目标有所不同,本题的目标应该是完
成所有的配送的时间最短。在问题一的基础上,我们可以设置租车数为 1,2,…,
用 MATLAB 编写遗传算法求解出不同租车数所对应的不同行驶路线。将租车数,
租车成本,运输成本,总成本,配送总时间作为表头列表,记录相应数据,比较
权衡总成本和配送时间即可得出配送方案。
三、 模型假设
1. 从牛奶站出发的牛奶配送车必须返回配送中心;
2. 牛奶站和每个配送点之间都可直达;
3. 每辆牛奶配送车的最大载货量相同;
4. 每个配送点的配送任务都是一次完成的;
5. 运输成本为 1 元/公里;
6. 计算时,若两个点之间没有直接到达的路,则将两点之间的距离设为 999;
四、 符号说明
表 1 符号说明表
符号
说明
ij
d
点 i 到点 j 的距离
ijk
x
表示第 k 辆车是否从点 i 到 j,如果是
则为 1,否则为 0
i
g
点 i 的需求量
ik
y
表示第 k 辆车是否经过点 i,若是则为
1,否则为 0
k
Q
每辆车的最大载货量
五、 模型的建立与求解
5.1 问题一模型的建立与求解
剩余13页未读,继续阅读
温情。
- 粉丝: 7
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0