2007邮路规划与邮车调度最优化理论研究

问题的来源及意义：在信息技术飞速发展的今天，互联网已经成为一种重要的通信手段，但在我们利用Email等方式交流信息的同时，邮政作为传统的通信手段仍然与我们的日常生活和工作息息相关，发挥着不可替代的作用。我国的邮政生产过程由收寄、分拣封发、邮政运输和投递四大环节组成。邮政运输作为邮政生产过程的第三大环节，是邮政赖以传递邮件实现实物空间转移的物质基础，涉及航空、铁路、公路、水运等多种运输途径以及各种邮政设施。时限与成本是邮政运输问题的两个重要指标。时限是指邮电部规定的邮件、报刊处理、传递的最大时间限制，时限关系到邮政通信质量的好坏；成本影响着企业的经营。我国将邮件按时限要求大致划分为快件和普件，针对不同的邮件类别实施相应的运输计划。快件主要强调传递时限短，普件着重考虑邮件运输成本的降低。在进行邮路规划和安排邮车运行计划时，针对不同的邮件种类，在不影响时限标准实现的前提下，必须尽可能地降低成本。

邮政运输网络是邮政企业运营的重要保障，是决定邮政企业竞争能力的主要因素。自20世纪60年代以来，发达国家随着社会经济的发展，为了使邮政满足社会的需求，适应相关行业之间的竞争形势，对邮路的结构、通信组织方式及运行机制作了较大的调整，逐步扩大网络的覆盖区域，并按时限要求改进业务分类，开办快件等业务。随着UPS等国际性物流公司进驻国内，我国邮政正面临极大的挑战。我国邮政必须发挥自身优势，在缩短邮件运输时限和降低成本的同时，节约能耗和人力资源，提高邮政行业的服务质量和信誉，切实提高我国邮政的运行效益，保持邮政行业的竞争能力和取得良好的社会效益。

问题描述：

我国的邮政运输网络采用邮区中心局体制，即以邮区中心局作为基本封发单元和网路组织的基本节点，承担着进、出、转口邮件的处理、封发和运输任务，在此基础上组织分层次的邮政网。邮路是邮政运输网络的基本组成单元，它是指利用各种运输工具按固定班期、规定路线运输邮件，并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线。邮路的结构形式有三种：辐射形、环形和混合形。如图1所示，邮路A为一条环形邮路，邮路B为一条辐射形邮路。

图1 邮路示意图

1、辐射形邮路：是指从起点局出发，走直线或曲折线的邮路，其特点是不论用一种或几种运输工具联运，从起点到终点后，仍按照原路线返回出发地点。因此须在同一条路线上往返两个行程。这种邮路可以缩短运递时间，加快邮运速度。但它的联系点较少，需用的运输工具较多，所耗费用较大。

2、环形邮路：是指邮政运输工具走环形路线的邮路，即运输工具从起点出发单向行驶，绕行一周，经过中途各站，回到出发地点。它的特点是不走重复路线，联系点较多，运输工具的利用率高，运费也较省。但是邮件送到最后几个交接点的时间较长。

3、混合形邮路：是指包含辐射形和环形两种结构形式的邮路。

某地区的邮政局、所分布如图2所示，分为地市中心局（简称地市局）、县级中心局（简称县局）和支局三级机构，该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。为使邮政企业实现低成本运营和较高的服务质量，我们需要对该地区的邮政运输网络进行重构，确定合适的邮路规划方案并进行邮车的合理调度。

为了满足邮政的时限要求，必须尽可能地保证各县局、支局在营业时间内收寄的多数邮件能当天运送回地市局进行分拣封发等处理，以及每天到达地市局的多数邮件能当天运送到目的地县局、支局。该地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。该地区的邮政运输流程及时限规定如下：

Step1:区级第一班次邮车从地市局D出发将邮件运送到各县局X_i和沿途支局，并将各县局X_i和沿途支局收寄的邮件运送回地市局D；区级第一班次邮车出发时间必须在06:00之后，返回地市局D时间必须在11:00之前。

Step2:县局X_i将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理，按寄达支局装上相应的县级邮车；县局X_i对邮件的集中处理时间为1小时（包括邮件的卸装、分拣封发等处理时间）。

Step3:各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局X_i；

Step4: 区级第二班次邮车从地市局D出发将邮件运送到各县局X_i和沿途支局，并将各县局X_i收寄的邮件（包括当日各县级邮车运回县局X_i的邮件）和沿途支局收寄的邮件运送回地市局D；请注意区级第二班次邮车在县局X_i卸装完邮件后的出发时间必须在县局X_i的全部县级邮车返回县局并集中处理1小时以后，最终返回地市局D的时间必须在18:00之前。

图2 某地区邮政局、所分布图

（图中代号1至73依次代表支局Z₁, Z₂, ……, Z₇₃）

假设区级两个班次邮车的行驶路线相同，要求区级邮政运输网必须至少覆盖该地市附近的16个支局Z₅₈, Z₅₉, ……, Z₇₃和5个县局X₁，……，X₅。各县级邮政运输网必须覆盖本县内区级邮车不到达的支局。该地区邮局间公路网分布见表1，并且县级邮车平均时速为30km/h，区级邮车的平均时速为65km/h，邮车在各支局卸装邮件耗时5分钟，在各县局卸装邮件耗时10分钟。

问题1：

