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

1、邮政运输网络中的邮路规划和邮车调度【摘要】：本题主要以现实中邮政网络规划问题为研究对象，在研究过程中针对不同情况下的最佳邮路设计和运输效益问题，分别建立了线性规划模型，并利用matlab软件搜索求解。针对问题一，首先利用matlab元胞数组功能录入x1县的邮政信息，建立包含各支局收、寄邮件数量和各线路行驶时间的数据库，然后在同时满足各线路邮件运输量不超过邮车最大承载量和各线路邮车运输时间不超过规定时限的条件下，调用数据库中相关信息并利用matlab软件搜索所有符合条件的邮路，其次以使用最少邮路覆盖全县邮政网络为目标，建立关于邮路设计的线性规划模型，并利用matlab软件求解得，覆盖全县最少需规

2、划3条邮路即最少使用3辆邮车就可满足全县邮件运输需求，最后在满足上述求解结果的条件下结合空车率计算方法，以减少收入最低为目标建立关于邮车调度的线性规划模型，利用matlab软件搜索求解得3辆邮车的具体路线安排分别为：xl-12-13-1-3-2-5,x1-4-6-9-11-10,x1-14-15-16-8-7,此时因空车率而降低的总收入为：62.4615元。针对问题二，通过对题目的分析，首先利用贪婪算法寻找市局内可到达各县局的最近支局，并将其作为通往各县局邮路在市区内的终点和在各县局内的起点，其次在确定市区和各县局内邮路的起点和终点后，在同时满足从市局出发的各邮路可完全覆盖市局邮政网络和各邮路

3、运行时间不超过规定时限的条件下，以邮路总运行费用最少为目标，建立线性规划模型，并利用贪婪算法逐步寻找最优解，最后解得市局需5辆邮车，各县局分别需要：2,2,0,0,2辆邮车，总路程最小为2089.1公里，此时的总费用最小为6267.4元，具体安排见模型求解。关键词：线性规化搜索求解贪婪算法1、问题重述1.1 问题的来源及意义：在信息技术飞速发展的今天，互联网已经成为一种重要的通信手段，但在我们利用Email等方式交流信息的同时，邮政作为传统的通信手段仍然与我们的日常生活和工作息息相关，发挥着不可替代的作用。时限与成本是邮政运输问题的两个重要指标。时限是指邮电部规定的邮件、报刊处理、传递的最大时

4、间限制，时限关系到邮政通信质量的好坏；成本影响着企业的经营。邮政运输网络是邮政企业运营的重要保障，是决定邮政企业竞争能力的主要因素。1.2 提出问题1以县局X及其所辖的16个支局乙，乙，,乙6为研究对象，假设区级第一班次邮车08:00到达县局X,区级第二班次邮车16:00从县局X1再出发返回地市局D,若每辆县级邮车最多容纳65袋邮件，试问最少需要多少辆邮车才能满足该县的邮件运输需求？同时，为提高邮政运输效益，应如何规划邮路和如何安排邮车的运行？2采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入，从而显著降低全区邮政运输网的总运行成本。考虑投入车况较好的邮车，通常每条邮路只需要一辆

5、邮车即能满足运载能力要求，试问应如何构建该地区的邮政运输网络（县的划分不能变更），请你给出邮路规划和邮车调度方案。请注意邮车的调度必须满足上文中有关该地区的邮政运输流程及时限规定。2、问题分析本题主要以现实生活中的邮路规划和邮车调度问题为研究对象，在研究过程中需考虑各支局之间是否可到达，邮车的调度是否满足题目要求和安排的邮路是否能覆盖邮政网络等因素。解决邮路规划和调度问题时需要明确以下几个方面：邮路的形式与种类在邮政运输网络中，将各地市局、县局、支局都近似看做结点，任意两点的连线都可看做是一条路径，邮路类型主要有环形、辐射型和混合型三种，由于实际邮政运输网络中存在两个邮局间无可到达路线的情况且

6、并非所有支局都可直达县局，因此，根据邮局问直达的情况即可推算出各条邮路的线路类型。线路搜索方法本文的关键是搜索方法的科学性，应首先寻找出所有的线路，其次，搜索同时满足每辆车的时限要求和邮车最大运载量的线路，即记录所有同时满足时限要求和最大运输量的线路，最后，根据线路是否覆盖所有支局且无重复数据得到最终的可到达线路。不同要求下对时限的理解与计算时限指的是邮电部规定的额邮件、报刊处理和传递的最大时间限制。在调度邮车的过程中主要考虑邮车在行驶过程中的耗时、在支局或县局的卸装时间、处理邮件的时间。对不同区域或规定时限其计算方法是不同的。3、模型假设1假设邮车在行驶过程中不会存在意外的等待时间；2假设区

