邮政运输论文数学建模

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

1 问题重述

古往今来，邮政在人们的生活中都扮演着不可或缺的角色。随着时代的发展，邮件投送的时限和成本成了邮政运输问题的关键因素。根据题目给出的实际情况，本文提出了关于如何合理规划邮路的问题，具体内容如下：

对一片有特定道路相连且有行政划分的地区进行邮路规划，有以下的问题需要解决：

(1) 以县局X1及其所辖的16个支局Z1, Z2, ……, Z16(下文简称为1，2，……)为研究对象。假设区级第一班次邮车08:00到达县局X1，区级第二班次邮车16:00从县局X1再出发返回地市局D，若每辆县级邮车最多容纳65袋邮件，在不超载的情况下，利用最少的车辆和最短的邮路，达到减少空车损失的目的。

(2) 采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入，从而显著降低全区邮政运输网的总运行成本的邮路规划。

2 模型的基本

假设

2.1. 假设在同一天内需要收发的邮件数量为定值，不再变化。

2.2. 假设每条邮路只安排一辆车，同时一辆车只行驶给其安排的对应的某条邮路。

2.3．假设所有的邮车在邮路上均按照平均时速匀速行驶，不受路况和天气及抛锚等其他因素的影响。

2.4．假设县局对市局送来邮件的集中处理时间(1

小时)既包括区级邮车的装卸时间10分钟，也包括县级邮车的装卸时间10分钟。且在这1个小时的起始阶段进行装卸区级邮车的工作；而县级邮车的装卸工作最早在集中处理工作结束前10分钟进行，也可以在集中处理工作结束之后进行。

2.5．假设县局对将要送到市局的邮件的集中处

理时间(1小时)既包括县级邮车的装卸时间10分钟，也包括区级邮车的装卸时间10分钟。且在这1个小时的起始阶段进行装卸县级邮车的工作；而区级邮车的装卸工作最早在集中处理工作结束前10分钟进行，也可以

在集中处理工作结束之后进行。

2.6．假设两班次的区级邮车行驶路线完全相同，

若路线为环形则运行方向必须一致。如：D→61→58→53→X→52→59→60→D与D→

5

60→59→52→X→53→58→61→D两种行车

5

路线即为不同的两条路线。

3 问题分析 3.1问题一的分析

首先要求邮车数量做出规划

目标：邮车数量最少

受到的约束有：地区的邮政运输有一定的流程和时限规定

前题：邮车不能超载

此问要求其各邮路经过最小路径同时有了时间限制，根据这些规定，要求县局邮车最早在09：00出发，且必须在15:00之前返回，这就要求县局每个邮路邮车从出发到返回所用的时间应该小于6个小时，且邮车行驶时间不仅要考虑行驶路程耗时，还要考虑邮路上在支局装卸邮件的耗时；有各支局需收发邮包数量的限制和县级邮车有运量的限

制，要求其满足在不超载的情况下同时要损失最小来安排最少车辆数，由题中给出的的寄达和收寄的数据，得出最小邮车数量最少为三辆。要求根据邮车数量规划出的全部邮路能覆盖该县局所辖的16个支局。这是一个规划目标为旅行商数目的多旅行商的问题。要求根据最小车辆数进一步对邮路进行规划，目标是使总支出（包括运行费用和空车损失费）最少。

针对此问题，我们运用了用 prim算法对原路线图进行处理，求得其最小生成树，求其的程序及图见附件一。并用直接观察法提出了分块准则，我们根据分块准则，建立了以邮路的总路程和三组路程，邮车总时间和时间均衡度为目标函数的多目标标模型，并重点考虑三组完成巡视时间和时间的均衡度为目标函数建立模型。并通过分析比较均衡度，最终得出了最佳邮路路线。 3 符号约定

D

：市级邮局 ：县级邮局

：表示县级邮局的集合

XiXX1,X2,X3,X4,X5W(i,j)：赋权邻接矩阵

Si：每辆邮车行驶的路程

Fijk:0—1变量，第i辆邮车第j次装卸邮件是否在第k个支局

Fijk=0第i辆车第j次在k支局卸装 Fijk=1 第i辆车第j次在k支局没有装卸 S:三辆邮车跑的总路程

Gkq:第k支局寄出的邮件总量

Gkh:寄达第k支局的邮件总量

Dkq:途中节点k到节点q的最短距离（由得出的最小生成树求得）

4 模型的建立与求解

4.1 模型一的建立 最少车辆数的确定

根据题目的要求，寄达县局Z的邮件量为

1

176袋，而收寄的邮件量为170袋，同时每一辆县级邮车最多容纳65袋邮件，因此至少需要出动3车次才能够完成这样的投送量。同时，派出的每

辆车必须在六个小时内完成邮寄和收寄的任务。所以派出至少三辆车。 邮路最小生成树的确定

为了便于制定出最佳的邮路方案，首先我们运用prim算法求得邮路的最小生成树（如图一）

其程序见附件一

图一 最小生成树

确定目标函数

目标函数一：邮路的总路程和三组行驶

路程的均衡度为目标函数。

一方面，根据题目要求，邮车必须在六个小时内完成邮寄和收寄任务，而县级邮车的行驶速度保持一定，所以其必须在一定的路程内完成任务。另一方面，虽然题目中没有提出行驶过程中由于耗油量造成的损失，但作为一个成功方案，我们必须将其考虑在内，即派出的邮车满足覆盖所有的支局外，各辆车跑的路程越少越好，即车在行驶过程中耗时越少越好。

总的最短路程MinSMinS

3ii 且各组行驶路程的均衡度应该小于0.1才算比较均衡即

