重庆邮电学院邮政自动化研究所 胡向东

　　 电子商务的快速发展对物流配送系统提出的更高要求，邮政部门正在努力提高服务质量、降低运营成本。邮政运输是实现实物邮件空间异地转移的基础，邮运路线安排是否合理直接影响到邮政通信的质量和效果。因此，如何开发路由规划软件，通过计算机自动处理来实现快速、智能、科学地安排邮运路线和邮运车次已成为我国邮政部门的当务之急。

一、影响邮政运输路由规划的主要 因素

　　 邮政运输是一个涉及多种因素的综合性复杂系统，下面分析影响邮政运输规划的主要因素。

1、邮路结构

　　 邮路结构是实现邮件异地转移的基础设施。它是在交通运输网络的基础上，按照一定的要求，挑选出来的适合于邮政运输的道路集合。在不同的地域，邮路等级有着很大的差别。相对来说，东南部交通运输网络发达，邮路等级较高，而西部地区则相对落后，邮路状况不甚理想。另外，由于自然灾害造成的邮路断路也时有发生。

　　邮政运输网路可分为全国干线网和省内网。干线网主要针对全国一、二级邮区中心局间的邮件运输，省内网则主要面对省内二、三级邮区中心局间的邮件运输。

2、运输工具

　　 运输工具是实现邮件异地转移的载体，是以一定的邮路结构为基础的。邮政运输主要依赖于委办，特别是干线运输，需要依托航空和铁路部门提供的运能支持，车辆开行时刻、停靠站点和容间大小都不具备自主权力。虽然经过一定时间的积累，自办邮路有了很大的发展，但主要还是通过汽车邮路来完成部分省内邮件的运输。另外，邮件运输还涉及到少量的轮船运输。

3、邮件种类和流量流向

　　 就运输环节而言，我国将邮件按时限要求大致划分为快件和普件，针对不同的邮件类别实施相应的运输计划。快件主要强调传递时限短，普件着重考虑邮件运输成本的降低。对于不同的邮件种类，其运输评价指标不一样。另外，邮件流量流向区域性差别大，邮件总量与流量流向随机变化，季节性强，变化幅度大。

4、时限

　　 时限是衡量邮政通信质量的重要指标。由于实物邮件的异地转移是邮政通信的基本内容，邮政运输中的每一个环节都有严格的处理时限标准，而且端到端有一个总的时限标准。通常，邮政运输在整个邮政通信作业过程中所占的时限比例较大，因此花在邮政运输中的时间是邮政运输路由规划时需要着重考虑的一个评价因素。影响时限标准实观的主要因素是运输时间和转运时间。

5、成本

　　成本是影响企业经营的一个重要指标，邮政运输部门也不例外。在进行邮政运输路由规划时，针对不同的邮件种类，在不影响时限标准实现的前提下，必须尽可能地降低运输成本。邮政运输成本由在途运输和转运成本组成。

二、分层模型的建立

　　从前面的分析可知，影响邮政运输的因素较多，而且这些因素所涉及到的数据量大、数据种类多、数据之间的关系复杂；这些因素还具有层次性特征：邮件以车次为载体，车次基于邮路运行。为了便于实现这个系统，我们首次提出分层模型，把整个邮政运输路由规划过程划分为邮政运输路由建立、运输车次安排和邮件发运计划自动生成三个层次，层次具有严格的单向依赖性。每一个层次采用结构化的设计方法，先实现单一中心局对间的单元函数，再由单元函数的循环算法完成全网的优化。通过“分而治之”，既保证了整个系统的结构清晰，又便于系统的分层实现，特别有利于系统的维护和更新升级（系统优化模型如图1所示）。

图1 系统优化模型

l、路由优化

　　 路由优化是整个优化过程的第一步，其目的就是要从现有的交通运输网络中寻找到各邮区中心局对间的最短路径。交通运输网络是一个网状结构，如果把分布于这个网状结构中的各邮区中心局简化为一个个数学上的点，把各邮区中心局间的运输线路简化为一条条带“权”的线，路由优化问题就转化为在一个以许多“点”和“线”组成的“图”中寻找各点与点间的最短路径。这可以利用“图论”中的Dijkstra算法、推广的Floyd算法、二重扫除算法等来实现。为提高系统的可靠性，运用 K短路算法得到若干备用邮路。

