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

邮政运输网络中的邮路规划和邮车调度【摘要】：此题主要以现实中邮政网络规划问题为研究对象，在研究过程中针对不同情况下的最正确邮路设计和运输效益问题，分别建立了线性规划模型，并利用matlab软件搜索求解。针对问题一，首先利用matlab元胞数组功能录入*1县的邮政信息，建立包含各支局收、寄数量和各线路行驶时间的数据库，然后在同时满足各线路运输量不超过邮车最大承载量和各线路邮车运输时间不超过规定时限的条件下，调用数据库中相关信息并利用matlab软件搜索所有符合条件的邮路，其次以使用最少邮路覆盖全县邮政网络为目标，建立关于邮路设计的线性规划模型，并利用matlab软件求解得，覆盖全县最少需规划3条邮路即最少使用3辆邮车就可满足全县运输需求，最后在满足上述求解结果的条件下结合空车率计算方法，以减少收入最低为目标建立关于邮车调度的线性规划模型，利用matlab软件搜索求解得3辆邮车的具体路线安排分别为：*1-12-13-1-3-2-5，*1-4-6-9-11-10,*1-14-15-16-8-7，此时因空车率而降低的总收入为：62.4615元。针对问题二，通过对题目的分析，首先利用贪婪算法寻找市局内可到达各县局的最近支局，并将其作为通往各县局邮路在市区内的终点和在各县局内的起点，其次在确定市区和各县局内邮路的起点和终点后，在同时满足从市局出发的各邮路可完全覆盖市局邮政网络和各邮路运行时间不超过规定时限的条件下，以邮路总运行费用最少为目标，建立线性规划模型，并利用贪婪算法逐步寻找最优解，最后解得市局需5辆邮车，各县局分别需要：2，2，0，0，2辆邮车，总路程最小为2089.1公里，此时的总费用最小为6267.4元，具体安排见模型求解。关键词：线性规化搜索求解贪婪算法1、问题重述1.1问题的来源及意义：在信息技术飞速开展的今天，互联网已经成为一种重要的通信手段，但在我们利用Email等方式交流信息的同时，邮政作为传统的通信手段仍然与我们的日常生活和工作息息相关，发挥着不可替代的作用。时限与本钱是邮政运输问题的两个重要指标。时限是指邮电部规定的、报刊处理、传递的最大时间限制，时限关系到邮政通信质量的好坏；本钱影响着企业的经营。邮政运输网络是邮政企业运营的重要保障，是决定邮政企业竞争能力的主要因素。1.2提出问题[1]以县局*1及其所辖的16个支局Z1,Z2,……,Z16为研究对象，假设区级第一班次邮车08:00到**局*1，区级第二班次邮车16:00从县局*1再出发返回地市局D，假设每辆县级邮车最多容纳65袋，试问最少需要多少辆邮车才能满足该县的运输需求？同时，为提高邮政运输效益，应如何规划邮路和如何安排邮车的运行？[2]采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入，从而显著降低全区邮政运输网的总运行本钱。考虑投入车况较好的邮车，通常每条邮路只需要一辆邮车即能满足运载能力要求，试问应如何构建该地区的邮政运输网络〔县的划分不能变更〕，请你给出邮路规划和邮车调度方案。请注意邮车的调度必须满足上文中有关该地区的邮政运输流程及时限规定。2、问题分析此题主要以现实生活中的邮路规划和邮车调度问题为研究对象，在研究过程中需考虑各支局之间是否可到达，邮车的调度是否满足题目要求和安排的邮路是否能覆盖邮政网络等因素。解决邮路规划和调度问题时需要明确以下几个方面：①邮路的形式与种类在邮政运输网络中，将各地市局、县局、支局都近似看做结点，任意两点的连线都可看做是一条路径，邮路类型主要有环形、辐射型和混合型三种，由于实际邮政运输网络中存在两个邮局间无可到达路线的情况且并非所有支局都可直**局，因此，根据邮局间直达的情况即可推算出各条邮路的线路类型。②线路搜索方法本文的关键是搜索方法的科学性，应首先寻找出所有的线路，其次，搜索同时满足每辆车的时限要求和邮车最大运载量的线路，即记录所有同时满足时限要求和最大运输量的线路，最后，根据线路是否覆盖所有支局且无重复数据得到最终的可到达线路。③不同要求下对时限的理解与计算时限指的是邮电部规定的额、报刊处理和传递的最大时间限制。在调度邮车的过程中主要考虑邮车在行驶过程中的耗时、在支局或县局的卸装时间、处理的时间。对不同区域或规定时限其计算方法是不同的。3、模型假设[1]假设邮车在行驶过程中不会存在意外的等待时间；[2]假设区级第一班次的邮车到达区级后的处理时间不予考虑；[3]假设车况较好的邮车没有最大运载量的约束；[4]假设不同邮车在不同时间到达支局或县局的卸装、分拣封发和等待时间等都是一样的；[5]假设不同县局邮车经过的支局各不一样，即一个支局只能由一辆邮车到达。4、符号系统及名词解释4.1符号说明符号及说明表示第辆车寄达支局的量表示第辆车在支局收寄的量表示邮车数目的编号第辆车的行驶时间行驶过程中的行程表示第辆车是否经过第个点表示第辆车运输的量备注为邮车的编号，其值取1，2…n;i为支局抽象为点的编号，其值取1，2…734.2名词解释[1]邮路:指利用各种运输工具按固定班期规定路线运输，并与沿线有交接频次的邮政局、所交换总包所行驶的路线，它是邮政运输网络的根本组成单元。[2]时限：指邮电部规定的、报刊处理传递的最大时间限制。[3]区级邮政运输网：从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成。[4]空车率:其计算方法为：(邮车最大承运的量-邮车运载的量)/邮车最大承运的量。5、模型的建立与求解5.1县局到支局的邮路规划和邮车调度模型准备1、行驶线路的一般表达形式和邮政运输流程如下图，A表示环形邮路，B表示辐射型邮路，在邮政运输网络中，将各地市局、县局、支局都近似看做结点，任意两点的连线都可看做是一条路径，由于实际邮政运输网络中存在两个邮局间无可到达路线的情况且并非所有支局都可直**局，因此，根据邮局间直达的情况即可推算出各条邮路的线路类型，将各种邮路的线路类型及运输流程表达如下：[1]构造线路的一般形式首先由各个邮局所在的位置抽象出点的集合，同时将邮车行走的线路表达为线路的集合，当且仅当邮局点在行驶线路上时，与间有一条边。邮局结点和组合成的线路必须满足一定的次序，即注考虑到是不同的线路。环形邮路的路线形式：设为第个县局的编号，为第个支局的编号，的以一条可用线路为例进展说明,具体线路如下：由图中可看出此时邮路的起始点和终点都是县局，且不走重复路线，这种情况下联系点较多，能大大增加运输工具的利用率，此种线路的缺点是送到最后几个结点的时间较长，时限的约束将使其到达的支局个数较少。②辐射邮路的路线形式由图示可初步判断出此种邮路的特点是从起点到终点后，仍按照原路线返回出发地点。因此须在同一条路线上往返两个行程。这种构造的邮路可以缩短运递时间，加快邮运速度。但它的联系点较少，需用的运输工具较多，所消耗用较大。混合邮路的路线形式邮车在运输的过程中，将会存在邮车经支局回到县局后继续开往支局运输的情况即混合邮路。这种情况是由于邮车由县局出发第一次运往各个支局并返回时仍然有局部空余时间，邮车再次由县局出发到附近支局运送。这一形式是辐射邮路和环形邮路的综合。[2]地区的邮政运输流程该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。运输流程如下：补充说明：图中B1、B2表示市局车辆运输的第一班次和第二班次，C1表示县局邮车的第一班次，且县局邮车有且仅有一个班次。具体流程为区级第一班次邮车从地市局D出发将运送到各县局*i和沿途支局，并将各县局*i和沿途支局收寄的运送回地市局D，各县级邮车将运送到其负责的支局并将这些支局收寄的运送回县局*i。2、确定邮车调度对时限要求在邮政运输中，时限和本钱是邮政运输问题的两个重要指标，其中，时限指的是邮电部规定的额、报刊处理和传递的最大时间限制。在调度邮车的过程中重点考虑以下几个方面的时间限制。[1]县级邮车在行驶过程中花费的时间〔简称行程时间〕：县级邮车的行程仅局限于邮车由县局出发并最终返回县局的县级邮车所行驶的全部路程，行程时间可表示为：邮车行驶单条邮路的路程可简单表示为行程，将行驶总公里数看做各行程的和，设表示邮路经过的支局编号(将第一个可到达的支局编号定位初值1，2，3…n依次表示路线中经由的支局),设表示经由的县局的次数，表示邮车数目的编号，第辆车的行驶时间为,行驶过程中的行程表示为，则此时单段距离可表示为，则行驶总公里数可表示为：县级邮车平均时速为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，反之以其直达公里里程赋权。建立表格如下：邮车运输网直达公里数赋权图*1z1z2z3z4z5z6z7z8z9z10z11z12z13z14z15z16*102744171127420002025212118270z1270312749000000052214100z2443101902732000470005000z317271901400000300003100z4114901401320002815000152530z52702701309210262600028290z642032020901303200000330z700000211301900000000z80000000190112000003321z900002826320110102000291413z10200473015260020100180014920z112500000000201802301400z122152000000000230272200z1321210000000000270000z141841503115280002914142200110z15270002529330331490001109z16000030000211320000090[4]构造线路矩阵设矩阵元素表示第个邮局到达第个邮局的线路，表示线路条数，每出现一次可到达结点记录一次，其中，当=时为无效路径，设定值为0，则：5、利用元胞数组调用可达线路由于每到达一个支局再次出发时将有多条路线可供选择，线路的选择虽然具有一定的层次关系，但每个支局可到达的点的数量各不一样，故本文采用MATLAB内建元胞构造，当元胞内队列不存在时不占用空间，元胞数组中可存储不同类型的元素和维数不一样的矩阵，具体元胞构造设计如下：元胞构造示意图[1]明确邮路的几个特点及规律从实际出发，邮车在选择线路的过程中应优先选择县局到支局的线路，而后由支局出发运送到其它支局，最终返回县局，需要明确以下几点规律：①邮车每经过一个支局都将有多种路径可供选择，且可选路线的数目是不确定的。②支局的编号并不能反映出邮车到达支局的先后顺序，即邮车有可能由支局B支局A(B的编号大于A的编号)。设表示线路编号，为间的邮路，为正整数，则将其表示为：③只需搜索每个支局能到达的所有结点即可找出所有情况。[2]构造邮车可到达线路矩阵矩阵元素表示第个有邮局到第个直达邮局的线路数，其中，=时为无效路径，设定值为0，以表示所有邮局结点的总数，则描述邮车可到达线路矩阵可表示为：6、明确选取线路的搜索方法应首先寻找出所有的线路，其次，搜索同时满足每辆车的时限要求和邮车最大运载量的线路，即记录所有同时满足时限要求和最大运输量的线路，最后，根据线路是否覆盖所有支局且无重复数据得到最终的可到达线路，具体搜索方法如下：[1]搜索所有的可到达线路邮政运输网络中存在局部邮局间不可直达的情况，将由县局到支局的线路表示为，则由县局*1出发仅Z7,Z8,Z9,Z16不可直接到**局，需经过其它支局后到**局*1,令从1开场搜索可到达线路的，此时选出的线路仅仅满足连通性。[2]搜索出同时满足时限和邮车运载能力的路线在所有可到达线路中，任意给定一条路线都将得到其形式时间和到达线路终点时邮车运载的。设为第个县局的编号，表示邮车的编号，当天处理和传递的总时间不大于时限要求，第辆邮车经过县局的卸装次数为,线路中第段距离可表示为,邮车从县局出发运往各个支局中经过的支局个数为，将时间限制表示为：为了满足每辆县级邮车最大运载量不超过65袋这一限制，同一支局寄达和收寄的存在数量差异，取每到达一个支局都记录寄达支局的量和支局收寄的量中较大的一个，设为第个县局的编号，表示邮车的编号，表示第辆车寄达支局的量，表示第辆车在支局收寄的量，表示第辆车运输的量，将每辆车运载能力的要求表示为：[3]搜索能覆盖所有网络结点的最少线路根据以上分析得到了符合邮车运载能力和时限要求的具体线路，在这些线路中仅有局部线路覆盖的支局数目较多，在其中找出经过支局最多的线路，采用“逐步逼近〞的思想进展搜索选取线路，当满足条件时停顿累加，即每条线路上经过的支局个数累加求到达最大数目16时记录线路条数，从而最终确定最少的线路(即邮车的最少数目)，设表示选择的邮车数目，每个邮车经过的支局个数为，将支局个数的限制表示为：注：的值取能满足上述条件的最小值，的取值*围为。7、引入“0—1”经过搜索得到所有同时满足时限要求和最大运输量的线路，其线路编号为，为了明确表示线路的选择，引入0—1变量表示第条路线是否被选择，值取1，2…16中的任意一个，属于无序取值。将其表示如下：8、最少邮车数量下的线路选择县级邮车一天只有一班车且行驶的线路唯一，根据逐步逼近找到了能覆盖所有网络结点的最少线路，线路的条数即是满足运输需求的最少车辆数。根据搜索出的线路形式即可规划邮路并安排邮车的行驶线路。9、空车率的求解方法为提高邮政运输效益，规划邮路和安排邮车的运行中考虑邮车的利用率，定义空车率=(邮车最大承运的量(袋)-邮车运载的量(袋))/邮车最大承运的量(袋)，单车由于空车率而减少的收入为(空车率2元/公里)。以下为求解空车率的具体方法：下表为每个支局寄达、收寄的量及每到一个支局邮车运载数目的改变量，根据其可判断出何处空车率的改变量较大：寄达局Z1Z2Z3Z4Z5Z6Z7Z8Z9Z10Z11Z12Z13Z14Z15Z16寄达Zi的量101569136114131711211211314Zi收寄的量9145109101391596713151016改变量-1-1-114-4252-8-552-632邮车到达各支局后的数量，为邮车到各支局的前一支局的数量，为邮车到达各支局后的改变量设表示线路上每相邻两邮局的段距离；为每到一个支局邮车运载数目的改变量；表示第条线路上第段距离的值；表示第条线路上在第个支局处的空车率；可将其表示为：模型的建立与求解模型一：寻找满足运载需求的最少车辆数1、模型的建立根据以上分析我们已经得到所有同时满足时限要求和最大运输量的线路，并以使用最少车辆数满足全县邮政运输需求，即使用最少线路覆盖全县邮政网络为目标，限定0—1变量的个数及取值建立0-1线性规划模型：【符号定义】：满足运输需求的总车辆数；：选取总线路的编号：第辆邮车经过县局的卸装次数；：表示线路中第段距离；：表示第条路线是否被选择；：第辆车寄达支局的量；：第辆车在支局收寄的量；：第辆邮车经过的支局个数；【模型说明】目标函数：求解满足运输需求的最少车辆数(即选择总线路的条数)；约束条件(1)：每辆邮车运输时的行驶路线均满足时限要求；约束条件(2)：每辆邮车运输时的行驶路线均满足最大运载量的要求；约束条件(3)：限定0—1变量表示第条路线是否被选择；约束条件(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辆邮车的具体路线安排分别为：*1-12-13-1-3-2-5，*1-4-6-9-11-10,*1-14-15-16-8-7，此时因空车率而降低的最少收入为：62.4615元。三辆车分别经过6、5和4+1个点的情况减少的收入*11312111043*1166.2462*1155621*1*114987*1*116三辆车分别经过6、5和5个点的情况减少的收入*112131325*162.4615*14691110*1*114151687*1三辆车分别经过6、6和4各点的情况减少的收入*110816432*174.5*11591112131*1*167514*15.2同时考虑市局和各县局时的邮路规划和邮车调度模型准备1、根本思路通过对题目的分析，首先利用贪婪算法寻找市局内可到达各县局的最近支局，并将其作为通往各县局邮路在市区内的终点和在各县局内的起点，其次在确定市区和各县局内邮路的起点和终点后，在同时满足从市局出发的各邮路可完全覆盖市局邮政网络和各邮路运行时间不超过规定时限的条件下，以邮路总运行费用最少为目标，建立线性规划模型，并利用贪婪算法逐步寻找最优解。2、引入“0—1”用表示总的邮政运输网上是否选择第段所在的路径将其表示为：3、求解目标确实定根据题意，应采用尽可能少、尽可能短的邮路以减少邮政部门车辆和人员等的投入，降低总运行本钱。因每条邮路的运行本钱为3元/公里，可将总运行本钱最低这一目标转化为求解总线路最短，根据总的最短线路里程数即可得到总运行本钱。设表示各个县的编号，其值取1~5；设表示邮政运输网上所有的可到达达路径的编号；表示到达第个县的线路上支局位于区内的点的个数；为总的邮政运输网上是否选择第段所在的路径；为第辆邮车从县局出发运往各个支局中经过的支局个数；表示市区车在县局内经过点的数目；表示由市局到达第个县的线路上第段的距离；表示第个县局邮车行驶线路中第段的距离；表示市局到进入第个县中第段的距离；求得区级邮政网络上的运输路程为和县级邮政网络上的运输路程为的表达式为：设S为总的路程，由上式得：综上所述，将这一目标表示为：4、约束条件确实定[1]约束区(县)级邮政运输网的覆盖区域根据题意，区级邮政运输网必须至少覆盖该地市附近的16个支局Z58,Z59,……,Z73和5个县局*1，……，*5。各县级邮政运输网必须覆盖本县内区级邮车不到达的支局。考虑投入车况较好的邮车，通常每条邮路只需要一辆邮车即能满足运载能力要求,将这一约束表示为：:表示到达第个县的线路上支局位于区内的点的个数；:表示到达第个县的线路上支局位于县内的点(由区局邮车满足运输需求)的个数；:第个县的县局邮车必须满足运输需求的支局数目；：第个县内所有的支局数目(包含县局本身)；[2]确定邮车调度对时限要求在调度邮车的过程中重点考虑以下几个方面的时间限制。邮车在行驶过程中花费的时间在邮路上运输花费的时间主要由两局部组成，一是在区级邮政网络上的运输时间，二是在县级邮政网络上的运输时间，应分别求出两者并求和。当邮车的时速确定时，运输时间主要与运输距离有关，设S为总的路程，前文已给出总运输公里数的表达式：县级邮车平均时速为30km/h，区级邮车平均时速为总的行程时间为：(1)邮车在支局的卸装耗时：邮车由县局向支局运输的过程中，每经过一个支局都将卸载一局部寄往此支局的，同时，装载一局部运往市区，根据时限要求，在各支局卸装耗时5分钟。设第辆车的卸装时间为，邮车从县局出发运往各个支局中经过的支局个数为，每次卸装的时间为5分钟，则：(2)邮车在各县局的卸装耗时设第辆车在县局卸装时间的卸装时间为，邮车经过县局的卸装次数为，由于在县局每次卸装的时间均为10分钟，因此，将这一时间表示为：(3)处理的时间结合题意，将处理占用的时间表示为：由于区级邮车在每个班次沿途收寄的运送到县局时需要集中处理一个小时后后再由区级邮车运往地市局。因此，根据时限规定对每辆邮车处理的耗时均为2小时。计算处理和传递的总时间综合考虑多方面的耗时，可计算得到第辆邮车在一天中处理、传递的总时间：(4)将(1)(2)(3)代入(4)得总的耗时：约束总时间(即对时限的要求)根据以上分析，综合考虑运输时间、卸装时间、处理的时间将时间约束表示为：模型的建立根据以上分析，将总运行本钱最低这一目标转化为求解总线路最短，根据总的最短线路里程数即可得到总运行本钱。约束时限和覆盖区域建立以下模型：符号说明：：表示各个县的编号，其值取1~5；：表示邮政运输网上所有的可到达达路径的编号；:表示到达第个县的线路上支局位于区内的点的个数；:表示到达第个县的线路上支局位于县内的点(由区局邮车满足运输需求)的个数；表示市区车在县局内经过点的数目；:第个县的县局邮车必须满足运输需求的支局数目；：第个县内所有的支局数目(包含县局本身)；：总的邮政运输网上是否选择第段所在的路径；：第辆车的行驶时间(一条线路对应一辆邮车，区级邮车数目为5)；：第辆邮车从县局出发运往各个支局中经过的支局个数；：第辆邮车经过县局的卸装次数；：表示由市局到达第个县的线路上第段的距离；：表示第个县局邮车行驶线路中第段的距离；：表示市局到进入第个县中第段的距离；模型说明：目标函数：邮车运输线路总公里数的最小值；约束条件(1)：约束区(县)级邮政运输网的覆盖区域；约束条件(2)：每辆邮车运输时的行驶路线均满足时限要求；约束条件(3)：限定邮车在区内的运输距离和县内的运输距离；模型求解1、算法思想——利用贪婪算法的思想逐步构造最优解邮局之间所有可能的连接可被视作一个无向图，图的每条边都被赋予一个权值，权值表示建成由这条边所表示的距离。包含图中所有顶点〔城市〕的连通子图都是一个可行解。设所有的权值都非负，则所有可能的可行解都可表示成无向图的一组生成树，而最优解是其中具有最小代价的生成树。在这个问题中，需要选择一个无向图中的边集合的子集，这个子集必须满足限制条件：所有的边构成一个生成树。而优化函数是子集中所有边的权值之和。在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策〔在一定的标准下〕。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则。2、求解结果最终求解得到的线路安排为：第一辆车，行程241.1公里，费用723.45元，用时4.7933小时D697035343230293133*32868D第二辆车，行程257公里，费用771元，用时4.954小时D724241*443403938373671D第三辆车，行程256公里，费用768元，用时4.69小时D666318*2272831646567D第四辆车，行程268公里，费用804元，用时4.9563小时D7342444651*553525861D第五辆车，行程253公里，费用760元，用时4.8小时D605962910*111151662D第六辆车，行程117公里，费用351元，用时4.4小时*1141087654*1第七辆车，行程136公里，费用408元，用时4.9497小时*13211312*1第八辆车，行程139公里，费用417元，用时5小时*22122232425*2第九辆车，行程157公里，费用471元，用时5.64小时*21719202625*2第十辆车，行程133公里，费用398元，用时4.84小时*5504948474551*5第十一辆车，行程132公里，费用396元，用时4.733小时*55455565754*5上述线路中1~5是从市局出发的五辆车，6~11为各县局总共出发的六辆车，求得总路程最短为2089.1公里，总的费用最少为：6267.4元。6、模型评价与推广此题针对现实生活中的邮路规划和邮车调度问题建立了线性规划模型，该模型针对现实生活中的种种情况给出了最优的邮车调度和邮路规划方法，实用性高是该模型的优点，但是在面对实际生活中的种种复杂情况，在程序计算中略显缺乏，搜索到所有路线情况所需时间过多，准确性纯在一定的问题，导致求出的最优解不是实际生活中的最优解。在对模型进展改良时，主要需要针对模型求解得程序进展进一步改良，增加程序搜索的细腻程度，以使程序可搜索到更多的可能组合线路，提高求解结果的准确性，在规划全县邮路线路时，需和问题一一样所有支局的收寄数才能更加准确的对邮路和邮车进展规划安排，综上所述，由于此题涉及问题实际化程度过高，需更多时间对求解程序进展调试才能求得更加准确的答案。7、附录问题一：限定时间的搜索程序*=[30027441711274230030030020252121182730027300312749300300300300300300300522141300300443130019300273230030030047300300300503003001727193001430030030030030030300300300313003001149300143001320300300281530030030015253027300273001330092130026263003003002829300423003230020930013300323003003003003003330030030030030030021133001930030030030030030030030030030030030030030030019300112030030030030033213003003003002826323001130010203003002914132030047301526300300201030018300300149202530030030030030030030030020183002330014300300215230030030030030030030030030023300272230030021213003003003003003003003003003002730030030030018415031152830030030029141422300300113002730030030025293330033149300300300113009300300300300303003003002113203003003003009300];y=[012345600010111213141501023400000001213140021030560001000014003120400000100001400410305600910000141516502040670910000141506020450709000001507000056080000000080000007091000001516900045608010110014151610023450089011001415161100000000910012014001210000000001101314001310000000000120000141234500091011120015015000456089100001401616000400089100000150];z=[10 15 6 9 13 6 11 4 13 17 11 2 11 21 13 149 14 510 910 13 9 15 9 6 7 13 15 10 16];z1=[9 14 510 910 13 9 15 9 6 7 13 15 10 16];a=cell(1,17);b=cell(1,17);d=cell(1,17);e=cell(1,17);fori=1:17m=0;forj=1:17if(*(i,j)<300)m=m+1;a{1,i}(m)=*(i,j);b{1,i}(m)=y(i,j);endendendm=0;m1=0;m3=0;m4=0;c=zeros(10000,0);k=[127761097359115531195];n1=[123456101112131415];forj=1:12z1=[914510910139 1596713 1510165];m4=0;n=n1(j)+1;z1(n)=0;fori=1:k(n)z1=[914510910139 1596713 1510165];z1(n)=0;m2=b{n}(i)+1;if(z1(m2)>0)z1(m2)=0;fori1=1:k(m2)z1=[914510910139 1596713 1510165];z1(n)=0;z1(m2)=0;m21=b{m2}(i1)+1;if(z1(m21)>0)z1(m21)=0;fori2=1:k(m21)z1=[91451091013915967131510165];z1(n)=0;z1(m2)=0;z1(m21)=0;m22=b{m21}(i2)+1;if(z1(m22)>0)z1(m22)=0;fori3=1:k(m22)z1=[91451091013915967131510165];z1(n)=0;z1(m2)=0;z1(m21)=0;z1(m22)=0;m23=b{m22}(i3)+1;if(z1(m23)>0)z1(m23)=0;fori4=1:k(m23)m24=b{m23}(i4)+1;if(z1(m24)>0)m3=0;m1=0;m=m+1;m1=m1+a{m2}(i1)/30+a{m21}(i2)/30+a{m22}(i3)/30+a{m23}(i4)/30+1/2+a{n}(i)/30+a{1}(j)/30+1/6;k1=b{1}(j);k2=b{n}(i);k3=b{m2}(i1);k4=b{m21}(i2);k5=b{m22}(i3);k6=b{m23}(i4);if(*(1,k6+1)<300)m1=m1+*(1,k4+1)/30;elsem1=2*m1-1/2-1/6;endif(z(1,k1)>z(2,k1))m3=m3+z(1,k1);elsem3=m3+z(1,k2);endif(z(1,k2)>z(2,k2))m3=m3+z(1,k2);elsem3=m3+z(2,k2);endif(z(1,k3)>z(2,k3))m3=m3+z(1,k3);elsem3=m3+z(2,k3);endif(z(1,k4)>z(2,k4))m3=m3+z(1,k4);elsem3=m3+z(2,k4);endif(z(1,k5)>z(2,k5))m3=m3+z(1,k5);elsem3=m3+z(2,k5);endif(z(1,k6)>z(2,k6))m3=m3+z(1,k6);elsem3=m3+z(2,k6);endif(m1<=6&m3<=65)m4=m4+1;d{j}(m4,1)=k1;d{j}(m4,2)=k2;d{j}(m4,3)=k3;d{j}(m4,4)=k4;d{j}(m4,5)=k5;d{j}(m4,6)=k6;d1{j}(m4,1)=m1;d1{j}(m4,2)=a{m2}(i1);d1{j}(m4,3)=a{m21}(i2);d1{j}(m4,4)=a{m22}(i3);d1{j}(m4,5)=a{m23}(i4);d1{j}(m4,6)=a{n}(i);d1{j}(m4,7)=a{1}(j);d1{j}(m4,8)=*(1,k4+1);endendendendendendendendendendendend问题一：限定运载量的搜索程序z=[10 15 6 9 13 6 11 4 13 17 11 2 11 21 13 149 14 510 910 13 9 15 9 6 7 13 15 10 16];fori=1:mforj=1:6q3(i,j)=z(1,q2(i,j));q4(i,j)=z(2,q2(i,j));endendq5=q3';q5=sum(q5);q6=q3;fori=1:mif(q5(i)>65)q6(i,:)=0;endendm1=0;fori=1:mif(q6(i,1)~=0)m1=m1+1;q7(m1,:)=q6(i,:);q8(m1,:)=q4(i,:);q9(m1,:)=q2(i,:);%支局q10(m1)=q5(i);endendfori=1:m1q11(i,1)=q10(i)-q7(i,1)+q8(i,1);q11(i,2)=q10(i)-q7(i,1)+q8(i,1)-q7(i,2)+q8(i,2);q11(i,3)=q10(i)-q7(i,1)+q8(i,1)-q7(i,2)+q8(i,2)-q7(i,3)+q8(i,3);q11(i,4)=q10(i)-q7(i,1)+q8(i,1)-q7(i,2)+q8(i,2)-q7(i,3)+q8(i,3)-q7(i,4)+q8(i,4);q11(i,5)=q10(i)-q7(i,1)+q8(i,1)-q7(i,2)+q8(i,2)-q7(i,3)+q8(i,3)-q7(i,4)+q8(i,4)-q7(i,5)+q8(i,5);q11(i,6)=q10(i)-q7(i,1)+q8(i,1)-q7(i,2)+q8(i,2)-q7(i,3)+q8(i,3)-q7(i,4)+q8(i,4)-q7(i,5)+q8(i,5)-q7(i,6)+q8(i,6);endfori=1:m1forj=1:6if(q11(i,j)>65)q11(i,:)=0;breakendendendm2=0;fori=1:m1if(q11(i,1)~=0)m2=m2+1;q12(m2,:)=q11(i,:);q13(m2,:)=q9(i,:);endend问题一：计算空车率的程序clccleara=te*tread('25.t*t');e=[0 27 44 17 11 27 42 0 0 0 20 25 21 21 18 27 027 0 31 27 49 0 0 0 0 0 0 0 52 21 41 0 044 31 0 19 0 27 32 0 0 0 47 0 0 0 50 0 017 27 19 0 14 0 0 0 0 0 30 0 0 0 31 0 011 49 0 14 0 13 20 0 0 28 15 0 0 0 15 25 3027 0 27 0 13 0 9 21 0 26 26 0 0 0 28 29 042 0 32 0 20 9 0 13 0 32 0 0 0 0 0 33 00 0 0 0 0 21 13 0 19 0 0 0 0 0 0 0 00 0 0 0 0 0 0 19 0 11 20 0 0 0 0 33 210 0 0 0 28 26 32 0 11 0 10 20 0 0 29 14 1320 0 47 30 15 26 0 0 20 10 0 18 0 0 14 9 2025 0 0 0 0 0 0 0 0 20 18 0 23 0 14 0 021 52 0 0 0 0 0 0 0 0 0 23 0 27 22 0 021 21 0 0 0 0 0 0 0 0 0 0 27 0 0 0 018 41 50 31 15 28 0 0 0 29 14 14 22 0 0 11 027 0 0 0 25 29 33 0 33 14 9 0 0 0 11 0 90 0 0 0 30 0 0 0 21 13 20 0 0 0 0 9 0];g=zeros(7200,3);r=zeros(7200,3);s=zeros(7200,3);t=zeros(7200,3);o=zeros(7200,1);q=zeros(7200,3);b2=zeros(7200,3);b3=zeros(7200,1);m=1;n=1;fori=1:7200%要改数forj=1:16ifa(i,j)==1b(i,j)=10;c(i,j)=9;endifa(i,j)==2b(i,j)=15;c(i,j)=14;endifa(i,j)==3b(i,j)=6;c(i,j)=5;endifa(i,j)==4b(i,j)=9;c(i,j)=10;endifa(i,j)==5b(i,j)=13;c(i,j)=9;endifa(i,j)==6;b(i,j)=6;c(i,j)=10;endifa(i,j)==7b(i,j)=11;c(i,j)=13;endifa(i,j)==8b(i,j)=4;c(i,j)=9;endifa(i,j)==9b(i,j)=13;c(i,j)=15;endifa(i,j)==10b(i,j)=17;c(i,j)=9;endifa(i,j)==11b(i,j)=11;c(i,j)=6;endifa(i,j)==12b(i,j)=2;c(i,j)=7;endifa(i,j)==13b(i,j)=11;c(i,j)=13;endifa(i,j)==14b(i,j)=21;c(i,j)=15;endifa(i,j)==15b(i,j)=13;c(i,j)=10;endifa(i,j)==16b(i,j)=14;c(i,j)=16;endifa(i,1)~=0d(i,1)=e(1,a(i,1)+1);endifa(i,2)~=0d(i,2)=e(a(i,1)+1,a(i,2)+1);endifa(i,3)