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

邮政运输网络中的邮路规划和邮车调度【摘要】：本题主要以现实中邮政网络规划问题为研究对象，在研究过程中针对不同情况下的最佳邮路设计和运输效益问题，分别建立了线性规划模型，并利用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符号说明符号及说明表示第辆车寄达支局的邮件量表示第辆车在支局收寄的邮件量表示邮车数目的编号第辆车的行驶时间行驶过程中的行程表示第辆车是否经过第个点表示第辆车运输的邮件量备注为邮车的编号，其值取1，2n;i为支局抽象为点的编号，其值取1，2734.2名词解释1 邮路:指利用各种运输工具按固定班期规定路线运输邮件，并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线，它是邮政运输网络的基本组成单元。2 时限：指邮电部规定的邮件、报刊处理传递的最大时间限制。3 区级邮政运输网：从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成。4 空车率:其计算方法为：(邮车最大承运的邮件量-邮车运载的邮件量)/邮车最大承运的邮件量。 5、模型的建立与求解5.1 县局到支局的邮路规划和邮车调度5.1.1 模型准备1、行驶线路的一般表达形式和邮政运输流程如图所示，A表示环形邮路，B表示辐射型邮路，在邮政运输网络中，将各地市局、县局、支局都近似看做结点，任意两点的连线都可看做是一条路径，由于实际邮政运输网络中存在两个邮局间无可到达路线的情况且并非所有支局都可直达县局，因此，根据邮局间直达的情况即可推算出各条邮路的线路类型，将各种邮路的线路类型及运输流程表达如下：1 构造线路的一般形式首先由各个邮局所在的位置抽象出点的集合，同时将邮车行走的线路表达为线路的集合，当且仅当邮局点在行驶线路上时，与间有一条边。邮局结点和组合成的线路必须满足一定的次序，即注考虑到是不同的线路。 环形邮路的路线形式：设为第个县局的编号，为第个支局的编号，的以一条可用线路为例进行说明,具体线路如下：由图中可看出此时邮路的起始点和终点都是县局，且不走重复路线，这种情况下联系点较多，能大大增加运输工具的利用率，此种线路的缺点是送到最后几个结点的时间较长，时限的约束将使其到达的支局个数较少。 辐射邮路的路线形式由图示可初步判断出此种邮路的特点是从起点到终点后，仍按照原路线返回出发地点。因此须在同一条路线上往返两个行程。这种结构的邮路可以缩短运递时间，加快邮运速度。但它的联系点较少，需用的运输工具较多，所耗费用较大。 混合邮路的路线形式邮车在运输邮件的过程中，将会存在邮车经支局回到县局后继续开往支局运输邮件的情况即混合邮路。这种情况是由于邮车由县局出发第一次运往各个支局并返回时仍然有部分空余时间，邮车再次由县局出发到附近支局运送邮件。这一形式是辐射邮路和环形邮路的综合。2 地区的邮政运输流程该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。运输流程如下：补充说明：图中B1、B2表示市局车辆运输的第一班次和第二班次，C1表示县局邮车的第一班次，且县局邮车有且仅有一个班次。具体流程为区级第一班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局，并将各县局Xi和沿途支局收寄的邮件运送回地市局D，各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局Xi。2、确定邮车调度对时限要求在邮政运输中，时限和成本是邮政运输问题的两个重要指标，其中，时限指的是邮电部规定的额邮件、报刊处理和传递的最大时间限制。在调度邮车的过程中重点考虑以下几个方面的时间限制。1 县级邮车在行驶过程中花费的时间（简称行程时间）：县级邮车的行程仅局限于邮车由县局出发并最终返回县局的县级邮车所行驶的全部路程，行程时间可表示为：邮车行驶单条邮路的路程可简单表示为行程，将行驶总公里数看做各行程的和，设表示邮路经过的支局编号(将第一个可到达的支局编号定位初值1，2，3n依次表示路线中经由的支局),设表示经由的县局的次数，表示邮车数目的编号，第辆车的行驶时间为,行驶过程中的行程表示为，则此时单段距离可表示为，则行驶总公里数可表示为： 县级邮车平均时速为30km/h，根据总公里数得到总的行程时间为： (1)2 邮车在支局的卸装耗时：邮车由县局向支局运输邮件的过程中，每经过一个支局都将卸载一部分寄往此支局的邮件，同时，装载一部分邮件运往市区，根据时限要求，在各支局卸装邮件耗时5分钟。设第辆车的卸装时间为，邮车从县局出发运往各个支局中经过的支局个数为，每次卸装的时间为5分钟，则： (2)3 邮车在各县局的卸装耗时邮车的行驶线路为先由区级邮车将邮件运往县级，而后到达县级的邮件将由县级邮车运往各个支局，在此过程中，由于车辆数的不确定性和邮路类型的差异，一般来说，每辆车在满足运载邮件的最大量或时限范围内时将返回县级，每辆县级邮车最多容纳65袋邮件，若仅仅是因运载邮件的数量满足最大容纳量返回县级，则在剩余时限范围内有可能再次由县局出发到达支局并返回，运载返回县级的次数是不确定的。 设第辆车在县局卸装时间的卸装时间为，邮车经过县局的卸装次数为，由于在县局每次卸装的时间均为10分钟，因此，将这一时间表示为： (3) 4 处理邮件的时间结合题意，当邮车从县局出发时，县局对邮件的集中处理时间为1小时，这一小时中包括邮件的卸装、分拣封发等处理时间。将处理邮件占用的时间表示为：当县级邮车沿途收寄的邮件运送到县局时同样需要集中处理一个小时后后再由区级邮车运往地市局。因此，根据时限规定对每辆邮车处理邮件的耗时均为2小时。5 计算邮件处理和传递的总时间 综合考虑多方面的耗时，可计算得到不同邮车在一天中处理、传递邮件的总时间： (4)将(1)(2)(3)代入(4)得总的耗时：3、限制每辆县级邮车最大容纳的邮件数量考虑到一般的邮车最多能容纳的邮件数量是一定的，对县级邮车没辆车能容纳的最多邮件数是65，根据寄达支局的邮件量和支局收寄的邮件量可求得每辆邮车在不同行驶位置运载的总邮件数。为了满足每辆县级邮车最大运载量不超过65袋邮件这一限制，同一支局寄达和收寄邮件的存在数量差异，取每到达一个支局都记录寄达支局的邮件量和支局收寄的邮件量中较大的一个，设为第个县局的编号，表示邮车的编号，表示第辆车寄达支局的邮件量，表示第辆车在支局收寄的邮件量，表示第辆车运输的邮件量，将对邮件数量的约束表示为：4、由邮路网络结构建立带权的邻接矩阵为了将邮路的网络形式用数学的语言描述出，应根据路径的特点将之看做无向图的形式，以带权的邻接矩阵的形式得到邮路的具体表现形式。1 明确矩阵的形式由线路网络结构建立带权的邻接矩阵根据地区邮政局所分布情况和邮局间直达公路里程的数据信息，令表示由所构成有向路径的权值，若不存在，则置第条邮路的第个分段的线路路程为0，为已找到从出发的的路径终点的集合，它的初始状态为空集。则第条邮路从出发到其余各顶点(终点)可到达路径的长度为：线路网路结构中各个结点间的距离代表了其权值的大小，由于任意两点间的路径是双向的，即结点和是同一线路，只是方向不同而已，因此，将之描述为无向图的形式，无向赋权图中的权矩阵其分量为：考虑无向图的邻接矩阵的对称性，采用压缩存储的方式只存入矩阵的下三角元素或上三角元素，但此时矩阵表达的实际意义难以直观表达出来，故采用一般的存储方式，根据以上定义构造带权的邻接矩阵如下：2 规律总结邻接矩阵的带权性，路径的权值体现了线路间的连通性和实际直达距离，根据任意两个点间的直达距离即可描述出线路的具体形式，根据点间的距离可计算出运输过程中的时间，同时根据可到达支局的数目得到邮车在不同时间和地点运载邮件的数目，同时考虑时限和邮车可运载邮件数量的约束进行搜索求解即可得到满足邮件运输要求的最少邮车数。邻接矩阵的对称性：将邮政运输网络中各个邮局代表的结点连线后构成无向图的形式，这种网络结构的特点决定了其矩阵的对称性。即任意两点间的路径是可顺向或反向的。3 建立表格确定矩阵中的元素根据邮局间的直达公里里程的详细信息得到任意两点间的可连通性和具体的直达距离，若两邮局(包括县局、支局)没有直达路线，则将距离赋权为0，反之以其直达公里里程赋权。建立表格如下：邮车运输网直达公里数赋权图x1z1z2z3z4z5z6z7z8z9z10z11z12z13z14z15z16x102744171127420002025212118270z1270312749000000052214100z2443101902732000470005000z317271901400000300003100z4114901401320002815000152530z52702701309210262600028290z642032020901303200000330z700000211301900000000z80000000190112000003321z900002826320110102000291413z10200473015260020100180014920z112500000000201802301400z122152000000000230272200z1321210000000000270000z141841503115280002914142200110z15270002529330331490001109z160000300002113200000904 构造线路矩阵设矩阵元素表示第个邮局到达第个邮局的线路，表示线路条数，每出现一次可到达结点记录一次，其中，当=时为无效路径，设定值为0，则：5、利用元胞数组调用可达线路由于每到达一个支局再次出发时将有多条路线可供选择，线路的选择虽然具有一定的层次关系，但每个支局可到达的点的数量各不相同，故本文采用MATLAB内建元胞结构，当元胞内队列不存在时不占用空间，元胞数组中可存储不同类型的元素和维数不相同的矩阵，具体元胞结构设计如下：元胞结构示意图1 明确邮路的几个特点及规律从实际出发，邮车在选择线路的过程中应优先选择县局到支局的线路，而后由支局出发运送邮件到其它支局，最终返回县局，需要明确以下几点规律： 邮车每经过一个支局都将有多种路径可供选择，且可选路线的数目是不确定的。 支局的编号并不能反映出邮车到达支局的先后顺序，即邮车有可能由支局B支局A(B的编号大于A的编号)。设表示线路编号， 为间的邮路，为正整数，则将其表示为： 只需搜索每个支局能到达的所有结点即可找出所有情况。2 构造邮车可到达线路矩阵矩阵元素表示第个有邮局到第个直达邮局的线路数，其中，=时为无效路径，设定值为0， 以表示所有邮局结点的总数，则描述邮车可到达线路矩阵可表示为：6、明确选取线路的搜索方法应首先寻找出所有的线路，其次，搜索同时满足每辆车的时限要求和邮车最大运载量的线路，即记录所有同时满足时限要求和最大运输量的线路，最后，根据线路是否覆盖所有支局且无重复数据得到最终的可到达线路，具体搜索方法如下：1 搜索所有的可到达线路 邮政运输网络中存在部分邮局间不可直达的情况，将由县局到支局的线路表示为，则由县局X1出发仅Z7,Z8,Z9,Z16不可直接到达县局，需经过其它支局后到达县局X1,令从1开始搜索可到达线路的，此时选出的线路仅仅满足连通性。2 搜索出同时满足时限和邮车运载能力的路线在所有可到达线路中，任意给定一条路线都将得到其形式时间和到达线路终点时邮车运载的邮件。设为第个县局的编号，表示邮车的编号，当天邮件处理和传递的总时间不大于时限要求，第辆邮车经过县局的卸装次数为,线路中第段距离可表示为,邮车从县局出发运往各个支局中经过的支局个数为，将时间限制表示为：为了满足每辆县级邮车最大运载量不超过65袋邮件这一限制，同一支局寄达和收寄邮件的存在数量差异，取每到达一个支局都记录寄达支局的邮件量和支局收寄的邮件量中较大的一个，设为第个县局的编号，表示邮车的编号，表示第辆车寄达支局的邮件量，表示第辆车在支局收寄的邮件量，表示第辆车运输的邮件量，将每辆车运载能力的要求表示为： 3 搜索能覆盖所有网络结点的最少线路根据以上分析得到了符合邮车运载能力和时限要求的具体线路，在这些线路中仅有部分线路覆盖的支局数目较多，在其中找出经过支局最多的线路，采用“逐步逼近”的思想进行搜索选取线路，当满足条件时停止累加，即每条线路上经过的支局个数累加求达到最大数目16时记录线路条数，从而最终确定最少的线路(即邮车的最少数目)，设表示选择的邮车数目，每个邮车经过的支局个数为，将支局个数的限制表示为：注：的值取能满足上述条件的最小值，的取值范围为。7、引入“01”决策变量经过搜索得到所有同时满足时限要求和最大运输量的线路，其线路编号为，为了明确表示线路的选择，引入01变量表示第条路线是否被选择，值取1，216中的任意一个，属于无序取值。将其表示如下：8、最少邮车数量下的线路选择县级邮车一天只有一班车且行驶的线路唯一，根据逐步逼近找到了能覆盖所有网络结点的最少线路，线路的条数即是满足运输需求的最少车辆数。根据搜索出的线路形式即可规划邮路并安排邮车的行驶线路。9、空车率的求解方法为提高邮政运输效益，规划邮路和安排邮车的运行中考虑邮车的利用率，定义空车率=(邮车最大承运的邮件量(袋)-邮车运载的邮件量(袋)/邮车最大承运的邮件量(袋)，单车由于空车率而减少的收入为(空车率2元/公里)。以下为求解空车率的具体方法： 下表为每个支局寄达、收寄的邮件量及每到一个支局邮车运载数目的改变量，根据其可判断出何处空车率的改变量较大：寄达局Z1Z2Z3Z4Z5Z6Z7Z8Z9Z10Z11Z12Z13Z14Z15Z16寄达Z i的邮件量101569136114131711211211314Z i收寄的邮件量9145109101391596713151016改变量-1-1-114-4252-8-552-632 邮车到达各支局后的邮件数量，为邮车到各支局的前一支局的邮件数量，为邮车到达各支局后的邮件改变量设表示线路上每相邻两邮局的段距离；为每到一个支局邮车运载数目的改变量； 表示第条线路上第段距离的值； 表示第条线路上在第个支局处的空车率；可将其表示为：5.1.2 模型的建立与求解模型一：寻找满足运载需求的最少车辆数1、模型的建立根据以上分析我们已经得到所有同时满足时限要求和最大运输量的线路，并以使用最少车辆数满足全县邮政运输需求，即使用最少线路覆盖全县邮政网络为目标，限定01变量的个数及取值建立0-1线性规划模型： 【符号定义】：满足运输需求的总车辆数； ：选取总线路的编号：第辆邮车经过县局的卸装次数； ：表示线路中第段距离；：表示第条路线是否被选择； ：第辆车寄达支局的邮件量；：第辆车在支局收寄的邮件量； ：第辆邮车经过的支局个数；【模型说明】目标函数：求解满足运输需求的最少车辆数(即选择总线路的条数)；约束条件(1)：每辆邮车运输邮件时的行驶路线均满足时限要求；约束条件(2)：每辆邮车运输邮件时的行驶路线均满足最大运载量的要求；约束条件(3)：限定01变量表示第条路线是否被选择；约束条件(4)：约束邮车数量的上下限；2、模型的求解算法步骤：使用matlab元胞数组功能，利用cell函数创建元胞，并将各支局收寄邮件数量和各支局可到达点的路线信息录入元胞数组中，从而建立关于县局邮政网络信息的数据库。调用数据库中相关信息，建立循环体对邮车路线进行准确的搜索，在满足各支局之间可到达的情况下，分别搜索一辆邮车经过6、5和4个支局时的邮路安排，并将所得邮路信息记录在所建数据库中。通过使用判断语句，首先在满足邮车运输时间不超过规定时限的条件下，对所得邮路进行筛选，记录下符合条件的邮路并结束判断，其次通过计算各支局收寄邮件的差值，得到邮车经过该支局时邮件数量的改变量，最后对符合条件的邮路，在满足经过各支局时邮车运载邮件数量均不超过邮车运载上限的条件下，使用判断语句对其再次进行筛选，最终所得结果即为满足题意的邮路并将其录入数据库。首先通过建立循环体分别对两辆邮车经过6，5、6，4和5，4个点的情况进行组合，然后通过使用判断语句去除其中含有公共点的线路，将剩余线路再次进行判断记录下能覆盖全县16个支局的线路，通过运行程序可知此时的组合无法覆盖全县。其次通过建立循环体分别对三辆邮车经过6，6，4和6，5，5个点的情况进行组合，重复上述步骤，记录下三辆车可覆盖全县的情况，通过运行程序可知此时有解，结束循环体。求解结果：最终求解得到能满足运输需求的最少车辆数为3.模型二：满足运输效益最大化下的邮路安排（重点考虑空车率）1、建立模型根据上文的分析以所有邮车由于空车率而减少的收入最少为目标，约束其取值得到以下模型: 模型说明：表示线路上每相邻两邮局的段距离；：所有邮车由于空车率而减少的收入；：第条线路上在第个支局处的空车率；：第条线路上第段距离的值；:邮车到达各支局后的邮件数量;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，此时因空车率而降低的最少收入为：62.4615元。三辆车分别经过6、5和4+1个点的情况减少的收入X11312111043X1166.2462X1155621X1X114987X1X116三辆车分别经过6、5和5个点的情况减少的收入X112131325X162.4615X14691110X1X114151687X1三辆车分别经过6、6和4各点的情况减少的收入X110816432X174.5X11591112131X1X167514X15.2 同时考虑市局和各县局时的邮路规划和邮车调度5.2.1 模型准备1、基本思路通过对题目的分析，首先利用贪婪算法寻找市局内可到达各县局的最近支局，并将其作为通往各县局邮路在市区内的终点和在各县局内的起点，其次在确定市区和各县局内邮路的起点和终点后，在同时满足从市局出发的各邮路可完全覆盖市局邮政网络和各邮路运行时间不超过规定时限的条件下，以邮路总运行费用最少为目标，建立线性规划模型，并利用贪婪算法逐步寻找最优解。2、引入“01”变量确定路径的选择用表示总的邮政运输网上是否选择第段所在的路径将其表示为：3、求解目标的确定根据题意，应采用尽可能少、尽可能短的邮路以减少邮政部门车辆和人员等的投入，降低总运行成本。因每条邮路的运行成本为3元/公里，可将总运行成本最低这一目标转化为求解总线路最短，根据总的最短线路里程数即可得到总运行成本。设表示各个县的编号，其值取15；设表示邮政运输网上所有的可到达达路径的编号；表示到达第个县的线路上支局位于区内的点的个数；为总的邮政运输网上是否选择第段所在的路径；为第辆邮车从县局出发运往各个支局中经过的支局个数；表示市区车在县局内经过点的数目；表示由市局到达第个县的线路上第段的距离；表示第个县局邮车行驶线路中第段的距离；表示市局到进入第个县中第段的距离；求得区级邮政网络上的运输路程为和县级邮政网络上的运输路程为的表达式为：设S为总的路程，由上式得： 综上所述，将这一目标表示为：4、约束条件的确定1 约束区(县)级邮政运输网的覆盖区域根据题意，区级邮政运输网必须至少覆盖该地市附近的16个支局Z58, Z59, , Z73和5个县局X1，X5。各县级邮政运输网必须覆盖本县内区级邮车不到达的支局。考虑投入车况较好的邮车，通常每条邮路只需要一辆邮车即能满足运载能力要求, 将这一约束表示为：:表示到达第个县的线路上支局位于区内的点的个数；:表示到达第个县的线路上支局位于县内的点(由区局邮车满足运输需求)的个数；:第个县的县局邮车必须满足运输需求的支局数目；：第个县内所有的支局数目(包含县局本身)；2 确定邮车调度对时限要求在调度邮车的过程中重点考虑以下几个方面的时间限制。 邮车在行驶过程中花费的时间在邮路上运输花费的时间主要由两部分组成，一是在区级邮政网络上的运输时间，二是在县级邮政网络上的运输时间，应分别求出两者并求和。当邮车的时速确定时，运输时间主要与运输距离有关，设S为总的路程，前文已给出总运输公里数的表达式： 县级邮车平均时速为30km/h，区级邮车平均时速为65km/h，根据总公里数得到总的行程时间为： (1) 邮车在支局的卸装耗时：邮车由县局向支局运输邮件的过程中，每经过一个支局都将卸载一部分寄往此支局的邮件，同时，装载一部分邮件运往市区，根据时限要求，在各支局卸装邮件耗时5分钟。设第辆车的卸装时间为，邮车从县局出发运往各个支局中经过的支局个数为，每次卸装的时间为5分钟，则： (2) 邮车在各县局的卸装耗时设第辆车在县局卸装时间的卸装时间为，邮车经过县局的卸装次数为，由于在县局每次卸装的时间均为10分钟，因此，将这一时间表示为： (3) 处理邮件的时间结合题意，将处理邮件占用的时间表示为：由于区级邮车在每个班次沿途收寄的邮件运送到县局时需要集中处理一个小时后后再由区级邮车运往地市局。因此，根据时限规定对每辆邮车处理邮件的耗时均为2小时。 计算邮件处理和传递的总时间 综合考虑多方面的耗时，可计算得到第辆邮车在一天中处理、传递邮件的总时间： (4)将(1)(2)(3)代入(4)得总的耗时： 约束总时间(即对时限的要求)根据以上分析，综合考虑运输时间、卸装时间、处理邮件的时间将时间约束表示为：5.2.2 模型的建立根据以上分析，将总运行成本最低这一目标转化为求解总线路最短，根据总的最短线路里程数即可得到总运行成本。约束时限和覆盖区域建立以下模型：符号说明：表示各个县的编号，其值取15；：表示邮政运输网上所有的可到达达路径的编号；:表示到达第个县的线路上支局位于区内的点的个数；:表示到达第个县的线路上支局位于县内的点(由区局邮车满足运输需求)的个数；表示市区车在县局内经过点的数目；:第个县的县局邮车必须满足运输需求的支局数目；：第个县内所有的支局数目(包含县局本身)；：总的邮政运输网上是否选择第段所在的路径；：第辆车的行驶时间(一条线路对应一辆邮车，区级邮车数目为5)；：第辆邮车从县局出发运往各个支局中经过的支局个数；：第辆邮车经过县局的卸装次数；：表示由市局到达第个县的线路上第段的距离； ：表示第个县局邮车行驶线路中第段的距离；：表示市局到进入第个县中第段的距离；模型说明：目标函数：邮车运输线路总公里数的最小值；约束条件(1)：约束区(县)级邮政运输网的覆盖区域；约束条件(2)：每辆邮车运输邮件时的行驶路线均满足时限要求；约束条件(3)：限定邮车在区内的运输距离和县内的运输距离； 5.2.3模型求解1、算法思想利用贪婪算法的思想逐步构造最优解邮局之间所有可能的连接可被视作一个无向图，图的每条边都被赋予一个权值，权值表示建成由这条边所表示的距离。包含图中所有顶点（城市）的连通子图都是一个可行解。设所有的权值都非负，则所有可能的可行解都可表示成无向图的一组生成树，而最优解是其中具有最小代价的生成树。在这个问题中，需要选择一个无向图中的边集合的子集，这个子集必须满足限制条件：所有的边构成一个生成树。而优化函数是子集中所有边的权值之和。在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则。2、求解结果最终求解得到的线路安排为：第一辆车，行程241.1公里，费用723.45元，用时4.7933小时D697035343230293133X32868D第二辆车，行程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第七辆车，行程136公里，费用408元，用时4.9497小时X13211312X1第八辆车，行程139公里，费用417元，用时5小时X22122232425X2第九辆车，行程157公里，费用471元，用时5.64小时X21719202625X2第十辆车，行程133公里，费用398元，用时4.84小时X5504948474551X5第十一辆车，行程132公里，费用396元，用时4.733小时X55455565754X5上述线路中15是从市局出发的五辆车，611为各县局总共出发的六辆车，求得总路程最短为2089.1公里，总的费用最少为：6267.4元。6、模型评价与推广本题针对现实生活中的邮路规划和邮车调度问题建立了线性规划模型，该模型针对现实生活中的种种情况给出了最优的邮车调度和邮路规划方法，实用性高是该模型的优点，但是在面对实际生活中的种种复杂情况，在程序计算中略显不足，搜索到所有路线情况所需时间过多，准确性纯在一定的问题，导致求出的最优解不是实际生活中的最优解。在对模型进行改进时，主要需要针对模型求解得程序进行进一步改进，增加程序搜索的细腻程度，以使程序可搜索到更多的可能组合线路，提高求解结果的准确性，在规划全县邮路线路时，需和问题一一样已知所有支局的收寄邮件数才能更加准确的对邮路和邮车进行规划安排，综上所述，由于本题涉及问题实际化程度过高，需更多时间对求解程序进行调试才能求得更加准确的答案。7、附录问题一：限定时间的搜索程序x=300 27 44 17 11 27 42 300 300 300 20 25 21 21 18 27 300 27 300 31 27 49 300 300 300 300 300 300 300 52 21 41 300 300 44 31 300 19 300 27 32 300 300 300 47 300 300 300 50 300 300 17 27 19 300 14 300 300 300 300 300 30 300 300 300 31 300 300 11 49 300 14 300 13 20 300 300 28 15 300 300 300 15 25 30 27 300 27 300 13 300 9 21 300 26 26 300 300 300 28 29 300 42 300 32 300 20 9 300 13 300 32 300 300 300 300 300 33 300 300 300 300 300 300 21 13 300 19 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 19 300 11 20 300 300 300 300 33 21 300 300 300 300 28 26 32 300 11 300 10 20 300 300 29 14 13 20 300 47 30 15 26 300 300 20 10 300 18 300 300 14 9 20 25 300 300 300 300 300 300 300 300 20 18 300 23 300 14 300 300 21 52 300 300 300 300 300 300 300 300 300 23 300 27 22 300 300 21 21 300 300 300 300 300 300 300 300 3