邮政运输网络中的邮路规划和邮车调整.pdf

邮政运输网络中的邮路规划和邮车调整.pdf第卷第期数学的实践与认识 VoI38 .
Z0087MATHEMATICS AND
邮政运输网络中的邮路规划和邮车调整
高玉建, 苏昊, 黄飞
(IO0083)
摘要: 主要针对我国邮政运输业中邮路规划和邮车调整问题,研究了在规定时间、规定邮车运载能力限制
的条件下,单个县级邮区内的最小成本/最小空车率邮路规划以及多个邮区协同规划的策略,提出了一个用
TSP
行政规划的基础上。对整个市区的支局进行重新划分并求解得到了优于前面邮路规划的新方案.
关键词: TsP
1 问题介绍
. 邮政运输网络中的邮路规划和邮车调度问题,详见第烊ü芯可Ы>喝麯题.
2
1)6
县邮局邮车在收到市邮局送来的邮件后才前往各个支邮局;
邮车到达目标支局后会写下寄往该支局的所有邮件,并装上该支局寄送出去的所有
邮件; ,
4)1
5)1
6)510
各邮车匀速行驶,并且不会出现故障.
’
3
问题一
设Ⅳ表示较厍诘挠事肥珻表示县级邮车最多能容纳的邮件袋数,1硎綳。
MzX
少的邮车数Ⅳ应当满足:
(1)CMNC粢罜≤骸堍簟罜
从附表龅氖菘梢约扑愠鱿鼐中枰T怂偷街Ь值挠始课袋,由各个支局运
送到县局的邮件量为苛鞠丶队食底疃嗳菽始捎,
,所以完成该任务所需邮车数的下界为旅嫖颐鞘宰鸥鲆恢钟食凳
的邮路规划及邮车调度方案,使每辆车在不超过最大承运邮件量并且不违反邮政运
输流程及时间限制的条件下,完成该县每天的邮件运输任务,并且使由于空车率而减少的收
收稿日期:——
174 数学的实践与认识
入达到最少.
由于邮路规划受到邮车运载能力的限制,因此在设计邮路方案时不仅需要考虑一个邮
路上都存在哪些支局,,我们很难直观
地判断是否存在一条邮路,既满足邮车的运载能力的限制,又可以通过所有支局,针对这个
问题,我们提出了如下的邮路存在性定理,以方便邮路规划最优化模型的建立:
1设邮车运载上限为揪示諾。,海琙。,邮局枰J杖⌒偶﨏,袋,待
寄邮件为簟艭甤且∑蛞欢ù嬖谟事稾—#粃ぁひ粃。一
, 』
x
证明令—獵。,,留下全部收取的
封邮件并取走庥始瞪峡占浣ɑ嵩黾樱环粗鬗,,
将按照升序排列后得到的序列为尬,,海撸艚玐—籞‘.··一籜作为
一个邮车工作的路线,则易知在停靠邮局后车上的邮件数为巍R弧艭
J=1
’
^
∑尬.,且车上的载重将经过一个先单调不增。≤再单调不减。≥的过程,因此,
J=1
,≥:
五
且∑视事稾—R粃.·籞R粁在运输过程中邮车不超载并且可以完成
i=1

给定了如上邮路存在性定理,,在建立调度方案的
Floyd
局ㄏ鼐趾椭Ь之间的最短距离,并保存该最短距离矩阵以备后面的模型求解使用.
下面我们首先建立模型的一些约束条件:
,硎居芍Ь諾,带到县局的邮件数
CarryggiC
,
运载的邮件数,则每个啊,应当满足:
时】(311)
A2C
辆车都不超载,则三辆车从县局出发时,
軲(312)
根据如上的约束条件,我们可以建立如下的最优化模型:
第橛食翟诖覼“前往。时,其空车率为:
EmpRate(Z79,iZ+1)=l(313)
J
· P(T=6
小时甌表示在支局装卸邮件的时间,所以一个邮路的路径应不超过县级邮车的速度口
与路上行驶时间丁一罰的乘积,即
期高玉建,等:邮政运输网络中的邮路规划和邮车调整 175
d()'(+1)(Trl)(314)
EmpRate(zZ+-)
种方案因空车率而减少的收入为:
3 g
∑∑。!。(315)
g=1
(315)Cost
Cost=min{2EmpRate(Zgi柏
F=1
艭,芃蹸(316)
l!l 1
甃
1 p
d()(+1)(Trl
31616
163161
C
下剪枝条件:
某一组的邮车运载辆小于——袋时,则所有包含该组的方案不符
合要求,提前中止包含该组的方案搜索,改变该组最后一个支局,进行另一种方案的搜索.
某一组的邮车运载量大于时,同样提前中止,进行下一方案搜索.
每得到第一组的方案就计算该组邮路因空车率而减少的收入,若它比前面得到的
的最小值大就停止该方案的搜索,若小,则继续寻找第二组邮路的方