7、级第一班次的邮车到达区级后的处理时间不予考虑；3假设车况较好的邮车没有最大运载量的约束；4假设不同邮车在不同时间到达支局或县局的卸装、分拣封发和等待时间等都是相同的；5假设不同县局邮车经过的支局各不相同，即一个支局只能由一辆邮车到达。4、符号系统及名词解释4.1符号说明%Pki表示第k辆车寄达支局Zi的邮件量qki表小第k辆车在支局乙收寄的邮件量付号及k表示邮车数目的编号T1k第k辆车的行驶时间说Sk行驶过程中的行程明hnk表示第k辆车是否经过第n个点Mk表小第k辆车运输的邮件量备注k为邮车的编号，其值取1,2-n;i为支局抽象为点的编号，其值取1,2-734.2名词解释1邮路：指利用各种运输

8、工具按固定班期规定路线运输邮件，并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线，它是邮政运输网络的基本组成单元。2时限：指邮电部规定的邮件、报刊处理传递的最大时间限制。3区级邮政运输网：从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成。4空车率：其计算方法为：（邮车最大承运的邮件量-邮车运载的邮件量）/邮车最大承运的邮件量。5、模型的建立与求解县局到支局的邮路规划和邮车调度模型准备S=s,s2,.,同时将邮车行走1、行驶线路的一般表达形式和邮政运输流程如图所小，A表小环形邮路，B表小辐射型邮路，在邮政运输网络中，将各地市局、县局、支局都近似看做结点，任意两点的连线都可看做是一

9、条路径，由于实际邮政运输网络中存在两个邮局间无可到达路线的情况且并非所有支局都可直达县局，因此，根据邮局问直达的情况即可推算出各条邮路的线路类型，将各种邮路的线路类型及运输流程表达如下：1构造线路的一般形式首先由各个邮局所在的位置抽象出点的集合的线路表达为线路的集合L=l1,l2,.,当且仅当邮局点s在行驶线路l上时，s与l间有一条边。邮局结点p和q组合成的线路必须满足一定的次序,即注考虑到piq与qTp是不同的线路。环形邮路的路线形式：设XiXj为第j个县局的编号，Z1Zi为第i个支局的编号，的以一条可用线路为例进行说明，具体线路如下：r相同线端jX1>Z10>Z11>Z1

10、6>Z9>Z15>X1由图中可看出此时邮路的起始点和终点都是县局，且不走重复路线，这种情况下联系点较多，能大大增加运输工具的利用率，此种线路的缺点是送到最后几个结点的时间较长，时限的约束将使其到达的支局个数较少。辐射邮路的路线形式由图示可初步判断出此种邮路的特点是从起点到终点后，仍按照原路线返回出发地点。因此须在同一条路线上往返两个行程。X1>Z14>Z14>X1这种结构的邮路可以缩短运递时间，加快邮运速度。但它的联系点较少，需用的运输工具较多，所耗费用较大。混合邮路的路线形式邮车在运输邮件的过程中，将会存在邮车经支局回到县局后继续开往支局运输邮件的情况即混

11、合邮路。这种情况是由于邮车由县局出发第一次运往各个支局并返回时仍然有部分空余时间，邮车再次由县局出发到附近支局运送邮件。这一形式是辐射邮路和环形邮路的综合。县局县局县局X1>Z10>Z11>Z16>Z9>Z8>X1>Z14>X1ids./h2地区的邮政运输流程该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。运输流程如下：地区的邮政运输

12、流程补充说明：图中B1、B2表示市局车辆运输的第一班次和第二班次，C1表示县局邮车的第一班次，且县局邮车有且仅有一个班次。具体流程为区级第一班次邮车从地市局D出发将邮件运送到各县局X和沿途支局，并将各县局X和沿途支局收寄的邮件运送回地市局D,各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局X。2、确定邮车调度对时限要求在邮政运输中，时限和成本是邮政运输问题的两个重要指标，其中，时限指的是邮电部规定的额邮件、报刊处理和传递的最大时间限制。在调度邮车的过程中重点考虑以下几个方面的时间限制。1县级邮车在行驶过程中花费的时间（简称行程时间）：县级邮车的行程仅局限于邮车由县局出发并最终