　　 通过路由优化，可实现具有NP特性的优化问题向有限个方案的多目标运输问题的转化，即将具有无限个方案的邮政运输多目标决策问题转化为基于K短路由的有限个方案多目标决策问题，从而大大缩小搜索空间，缩短搜索时间。

2、车次优化

　　 基于得到的K短路由，根据现有的车次运行状态，采用精确算法中的分枝定界法来确定它们的链接关系（即执行模式），并由相应的评价指标（评价模型）来确定其优劣次序。

（l）规范化处理

　　 由于邮政运输的决策属性：成本和时限的量纲和数量级各不相同，具有不可公度性和矛盾性。为消除这种差异对决策结果的影响，在进行车次优化时，首先应对决策矩阵进行规范化处理。

　　 邮政运输的决策属性类型属于成本型，这条我们采用目前在多属性决策问题求解中用得最多的极变差法决策矩阵规范方法，规范化矩阵的分量越大，表明对应的评价对象的评价因素占的优势越大；反之，则越小。

（2）权系数的确定

　　 在多属性决策问题的求解中，属性的权系数被用来反映属性的相对重要性，对决策结果具有决定性影响。属性越重要，其权系数越大；反之，就越小。根据邮政运输需求的特点，采用主观赋权法中的专家调查法。

（3）车次链的确定

　　 车次优化中用到的车次链数据结构如下：

typedef struCt｛
CTimeSpantTimeSum；
nitiNumtrans；
//Former：
nitilD-Former；
nitiFrom-Former；
nitiTo-Formef；
CString sTool-Former；
CString sNum-Former；
NitiWhatday-Former；
//Current：
nitilD-Cur；
nit iFrom-Cur；
intiTo-Cur；
bool blsStepoverFrom-Cur；
bool blsStepoverTo-Cur；
CString sTool-Cur；
CString sNum-Cur；
CTime tDays-Cur；
CTime tDayslnner-Cur；
NitiWhatday-Cur；
NitiCost-Cur；
NitiCostlnne-Cur；
｝SCheduLink；

　　 车次链的一个实例表示网络网中相邻节点的一个车次。其中tTimeSum是车次链上从起点到当前点的累计时限。iNumtrans 是车次链上从起点到当前点的转车次数。Former部分用于确定车次链上前一段车次的序列号、起点、止点、车次和星期。Current部分用于确定车次链上当前段车次的序列号、起点、止点、是否经停、车次、运行时间、到达时间、内部处理时间、星期、运输成本和内部处理成本。

　　 在确定邮政运输的车次链时，由于要受到车次运行时序关系和邮政运输时限标准的限制，因此在树状搜索中，它与传统方法不同的是不能保证每次搜索结果都是可用的，为了保证搜索结果的可用性，除可进行通常的正向搜索外，还需要进行反向回溯操作。采用宽度优先搜索与深度优先回溯相结合的办法能够很好地实现上述要求。

（4）车次方案的综合排序

　　 在前两步的基础上，便可对车次优化的多属性决策问题的决策方案进行综合排序。根据每个评价对象的优属度大小，进行优次排序，达到评判的目的，从而实现对车次的优化。

3、发运计划的自动生成

　　 这是邮运规划中的最后一步。在实际优化过程中，在执行模式即各邮区中心局对间路由和可行车次链优先次序确定的情况下，采用基于优先规则的启发式算法把可行调度工作（邮件流量流向）按照一定的优先规则排序，再根据排定的顺序利用串行调度方案，拉车载容量（运能）进行邮件的匹配，生成一个完全的调度计划。用户可选择快件与普件分离、重件与轻件分离等运输管理方式。

　　 这步主要考虑三个约束条件：（l）两局间的所有车次链的可用容量必须大于或等于其间的邮件流量。（否则，超出部分的邮件将被滞留）。（2）两局间邮件量越大，距离越远，执行发运计划的优先权越高。（3）位于一个车次链上的所有局对，在满足时限的前提下，按优先权大小共享该车次链的容间。

　　 基于所建立的分层模型，运用VC＋＋6.0作为开发工具，中心和本地数据库管理系统分别采用Oracle和Access，成功地实现了“邮政通信物流网最优计划调度系统”。

　　邮政运输路由规划是个涉及多种影响因素的综合性系统。根据这些影响因素的层次性依赖关系引入的分层模型为邮政运输路由规划提供了有效的支持，满足快速建立运输路由和自动生成发运计划的要求；也保证了用户能够针对不同条件灵活地实施不同层次的优化操作，从而大大节省不必要的机时；特别有利于系统的实现和维护。