论文部分内容阅读
本文提出了一类新的时变网络优化问题—时间依赖网络中国邮路问题。时间依赖特性使得该问题变得十分困难,传统理论在时间依赖网络中不再适用。因此本文围绕时间依赖网络中国邮路问题的计算复杂性、整数规划模型和算法等方面开展研究,具体说来,分为一下三个方面:(1)从计算复杂性、传统算法适用性以及最优解性质三个层面对时间依赖网络中国邮路问题的性质进行分析:①证明了即使在时间依赖网络满足欧拉性质和先进先出性质的条件下,时间依赖网络中国邮路问题依然是NP-困难问题;②证明了传统中国邮路中的经典算法—二阶段算法和弧路由转换算法均不适用于时间依赖网络,为修正和改良已有算法提供了理论依据;③提出了先进先出网络中国邮路问题的两个最优解性质,并将最优解性质应用于精确算法的支配条件和递推方程的设计。(2)从整数线性规划模型、多面体分析两方面入手研究了时间依赖网络中国邮路问题的数学规划方法:①建立了时间依赖网络中国(乡村)邮路问题的圈变量、交错圈变量、弧变量以及弧-路径变量等四类整数线性规划模型:②基于圈变量和弧-路径变量整数规划模型进行了多面体分析,证明了多面体的维数和极大诱导不等式,并给出了两类时间相关强有效不等式,将这些不等式作为割平面动态添加到算法中,能够有效提高问题最优解下界。(3)提出时间依赖网络中国邮路问题的三类算法:①提出了先进先出网络中国邮路问题的分支限界算法和动态规划算法;②基于圈变量模型和弧-路径变量模型的多面体分析,提出了时间依赖网络中国(乡村)邮路问题的割平面算法;③基于时间自动机,给出三类时变中国邮路问题:时间窗中国邮路、时间依赖旅行时间中国邮路、时间依赖服务代价中国邮路的统一求解框架。