13、返回县局的县级邮车所行驶的全部路程，行程时间可表示为：行程时间行驶总公里数邮车行驶单条邮路的路程可简单表示为行程，将行驶总公里数看做各行程的和，设i表示邮路经过的支局编号（将第一个可到达的支局编号定位初值1,2,3-n依次表示路线中经由的支局），设j表示经由的县局的次数，k表示邮车数目的编号，第k辆车的行驶时间为丁伟，行驶过程中的行程表示为Sk,则此时单段距离可表示为dc,则行驶总公里数可表示为：n、八dc（nN）cm县级邮车平均时速为30km/h,根据总公里数得到总的行程时间为：丁卜产（dc/3。）（1）c42邮车在支局的卸装耗时：邮车由县局向支局运输邮件的过程中，每经过一个支局都将卸载一部

14、分寄往此支局的邮件，同时，装载一部分邮件运往市区，根据时限要求，在各支局卸装邮件耗时5分钟。卸装时间=经过的支局个数M每次卸装的时间设第k辆车的卸装时间为T2k,邮车从县局出发运往各个支局中经过的支局个数为“，每次卸装的时间为5分钟，则：1T2k=-nk123邮车在各县局的卸装耗时邮车的行驶线路为先由区级邮车将邮件运往县级，而后到达县级的邮件将由县级邮车运往各个支局，在此过程中，由于车辆数的不确定性和邮路类型的差异，一般来说，每辆车在满足运载邮件的最大量或时限范围内时将返回县级，每辆县级邮车最多容纳65袋邮件，若仅仅是因运载邮件的数量满足最大容纳量返回县级，则在剩余时限范围内有可能再次由县局出

15、发到达支局并返回，运载返回县级的次数是不确定的。县局卸装时间=经过县局卸装次数父每次卸装时间设第k辆车在县局卸装时间的卸装时间为飞邮车经过县局的卸装次数为n°k,由于在县局每次卸装的时间均为10分钟，因此，将这一时间表示为：1，一T3k=n0k二64处理邮件的时间结合题意，当邮车从县局出发时，县局对邮件的集中处理时间为1小时，这一小时中包括邮件的卸装、分拣封发等处理时间。将处理邮件占用的时间表示为：处理邮件时间=出发前处理邮件的时间+返回处理邮件时间当县级邮车沿途收寄的邮件运送到县局时同样需要集中处理一个小时后后再由区级邮车运往地市局。因此，根据时限规定对每辆邮车处理邮件的耗时均为2

16、小时。5计算邮件处理和传递的总时间综合考虑多方面的耗时，可计算得到不同邮车在一天中处理、传递邮件的总时间Tk:Tk飞Tk2Tk32(4)将(2)(3)代入得总的耗时：Tk=E&/3o)+jnk+Pnok+Zc=i1263、限制每辆县级邮车最大容纳的邮件数量考虑到一般的邮车最多能容纳的邮件数量是一定的，对县级邮车没辆车能容纳的最多邮件数是65,根据寄达支局乙的邮件量和支局乙收寄的邮件量可求得每辆邮车在不同行驶位置运载的总邮件数。为了满足每辆县级邮车最大运载量不超过65袋邮件这一限制，同一支局寄达和收寄邮件的存在数量差异，取每到达一个支局都记录寄达支局乙的邮件量和支局Zi收寄的邮件量中较大

17、的一个，设X1Xi为第i个县局的编号，k表示邮车的编号，Pki表示第k辆车寄达支局Zi的邮件量，qki表示第k辆车在支局乙收寄的邮件量乙，Mk表示第k辆车运输的邮件量，将对邮件数量的约束表示为：nkMk=，max(pki,qki)£65(i的值取12.16)i14、由邮路网络结构建立带权的邻接矩阵为了将邮路的网络形式用数学的语言描述出，应根据路径的特点将之看做无向图的形式，以带权的邻接矩阵的形式得到邮路的具体表现形式。1明确矩阵的形式由线路网络结构建立带权的邻接矩阵arcs根据地区邮政局所分布情况和邮局间直达公路里程的数据信息，令arcsij表示由fez）或（z，zj所构成有向路径的

18、权值，若依2）或«”,不存在，则置第i条邮路的第j个分段的线路路程arcsij为0,s为已找到从v或x出发的的路径终点的集合，它的初始状态为空集。则第i条邮路从v或x出发到其余各顶点（终点）m或Xi可到达路径的长度为：Di=arcsij线路网路结构中各个结点间的距离代表了其权值的大小，由于任意两点间的路径是双向的，即结点AtB和BtA是同一线路，只是方向不同而已，因此，将之描述为无向图的形式，无向赋权图中的权矩阵W（Wj）nM其分量为：'wWi,Vj）顶点Vi与v才目连弧的长度w70顶点Vi与Vjj考虑无向图的邻接矩阵的对称性，采用压缩存储的方式只存入矩阵的下三角元素或上三角

