全国第四届研究生数学建模竞赛
全国第四届研究生数学建模竞赛
题 目 邮路规划与邮车调度最优化理论研究
摘 要:
本文对小规模 NP 类邮路规划与邮车调度问题,建立了可精确求解方案的 0-1
规划模型,并在满足邮政运输需求的前提下给出了最佳方案。问题一首先以县支
局、县局为顶点构建无向赋权图,建立最短路模型,求解各局间的最短距离阵 D,
其中顶点到自己路程为 0;然后在 D 的基础上以 (第 i 条邮路第 j 次是否收发
第 k 支局邮件)为决策变量,以邮车工作时间、车辆运载能力为主要约束,建立以
总空载损失费用最小为目标的 0-1 非线性规划模型,运用规划软件 Lingo 得到最
优或次优解 59.8154 元,具体邮路规划与邮车调度见 5.2.3。问题二考虑到市邮
路成本,我们采用分层规划策略,首先以市支局、县局为顶点构建无向赋权图 ,
求解出最短路矩阵 D20,以 为决策变量,邮车工作时间为主要约束,建立以邮路
运行成本最小为目标的 0-1 非线性规划模型,求解得到最优或次优解 2×2742 元,
邮路规划与邮车调度见 6.1.3;然后,建立各县区的最短路矩阵 D21~D25,同样
建立规划模型Ⅱ(ii)可求解得到最优或次优解,其中时间约束较复杂见 6.2.1;最
后,全市总运行费用为 9549 元,全市邮路规划与邮车调度见 6.2.3。问题三由于县
局地理位置不变,对区邮路无影响,故我们以全市各县支局为中心采用逐步最优方
法对所有县区支局重新划分,得到的县分区方案见 7.2;然后构建所有新县区无
向赋权图,得到最短路矩阵 D31~D35,采用第 2 问规划模型Ⅱ(ii),得到全市总运
行费用为 9267 元,邮路规划与邮车调度见 7.3.3,结论是降低成本并不非常明显。
所以在第四问中考虑县局迁移,建立了全局选址规划模型,但模型规模较大,我们
建立近似的启发式算法完成县局选址(见 8.3),随后以 D21~D2 为最短路矩阵,运
用模型Ⅱ(ii)求解得到目标值 8997 元,邮路规划与邮车调度见 8.3 表 4.2;在此基础
上我们还考虑县局拉送邻县较近站点,同样使用模型Ⅱ(ii)对新县区划分的邮路规
划求解,得到目标值 8865 元,具体方案见表 4.4;最后还对邮路规划进一步松弛推
广与研究。
关键字: 无向赋权图 0-1 非线性规划
参赛队号 1042609 参赛学校 青岛科技大学
参赛密码
(由组委会填写)
题号 D