邮政运输网络中的邮路规划和邮车调度文档格式.docx
- 文档编号:8514816
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:10
- 大小:151.39KB
邮政运输网络中的邮路规划和邮车调度文档格式.docx
《邮政运输网络中的邮路规划和邮车调度文档格式.docx》由会员分享,可在线阅读,更多相关《邮政运输网络中的邮路规划和邮车调度文档格式.docx(10页珍藏版)》请在冰点文库上搜索。
为了满足邮政的时限要求,必须尽可能地保证各县局、支局在营业时间内收寄的多数邮件能当天运送回地市局进行分拣封发等处理,以及每天到达地市局的多数邮件能当天运送到目的地县局、支局。
该地区从地市局到县局每天两班车,从县局到支局每天仅有一班车。
该地区的邮政运输流程及时限规定如下:
Step1:
区级第一班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局,并将各县局Xi和沿途支局收寄的邮件运送回地市局D;
区级第一班次邮车出发时间必须在06:
00之后,返回地市局D时间必须在11:
00之前。
Step2:
县局Xi将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理,按寄达支局装上相应的县级邮车;
县局Xi对邮件的集中处理时间为1小时(包括邮件的卸装、分拣封发等处理时间)。
Step3:
各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局Xi;
Step4:
区级第二班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局,并将各县局Xi收寄的邮件(包括当日各县级邮车运回县局Xi的邮件)和沿途支局收寄的邮件运送回地市局D;
请注意区级第二班次邮车在县局Xi卸装完邮件后的出发时间必须在县局Xi的全部县级邮车返回县局并集中处理1小时以后,最终返回地市局D的时间必须在18:
假设区级两个班次邮车的行驶路线相同,要求区级邮政运输网必须至少覆盖该地市附近的16个支局Z58,Z59,……,Z73和5个县局X1,……,X5。
各县级邮政运输网必须覆盖本县内区级邮车不到达的支局。
该地区邮局间公路网分布见表1,并且县级邮车平均时速为30km/h,区级邮车的平均时速为65km/h,邮车在各支局卸装邮件耗时5分钟,在各县局卸装邮件耗时10分钟。
问题1:
以县局X1及其所辖的16个支局Z1,Z2,……,Z16为研究对象,假设区级第一班次邮车08:
00到达县局X1,区级第二班次邮车16:
00从县局X1再出发返回地市局D,若每辆县级邮车最多容纳65袋邮件,试问最少需要多少辆邮车才能满足该县的邮件运输需求?
同时,为提高邮政运输效益,应如何规划邮路和如何安排邮车的运行?
(邮件量见表2,空车率=(邮车最大承运的邮件量(袋)-邮车运载的邮件量(袋))/邮车最大承运的邮件量(袋),单车由于空车率而减少的收入为(空车率*2元/公里))
问题2:
采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入,从而显著降低全区邮政运输网的总运行成本。
考虑投入车况较好的邮车,通常每条邮路只需要一辆邮车即能满足运载能力要求,试问应如何构建该地区的邮政运输网络(县的划分不能变更),请你给出邮路规划和邮车调度方案。
请注意邮车的调度必须满足上文中有关该地区的邮政运输流程及时限规定。
(每条邮路的运行成本为3元/公里)
问题分析
对于问题一,由于题中仅提供了两支局间直达距离,但这不一定是最短距离。
因此,首先需要利用Floyd算法把各支局间的最短路径矩阵D求出。
估计最少三辆车可以完成任务,因为县局开出去的车总共要带上176袋邮件,而每辆车最多承载65袋邮件,故最少需要【176/65】=3辆车。
而在求解如何规划邮路和如何安排邮车的运行的问题中,我们综合考虑了邮车运输时限约束,邮车运载能力限制,该区邮政运输流程的规定等因素,建立了一系列的约束条件,而以所需邮车数目最少和运输效益最大(由空载率损失的费用最小)分别为目标函数,由于双目标问题实际中不可解,而本问中研究点数较少,所以车辆数目不多,这里采取将目标一转化为约束的方法求解。
对于问题二,要规划该地区的邮政运输网络,采用尽可能少,尽可能短的邮路可以减少邮政部门车辆和人员等的投入。
我们将区级邮路和县级邮路分别进行了规划,在模型建立过程中,我们以总路程最小为目标函数,以邮车运输时限约束,区级邮政运输网必须覆盖该地市附近的16个支局和5个县局,而县级邮政运输网必须覆盖自己所在县的所有支局,建立非线性规划模型求解。
基本假设
1.假设一辆邮车仅负责一条邮路。
2.假设一个邮局的邮件仅由一辆邮车运送。
3.假设所有邮车均按平均时速匀速行使。
4.所有的邮路均可按环形,辐射性或者混合型来行使。
5.区级两个班次邮车的行驶路线相同,但方向可以不同。
6.每条邮路只需要一辆邮车即能满足运载能力要求,且车辆不存在超载现象。
7.若区车在由市支局驶向县局时途径县支局则在该县支局进行邮件交换。
符号说明
MAX:
县级邮车最多邮件的容纳量;
hk:
支局k收寄的邮件量;
gk:
寄达支局k的邮件量;
:
第i辆车在k、p之间运行的空车率;
n:
邮车数量;
单位距离的运行成本
单位距离单位空车率的损失;
第i辆车第j次停靠是否在k支局;
支局k、p之间的最短距离。
模型的建立与求解
模型Ⅰ
1、邮车运输时限约束
设第i辆车最多经过m个支局进行装卸,题中给出邮车在各支局装卸邮件需消耗5分钟,则则第i辆车在运输过程中耗费在各支局装卸邮件的时间为:
结合Fijk定义可知,当且仅当Fijk与Fi,j+1,q同时为1时表示第i辆车由支局k到支局q,其余情况为不经过
已知各县级车平均行使速度为30km/h,以dkq表示第k个支局到第j个支局的最短路距离,则第i辆车运输途中耗时为:
第i辆车邮运过程总耗时不超过运输时限(6小时)约束可表示为:
=
+
(1.1)
已求最少需要3辆邮车,第i辆车最多进行m次卸装,则该县邮政运输网必须覆盖本县内所有的支局且仅覆盖一次可表示为:
(k=1,2,3……,16)(1.2)
各邮车每次仅到一个支局装卸。
要一共需要历经17个支局,若将从X1出发时标记为1,则回到X1时应该为18,由于
表示第i辆车第j次装卸邮件是否在第k个支局,则只要经过第k个顶点则
=1。
则对于X1县邮局图中的18个顶点标记而言,第i辆车第j次仅到一个邮局可表示为:
(i=1,2,3,……n;
j=1,2,……,m)邮车始终点为X1
由题中关于该区邮政运输流程的规定,县局X1将邮件处理后通过县级邮车将邮件运往县内各支局,同时将各支局需要寄送的邮件运回X1进行同意处理后配送,则本县级邮车行驶的始终点始终为X1。
在模型准备中将X1看作图中编号为17的顶点,设第i辆车最多经过节点数为m,则各邮车由X1出发并最终回到X1可表示为:
(i=1,2,……n)(1.5)
2、邮车运载能力限制
根据问题1的要求,每辆县级邮车最多容纳65袋邮件,这里实际上限制了两个方面:
其一,每辆车在出发时装载所要运送的所有邮件量,而这些邮件需要在沿途支局全部卸下,所以各车卸下的邮件量总数不能超过65袋;
其二,邮车在经过支局时卸下一部分邮件,同时收取一部分邮件,则在每个分局装卸完成后,各车上所载邮件数不超过65袋。
以gk表示寄达第k个支局的邮件总量,第i量车最多经过节点数为m,
表示第i辆车第j次装卸邮件是否在第k个支局,则第i辆车在出发时装载的所要运送的所有邮件量为:
邮车在运输途中不断的装卸邮件,以hk表示第k个支局寄出的邮件量,则经过第k个支局时邮车上邮件数量变化量为gk-hk,第i辆车在出发时及运输途中邮件总量始终不超过邮件运载能力MAX,约束可标示为
(l=1,2,……,m)(1.3)
第一目标:
所需邮车数目最少
根据问题一要求,需求在满足邮运约束下,最少需要的邮车数量.所以应以邮车数量最少为第一目标,再在最少车辆数的基础上,以由空载率损失的费用最小为第二目标对邮路进行规划及邮车运输安排.
由于双目标问题实际中不可解,而本问中研究点数较少,所以车辆数目不会太多,这里采取将目标一转化为约束的方法求解.
具体方法为:
以目标二为目标进行建模编程,在模型中以n表示所需最少车辆数,再依次对n赋值1,2,3,⋯令模型可解的最小n值即为所求最小车辆数.
第二目标:
运输效益最大(由空载率损失的费用最小)
在满足邮车数量最少的前提下,应尽量提高运输效益.提高运输效益的方法为尽量降低由于空车率而减少的收入,根据题目信息,空车率的计算表达式为:
基于以上分析,以空车率而减少的收入为目标,以(1.1)~(1.5)为约束,建立县邮路规划模型如下:
MinZ=
模型Ⅱ-A(区级邮路)
区级邮车运输时限约束
记k=74,75,76,77,78,79,80分别为县局
和起始点市局D,终点市局D的编号,
为区车数量(
=1,2,3,4,5,根据结果取符合运输条件的最小值)。
当k=58,59,⋯,78时,在各区支局和县局装卸邮件,设第i辆区车最多在m个区支局和县局进行邮件装卸,在
个区支局进行装卸,在
个县局进行装卸。
已知邮车在各支局装卸邮件耗时5分钟,在各县局装卸邮件耗时10分钟,则第i辆区车在运输过程中耗费在各区支局和县局装卸邮件的时间为:
i=1,2,3…
已知各区级车平均行驶速度为65km/h,以
表示区级邮路图的k局到p局的最短路距离,且当且仅当
同时为1时表示第i辆区车经过弧(k,q),则第i辆区车运输途中耗时为:
区级邮路中可能包括途径的县支局,也要进行邮件装卸,
令
,则所需时间为:
区级邮车在运输过程中耗时由在各支局、县局装卸邮件耗时及运输途中耗时三部分构成,第i辆区车邮运过程总耗时不超过区级车运输时限(5小时)约束可表示为:
(2.1)
区级运输网覆盖面约束
根据该地区的邮政运输规定,区级邮政运输网必须覆盖该地市附近的16个支局和5个县局,即对于区级邮路网络中的任一节点而言,至少有一辆邮车经过。
设最少需要
量区邮车,则该区级邮政运输网必须覆盖该地市附近的16个支局和5个县局可表示为:
(k=58,59,…78)(2.2)
各区级邮车每次仅到一个邮局对于区级邮路的23个节点而言,第i辆车第j次仅到一个邮局可表示为:
(2.3)
由于区级邮路中的县支局有且仅有一辆区车在此局进行邮件装卸,则有:
(k=1,2,…57)(2.4)
区级邮车始、终点为市局D。
由于在区级邮路图中将D抽象为始点79及终点80,则各区级邮车由D出发并最终回到D可表示为:
(2.5)
模型Ⅱ-A的建立
基于以上分析,以所有区级邮车总运输成本最低为目标,(2.1~2.5)为约束,建立区级邮路规划模型:
模型Ⅱ-B(县级邮路)
以
局为例说明,其他县局情况同
。
邮车运输时限约束
对于任一县,第s辆县邮车最多在m个县支局进行装卸,运输过程中耗费在所需覆盖的区级邮车未到达的各支局装卸邮件的时间和行进时间需满足下式:
县级车运输时限T的确定
由于题中仅说明第一、二班区级车的路线相同,则两班车行驶的方向分相同、不相同两种情况。
下面分别分析这两种情况下的T。
情况1:
区级两班车行走路线方向一致
在极限情况下,为使县级车的运输总时间最大,令第一班车6:
00离开市局到达县局运输时间为t1,第二班车最晚18:
00到达市局,令第二班车由该县局到达市局的运输时间为t2。
由于第一、二班车沿同一路线行走,另外加上邮车在县局停留的10分钟,得到每一班车的总时间t,即:
由于县级车出发时在第一班车到达1小时以后,并且在第二班车离开县局时的1小时之前返回。
故县级车的最大运输时间范围满足:
情况2:
区级两班车行走路线方向相反
为使县级车的运输总时间更大,第一班车走最短路到达县局,第二班车沿反向走远路到达县局。
此时,第一班车由市局到达县局的时间和第二班车离开县局返回市局的时间都为t1。
故此时县级车的运输时间满足:
县级邮车始、终点为县局
由题中关于该区邮政运输流程的规定,该县级邮车从其所在县局
出发将邮件运送到其所负责的支局,并将各支局收寄的邮件运回
;
则该县级邮车行程的始终点皆为
该县的邮车始、终点为所在县的县局为
为:
模型ⅡB的建立
基于以上分析,以县级邮车运输成本最低为目标,建立各县级邮路规划模型:
Min3*
模型的评价
总体来说我们的模型是成功的,解决的题目中的两个问题。
因为模型建立过程中考虑因素很多,建立的假设很多,所以在模型的求解过程中比较困难。
在实际情况中,一个支局可能有多辆邮车服务,而且在解决第二个问题时没有考虑空车率,综合考虑这些因素可能会得到更优化的结果。
参考文献
【1】陈汝栋,于延荣.[M].第二版.北京:
国防工业出版社,2009,77-91.
【2】费浦生,羿徐明.[M].第一版.武汉:
武汉大学出版社,2006,215-225.
【3】陈光亭,裘哲勇.[M].第一版.北京:
高等教育出版社,2010,26-33.
【4】严喜祖,宋中民.[M].第一版.北京:
科学出版社,43-68.
【5】袁新生,邵大宏,郁时炼.北京:
科学出版社,6-12,70-73.
【6】卢晓珊,何伟,贺永进.邮政运输网络中的邮政规划和邮政调度研究[J],
数学的实践与认识,2009,39(17):
66-71.
【7】汤志高,王继利,曹颖瑛.邮政规划与邮政调度最优化理论研究[J],数学
的实践与认识,2008,38(13):
201-209.
附录
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 邮政 运输 网络 中的 邮路 规划 邮车 调度