19、元素，但此时矩阵表达的实际意义难以直观表达出来，故采用一般的存储方式，根据以上定义构造带权的邻接矩阵如下：0.aij+FFarcs=：，+;aj.02规律总结邻接矩阵的带权性，路径的权值体现了线路间的连通性和实际直达距离，根据任意两个点间的直达距离即可描述出线路的具体形式，根据点间的距离可计算出运输过程中的时间，同时根据可到达支局的数目得到邮车在不同时间和地点运载邮件的数目，同时考虑时限和邮车可运载邮件数量的约束进行搜索求解即可得到满足邮件运输要求的最少邮车数。邻接矩阵的对称性：将邮政运输网络中各个邮局代表的结点连线后构成无向图的形式，这种网络结构的特点决定了其矩阵的对称性。即任意两点间的路径

20、是可顺向或反向的。3建立表格确定矩阵中的元素根据邮局间的直达公里里程的详细信息得到任意两点间的可连通性和具体的直达距离，若两邮局（包括县局、支局）没有直达路线，则将距离赋权为0,反之以其直达公里里程赋权。建立表格如下：邮车运输网直达公里数赋权图x1z1z2z3z4z5z6z7z8z9z10z11z12z13z14z15z16x102744171127420002025212118270z1270312749000000052214100z2443101902732000470005000z317271901400000300003100z4114901401320002815000152530

21、z52702701309210262600028290z642032020901303200000330z700000211301900000000z80000000190112000003321z900002826320110102000291413z10200473015260020100180014920z112500000000201802301400z122152000000000230272200z1321210000000000270000z141841503115280002914142200110z15270002529330331490001109z160000300002

22、113200000904构造线路矩阵设矩阵元素a。表示第i个邮局到达第j个邮局的线路，n表示线路条数，每出现一次可到达结点记录一次，其中，当i=j时为无效路径，设定值为0,则：n(i二j)aij=j0(i=j)5、利用元胞数组调用可达线路由于每到达一个支局再次出发时将有多条路线可供选择，线路的选择虽然具有一定的层次关系，但每个支局可到达的点的数量各不相同，故本文采用MATLAB内建元胞结构，当元胞内队列不存在时不占用空间，元胞数组中可存储不同类型的元素和维数不相同的矩阵，具体元胞结构设计如下：元胞结构示意图21+1i1明确邮路的几个特点及规律从实际出发，邮车在选择线路的过程中应优先选择县局到支

23、局的线路，而后由支局出发运送邮件到其它支局，最终返回县局，需要明确以下几点规律：邮车每经过一个支局都将有多种路径可供选择，且可选路线的数目是不确定的。支局的编号并不能反映出邮车到达支局的先后顺序，即邮车有可能由支局Bt支局A(B的编号大于A的编号)。设i,j表示线路编号，坊为i,j间的邮路，k为正整数，则将其表示为：lb(Hk)(jA)第i个支局的编号小于第(i+1)个支局编号jbd*)。4)日人只需搜索每个支局能到达的所有结点即可找出所有情况。2构造邮车可到达线路矩阵矩阵元素a。表示第i个有邮局到第j个直达邮局的线路数n,其中，i=j时为无效路径，设定值为0,以N表示所有邮局结点的总数，则描

24、述邮车可到达线路矩阵可表示为：a11知IIIIIHIIa1Na21a22IIIIINIIa2NAn>N=+*4i*+aij.+iaN14aN2IIIIIHHaNN)6、明确选取线路的搜索方法应首先寻找出所有的线路，其次，搜索同时满足每辆车的时限要求和邮车最大运载量的线路，即记录所有同时满足时限要求和最大运输量的线路，最后，根据线路是否覆盖所有支局且无重复数据得到最终的可到达线路，具体搜索方法如1搜索所有的可到达线路邮政运输网络中存在部分邮局间不可直达的情况，将由县局到支局的线路表示为X1>Zi,则由县局X1出发仅Z7,Z8,Z9,Z16不可直接到达县局，需经过其它支局后到达县局X1

