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

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

【摘要】：本题主要以现实中邮政网络规划问题为研究对象，在研究过程中针对不同情况下的最佳邮路设计和运输效益问题，分别建立了线性规划模型，并利用matlab软件搜索求解。

针对问题一，首先利用matlab元胞数组功能录入x1县的邮政信息，建立包含各支局收、寄邮件数量和各线路行驶时间的数据库，然后在同时满足各线路邮件运输量不超过邮车最大承载量和各线路邮车运输时间不超过规定时限的条件下，调用数据库中相关信息并利用matlab软件搜索所有符合条件的邮路，其次以使用最少邮路覆盖全县邮政网络为目标，建立关于邮路设计的线性规划模型，并利用matlab软件求解得，覆盖全县最少需规划3条邮路即最少使用3辆邮车就可满足全县邮件运输需求，最后在满足上述求解结果的条件下结合空车率计算方法，以减少收入最低为目标建立关于邮车调度的线性规划模型，利用matlab软件搜索求解得3辆邮车的具体路线安排分别为：x1-12-13-1-3-2-5，x1-4-6-9-11-10,x1-14-15-16-8-7，此时因空车率而降低的总收入为：62.4615元。

针对问题二，通过对题目的分析，首先利用贪婪算法寻找市局内可到达各县局的最近支局，并将其作为通往各县局邮路在市区内的终点和在各县局内的起点，其次在确定市区和各县局内邮路的起点和终点后，在同时满足从市局出发的各邮路可完全覆盖市局邮政网络和各邮路运行时间不超过规定时限的条件下，以邮路总运行费用最少为目标，建立线性规划模型，并利用贪婪算法逐步寻找最优解，最后解得市局需5辆邮车，各县局分别需要：2，2，0，0，2辆邮车，总路程最小为2089.1公里，此时的总费用最小为6267.4元，具体安排见模型求解。

关键词： 线性规化 搜索求解 贪婪算法

1、问题重述

1.1 问题的来源及意义：

在信息技术飞速发展的今天，互联网已经成为一种重要的通信手段，但在我们利用Email等方式交流信息的同时，邮政作为传统的通信手段仍然与我们的日常生活和工作息息相关，发挥着不可替代的作用。时限与成本是邮政运输问题的两个重要指标。时限是指邮电部规定的邮件、报刊处理、传递的最大时间限制，时限关系到邮政通信质量的好坏；成本影响着企业的经营。

邮政运输网络是邮政企业运营的重要保障，是决定邮政企业竞争能力的主要因素。

1.2 提出问题

[1]以县局X1及其所辖的16个支局Z1, Z2, ??, Z16为研究对象，假设区级第一班次邮车08:00到达县局X1，区级第二班次邮车16:00从县局X1再出发返回地市局D，若每辆县级邮车最多容纳65袋邮件，试问最少需要多少辆邮车才能满足该县的邮件运输需求？同时，为提高邮政运输效益，应如何规划邮路和如何安排邮车的运行？

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

2、问题分析

本题主要以现实生活中的邮路规划和邮车调度问题为研究对象，在研究过程中需考虑各支局之间是否可到达，邮车的调度是否满足题目要求和安排的邮路是否能覆盖邮政网络等因素。解决邮路规划和调度问题时需要明确以下几个方面： ① 邮路的形式与种类

在邮政运输网络中，将各地市局、县局、支局都近似看做结点，任意两点的连线都可看做是一条路径，邮路类型主要有环形、辐射型和混合型三种，由于实际邮政运输网络中存在两个邮局间无可到达路线的情况且并非所有支局都可直达县局，因此，根据邮局间直达的情况即可推算出各条邮路的线路类型。 ② 线路搜索方法

本文的关键是搜索方法的科学性，应首先寻找出所有的线路，其次，搜索同时满足每辆车的时限要求和邮车最大运载量的线路，即记录所有同时满足时限要求和最大运输量的线路，最后，根据线路是否覆盖所有支局且无重复数据得到最终的可到达线路。

③ 不同要求下对时限的理解与计算

时限指的是邮电部规定的额邮件、报刊处理和传递的最大时间限制。在调度邮车的过程中主要考虑邮车在行驶过程中的耗时、在支局或县局的卸装时间、处理邮件的时间。对不同区域或规定时限其计算方法是不同的。

3、模型假设

[1] 假设邮车在行驶过程中不会存在意外的等待时间；

[2] 假设区级第一班次的邮车到达区级后的处理时间不予考虑；

[3] 假设车况较好的邮车没有最大运载量的约束； [4] 假设不同邮车在不同时间到达支局或县局的卸装、分拣封发和等待时间等都是相同的；

[5] 假设不同县局邮车经过的支局各不相同，即一个支局只能由一辆邮车到达。

4、符号系统及名词解释

4.1符号说明 符号及说明 备注 pki 表示第k辆车寄达支局Zi的邮件量 qki 表示第k辆车在支局Zi收寄的邮件量 表示邮车数目的编号 T1k 第k辆车的行驶时间 k Sk 行驶过程中的行程 hnk 表示第k辆车是否经过第n个点 Mk 表示第k辆车运输的邮件量 k为邮车的编号，其值取1，2?n;i为支局抽象为点的编号，其值取1，2?73

4.2名词解释

