對偶陡升法求解多貨品有界網路流量問題

摘要

本文旨在探討多貨品有界網路流量問題之演算法，本研究從一組偶題可行、原題不一定可行、符合互補差餘條件之基本解，利用對偶陡升方法逐步改善原題不可行之情形，以獲得最佳解。此種演算法經證明是具備有限收斂性，計算複雜度是多項型計算型態。經利用演算法程式，測試結果顯示不論是求解單一貨品有界網路問題或是多貨品有界網路問題時，其計算速度相當有效率。

Abstract

This study deals with the development of algorithms for multicommodity network flow problems. A relaxation strategy is proposed to obtain a dual feasible, but primal not necessarily feasible solution, which satisfies the complementary slackness conditions. Dual ascent methods are used to improve the primal infeasibility and to obtain an optimal solution. The algorithm is proven to have finite convergence and to possess a polynomial-type complexity. The computational experience shows that the CPU time for running the single-commodity network flow problem is less than one second for the test problems with the arc number not exceeding 400 and the CPU time for running the multicommodity network flow problem depends on the number of commodities and the binding coupling constraints.

關鍵詞:

• 多貨品有界網路流量問題
• 對偶陡升法

Key Words:

• capacitated multicommodity network flow
• dual ascent method