25、,令i从1开始搜索可到达线路的，此时选出的线路仅仅满足连通性。2搜索出同时满足时限和邮车运载能力的路线在所有可到达线路中，任意给定一条路线都将得到其形式时间和到达线路终点时邮车运载的邮件。设X1Xi为第i个县局的编号，k表示邮车的编号，当天邮件处理和传递的总时间Tk不大于时限要求，第k辆邮车经过县局的卸装次数为nok,线路中第c段距离可表示为dc,邮车从县局出发运往各个支局中经过的支局个数为叫，将时间限制表小为：16nok2<8为了满足每辆县级邮车最大运载量不超过65袋邮件这一限制，同一支局寄达和收寄邮件的存在数量差异，取每到达一个支局都记录寄达支局乙的邮件量和支局Zi收寄的邮件量中较大

26、的一个，设X1Xi为第i个县局的编号，k表示邮车的编号，Pki表示第k辆车寄达支局Zi的邮件量，qki表示第k辆车在支局乙收寄的邮件量Zi,Mk表示第k辆车运输的邮件量，将每辆车运载能力的要求表示为：nkMk=£max(pki,qki)«65(i的值取1,2.16)i13搜索能覆盖所有网络结点的最少线路根据以上分析得到了符合邮车运载能力和时限要求的具体线路，在这些线路中仅有部分线路覆盖的支局数目较多，在其中找出经过支局最多的线路，采用“逐步逼近”的思想进行搜索选取线路，当满足条件时停止累加，即每条线路上经过的支局个数累加求达到最大数目16时记录线路条数，从而最终确定最少的线

27、路（即邮车的最少数目），设k表示选择的邮车数目，每个邮车经过的支局个数为Rk,将支局个数的限制表示为：n'、Rk=16（nN）k4注：k的值取能满足上述条件的最小值，k的取值范围为iwk916。7、引入“01”决策变量经过搜索得到所有同时满足时限要求和最大运输量的线路，具线路编号为k,为了明确表示线路的选择，引入01变量Xk表示第k条路线是否被选择，k值取1,216中的任意一个，属于无序取值。将其表示如下：1选择第k条线路Xk0否则8、最少邮车数量下的线路选择县级邮车一天只有一班车且行驶的线路唯一，根据逐步逼近找到了能覆盖所有网络结点的最少线路，线路的条数即是满足运输需求的最少车辆数。

28、根据搜索出的线路形式即可规划邮路并安排邮车的行驶线路。9、空车率的求解方法为提高邮政运输效益，规划邮路和安排邮车的运行中考虑邮车的利用率，定义空车率二（邮车最大承运的邮件量（袋）-邮车运载的邮件量（袋）/邮车最大承运的邮件量（袋），单车由于空车率而减少的收入为（空车率父2元/公里）。以下为求解空车率的具体方法：步骤1=步骤2口步骤3计算在/、同线路上支局的空车率将每条线路上的空车率累加找出3条空车率最小的累加下表为每个支局寄达、收寄的邮件量及每到一个支局邮车运载数目的改变量，根据其可判断出何处空车率的改变量较大：寄达局ZZ2乙乙乙Z6Z7Z8Z9ZioZ11Z12Z13Z14Z15Z16寄达Z

29、i的邮件量101569136114131711211211314Zi收寄的邮件量9145109101391596713151016改变量-1-1-114-4252-8-552-632邮车到达各支局后的邮件数量ak=为十Axk,除为邮车到各支局的前一支局的邮件数量，Ax为邮车到达各支局后的邮件改变量设g表示线路上每相邻两邮局的段距离；己为每到一个支局邮车运载数目的改变量；fig表示第i条线路上第g段距离的值；。表示第i条线路上在第j个Aa支局处的空车率；可将其表示为:d265f'g6c65-a5.1.2模型的建立与求解模型一：寻找满足运载需求的最少车辆数1、模型的建立根据以上分析我们已经