MaxSMinS0.1 MaxSsiisi

目标函数二：空载损失的费用最小，即

空载率小时损失小

为了安全起见，邮车有限载的约束，空车率=邮车运载的邮件量（袋）/邮车最大承运的邮件量（袋）

约束条件：

1 县级邮车运输网必须覆盖本县内所有的支局 由上面对问题分析县局至少要派出三辆邮车，三辆邮车跑各自的路线，三个路线所经过的支局点合起来必须覆盖本县内所有支局，且仅覆盖一次，所以有：

3 m

ΣΣFijk=16（k=1,2,3,……16）

i=1j=1 2 邮车运载能力的限制

根据问题一的要求，每辆县级邮车最多容纳量65袋邮件，这里实际限制了两个方面。其一，必须保证邮车从县局出发时其装载的邮件不超过65袋，其二也必须保证邮车在卸下一部分邮件，同时也要收取一部分邮件，邮车在支局的卸装过程完成后，必须保证邮车还是没有超载，否则不在该支局进行卸装货物货物。

根据设定的已知变量，所以得出第i辆车从县局出发时，装载的所要运送的邮件的量为：

3 m

ΣΣFijkGkh（k=1,2,3,……16）

i=1j=1

邮车在运输途中不断地卸装邮件，则可以得出，某辆邮车在某个支局进行装卸过程中，邮件

的变化量为Gkq—Gkh，则第i辆车在出发时及运输途中邮件总量不超过有车运输能力（65袋）约束可表示为

3 m 3 m

ΣΣFijkGkh+ΣΣFi(Gkq—Gkh) <=65

i=1j=1 i=1j=1 3. 邮车运输时限约束

据假设的条件，根区级第一班邮车08:00到达县局X1，区级第二班班车16:00从从县局返回市局，前后除去两个小时的邮件处理时间，该县邮车一天最多可跑六个小时。

由于三辆邮车所经过的支局正好覆盖并且只覆盖一次X1县的16个支局，并且假设邮车在每个支局进行卸装过程中耗时为五分钟，所以在整个运输过程中，而整个有车运输消耗时间有两部分组成，卸装货物过程造成的时间消耗和有车在运输途中的耗时，并有总的耗时不超过六小时

第i辆邮车在卸装邮件耗时大概为 小时， 第i辆邮车在运输途中耗时： 4.1.2 模型的求解

求解过程中，根据最小树分块原则，将图分成三个连通子图。为了制定合理的路线，在分组

是应遵循以下原则

准则一：尽量使同一干枝及其分枝上的点分在同一组； 准则二：应将相邻的干枝上的点分在同一组； 准则三：尽量将长的干枝与短的干枝分在同一组. 准则四：尽量使各组的停留时间相等.

附件一

clc,clear a=zeros(53);

a(50,1 )=6.0;a(50,53)=12.9;a(50,38)=11.5;a(50,2)=9.2;a(50,48)=19.8;a(50,51)=10.1;

a(1,36)=10.3; a(1,37)=5.9;a(1,38)=11.2; a(2,3)=4.8;a(2,5)=8.3;

a(3,38)=7.9;a(3,39)=8.2;a(4,39)=12.7;a(4,8)=20.4; a(5,48)=11.4;a(5,39)=11.3;a(5,6)=9.7; a(6,48)=9.5;a(6,7)=7.3;a(6,47)=11.8;

a(7,39)=15.1;a(7,40)=7.2;a(7,47)=14.5;a(8,40)=8.0; a(9,40)=7.8;a(9,41)=5.6;a(10,41)=10.8; a(11,45)=13.2;a(11,40)=14.2;a(11,42)=6.8; a(12,42)=7.8;a(12,41)=12.2;a(12,43)=10.2;

a(13,44)=16.4;a(13,45)=9.8;a(13,42)=8.6;a(13,14)=8.6; a(14,15)=15;a(14,43)=9.9;a(15,44)=8.8;

a(16,17)=6.8;a(16,44)=11.8;a(17,22)=6.7;a(17,46)=9.8; a(18,46)=9.2;a(18,45)=8.2;a(18,44)=8.2; a(19,20)=93;a(19,47)=7.2;a(19,45)=8.1; a(20,21)=7.9;a(20,25)=6.5;a(20,47)=5.5; a(21,23)=9.1;a(21,25)=6.5;a(21,46)=4.1;

a(22,23)=10.0;a(22,46)=10.1;a(23,24)=8.9;a(23,49)=7.9; a(24,27)=18.8;a(24,49)=13.2;a(25,49)=8.8;a(25,48)=12.0; a(26,27)=7.8;a(26,51)=10.5;a(26,49)=10.5;a(27,28)=7.9; a(28,52)=8.3;a(28,51)=12.1;

a(29,52)=7.2;a(29,53)=7.9;a(29,51)=15.2; a(30,32)=10.3;a(30,52)=7.7;

a(31,32)=8.1;a(31,33)=7.3; a(31,53)=9.2; a(32,33)=19;a(32,35)=14.9;a(33,36)=7.4; a(34,35)=8.2;a(34,36)=11.5;a(34,13)=17.6;

a(37,38)=12.2;a(36,53)=8.8;a(37,38)=11.0;a(44,45)=15.8;a(48,49)=14.2; a=a+a';

a(find(a==0))=inf; result=[]; p=1;

tb=2:length(a);

while length(result)~=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp);

[jb,kb]=find(a(p,tb)==d); j=p(jb(1));k=tb(kb(1)); result=[result,[j;k;d]]; p=[p,k];

tb(find(tb==k))=[]; end result