邮政运输论文数学建模.docx
- 文档编号:2726097
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:8
- 大小:63.72KB
邮政运输论文数学建模.docx
《邮政运输论文数学建模.docx》由会员分享,可在线阅读,更多相关《邮政运输论文数学建模.docx(8页珍藏版)》请在冰点文库上搜索。
邮政运输论文数学建模
ThismodelpaperwasrevisedbyLINDAonDecember15,2012.
邮政运输论文数学建模
邮政运输网络中的邮路规划和邮车调度问题
1问题重述
古往今来,邮政在人们的生活中都扮演着不可或缺的角色。
随着时代的发展,邮件投送的时限和成本成了邮政运输问题的关键因素。
根据题目给出的实际情况,本文提出了关于如何合理规划邮路的问题,具体内容如下:
对一片有特定道路相连且有行政划分的地区进行邮路规划,有以下的问题需要解决:
(1)以县局X1及其所辖的16个支局Z1,Z2,……,Z16(下文简称为1,2,……)为研究对象。
假设区级第一班次邮车08:
00到达县局X1,区级第二班次邮车16:
00从县局X1再出发返回地市局D,若每辆县级邮车最多容纳65袋邮件,在不超载的情况下,利用最少的车辆和最短的邮路,达到减少空车损失的目的。
(2)采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入,从而显着降低全区邮政运输网的总运行成本的邮路规划。
2模型的基本假设
.假设在同一天内需要收发的邮件数量为定值,不再变化。
.假设每条邮路只安排一辆车,同时一辆车只行驶给其安排的对应的某条邮路。
.假设所有的邮车在邮路上均按照平均时速匀速行驶,不受路况和天气及抛锚等其他因素的影响。
.假设县局对市局送来邮件的集中处理时间(1小时)既包括区级邮车的装卸时间10分钟,也包括县级邮车的装卸时间10分钟。
且在这1个小时的起始阶段进行装卸区级邮车的工作;而县级邮车的装卸工作最早在集中处理工作结束前10分钟进行,也可以在集中处理工作结束之后进行。
.假设县局对将要送到市局的邮件的集中处理时间(1小时)既包括县级邮车的装卸时间10分钟,也包括区级邮车的装卸时间10分钟。
且在这1个小时的起始阶段进行装卸县级邮车的工作;而区级邮车的装卸工作最早在集中处理工作结束前10分钟进行,也可以在集中处理工作结束之后进行。
.假设两班次的区级邮车行驶路线完全相同,若路线为环形则运行方向必须一致。
如:
D→61→58→53→X5→52→59→60→D与D→60→59→52→X5→53→58→61→D两种行车路线即为不同的两条路线。
.分组之后,各小组只能走自己区内的路,不能走其他小组的路。
3问题分析
问题一的分析
首先要求邮车数量做出规划
目标:
邮车数量最少
受到的约束有:
地区的邮政运输有一定的流程和时限规定
前题:
邮车不能超载
此问要求其各邮路经过最小路径同时有了时间限制,根据这些规定,要求县局邮车最早在09:
00出发,且必须在15:
00之前返回,这就要求县局每个邮路邮车从出发到返回所用的时间应该小于6个小时,且邮车行驶时间不仅要考虑行驶路程耗时,还要考虑邮路上在支局装卸邮件的耗时;有各支局需收发邮包数量的限制和县级邮车有运量的限制,要求其满足在不超载的情况下同时要损失最小来安排最少车辆数,由题中给出的的寄达和收寄的数据,得出最小邮车数量最少为三辆。
要求根据邮车数量规划出的全部邮路能覆盖该县局所辖的16个支局。
这是一个规划目标为旅行商数目的多旅行商的问题。
要求根据最小车辆数进一步对邮路进行规划,目标是使总支出(包括运行费用和空车损失费)最少。
针对此问题,我们运用了用prim算法对原路线图进行处理,求得其最小生成树,求其的程序及图见附件一。
并用直接观察法提出了分块准则,我们根据分块准则,建立了以邮路的总路程和三组路程,邮车总时间和时间均衡度为目标函数的多目标标模型,并重点考虑三组完成巡视时间和时间的均衡度为目标函数建立模型。
并通过分析比较均衡度,最终得出了最佳邮路路线。
3符号约定
:
市级邮局
:
县级邮局
:
表示县级邮局的集合
:
赋权邻接矩阵
:
每辆邮车行驶的路程
Fijk:
0—1变量,第i辆邮车第j次装卸邮件是否在第k个支局
Fijk=0第i辆车第j次在k支局卸装
Fijk=1第i辆车第j次在k支局没有装卸
S:
三辆邮车跑的总路程
Gkq:
第k支局寄出的邮件总量
Gkh:
寄达第k支局的邮件总量
Dkq:
途中节点k到节点q的最短距离(由得出的最小生成树求得)
4模型的建立与求解
模型一的建立
4.1.1最少车辆数的确定
根据题目的要求,寄达县局Z1的邮件量为176袋,而收寄的邮件量为170袋,同时每一辆县级邮车最多容纳65袋邮件,因此至少需要出动3车次才能够完成这样的投送量。
同时,派出的每辆车必须在六个小时内完成邮寄和收寄的任务。
所以派出至少三辆车。
4.1.2邮路最小生成树的确定
为了便于制定出最佳的邮路方案,首先我们运用prim算法求得邮路的最小生成树(如图一)
其程序见附件一
图一最小生成树
4.1.1确定目标函数
目标函数一:
邮路的总路程和三组行驶路程的均衡度为目标函数。
一方面,根据题目要求,邮车必须在六个小时内完成邮寄和收寄任务,而县级邮车的行驶速度保持一定,所以其必须在一定的路程内完成任务。
另一方面,虽然题目中没有提出行驶过程中由于耗油量造成的损失,但作为一个成功方案,我们必须将其考虑在内,即派出的邮车满足覆盖所有的支局外,各辆车跑的路程越少越好,即车在行驶过程中耗时越少越好。
总的最短路程
且各组行驶路程的均衡度
应该小于才算比较均衡即
目标函数二:
空载损失的费用最小,即空载率小时损失小
为了安全起见,邮车有限载的约束,空车率=邮车运载的邮件量(袋)/邮车最大承运的邮件量(袋)
约束条件:
1县级邮车运输网必须覆盖本县内所有的支局
由上面对问题分析县局至少要派出三辆邮车,三辆邮车跑各自的路线,三个路线所经过的支局点合起来必须覆盖本县内所有支局,且仅覆盖一次,所以有:
3m
ΣΣFijk=16(k=1,2,3,……16)
i=1j=1
2邮车运载能力的限制
根据问题一的要求,每辆县级邮车最多容纳量65袋邮件,这里实际限制了两个方面。
其一,必须保证邮车从县局出发时其装载的邮件不超过65袋,其二也必须保证邮车在卸下一部分邮件,同时也要收取一部分邮件,邮车在支局的卸装过程完成后,必须保证邮车还是没有超载,否则不在该支局进行卸装货物货物。
根据设定的已知变量,所以得出第i辆车从县局出发时,装载的所要运送的邮件的量为:
3m
ΣΣFijkGkh(k=1,2,3,……16)
i=1j=1
邮车在运输途中不断地卸装邮件,则可以得出,某辆邮车在某个支局进行装卸过程中,邮件的变化量为Gkq—Gkh,则第i辆车在出发时及运输途中邮件总量不超过有车运输能力(65袋)约束可表示为
3m3m
ΣΣFijkGkh+ΣΣFi(Gkq—Gkh)<=65
i=1j=1i=1j=1
3.邮车运输时限约束
据假设的条件,根区级第一班邮车08:
00到达县局X1,区级第二班班车16:
00从从县局返回市局,前后除去两个小时的邮件处理时间,该县邮车一天最多可跑六个小时。
由于三辆邮车所经过的支局正好覆盖并且只覆盖一次X1县的16个支局,并且假设邮车在每个支局进行卸装过程中耗时为五分钟,所以在整个运输过程中,而整个有车运输消耗时间有两部分组成,卸装货物过程造成的时间消耗和有车在运输途中的耗时,并有总的耗时不超过六小时
第i辆邮车在卸装邮件耗时大概为小时,
第i辆邮车在运输途中耗时:
4.1.2模型的求解
求解过程中,根据最小树分块原则,将图分成三个连通子图。
为了制定合理的路线,在分组是应遵循以下原则
准则一:
尽量使同一干枝及其分枝上的点分在同一组;
准则二:
应将相邻的干枝上的点分在同一组;
准则三:
尽量将长的干枝与短的干枝分在同一组.
准则四:
尽量使各组的停留时间相等.
附件一
clc,clear
a=zeros(53);
a(50,1)=;a(50,53)=;a(50,38)=;a(50,2)=;a(50,48)=;a(50,51)=;
a(1,36)=;a(1,37)=;a(1,38)=;
a(2,3)=;a(2,5)=;
a(3,38)=;a(3,39)=;a(4,39)=;a(4,8)=;
a(5,48)=;a(5,39)=;a(5,6)=;
a(6,48)=;a(6,7)=;a(6,47)=;
a(7,39)=;a(7,40)=;a(7,47)=;a(8,40)=;
a(9,40)=;a(9,41)=;a(10,41)=;
a(11,45)=;a(11,40)=;a(11,42)=;
a(12,42)=;a(12,41)=;a(12,43)=;
a(13,44)=;a(13,45)=;a(13,42)=;a(13,14)=;
a(14,15)=15;a(14,43)=;a(15,44)=;
a(16,17)=;a(16,44)=;a(17,22)=;a(17,46)=;
a(18,46)=;a(18,45)=;a(18,44)=;
a(19,20)=93;a(19,47)=;a(19,45)=;
a(20,21)=;a(20,25)=;a(20,47)=;
a(21,23)=;a(21,25)=;a(21,46)=;
a(22,23)=;a(22,46)=;a(23,24)=;a(23,49)=;
a(24,27)=;a(24,49)=;a(25,49)=;a(25,48)=;
a(26,27)=;a(26,51)=;a(26,49)=;a(27,28)=;
a(28,52)=;a(28,51)=;
a(29,52)=;a(29,53)=;a(29,51)=;
a(30,32)=;a(30,52)=;
a(31,32)=;a(31,33)=;a(31,53)=;
a(32,33)=19;a(32,35)=;a(33,36)=;
a(34,35)=;a(34,36)=;a(34,13)=;
a(37,38)=;a(36,53)=;a(37,38)=;a(44,45)=;a(48,49)=;
a=a+a';
a(find(a==0))=inf;
result=[];
p=1;
tb=2:
length(a);
whilelength(result)~=length(a)-1
temp=a(p,tb);temp=temp(:
);
d=min(temp);
[jb,kb]=find(a(p,tb)==d);
j=p(jb
(1));k=tb(kb
(1));
result=[result,[j;k;d]];
p=[p,k];
tb(find(tb==k))=[];
end
result
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 邮政 运输 论文 数学 建模