没有合适的资源?快使用搜索试试~ 我知道了~
图论Dijkstra模型-邮政运输网络中的邮路规划和邮车调度.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 22 浏览量
2022-05-01
20:07:10
上传
评论
收藏 551KB PDF 举报
温馨提示
试读
35页
图论Dijkstra模型-邮政运输网络中的邮路规划和邮车调度.pdf
资源推荐
资源详情
资源评论
全
全
国
国
第
第
四
四
届
届
研
研
究
究
生
生
数
数
学
学
建
建
模
模
竞
竞
赛
赛
题 目 邮政运输网络中的邮路规划和邮车调度
摘 要:
本题是一道 VRP 问题,它涉及到最短路线、最小费用等条件下的优化问题.
我们首先利用 Dijkstra 算法求出任意点的最短距离,然后针对每一个小问题,我们
提出了具体的求解策略:
问题一中,我们论证出最少需要 3 辆邮车才能满足要求.然后对 X1 区域根据
装载量、时间要求遍历出所有的可行路线,最后选出因空车率而减小的收入最小
的邮路,具体的路线安排见文中表 1.4. 其减少的收入为 49.35 元.
问题二中,我们对地市局发车数进行讨论,将整个区域进行划分,在每个小区域
应用分枝定界法求出运行成本的路线.从而得到近似最优解,再通过对区域的微调
讨论出使邮车数目更小的、更节省运行成本的邮路规划和调度方案.在不同的方
案下得到的最优值如下:
方案 邮车数 运行成本(元)
区级邮车上、下午停留的支局相同
12 10197
区级邮车上、下午停留的支局不同
11 9771
问题三中,在允许区级邮车上、下午停留的支局不同的情况下, 我们将
Z56,Z57 由县局 X1 负责运送,Z27 由县局 X2 负责运送,这样只需要 10 辆邮车,并
使每天节省 354 元,具体的行车路线见文中表 3.2 .
问题四是一个选址问题.我们借助于中心点算法,考虑各支局在本县区域内
的位置,并结合与地市局的距离,提出了相应的选址方案:将 X1 县局移到 Z4,X2
县局移到 Z21,X5 县局移到 Z52,每天将节省 789 元的运行成本,具体调度方案见文
中表 4.4.
参赛队号 1029301 参赛学校 南京邮电大学
参赛队员姓名 于文涛 马钰昕 李晗
参赛密码
(由组委会填写)
题号 D
1
一、问题重述:
某地区的邮政局分为地市中心局(简称地市局)、县级中心局(简称县局)
和支局三级机构,该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构
成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部
邮路构成,县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全
部邮路构成。为使邮政企业实现低成本运营和较高的服务质量,我们需要对该地
区的邮政运输网络进行重构,确定合适的邮路规划方案并进行邮车的合理调度。
为了满足邮政的时限要求,必须尽可能地保证各县局、支局在营业时间内收
寄的多数邮件能当天运送回地市局进行分拣封发等处理,以及每天到达地市局的
多数邮件能当天运送到目的地县局、支局。该地区从地市局到县局每天两班车,
从县局到支局每天仅有一班车。该地区的邮政运输流程及时限规定如下:
Step1:区级第一班次邮车从地市局D出发将邮件运送到各县局X
i
和沿途支
局,并将各县局X
i
和沿途支局收寄的邮件运送回地市局D;区级第一班次邮车出
发时间必须在06:00之后,返回地市局D时间必须在11:00之前。
Step2:县局X
i
将当天区级第一班次邮车及前一天的区级第二班次邮车所送达
的本县邮件进行集中处理,按寄达支局装上相应的县级邮车;县局X
i
对邮件的集
中处理时间为1小时(包括邮件的卸装、分拣封发等处理时间)。
Step3:各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运
送回县局X
i
;
Step4: 区级第二班次邮车从地市局D出发将邮件运送到各县局X
i
和沿途支
局,并将各县局X
i
收寄的邮件(包括当日各县级邮车运回县局X
i
的邮件)和沿途
支局收寄的邮件运送回地市局D;请注意区级第二班次邮车在县局X
i
卸装完邮件
后的出发时间必须在县局X
i
的全部县级邮车返回县局并集中处理1小时以后,最
终返回地市局D的时间必须在18:00之前。
假设区级两个班次邮车的行驶路线相同,要求区级邮政运输网必须至少覆盖
该地市附近的16个支局Z
58
, Z
59
, ……, Z
73
和5个县局X
1
,……,X
5
。各县级邮政
运输网必须覆盖本县内区级邮车不到达的支局。该地区邮局间公路网分布见表1,
并且县级邮车平均时速为30km/h,区级邮车的平均时速为65km/h,邮车在各支局
卸装邮件耗时5分钟,在各县局卸装邮件耗时10分钟。
问题1:
以县局X
1
及其所辖的16个支局Z
1
, Z
2
, ……, Z
16
为研究对象,假设区级第一
班次邮车08:00到达县局X
1
,区级第二班次邮车16:00从县局X
1
再出发返回地市局
D,若每辆县级邮车最多容纳65袋邮件,试问最少需要多少辆邮车才能满足该县
的邮件运输需求?同时,为提高邮政运输效益,应如何规划邮路和如何安排邮车
的运行?(邮件量见表2,空车率=(邮车最大承运的邮件量(袋)-邮车运载的邮件
量(袋))/邮车最大承运的邮件量(袋),单车由于空车率而减少的收入为(空车率
*2元/公里)).
问题2:
采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入,从
而显著降低全区邮政运输网的总运行成本。考虑投入车况较好的邮车,通常每条
邮路只需要一辆邮车即能满足运载能力要求,试问应如何构建该地区的邮政运输
网络(县的划分不能变更),请你给出邮路规划和邮车调度方案。请注意邮车的
2
调度必须满足上文中有关该地区的邮政运输流程及时限规定。(每条邮路的运行
成本为3元/公里)
问题3:
考虑到部分县与县交界地带的支局,其邮件由邻县县局负责运送可能会降低
全区的运行成本,带来可观的经济效益。若允许在一定程度上打破行政区域的限
制,你能否给出更好的邮路规划和邮车调度方案?(在此同样不必考虑邮车的运
载能力的限制,每条邮路的运行成本为3元/公里)
问题4:
县局选址的合理与否对构建经济、快速的邮政运输网络起到决定性的作用。假设
图 2 中县局 X
1
,……,X
5
均允许迁址到本县内任一支局处,同时原来的县局弱
化为普通支局。设想你是该地区网运部门负责人,请你重新为各个县局选址,陈
述你的迁址理由并以书面材料形式提交省局网运处。
更多数学建模资料请关注微店店铺“数学建模学习交流”
https://k.weidian.com/RHO6PSpA
3
二、问题假设与符号说明
2.1、问题假设:
1、邮车在路上的速度总是一定,不会出现抛锚或阻塞而耽误时间;
2、分组之后,各小组只能走自己组内的路,不能走其它组的路;
3、各个小组的邮车行驶速度一样;
4、卸车寄达该局的所有邮件;上车该局收寄的所有邮件;
5、县局需对邮件处理 1 小时,且不包括区局邮车装卸邮件的时间;
2.2 符号说明:
符号 符号说明
D
区局
i
X
第
i
个县局
i
Z
第
i
个支局
,i j
D
从支局点 Zi 到支局点 Zj 路径的距离
( )u i
从支局点 Z1 到支局点 Zi 已选取的最小距离
( )r i
从支局点 Z1 到支局点 Zi 已选取的最小路径
i
I
第
i
个支局需寄达的邮件数量
i
O
第
i
个支局收寄的邮件数量
Q
寄达邮件总量
n
邮车数量
县局 X1 所辖支局的分为三个区域,划分的集合
i
W
每辆邮车离开第
i
个支局时所装邮件数量
i
T
区级邮车到县局
Xi
花费的时间
K
邮车的空车率
S
总的空车损失费用
i
S
第
i
辆车的空车损失费用
4
i
A
第
i
辆车所经过的所有局的全排列
k
p
一辆邮车所经过局的全排列的第
k
个全排列
,i j
W
表示第
i
种分区方式下从第
j
个支局出发邮车上所装
邮件数量
,i j
K
邮车从第
i
个局到第
j
个局邮车的空车率
t
邮车出行一共花费的时间
l
t
邮车第
l
种运行方式一共花费的时间
i
m
第
i
辆邮车一共经过的支局数目
v
县级邮车的行驶速度,为已知常量
剩余34页未读,继续阅读
资源评论
普通网友
- 粉丝: 12w+
- 资源: 9335
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功