邮路规划和邮车调度的优化一、问题的提出本题是2007年全国研究生数学建模竞赛D题，题目如下：我国的邮政运输网络采用邮区中心局体制，即以邮区中心局作为基本封发单元和网路组织的基本节点，承担着进、出、转口邮件的处理、封发和运输任务，在此基础上组织分层次的邮政网。邮路是邮政运输网络的基本组成单元，它是指利用各种运输工具按固定班期、规定路线运输邮件，并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线。邮路的结构形式有三种：辐射形、环形和混合形。如图1所示，邮路A为一条环形邮路，邮路B为一条辐射形邮路。图1 邮路示意图1、辐射形邮路：是指从起点局出发，走直线或曲折线的邮路，其特点是不论用一种或几种运输工具联运，从起点到终点后，仍按照原路线返回出发地点。因此须在同一条路线上往返两个行程。这种邮路可以缩短运递时间，加快邮运速度。但它的联系点较少，需用的运输工具较多，所耗费用较大。2、环形邮路：是指邮政运输工具走环形路线的邮路，即运输工具从起点出发单向行驶，绕行一周，经过中途各站，回到出发地点。它的特点是不走重复路线，联系点较多，运输工具的利用率高，运费也较省。但是邮件送到最后几个交接点的时间较长。3、混合形邮路：是指包含辐射形和环形两种结构形式的邮路。某地区的邮政局、所分布如图2所示，分为地市中心局（简称地市局）、县级中心局（简称县局）和支局三级机构，该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。为使邮政企业实现低成本运营和较高的服务质量，我们需要对该地区的邮政运输网络进行重构，确定合适的邮路规划方案并进行邮车的合理调度。为了满足邮政的时限要求，必须尽可能地保证各县局、支局在营业时间内收寄的多数邮件能当天运送回地市局进行分拣封发等处理，以及每天到达地市局的多数邮件能当天运送到目的地县局、支局。该地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。该地区的邮政运输流程及时限规定如下：Step1：区级第一班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局，并将各县局Xi和沿途支局收寄的邮件运送回地市局D；区级第一班次邮车出发时间必须在06:00之后，返回地市局D时间必须在11:00之前。Step2：县局Xi将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理，按寄达支局装上相应的县级邮车；县局Xi对邮件的集中处理时间为1小时（包括邮件的卸装、分拣封发等处理时间）。Step3：各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局Xi；图2 某地区邮政局、所分布图（图中代号1至73依次代表支局Z1, Z2, , Z73）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元/km）问题2：采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入，从而显著降低全区邮政运输网的总运行成本。考虑投入车况较好的邮车，通常每条邮路只需要一辆邮车即能满足运载能力要求，试问应如何构建该地区的邮政运输网络（县的划分不能变更），请你给出邮路规划和邮车调度方案。请注意邮车的调度必须满足上文中有关该地区的邮政运输流程及时限规定。（每条邮路的运行成本为3元/km）问题3：考虑到部分县与县交界地带的支局，其邮件由邻县县局负责运送可能会降低全区的运行成本，带来可观的经济效益。若允许在一定程度上打破行政区域的限制，你能否给出更好的邮路规划和邮车调度方案？（在此同样不必考虑邮车的运载能力的限制，每条邮路的运行成本为3元/km）问题4：县局选址的合理与否对构建经济、快速的邮政运输网络起到决定性的作用。假设图2中县局X1，X5均允许迁址到本县内任一支局处，同时原来的县局弱化为普通支局。设想你是该地区网运部门负责人，请你重新为各个县局选址，陈述你的迁址理由并以书面材料形式提交省局网运处。表1：(详细信息请参照Excel文档:邮局间直达公路里程.xls) 邮局i邮局j直达公路里程（km）DZ4250DZ5954DZ6043DZ6122DZ6240DZ6351DZ6551Z72Z7313表2： 支 邮 局 件 量Z1Z2Z3Z4Z5Z6Z7Z8Z9Z10Z11Z12Z13Z14Z15Z16寄达局为Z i的邮件量（袋）101569136114131711211211314支局Z i收寄的邮件量（袋）9145109101391596713151016二、基本假设1各条路线的路况相差不大，耗费与路程成正比。2邮车保持匀速行驶。三、问题1的分析和建模准备1分析本问题以一个县（包含县局X1和16个支局）为研究对象，解决以下两个问题：(1) 在满足该县邮件运输需求的前提条件下，求出最少邮车数量；(2) 合理规划各邮车的运行路线，在确保完成邮件运输任务的条件下，使经济效益最高。以上两个问题可以分成两步来解决，第一步确定最少用多少辆邮车能够按时完成邮件运输任务，第二步对16个支局进行优化分组，使得费用最省。首先考虑最少邮车数量，由题目所给表2中的数据，寄达16个支局的邮件总数为176袋，从各支局收寄的邮件总数为170袋，每一辆邮车最多容纳65袋邮件，至少需要辆邮车，由于邮车数量n为整数，因此，即最少需要3辆邮车。如果3辆邮车在规定的时间内能够完成邮件运输任务，则3辆车就是邮车数量的最优解。假设3辆邮车可以按时完成任务，则第二步要解决的问题是，将16个支局分成3组，分别由3辆邮车包干负责邮件送达和收寄，每组（每辆邮车）的起点和终点都是县局，每个支局都必须有邮车到达，且只需一次，科学地规划邮车在本组内的行驶路线，使得总费用最小，题目所给由于空车率而减小的收入为空车率*2元/km，如果空车率变化不大，则损失与总行驶公里数成正比，而邮车的行驶费用（含耗油量、磨损折旧、维修）通常与行驶公里数成正比，所以，只要3辆邮车的总行驶里程最小，则行驶成本（费用）费用也是最小，假如16个支局已经分成了3组，各组安排一辆邮车，它在本组内的最优行驶路线相当于找出一条能够到达组内每个支局一次且只需一次，最后回到县局，行驶里程最短的路线，这个问题相当于旅行售货商(TSP)模型，但是有附加约束条件（时间约束和载重约束）。安排3辆邮车的最优行驶路线可以作为一个整体优化模型，其目标可以有以下两点考虑：(1) 3辆邮车的合计行驶里程最少；(2) 空车率损失最小。空车率与寄达各支局的邮件量以及从各支局收寄的邮件量有关，在邮车达到一个支局以后，卸下寄达该支局的邮件，装上需要寄走的邮件，空车率发生一些变化，因为邮车的负载每天有变化，所以空车率每天都不相同。县局以及各支局之间的距离是相对固定不变的，我们应当尽可能使每一辆邮车的行驶路线相对固定，避免每天重新做规划，使路线变来变去，万一某一天某个支局的邮件较多，偶尔超载几袋邮件不至于发生大问题。由此看来，两个目标函数相比较，第一目标是关键，把3辆邮车的总行驶里程最少作为首要目标，而第二目标，即空车率最小可以作为次要目标。设各辆邮车的行驶里程为，则目标函数可以写成： (1)约束条件有以下两条：(1) 时间约束按照题意，区级（地市局）邮车8:00达到县局，集中处理1小时（含邮件的卸装），县级邮车在9:00出发前往本县支局，因为区级邮车16:00从县局出发返回，县级邮车完成运输任务返回县局以后，县局还需要集中处理1小时，所以县级邮车必须在15:00之前回到县局，可以利用的时间最多为6小时，即行车时间加上装卸时间合起来不超过6小时，如果某一辆邮车的行驶里程为L，负责m个支局，则行车时间为小时（2L分钟），卸装邮件用时5m分钟，于是该邮车的时间约束可以表示为： (2)(2) 运载量约束题目规定，每一辆邮车最多装65袋邮件。假设按照行车计划，某一辆邮车去m个支局，寄达这些支局的邮件量为Pj，支局收寄的邮件量为Qj，则该邮车从县局出发时的邮件总量为，达到某个支局以后，卸下Pj袋，装上Qj袋，经过若干次卸和装，到达第n个支局以后，邮车上的邮件量变为，在达到最后一个支局后，所有寄达各支局的邮件全部卸完，从各支局收寄的邮件全部装上邮车，总装载量变为，在邮车行驶全过程中，限制运载量始终不超过65袋，于是运载量约束可以表示为： (3)由以上分析可知，问题1需要解决的问题是：先把16个支局分成3个组，一辆邮车承包一个组，负责组内各支局邮件的送达和收寄，然后规划各组最优行驶路线使目标函数最优，分组以及组内行车路线都会影响最后结果，这是一个求整体最优化的规划问题，它有明确的目标函数和约束条件，但不能把分组和组内行驶路线隔离起来，即不能孤立地分开处理成两个问题。这相当于有附加约束条件的多人旅行商问题。为了对16个支局进行科学分组并建立解决问题1的数学模型，需要做一些建模前的准备工作，例如求出16个支局和县城共17个节点中任意两个点之间的最短路、找出该公路网的最小生成树、根据两两节点之间的距离对16个支局进行聚类分析。2任意两点之间的最短路径在图论中求解最短路的较成熟的方法是Dijkstra和Floyd算法，其中Dijkstra算法适用于指定某个节点为起点，从该点出发到其它任意点的最短路，换另外起点时需要重新编程，而Floyd算法能够一次性求出任意两点之间的最短路，它是一种通过循环进行逐步比较、动态寻优的方法，可以在Matlab中用矩阵运算来解决，输入节点的距离矩阵，输出计算结果（最短路矩阵和表示最短路经过哪些节点的路径矩阵）先编写Flody算法的子程序（函数）如下：function D,R=floyd(a)n=size(