[1] 邮路:指利用各种运输工具按固定班期规定路线运输邮件，并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线，它是邮政运输网络的基本组成单元。

[2] 时限：指邮电部规定的邮件、报刊处理传递的最大时间限制。 [3] 区级邮政运输网：从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成。

[4] 空车率:其计算方法为：(邮车最大承运的邮件量-邮车运载的邮件量)/邮车最大承运的邮件量。

5、模型的建立与求解

5.1 县局到支局的邮路规划和邮车调度 5.1.1 模型准备

1、行驶线路的一般表达形式和邮政运输流程

如图所示，A表示环形邮路，B表示辐射型邮路，在邮政运输网络中，将各地市局、县局、支局都近似看做结点，任意两点的连线都可看做是一条路径，由于实际邮政运输网络中存在两个邮局间无可到达路线的情况且并非所有支局都可直达县局，因此，根据邮局间直达的情况即可推算出各条邮路的线路类型，将各种邮路的线路类型及运输流程表达如下： [1] 构造线路的一般形式

首先由各个邮局所在的位置抽象出点的集合S?{s1,s2,...}，同时将邮车行走的线路表达为线路的集合L?{l1,l2,...}，当且仅当邮局点s在行驶线路l上时，s与

l间有一条边。邮局结点p和q组合成的线路必须满足一定的次序，即注考虑到p?q与q?p是不同的线路。 ① 环形邮路的路线形式：

设X1~Xj为第j个县局的编号，Z1~Zi为第i个支局的编号，的以一条可用

线路为例进行说明,具体线路如下：

相同线端X1?Z10?Z11?Z16?Z9?Z15?X1始末点由图中可看出此时邮路的起始点和终点都是县局，且不走重复路线，这种情况下联系点较多，能大大增加运输工具的利用率，此种线路的缺点是送到最后几个结点的时间较长，时限的约束将使其到达的支局个数较少。 ② 辐射邮路的路线形式

由图示可初步判断出此种邮路的特点是从起点到终点后，仍按照原路线返回出发地点。因此须在同一条路线上往返两个行程。

X1?Z14?Z14?X1

这种结构的邮路可以缩短运递时间，加快邮运速度。但它的联系点较少，需用的运输工具较多，所耗费用较大。 ③ 混合邮路的路线形式

邮车在运输邮件的过程中，将会存在邮车经支局回到县局后继续开往支局运输邮件的情况即混合邮路。这种情况是由于邮车由县局出发第一次运往各个支局并返回时仍然有部分空余时间，邮车再次由县局出发到附近支局运送邮件。这一形式是辐射邮路和环形邮路的综合。

县局县局县局X1?Z10?Z11?Z16?Z9?Z8?X1?Z14?X1

[2] 地区的邮政运输流程

该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。运输流程如下：

地区的邮政运输流程B1市局邮车B2地市局寄达并县局收寄于沿途支局寄达并收寄于县局沿途支局终到站地市局县局邮车C1县局起始站 补充说明： 图中B1、B2表示市局车辆运输的第一班次和第二班次，C1表示县局邮车的第一班次，且县局邮车有且仅有一个班次。 具体流程为区级第一班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局，并将各县局Xi和沿途支局收寄的邮件运送回地 市局D，各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局Xi。

2、确定邮车调度对时限要求

在邮政运输中，时限和成本是邮政运输问题的两个重要指标，其中，时限指的是邮电部规定的额邮件、报刊处理和传递的最大时间限制。在调度邮车的过程中重点考虑以下几个方面的时间限制。

[1] 县级邮车在行驶过程中花费的时间（简称行程时间）：

县级邮车的行程仅局限于邮车由县局出发并最终返回县局的县级邮车所行驶的全部路程，行程时间可表示为：

行程时间?行驶总公里数

时速邮车行驶单条邮路的路程可简单表示为行程，将行驶总公里数看做各行程的和，设i表示邮路经过的支局编号(将第一个可到达的支局编号定位初值1，2，3?n依次表示路线中经由的支局),设j表示经由的县局的次数，k表示邮车数目的编号，第k辆车的行驶时间为T1k,行驶过程中的行程表示为Sk，则此时单段距离可表示为dc，则行驶总公里数可表示为：

sk?n?dc?1c(n?N)

县级邮车平均时速为30km/h，根据总公里数得到总的行程时间为：

Tk1??(dc?1nc30) (1)

[2] 邮车在支局的卸装耗时：

邮车由县局向支局运输邮件的过程中，每经过一个支局都将卸载一部分寄往此支局的邮件，同时，装载一部分邮件运往市区，根据时限要求，在各支局卸装邮件耗时5分钟。

卸装时间?经过的支局个数?每次卸装的时间

设第k辆车的卸装时间为T2k，邮车从县局出发运往各个支局中经过的支局个数为nk，每次卸装的时间为5分钟，则：

T2k?1?nk (2) 12[3] 邮车在各县局的卸装耗时

邮车的行驶线路为先由区级邮车将邮件运往县级，而后到达县级的邮件将由县级邮车运往各个支局，在此过程中，由于车辆数的不确定性和邮路类型的差异，一般来说，每辆车在满足运载邮件的最大量或时限范围内时将返回县级，每辆县

本文来源：https://www.bwwdw.com/article/2r02.html