拉氏鬆弛演算法在多旅行者問題上之運用

Abstract

多旅行者問題為單一旅行者問題之延伸。它可應用在途程和排程的問題上，如貨物 運送路徑問題、計程車呼叫問題、校車排程問題以及電腦網路拓撲設計等。此問題 的最終目的乃是希望整個旅行成本降至最低。本論文中，發展出一個以拉氏鬆弛法 為基礎的兩段式方法來求得本問題之最佳近似解。在第一階段中，首先放鬆附屬條 件產生一個原來問題的『拉氏問題』，解此問題並因而得到原來問題之下限；接著 利用一啟發式之方法修改此拉氏問題解，如此便得到原來問題之可行解（即上限） 。我們發現，如此重覆第一階段多次後，其上限和下限的改善情形降低，但在此時 ，我們已有足夠的資訊可以知道路徑的選擇情況。故此時我們可以進入第二階段。 在第二階段中，首先藉著一個『啟發式列舉法』改進在第一階段中求得之可行解； 接著利用『分枝定界法』找尋比第一階段更好的下限及上限。實驗的測試中，設計 的城市數可達一百個而銷售旅行者數最多為十人。所有實驗結果顯示，求得的下限 和上限差距之平均值在 3﹪以內。本論文所提出的『拉氏鬆弛演算法』有以下的優 點：第一、它可應用在其他整數規劃的問題。第二、它是一種近似法同時提供一上 限及下限。第三、對於那些只想求得一好的可行解的使用者來說，可以省略第二階 段只執行第一階段，如此可加快求解的速度。