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的邮件量 第i辆车在k p之间运行的空车率 ikp n 邮车数量 单位距离的运行成本 1 k 单位距离单位空车率的损失 2 k 第i辆车第j次停靠是否在k支局 ijk F 支局k p之间的最短距离 kp d 模型的建立与求解 模型模型 1 邮车运输时限约束 设第i辆车最多经过m个支局进行装卸 题中给出邮车在各支局装卸邮件需 消耗5分钟 则则第i辆车在运输过程中耗费在各支局装卸邮件的时间为 1 5 60 Tm h 结合Fijk 定义可知 当且仅当Fijk 与F i j 1 q 同时为1 时表示第i 辆车 由支局k 到支局q 其余情况为不经过 1 1 i 0 ik q ijki jq k q FF 第辆车经过弧 第辆车不经过弧 已知各县级车平均行使速度为30km h 以dkq 表示第k个支局到第j个支局 的最短路距离 则第i辆车运输途中耗时为 1 1818 2 1 11130 m kq ijki kq jkq d TF Fh 第i辆车邮运过程总耗时不超过运输时限 6小时 约束可表示为 1 1 12 TT 5 60 m 1 1818 1 11130 m kq ijki kq jkq d F F 已求最少需要3辆邮车 第i辆车最多进行m次卸装 则该县邮政运输网必须 覆盖本县内所有的支局且仅覆盖一次可表示为 k 1 2 3 16 1 2 n 11 1 m ikj ij F 各邮车每次仅到一个支局装卸 要一共需要历经17个支局 若将从X1出发 时标记为1 则回到X1时应该为18 由于表示第i辆车第j次装卸邮件是否在 ikj F 第k个支局 则只要经过第k个顶点则 1 ikj F 则对于X1县邮局图中的18个顶点标记而言 第i辆车第j次仅到一个邮局可 表示为 i 1 2 3 n j 1 2 m 邮车始终点为X1 18 ijk k 1 1 F 由题中关于该区邮政运输流程的规定 县局X1将邮件处理后通过县级邮车 将邮件运往县内各支局 同时将各支局需要寄送的邮件运回X1进行同意处理后 配送 则本县级邮车行驶的始终点始终为X1 在模型准备中将X 1 看作图中编号为17 的顶点 设第i 辆车最多经过节点 数为m 则各邮车由X 1 出发并最终回到X 1 可表示为 i 1 2 n 1 5 18 18 F 1 F1 i ji m 2 邮车运载能力限制 根据问题1的要求 每辆县级邮车最多容纳65袋邮件 这里实际上限制了两 个方面 其一 每辆车在出发时装载所要运送的所有邮件量 而这些邮件需要 在沿途支局全部卸下 所以各车卸下的邮件量总数不能超过65袋 其二 邮车 在经过支局时卸下一部分邮件 同时收取一部分邮件 则在每个分局装卸完成 后 各车上所载邮件数不超过65袋 以gk表示寄达第k个支局的邮件总量 第i量车最多经过节点数为m 表 ijk F 示第i辆车第j次装卸邮件是否在第k个支局 则第i辆车在出发时装载的所要运 送的所有邮件量为 16 11 m ijkk jk F gMAX 邮车在运输途中不断的装卸邮件 以hk表示第k个支局寄出的邮件量 则经 过第k个支局时邮车上邮件数量变化量为gk hk 第i辆车在出发时及运输途中邮 件总量始终不超过邮件运载能力MAX 约束可标示为 l 1 2 m 1 3 1717 1111 ml ijkkijkkk jkik F gFhgMAX 第一目标 所需邮车数目最少 根据问题一要求 需求在满足邮运约束下 最少需要的邮车数量 所以应 以邮车数量最少为第一目标 再在最少车辆数的基础上 以由空载率损失的费 用最小为第二目标对邮路进行规划及邮车运输安排 由于双目标问题实际中不可解 而本问中研究点数较少 所以车辆数目不 会太多 这里采取将目标一转化为约束的方法求解 具体方法为 以目标二为目标进行建模编程 在模型中以n 表示所需最少 车辆数 再依次对n 赋值1 2 3 令模型可解的最小n 值即为所求最小车辆 数 第二目标 运输效益最大 由空载率损失的费用最小 在满足邮车数量最少的前提下 应尽量提高运输效益 提高运输效益的方 法为尽量降低由于空车率而减少的收入 根据题目信息 空车率的计算表达式 为 邮车最大承载的邮件量邮车运载的邮件量 空车率 邮车最大承载的邮件量 基于以上分析 以空车率而减少的收入为目标 以 1 1 1 5 为约 束 建立县邮路规划模型如下 Min Z 3m 1 18181 1818 1 1 i 1j 1 k 11111 3 2 m kpijki jqijki jqikpkp qjkq d F FF Fd 1 1818 1 111 n 11 1717 1111 18 1 5 1 1 6030 1 k1 2 3 16 1 2 l1 2m 1 3 0 1 1 4 F 1 F m kq ijki kq jkq m ikj ij ml ijkkijkkk jkik ijk i ji m d mF F F stF gFhgMAX F 8 1 15 模型模型 A A 区级邮路 区级邮路 区级邮车运输时限约束 记k 74 75 76 77 78 79 80分别为县局和起始点市局 12345 X X X X X D 终点市局D的编号 为区车数量 1 2 3 4 5 根据结果取符合运输条 1 n 1 n 件的最小值 当k 58 59 78 时 在各区支局和县局装卸邮件 设第i 辆区车最多在m个区支局和县局进行邮件装卸 在个区支局进行装卸 在 1 m 个县局进行装卸 已知邮车在各支局装卸邮件耗时5分钟 在各县局装卸邮 2 m 件耗时10分钟 则第i 辆区车在运输过程中耗费在各区支局和县局装卸邮件的 时间为 i 1 2 3 12 7378 1 158174 510 6060 mm ijkijk jkjk TFFh 1 n 已知各区级车平均行驶速度为65km h 以表示区级邮路图的k局到p局 kp d 的最短路距离 且当且仅当同时为1时表示第i 辆区车经过弧 k q 1 ijki jq F F 则第i辆区车运输途中耗时为 i 1 2 3 1 8080 2 1 15858 65 m kq ijki jq jkq k q d TFh F 1 n 区级邮路中可能包括途径的县支局 也要进行邮件装卸 令 则所需时间为 1 ik 0 ik y 区车经过县支局 否则 i 1 2 3 57 3 1 5 60 ik k Tyh 1 n 区级邮车在运输过程中耗时由在各支局 县局装卸邮件耗时及运输途中耗 时三部分构成 第i辆区车邮运过程总耗时不超过区级车运输时限 5 小时 约束 可表示为 2 1 123 5TTT 区级运输网覆盖面约束 根据该地区的邮政运输规定 区级邮政运输网必须覆盖该地市附近的16个 支局和5个县局 即对于区级邮路网络中的任一节点而言 至少有一辆邮车经过 设最少需要 量区邮车 则该区级邮政运输网必须覆盖该地市附近的16个 1 n 支局和5个县局可表示为 k 58 59 78 2 2 1 11 1 n m ijk ij F 各区级邮车每次仅到一个邮局对于区级邮路的23个节点而言 第i 辆车第j 次仅到一个邮局可表示为 2 3 80 1 58 1 2 1 1 2 1 2 ijk k in F jm mm 由于区级邮路中的县支局有且仅有一辆区车在此局进行邮件装卸 则有 k 1 2 57 2 4 1 1 10 n ik i y 或 区级邮车始 终点为市局D 由于在区级邮路图中将D抽象为始点79及终点 80 则各区级邮车由D出发并最终回到D可表示为 2 5 1 79 2 80 1 1 ii m FF 模型 A的建立 基于以上分析 以所有区级邮车总运输成本最低为目标 2 1 2 5 为约束 建立区级邮路规划模型 1 1 8080 1 115858 3 2 n m ijki jqkq ijkq k q MinF Fd 12 1 73781 808057 1 1 158174158581 11 80 1 58 5105 5 i 1 2 n 60606560 1 k 58 59 78 1 2 1 1 2 1 2 mm m kq ijkijkijki jqik jkjkjkqk k q n m ijk ij ijk k i d FFFy F in stF jm mm y F 1 1 1 79 2 80 10 k1 2 57 1 1 n k i ii m FF 或 模型模型 B B 县级邮路 县级邮路 以局为例说明 其他县局情况同 1 X 1 X 邮车运输时限约束 对于任一县 第s辆县邮车最多在m个县支局进行装卸 运输过程中耗费在所需 覆盖的区级邮车未到达的各支局装卸邮件的时间和行进时间需满足下式 161 1818 1 11111 5 1 1 6030 mm kq iksjkiksjks jq jkjkq k q d yFyFFT 县级车运输时限T的确定 由于题中仅说明第一 二班区级车的路线相同 则两班车行驶的方向分相同 不相同两种情况 下面分别分析这两种情况下的T 情况1 区级两班车行走路线方向一致 在极限情况下 为使县级车的运输总时间最大 令第一班车6 00 离开市局到 达县局运输时间为t1 第二班车最晚18 00 到达市局 令第二班车由该县局到 达市局的运输时间为t2 由于第一 二班车沿同一路线行走 另外加上邮车在 县局停留的10 分钟 得到每一班车的总时间t 即 12 10 60 ttt 由于县级车出发时在第一班车到达1小时以后 并且在第二班车离开县局时的1 小时之前返回 故县级车的最大运输时间范围满足 12 12 2 Ttt 情况2 区级两班车行走路线方向相反 为使县级车的运输总时间更大 第一班车走最短路到达县局 第二班车沿反向 走远路到达县局 此时 第一班车由市局到达县局的时间和第二班车离开县局 返回市局的时间都为t1 故此时县级车的运输时间满足 1 12 22 Tt 县级邮车始 终点为县局 1 X 由题中关于该区邮政运输流程的规定 该县级邮车从其所在县局出发将邮件 1 X 运送到其所负责的支局 并将各支局收寄的邮件运回 则该县级邮车行程的 1 X