邮政运输网络中的邮路规划和邮车调度.doc

邮政运输网络中的邮路规划和邮车调度
一、问题重述
邮政运输问题是邮政生产过程四大环节的物质基础。时限与成本是邮政运输问题的两个重要指标,时限是指邮件、报刊处理、传递的最大时间限制,是邮车调度需要满足的基本要求,成本影响着企业的经营,包括道路成本以及空车成本,在邮路设计时,在满足时限的前提下,需要使成本最小。时限和成本对于邮路规划和邮车调度有着重要的影响。
中国的邮政运输网络采用以邮区中心局作为基本封发单元和网路组织的基本节点,负责处理、封发、运输邮件,在此基础上组织分层次的邮政网。邮路是邮政运输网络的基本组成单元,它是指利用各种运输工具按固定班期、规定路线运输邮件,并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线。
本文中要考虑的问题是:某地区的邮政分为地市局、县局和支局三级机构,该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成,县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。该地区地市局为D,周围共有5个县局X1,……,X5,每个县局包含若干个支局Z1,……, Z73。区级邮政运输网至少负责收发5个县局以及所在地市的16个支局Z58, Z59,……,Z73的邮件;各县局邮政运输网必须覆盖本县内区级邮车不能到达的支局。见图1,红线为区级邮政运输网,黑线为县级邮政运输网。区级邮政运输网贯穿各个县局,收寄邮件;县级邮政运输网贯穿本县支局。邮件的流动方向如图2所示,箭头表示邮件的流向,不表示实际路径。
图1 图2
该地区从地市局到县局每天两班车,从县局到支局每天仅有一班车。该地区的邮政运输流程如下:
Step1:区级第一班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局,并将各县局Xi和沿途支局收寄的邮件运送回地市局D;
Step2:区级邮车离开后,县局Xi将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理,按寄达支局装上相应的县级邮车;
Step3:各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局Xi;
Step4: 区级第二班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局,并将各县局Xi收寄的邮件和沿途支局收寄的邮件运送回地市局D。
这个问题里,对县局Xi,它的时限包括:区级第一班邮车开走一小时后才可发出县级邮车,沿途在各支局耗时5分钟,县级邮车须在区级第二班邮车开走一小时前返回。对于地市局D,它的时限包括:第一班邮车出发时间必须在6:00之后,沿途在各支局耗时5分钟,在各县局需要等到县级邮车返回一小时之后才能离开,返回地市局D必须在11:00之前。当邮车运载能力有限时,每辆邮车在各个支局、省局装载后都不应超过其运载能力。
二、模型假设
,行驶时间及费用也相同。
, Z59, ……,和5个县局X1,……,X5。
。
,区级邮车的平均速度为65km/h,邮车在各支局装卸邮件耗时5分钟,在各县局装卸邮件耗时10分钟,不考虑任何突发事件。
。
。
三、问题一模型与求解

对于这个问题我们只关心完成这个县邮运任务的最少的邮车数量以及在最少的邮车数量实现邮路总长度最短或者总耗时间最短。针对此问题我们假设第一辆地市区邮政运输车不到达X1内的任何支局。在这个假设下要求县邮车需要到达X1内所有的支局。在这个问题中我们理解的每天邮车只有一个班次指的是允许多辆车在同一时间内出发,但每天只允许出发一次。每辆邮车的最大装载量不超过63,最长行使时间不超过6小时。
设X1县内共有条邮路,分别为
,表示第条邮路上一共需要收发邮件邮支局的总数且(每个支局都要经过)
,,这里我们的邮路是指一辆邮车按顺序经过并收发邮件的支局序列,序列两端加上出发总局。, 分别表示第个邮局接收与发出去的邮件, 分别表示第条邮路中邮车全程包括收发邮件的总时间与邮车全程中最重时刻的装载量, 表示第个邮局到第个邮局的最短距离则,表示第条邮路在第个邮局时的装载量,表示出发时的装载量则:
,显然有
显然在保证邮路最少的情况下,邮路最短时我们有多目标规划模型
最少空车损失的模型为
这里由于问题的规模比较小,我们这里及以后各问题都利用枚举法求最小的。

(PSO)简介
PSO是从模拟鸟群的捕食行为中得到启示的算法。设想这样一个场景:一