时间依赖无向中国邮路问题的分支限界算法 (2011年)

【文件属性】：
文件名称：时间依赖无向中国邮路问题的分支限界算法 (2011年)
文件大小：363KB
文件格式：PDF
更新时间：2024-06-10 22:06:15
工程技术 论文 时间依赖网络相比传统网络模型有更广泛的应用领域，比如公交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时，中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法，如奇偶图上作业法和Edmonds＆Johnson算法，以及不能有效求解时间依赖中国邮路问题的根本原因；其次给出了一般时变无向中国邮路问题的特性，并在此基础上设计了该问题的分支限界最优化算法；然后针对FIFO（First In First Out）这一类特殊时变网络，设计了新的剪枝条件，从而得到