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

第二周培训论文摘要对小规模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,区