07年数学建模]邮政运输网络中的邮路规划和邮车调度

邮政运输网络中的邮路规划和邮车调度第二周培训论文摘要对小规模TSP问题，建立了可精确求解方案的0-1规划模型，并在满足邮政运输需求的前提下给出了最佳方案。问题一首先以县支局、县局为顶点构建无向赋权图，通过Floyd算法求解各局间的最短距离；然后以Fijk为决策变量，以邮车工作时间、车辆运载能力为主要约束，以总空载损失费用最小为目标0-1非线性规划模型，运用规划软件Lingo求解。问题二考虑到市邮路成本,我们采用分层规划策略,首先以市支局、县局为顶点构建无向赋权图,求解出最短路矩阵,建立以邮路运行成本最小为目标，邮车工作时间为约束条件的0-1非线性规划模型求解;然后,建立各县区的最短路矩阵,同样建立0-1非线性规划规划模型求解各县运输方案。关键词：无向赋权图Floyd算法0—1非线性规划问题重述我国的邮政运输网络采用邮区中心局体制，即以邮区中心局作为基本封发单元和网路组织的基本节点，承担着进、出、转口邮件的处理、封发和运输任务，在此基础上组织分层次的邮政网。邮路是邮政运输网络的基本组成单元，它是指利用各种运输工具按固定班期、规定路线运输邮件，并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线。邮路的结构形式有三种：辐射形、环形和混合形。某地区的邮政局分为地市中心局（简称地市局）、县级中心局（简称县局）和支局三级机构，该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。为使邮政企业实现低成本运营和较高的服务质量，我们需要对该地区的邮政运输网络进行重构，确定合适的邮路规划方案并进行邮车的合理调度。为了满足邮政的时限要求，必须尽可能地保证各县局、支局在营业时间内收寄的多数邮件能当天运送回地市局进行分拣封发等处理，以及每天到达地市局的多数邮件能当天运送到目的地县局、支局。该地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。该地区的邮政运输流程及时限规定如下：Step1:区级第一班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局，并将各县局Xi和沿途支局收寄的邮件运送回地市局D；区级第一班次邮车出发时间必须在06:00之后，返回地市局D时间必须在11:00之前。Step2:县局Xi将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理，按寄达支局装上相应的县级邮车；县局Xi对邮件的集中处理时间为1小时（包括邮件的卸装、分拣封发等处理时间）。Step3:各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局Xi；Step4:区级第二班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局，并将各县局Xi收寄的邮件（包括当日各县级邮车运回县局Xi的邮件）和沿途支局收寄的邮件运送回地市局D；请注意区级第二班次邮车在县局Xi卸装完邮件后的出发时间必须在县局Xi的全部县级邮车返回县局并集中处理1小时以后，最终返回地市局D的时间必须在18:00之前。假设区级两个班次邮车的行驶路线相同，要求区级邮政运输网必须至少覆盖该地市附近的16个支局Z58,Z59,……,Z73和5个县局X1，……，X5。各县级邮政运输网必须覆盖本县内区级邮车不到达的支局。该地区邮局间公路网分布见表1，并且县级邮车平均时速为30km/h，区级邮车的平均时速为65km/h，邮车在各支局卸装邮件耗时5分钟，在各县局卸装邮件耗时10分钟。问题1：以县局X1及其所辖的16个支局Z1,Z2,……,Z16为研究对象，假设区级第一班次邮车08:00到达县局X1，区级第二班次邮车16:00从县局X1再出发返回地市局D，若每辆县级邮车最多容纳65袋邮件，试问最少需要多少辆邮车才能满足该县的邮件运输需求？同时，为提高邮政运输效益，应如何规划邮路和如何安排邮车的运行？（邮件量见表2，空车率=(邮车最大承运的邮件量(袋)-邮车运载的邮件量(袋))/邮车最大承运的邮件量(袋)，单车由于空车率而减少的收入为（空车率*2元/公里））问题2：采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入，从而显著降低全区邮政运输网的总运行成本。考虑投入车况较好的邮车，通常每条邮路只需要一辆邮车即能满足运载能力要求，试问应如何构建该地区的邮政运输网络（县的划分不能变更），请你给出邮路规划和邮车调度方案。请注意邮车的调度必须满足上文中有关该地区的邮政运输流程及时限规定。（每条邮路的运行成本为3元/公里）问题分析对于问题一，由于题中仅提供了两支局间直达距离，但这不一定是最短距离。因此，首先需要利用Floyd算法把各支局间的最短路径矩阵D求出。估计最少三辆车可以完成任务，因为县局开出去的车总共要带上176袋邮件，而每辆车最多承载65袋邮件，故最少需要【176／65】=3辆车。而在求解如何规划邮路和如何安排邮车的运行的问题中，我们综合考虑了邮车运输时限约束，邮车运载能力限制，该区邮政运输流程的规定等因素，建立了一系列的约束条件，而以所需邮车数目最少和运输效益最大(由空载率损失的费用最小)分别为目标函数，由于双目标问题实际中不可解,而本问中研究点数较少,所以车辆数目不多,这里采取将目标一转化为约束的方法求解。对于问题二，要规划该地区的邮政运输网络，采用尽可能少，尽可能短的邮路可以减少邮政部门车辆和人员等的投入。我们将区级邮路和县级邮路分别进行了规划，在模型建立过程中，我们以总路程最小为目标函数，以邮车运输时限约束，区级邮政运输网必须覆盖该地市附近的16个支局和5个县局，而县级邮政运输网必须覆盖自己所在县的所有支局，建立非线性规划模型求解。基本假设1.假设一辆邮车仅负责一条邮路。2.假设一个邮局的邮件仅由一辆邮车运送。3.假设所有邮车均按平均时速匀速行使。4.所有的邮路均可按环形，辐射性或者混合型来行使。5.区级两个班次邮车的行驶路线相同，但方向可以不同。6.每条邮路只需要一辆邮车即能满足运载能力要求，且车辆不存在超载现象。7.若区车在由市支局驶向县局时途径县支局则在该县支局进行邮件交换。符号说明MAX：县级邮车最多邮件的容纳量；hk：支局k收寄的邮件量；gk：寄达支局k的邮件量；ikp：第i辆车在k、p之间运行的空车率；n：邮车数量；1k：单位距离的运行成本2k：单位距离单位空车率的损失；ijkF：第i辆车第j次停靠是否在k支局；kpd：支局k、p之间的最短距离。模型的建立与求解模型Ⅰ1、邮车运输时限约束设第i辆车最多经过m个支局进行装卸，题中给出邮车在各支局装卸邮件需消耗5分钟，则则第i辆车在运输过程中耗费在各支局装卸邮件的时间为：1560Tmh结合Fijk定义可知,当且仅当Fijk与Fi,j+1,q同时为1时表示第i辆车由支局k到支局q,其余情况为不经过,1,1i,*0ik,qijkijqkqFF第辆车经过弧第辆车不经过弧已知各县级车平均行使速度为30km/h，以dkq表示第k个支局到第j个支局的最短路距离,则第i辆车运输途中耗时为:118182,1,11130mkqijkikqjkqdTFFh第i辆车邮运过程总耗时不超过运输时限（6小时）约束可表示为：12TT=560m+11818,1,11130mkqijkikqjkqdFF(1.1)已求最少需要3辆邮车，第i辆车最多进行m次卸装，则该县邮政运输网必须覆盖本县内所有的支局且仅覆盖一次可表示为：n111mikjijF(k=1,2,3……,16)（1.2）各邮车每次仅到一个支局装卸。要一共需要历经17个支局，若将从X1出发时标记为1，则回到X1时应该为18，由于ikjF表示第i辆车第j次装卸邮件是否在第k个支局，则只要经过第k个顶点则ikjF=1。则对于X1县邮局图中的18个顶点标记而言，第i辆车第j次仅到一个邮局可表示为：18ijkk=11F（i=1，2，3，……n；j=1，2，……，m）邮车始终点为X1由题中关于该区邮政运输流程的规定，县局X1将邮件处理后通过县级邮车将邮件运往县内各支局，同时将各支局需要寄送的邮件运回X1进行同意处理后配送，则本县级邮车行驶的始终点始终为X1。在模型准备中将X1看作图中编号为17的顶点,设第i辆车最多经过节点数为m,则各邮车由X1出发并最终回到X1可表示为:,,18,,18F=1,F1ijim（i=1，2，……n）（1.5）2、邮车运载能力限制根据问题1的要求，每辆县级邮车最多容纳65袋邮件，这里实际上限制了两个方面：其一，每辆车在出发时装载所要运送的所有邮件量，而这些邮件需要在沿途支局全部卸下，所以各车卸下的邮件量总数不能超过65袋；其二，邮车在经过支局时卸下一部分邮件，同时收取一部分邮件，则在每个分局装卸完成后，各车上所载邮件数不超过65袋。以gk表示寄达第k个支局的邮件总量，第i量车最多经过节点数为m，ijkF表示第i辆车第j次装卸邮件是否在第k个支局，则第i辆车在出发时装载的所要运送的所有邮件量为：1611mijkkjkFgMAX邮车在运输途中不断的装卸邮件，以hk表示第k个支局寄出的邮件量，则经过第k个支局时邮车上邮件数量变化量为gk-hk，第i辆车在出发时及运输途中邮件总量始终不超过邮件运载能力MAX，约束可标示为17171111mlijkkijkkkjkikFgFhgMAX（l=1，2，……，m）（1.3）第一目标:所需邮车数目最少根据问题一要求,需求在满足邮运约束下,最少需要的邮车数量.所以应以邮车数量最少为第一目标,再在最少车辆数的基础上,以由空载率损失的费用最小为第二目标对邮路进行规划及邮车运输安排.由于双目标问题实际中不可解,而本问中研究点数较少,所以车辆数目不会太多,这里采取将目标一转化为约束的方法求解.具体方法为:以目标二为目标进行建模编程,在模型中以n表示所需最少车辆数,再依次对n赋值1,2,3,⋯令模型可解的最小n值即为所求最小车辆数.第二目标:运输效益最大(由空载率损失的费用最小)在满足邮车数量最少的前提下,应尽量提高运输效益.提高运输效益的方法为尽量降低由于空车率而减少的收入,根据题目信息,空车率的计算表达式为:-=邮车最大承载的邮件量邮车运载的邮件量空车率邮车最大承载的邮件量基于以上分析，以空车率而减少的收入为目标，以（1.1）～（1.5）为约束，建立县邮路规划模型如下：MinZ=3m+1181811818,1,,1,i=1j=1k11111*3*2)mkpijkijqijkijqikpkpqjkqdFFFFd（11818,1,111n1117171111,,18,,15(1.1)60301(k1,2,3,16)(1.2)l12m(1.3)0,1(1.4)F=1,FmkqijkikqjkqmikjijmlijkkijkkkjkikijkijimdmFFFstFgFhgMAXF（，，，）81.（15）模型Ⅱ-A（区级邮路）区级邮车运输时限约束记k=74,75,76,77，78,79，80分别为县局12345X,X,X,X,X和起始点市局D，终点市局D的编号，1n为区车数量（1n=1,2,3,4,5，根据结果取符合运输条件的最小值）。当k=58,59，⋯,78时，在各区支局和县局装卸邮件,设第i辆区车最多在m个区支局和县局进行邮件装卸，在1m个区支局进行装卸，在2m个县局进行装卸。已知邮车在各支局装卸邮件耗时5分钟,在各县局装卸邮件耗时10分钟，则第i辆区车在运输过程中耗费在各区支局和县局装卸邮件的时间为:1273781158174510()6060mmijkijkjkjkTFFhi=1,2,3…1n已知各区级车平均行驶速度为65km/h,以kpd表示区级邮路图的k局到p局的最短路距离,且当且仅当,,1,ij