图论loyd算法算法-邮政运输网络中的邮路规划和邮车调度.pdf

1

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

摘要

本文针对问题一带有时间窗的邮政运输问题（VRPTW），建立起了双目标的

模型，首先要求车辆最少，其次要求因为空车率而造成的收益损失要尽可能小。

对于问题一的求解文中使用了两种方法，首先是基于 2-opt 方法进行线路内优化

的节约算法，通过忽略时间窗约束求出了一组解，经时间约束检验为可行解。然

对于问题二这种 6 个 VRPTW 的耦合计算问题，考虑到这是 NP-hard 问题，

所以重点放在寻找较优解上。首先考虑对区级 VRPTW 通过模拟退火算法进行优

化求解，推求出各县级的时间约束，再对县级进行优化求解，求得一个可行解，

因为这是分两层利用模拟退火算法进行寻优的，有理由认为这是一个较优的解：

总计使用 15 辆车，其中地市级邮车 4 辆，除了县 X

5

是三辆外其他四个县均为 2

辆，一天运行总里程为 3164km，运行总成本为 9411 元，并给出了具体邮路。

对于问题三，本文着重考察县界附近的支局，运用聚类的思想将各支局归入

距离最短的市局或县局内，至此，问题三就被转化成了另一个问题二，通过相同

的计算我们得到了比问题二好的结果，可见打破县界是有效的。

关键词： VRPTW 模拟退火算法 破界 选址

2

合形。

某地区的邮政局、所分布如图 1-1 所示，分为地市中心局（简称地市局）、

县级中心局（简称县局）和支局三级机构，该地区的邮政运输网络由区级邮政运

输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局

的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县

局的县级邮车所行驶的全部邮路构成。为使邮政企业实现低成本运营和较高的服

务质量，我们需要对该地区的邮政运输网络进行重构，确定合适的邮路规划方案

并进行邮车的合理调度。

4

19

33

3

Step1:区级第一班次邮车从地市局 D 出发将邮件运送到各县局 Xi 和沿途支

局，并将各县局 Xi 和沿途支局收寄的邮件运送回地市局 D；区级第一班次邮车

出发时间必须在 06:00 之后，返回地市局 D 时间必须在 11:00 之前。

Step2:县局 Xi 将当天区级第一班次邮车及前一天的区级第二班次邮车所送

达的本县邮件进行集中处理，按寄达支局装上相应的县级邮车；县局 Xi 对邮件

的集中处理时间为 1 小时（包括邮件的卸装、分拣封发等处理时间）。

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

回县局 Xi；

Step4: 区级第二班次邮车从地市局 D 出发将邮件运送到各县局 Xi 和沿途支

局，并将各县局 Xi 收寄的邮件（包括当日各县级邮车运回县局 Xi 的邮件）和沿

见表 1，并且县级邮车平均时速为 30km/h，区级邮车的平均时速为 65km/h，邮

车在各支局卸装邮件耗时 5 分钟，在各县局卸装邮件耗时 10 分钟。

问题一：

以县局 X1 及其所辖的 16 个支局 Z1, Z2, ……, Z16 为研究对象，假设区级

第一班次邮车 08:00 到达县局 X1，区级第二班次邮车 16:00 从县局 X1 再出发返

回地市局 D，若每辆县级邮车最多容纳 65 袋邮件，试问最少需要多少辆邮车才

能满足该县的邮件运输需求？同时，为提高邮政运输效益，应如何规划邮路和如

何安排邮车的运行？（邮件量见表 2，空车率=(邮车最大承运的邮件量(袋)-邮车

运载的邮件量(袋))/邮车最大承运的邮件量(袋)，单车由于空车率而减少的收入为

（空车率*2 元/公里））

成本为 3 元/公里）

问题三：

考虑到部分县与县交界地带的支局，其邮件由邻县县局负责运送可能会降低

全区的运行成本，带来可观的经济效益。若允许在一定程度上打破行政区域的限

制，你能否给出更好的邮路规划和邮车调度方案？（在此同样不必考虑邮车的运

载能力的限制，每条邮路的运行成本为 3 元/公里）

4

问题四：

县局选址的合理与否对构建经济、快速的邮政运输网络起到决定性的作用。

假设图 2 中县局 X1，……，X5 均允许迁址到本县内任一支局处，同时原来的县

陈述你的迁址理由并以书面材料形式提交省局网运处。

使车辆有序地通过它们，在满足一定的约束条件（在这里是各支局邮件的寄达量、

邮件的收寄量、车辆出发和返回时间、车辆容量限制）下，达到所用车辆数量最

少、车辆总计运行的路程尽量少、把因空车率而造成的损失尽可能降低到最小的

目标。

PDPTW 被定义为一个整数规划问题，是有时间窗的车辆路径问题（Vehicle

Routing Problem with Time Windows ，VRPTW）的一般性推广，VRTW 是具有

时间窗的 VRP，VRP 又是 TSP 的推广，而 TSP 已被证明是一个 NP-hard 问题，

因此，PDPTW 也具有相同的复杂性。这类问题的规模较大，复杂度很高，有许

多实际的约束条件，解决难度大。经过分析发现对于本问题而言装邮包点和卸邮

益是不甚合理的。一个明显的例子就是在环形邮路的情况下正向与逆向行驶完成

的工作量是一样的，但通常会出现随着抵达支局的先后次序不同而发生空车率不

同的现象，这与实际情况是不相符的。但考虑到由空车率算出收益的减少能从大

体上反映出收益的情况，而且是否使用这个概念只牵扯到目标函数的选取，对于

问题的类型没有影响，所以本着尊重题目本意的态度，对该收益的评估方法予以

保留。

问题二是一个两层次（地区级层、县级层）有时间窗的车辆路径综合规划问

题，本身 PDPTW 就属于 NP-hard 问题，具有很高的复杂度，因此对于本问题想

求得最优解是不现实的。各县级邮政运输网必须覆盖本县内区级邮车不到达的支

局，也就是说县内被区级邮政运输网覆盖的支局县级的邮政运输网就不需覆盖，