替代對偶鬆弛法應用於貨物載運規劃問題之研究

The Surrogate Duality Relaxation for Load Planning Problem

貨物載運規劃問題(Loading Planning)其目的在派遣適當的貨櫃，選擇最佳的配送路線滿足學業所起迄點對的需求，以期總學運成本為最低;對公路貨運中之零擔貨運業者而言，為其在實務上之重要課題。本文針對此問題以整體最佳化為考量，構建一線性整數規劃模式，在求解演算法方面，提出以替代鬆施法(Surrogate Relaxation Method)為架構的求解演算法，本研究以一國內路線貨運公司構建軸幅式貨物營運網路為測試個案，由測試個案結果顯示，CPU的使用時間，相較於拉氏鬆施法減少了近112電腦CPU使用時間，可行解目標值皆可收傲，且所得到之可行解與最佳解間距極小。因此，值得進一步探討其應用於大型實際學運路網之可行性，期能俾益於貨運業之實務工作。

The loading planning problem for freight common carrier is to simultaneously determine freight routes for all O-D pairs and a balanced trailer movements to minimize the total operating cost. It is one of the important operational issues for freight common carriers. Decomposition and Lagrangian relaxation are two most1y common used algorithms for this type of integer programming problems. However, studies ~how the surrogate duality relaxation provides a better bound than the Lagrangian relaxation for integer programming in various subjects: In this research we develop and implement a surrogate duality relaxation algorithms for loading planning problem:. We use two Sub-networks of one of the top three common carrier's operatiop.s networks in Taiwan to evaluate the performance of the algorithms. The computational results with this Algorithms are encouraging. It only one-half of computational times ofthe Lagrangian relaxation method, but produces a better local optimum. Overall, the research demonstrates a potential of applying this approach to large carrier' s logistical system design.