以县局X₁及其所辖的16个支局Z₁, Z₂, ……, Z₁₆为研究对象，假设区级第一班次邮车08:00到达县局X₁，区级第二班次邮车16:00从县局X₁再出发返回地市局D，若每辆县级邮车最多容纳65袋邮件，试问最少需要多少辆邮车才能满足该县的邮件运输需求？同时，为提高邮政运输效益，应如何规划邮路和如何安排邮车的运行？（邮件量见表2，空车率=(邮车最大承运的邮件量(袋)-邮车运载的邮件量(袋))/邮车最大承运的邮件量(袋)，单车由于空车率而减少的收入为（空车率*2元/公里））

问题2：

采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入，从而显著降低全区邮政运输网的总运行成本。考虑投入车况较好的邮车，通常每条邮路只需要一辆邮车即能满足运载能力要求，试问应如何构建该地区的邮政运输网络（县的划分不能变更），请你给出邮路规划和邮车调度方案。请注意邮车的调度必须满足上文中有关该地区的邮政运输流程及时限规定。（每条邮路的运行成本为3元/公里）

问题3：

考虑到部分县与县交界地带的支局，其邮件由邻县县局负责运送可能会降低全区的运行成本，带来可观的经济效益。若允许在一定程度上打破行政区域的限制，你能否给出更好的邮路规划和邮车调度方案？（在此同样不必考虑邮车的运载能力的限制，每条邮路的运行成本为3元/公里）

问题4：

县局选址的合理与否对构建经济、快速的邮政运输网络起到决定性的作用。假设图2中县局X₁，……，X₅均允许迁址到本县内任一支局处，同时原来的县局弱化为普通支局。设想你是该地区网运部门负责人，请你重新为各个县局选址，陈述你的迁址理由并以书面材料形式提交省局网运处。

邮路规划与邮车调度最优化理论研究

汤志高[1]，王继利[2]，曹颖瑛[2]
指导教师:曹华林[2]、梁希泉[1]
（[1]青岛科技大学数理学院，青岛266061）
([2]海军航空工程学院(青岛)航空机械系，青岛266041）

摘 要：本文对小规模MTSP问题,建立了可精确求解方案的0-1规划模型,并在满足邮政运输需求的前提下给出了最佳方案。问题一首先以县支局、县局为顶点构建无向赋权图,通过Floyd算法求解各局间的最短距离；然后以F_ijk为决策变量,以邮车工作时间、车辆运载能力为主要约束，建立以总空载损失费用最小为目标的0-1非线性规划模型Ⅰ,运用规划软件Lingo求解。问题二考虑到市邮路成本，我们采用分层规划策略，首先以市支局、县局为顶点构建无向赋权图,求解出最短路矩阵,建立以邮路运行成本最小为目标的0-1非线性规划模型IIA求解；然后,建立各县区的最短路矩阵，同样建立规划模型IIB求解各县运输方案。问题三由于县局地理位置不变,对区邮路无影响,故以全市各县支局为中心采用逐步最优方法对所有县区支局重新划分；然后采用模型IIB求解。第四问中考虑县局迁移,我们建立近似的启发式算法完成县局选址，并运用规划模型II求解的到新方案。最后，我们对两种区域划分调整方法还进行了定量的分析。

关键字：无向赋权图, 0-1非线性规划

Optimization theory research on Post Route and Mail Cart
TANG ZHi-gao[1], Wang Ji-li[2], Cao Ying-ying[2]
Advisor: CAO Hua-lin[2], Liang Xi-quan[1]
([1] Department of Mathematical, Qingdao University of Science & Technology, Qingdao 266061)
([2] Department of Mechanical, Naval Aeronautical Engineering Academy ,Qingdao 266041)

Abstract: As to the in miniature MTSP problem, 0-1 programming models are developed that can give precise solutions in this paper, and best solutions are obtained on the premise that the requirements of post transportation are satisfied. In the first problem, an undirected weighted diagram is established with the county branch post offices and county post offices as vertexes, and the shortest distance between each two post offices can be calculated by Floyd algorithm. Then make F_ijk be the decisive variable and let the working time and carrying capacity of vehicle be the main constraints to develop the 0-1 nonlinear programming model Ⅰwith the total fare lost of no-load as the objective. Programming software Lingois used to solve this model. In the second problem, layered programming strategy is adopted considering the city post transportation cost. At first, we establish an undirected weighted diagram with the branch city post offices and county post offices as vertexes, obtain the shortest path matrix, and develop the 0-1 nonlinear programming model IIA with minimum post transportation cost as the objective. Then we establish the shortest path matrix of county post offices and develop programming model IIB similarly to get transport solutions of each county. In the third problem, because the geographical location of each county post office doesn’t change and it has no influence to county post route, we redivide all the county branch post offices by optimal method step by step centering on each branch post office in the whole city; then develop model IIB to solve it. In the fourth problem, we develop approximate heuristic algorithm to select address for county post offices and develop programming models II to get new solutions. At the end, we make quantitative analysis about the two region division adjusting methods.

Keywords:Undirected eighted diagram, 0-1 nonlinear programming

下载题目： 【Download】

下载原稿(适合学习，但请务必自己先练习后看本文，否则将事倍功半)： 【Download】

下载出版论文*： 【Download】

附历届数学建模赛获奖名单： 【Download】

注：作者保留一切权利，转帖请注明出处，不得用于商业用途。*已出版论文禁止转载。