30、得到所有同时满足时限要求和最大运输量的线路，并以使用最少车辆数满足全县邮政运输需求，即使用最少线路覆盖全县邮政网络为目标，限定01变量的个数及取值建立0-1线性规划模型：nMin.'=、,Xki*'J1/11人父£(dc/30)+xnk+Mn0k+2M8(1)Ti126nkS.t(xkM£max(pki,qki)<65(i的值取12.16).(2)iAXkW0,1(3)J<k<16(4)【符号定义】九满足运输需求的总车辆数；k：选取总线路的编号n°k：第k辆邮车经过县局的卸装次数；d/表示线路中第c段距离；xj表示第k条路线是否被

31、选择；pki:第k辆车寄达支局乙的邮件量；qki：第k辆车在支局Zi收寄的邮件量；：第k辆邮车经过的支局个数；【模型说明】目标函数：求解满足运输需求的最少车辆数(即选择总线路的条数)；约束条件(1)：每辆邮车运输邮件时的行驶路线均满足时限要求；约束条件(2):每辆邮车运输邮件时的行驶路线均满足最大运载量的要求；约束条件(3):限定01变量表示第k条路线是否被选择；约束条件(4):约束邮车数量的上下限；2、模型的求解算法步骤：step1:使用matlab元胞数组功能，利用cell函数创建元胞，并将各支局收寄邮件数量和各支局可到达点的路线信息录入元胞数组中，从而建立关于县局邮政网络信息的数据库。s

32、tep2:调用数据库中相关信息，建立循环体对邮车路线进行准确的搜索，在满足各支局之间可到达的情况下，分别搜索一辆邮车经过6、5和4个支局时的邮路安排，并将所得邮路信息记录在所建数据库中。step3:通过使用判断语句，首先在满足邮车运输时间不超过规定时限的条件下，对所得邮路进行筛选，记录下符合条件的邮路并结束判断，其次通过计算各支局收寄邮件的差值，得到邮车经过该支局时邮件数量的改变量，最后对符合条件的邮路，在满足经过各支局时邮车运载邮件数量均不超过邮车运载上限的条件下，使用判断语句对其再次进行筛选，最终所得结果即为满足题意的邮路并将其录入数据库。step4:首先通过建立循环体分别对两辆邮车经过6

33、,5、6,4和5,4个点的情况进行组合，然后通过使用判断语句去除其中含有公共点的线路，将剩余线路再次进行判断记录下能覆盖全县16个支局的线路，通过运行程序可知此时的组合无法覆盖全县。step5:其次通过建立循环体分别对三辆邮车经过6,6,4和6,5,5个点的情况进行组合，重复上述步骤，记录下三辆车可覆盖全县的情况，通过运行程序可知此时有解，结束循环体。求解结果：最终求解得到能满足运输需求的最少车辆数为3.模型二：满足运输效益最大化下的邮路安排（重点考虑空车率）1、建立模型根据上文的分析以所有邮车由于空车率而减少的收入最少为目标，约束其取值得到以下模型：316MinMdjykj,.65akd=2

34、m-k-xfdij2a匚fig65figNS.ty'0,1)n2x=iiV模型说明：g：表示线路上每相邻两邮局的段距离；M:所有邮车由于空车率而减少的收入；为:第i条线路上在第j个支局处的空车率;fig:第i条线路上第g段距离的值；aik：邮车到达各支局后的邮件数量；2、模型求解不同车辆运达的支局数目各不相同，因此分三种情况进行求解，其中三辆车分别经过6、5和4+1个点的是指第三辆车行驶的线路为混合邮路。利用matlab软件搜索求解得3辆邮车的具体路线安排分别为：x1-12-13-1-3-2-5,x1-4-6-9-11-10,x1-14-15-16-8-7,此时因空车率而降低的最少收入

35、为：62.4615元。三辆车分别经过6、5和4+1个点的情况减少的收入X11312111043X1X1X115145968271X1X1X1_166.246216三辆车分别经过6、5和5个点的情况减少的收入X112131325X1X14691110X162.4615X114151687X1三辆车分别经过6、6和4各点的情况减少的收入X110816432X1X11591112131X174.5X167514X15.2同时考虑市局和各县局时的邮路规划和邮车调度模型准备1、基本思路通过对题目的分析，首先利用贪婪算法寻找市局内可到达各县局的最近支局，并将其作为通往各县局邮路在市区内的终点和在各县局内的

36、起点，其次在确定市区和各县局内邮路的起点和终点后，在同时满足从市局出发的各邮路可完全覆盖市局邮政网络和各邮路运行时间不超过规定时限的条件下，以邮路总运行费用最少为目标，建立线性规划模型，并利用贪婪算法逐步寻找最优解。2、引入“01”变量确定路径的选择用gu表示总的邮政运输网上是否选择第u段所在的路径将其表示为：第u段路径被选择gu二0否则3、求解目标的确定根据题意，应采用尽可能少、尽可能短的邮路以减少邮政部门车辆和人员等的投入，降低总运行成本。因每条邮路的运行成本为3元/公里，可将总运行成本最低这一目标转化为求解总线路最短，根据总的最短线路里程数即可得到总运行成本。设i表示各个县的编号，其值取

37、15;设u表示邮政运输网上所有的可到达达路径的编号；的表示到达第i个县的线路上支局位于区内的点的个数；gu为总的邮政运输网上是否选择第u段所在的路径；ni为第i辆邮车从县局出发运往各个支局中经过的支局个数；ni3表示市区车在县局内经过点的数目；hik表示由市局到达第i个县的线路上第k段的距离；%表示第i个县局邮车行驶线路中第k段的距离；Oik表示市局到进入第i个县中第k段的距离；求得区级邮政网络上的运输路程为§和县级邮政网络上的运输路程为S2的表达式为：5n,iS=££hjgui口k-15Mi£likEgui±kJ5n3S3=ZZokl1gu、

38、ijk4设S为总的路程，由上式得：5nii5Mi5n3SHhkgu七三likh匚QkJgui，kji4k4ik综上所述，将这一目标表示为：5ni5Mi5n3MinS=EE廉五+££%互+££QkEui，k目i，kik4、约束条件的确定1约束区（县）级邮政运输网的覆盖区域根据题意，区级邮政运输网必须至少覆盖该地市附近的16个支局Z58,乙9,Z73和5个县局Xi,，%。各县级邮政运输网必须覆盖本县内区级邮车不到达的支局。考虑投入车况较好的邮车，通常每条邮路只需要一辆邮车即能满足运载能力要求，将这一约束表示为：L5£%=16（1）'iV1M

39、i=m+k（2）61：表示到达第i个县的线路上支局位于区内的点的个数；62:表示到达第i个县的线路上支局位于县内的点（由区局邮车满足运输需求）的个数；Mi:第i个县的县局邮车必须满足运输需求的支局数目；mi:第i个县内所有的支局数目（包含县局本身）；2确定邮车调度对时限要求在调度邮车的过程中重点考虑以下几个方面的时间限制。邮车在行驶过程中花费的时间在邮路上运输花费的时间主要由两部分组成，一是在区级邮政网络上的运输时间，二是在县级邮政网络上的运输时间，应分别求出两者并求和。当邮车的时速确定时，运输时间主要与运输距离有关，设S为总的路程，前文已给出总运输公里数的表达式：5ni15Mi5n3S=&#

40、39;hikMu'、'lik-gu'QQik-guk._,/Jk工、iAk,3SS2s3县级邮车平均时速为30km/h,区级邮车平均时速为65km/h,根据总公里数得到总的行程时间为:Ti_S1S2S3-653065邮车在支局的卸装耗时：邮车由县局向支局运输邮件的过程中，每经过一个支局都将卸载一部分寄往此支局的邮件，同时，装载一部分邮件运往市区，根据时限要求，在各支局卸装邮件耗时5分钟。卸装时间=经过的支局个数M每次卸装的时间设第k辆车的卸装时间为T2k,邮车从县局出发运往各个支局中经过的支局个数为nk,每次卸装的时间为5分钟，则：1，T2ini(2)12邮车在各县局的

41、卸装耗时设第k辆车在县局卸装时间的卸装时间为Rk,邮车经过县局的卸装次数为n°k,由于在县局每次卸装的时间均为10分钟，因此，将这一时间表示为：_1T3i=n0i否(3)处理邮件的时间结合题意，将处理邮件占用的时间表示为：处理邮件时间=出发前处理邮件的时间+返回处理邮件时间由于区级邮车在每个班次沿途收寄的邮件运送到县局时需要集中处理一个小时后后再由区级邮车运往地市局。因此，根据时限规定对每辆邮车处理邮件的耗时均为2小时。计算邮件处理和传递的总时间综合考虑多方面的耗时，可计算得到第i辆邮车在一天中处理、传递邮件的总时间Ti:TiJ7Ti32将(2)(3)代入得总的耗时：SiS2s311

42、Ti二一一一一ninoi2653065126约束总时间(即对时限的要求)根据以上分析，综合考虑运输时间、卸装时间、处理邮件的时间将时间约束表小为：5"S2s工ni1n0i2<126530651265.2.2模型的建立根据以上分析，将总运行成本最低这一目标转化为求解总线路最短，根据总的最短线路里程数即可得到总运行成本。约束时限和覆盖区域建立以下模型：5niiMinShkEu'、'、hk_gu'、'、Oik_guijk=：1ik二1ijk5%=16i1Mi=甲-52T三3J16530651216noi5ni3TW12JStgu?0,1(uwN)5ni

43、1S=£Zhkgui4kz15MiS2=N£likgu>(3)i=1k=15%3S3-XXoikEguykm符号说明:i:表示各个县的编号，其值取15;u:表示邮政运输网上所有的可到达达路径的编号；61：表示到达第i个县的线路上支局位于区内的点的个数;ni2：表示到达第i个县的线路上支局位于县内的点（由区局邮车满足运输需求）的个数；ni3：表示市区车在县局内经过点的数目；Mi:第i个县的县局邮车必须满足运输需求的支局数目；mi:第i个县内所有的支局数目（包含县局本身）；gu：总的邮政运输网上是否选择第u段所在的路径；工：第i辆车的行驶时间（一条线路对应一辆邮车，区级邮

44、车数目为5）;Q：第i辆邮车从县局出发运往各个支局中经过的支局个数；noi:第i辆邮车经过县局的卸装次数；廉：表示由市局到达第i个县的线路上第k段的距离；lik:表示第i个县局邮车行驶线路中第k段的距离；M：表示市局到进入第i个县中第k段的距离；模型说明：目标函数：邮车运输线路总公里数的最小值；约束条件（1）：约束区（县）级邮政运输网的覆盖区域；约束条件（2）：每辆邮车运输邮件时的行驶路线均满足时限要求;约束条件（3）:限定邮车在区内的运输距离和县内的运输距离；5.2.3模型求解1-算法思想一一利用贪婪算法的思想逐步构造最优解邮局之间所有可能的连接可被视作一个无向图，图的每条边都被赋予一个权值

45、，权值表示建成由这条边所表示的距离。包含图中所有顶点（城市）的连通子图都是一个可行解。设所有的权值都非负，则所有可能的可行解都可表示成无向图的一组生成树，而最优解是其中具有最小代价的生成树。在这个问题中，需要选择一个无向图中的边集合的子集，这个子集必须满足限制条件：所有的边构成一个生成树。而优化函数是子集中所有边的权值之和。在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则。2、求解结果最终求解得到的线路安排为：第一辆车，行程241.1公里，费用723.45元，用时4.7933小时D6970

46、35343230293133X32868D第二辆车，行程257公里，费用771元，用时4.954小时D724241X443403938373671D第三辆车，行程256公里，费用768元，用时4.69小时D666318X2272831646567D第四辆车，行程268公里，费用804元，用时4.9563小时D7342444651X553525861D第五辆车，行程253公里，费用760元，用时4.8小时D605962910X111151662D第六辆车，行程117公里，费用351元，用时4.4小时X1141087654X1第七4两车，行程136公里，费用408元，用时4.9497小时X1321

47、1312X1第八辆车，行程139公里，费用417元，用时5小时X22122232425X2第九辆车，行程157公里，费用471元，用时5.64小时X21719202625X2第十辆车，行程133公里，费用398元，用时4.84小时X5504948474551X5第T一辆车，彳丁程132公里，费用396元，用时4.733小时X55455565754X5上述线路中15是从市局出发的五辆车，611为各县局总共出发的六辆车,求得总路程最短为2089.1公里，总的费用最少为：6267.4元。6、模型评价与推广本题针对现实生活中的邮路规划和邮车调度问题建立了线性规划模型，该模型针对现实生活中的种种情况给出

48、了最优的邮车调度和邮路规划方法，实用性高是该模型的优点，但是在面对实际生活中的种种复杂情况，在程序计算中略显不足，搜索到所有路线情况所需时间过多，准确性纯在一定的问题，导致求出的最优解不是实际生活中的最优解。在对模型进行改进时，主要需要针对模型求解得程序进行进一步改进，增加程序搜索的细腻程度，以使程序可搜索到更多的可能组合线路，提高求解结果的准确性，在规划全县邮路线路时，需和问题一一样已知所有支局的收寄邮件数才能更加准确的对邮路和邮车进行规划安排，综上所述，由于本题涉及问题实际化程度过高，需更多时间对求解程序进行调试才能求得更加准确的答案。7、附录问题一：限定时间的搜索程序x=30027441

49、711274230030030020252121182730027300312730030030049300300300300522141300300443130019300300300300273247300300300503003001727193003003003001430030030300300300313003001149300143003002830013201530030030015253027300273002130026133009263003003002829300423003230013300322093003003003003003003330030030030030

50、030019300300211330030030030030030030030030030030019300113003003002030030030030033213003003003003001130028263210203003002914132030047303002010300152630018300300149202530030030030030020300300300183002330014300300215230030030030030030030030030023300272230030021213003003003003003003003003003002730030030030018415031152830030030029141422300300113002730030030025293330033149300300300113009300300300300303003003002113203003003003009300;y=012345600010111213141501