應用時窗分割與整數化策略簡化時窗收卸貨問題之研究

Applying Time Window Partitioning and Discretization Strategy to Simplify PDPTW into SPDP

李泰琳(Tai-Lin Li) ； 張靖(Ching Chang)

《運輸學刊》 20卷3期 (2008/09) Pp. 313-350

https://doi.org/10.6383/JCIT.200809.0313

摘要

本研究利用時窗分割與整數化策略將時窗收卸貨問題(PDPTW)轉換為無時窗的近似PDP (SPDP)，即得以求解PDPTW時不用考慮時窗。在轉換過程中進一步提出問題規模精簡策略與關連式旅行網路結構表，大量減少轉換過程中所衍生出新的限制式與決策變數的數量。研究中利用Lau and Liang (2002)的方法，修改國際標準題庫VRPTW 例題，產生具有相同最適解之PDPTW例題進行測試。本研究首先提出SPDP之數學規劃模式，利用小規模例題，透過LINGO來驗證，當時窗切割夠細的話，轉換所得之SPDP與原PDPTW之最適解是相同的，即求解時窗切割夠細的SPDP即可求得原PDPTW之最適解；其次利用較大規模問題，透過啟發式演算法來驗證，顯示求解SPDP較直接求解原PDPTW，其解的精確度平均提升7.88%，求解時間大幅減少達88.10%，因此本研究確定先將PDPTW轉換為SPDP求解較直接求解PDPTW，確實可以在較短的時間內求出品質較佳的近似最佳解。

關鍵字

時窗收卸貨問題 ； 時窗分割策略 ； 巨集啟發式演算法

並列摘要

The goal of this paper is to provide a new concept to solve a Pickup and Delivery Problem with Time Windows (PDPTW) efficiently and accurately. In order to achieve this goal, a PDPTW is transferred into a new Similar PDP (SPDP) without time window by adopting the Time Window Partitioning and Discretization Strategy. Every time window of each pickup or delivery point is partitioned as many equal-length sub time windows. Besides, only one of all sub time windows of the pickup or delivery point can be served. The SPDP is formulated as a 0-1 integer programming model in this paper. The optimal solution obtained by LINGO of the transferred SPDP is equal to the optimal solution of the original PDPTW when the time window is partitioned small enough, i.e. the SPDP is the same as PDPTW when the length of the sub time window is short enough. However, the size of the transferred SPDP is much bigger than the original PDPTW because a lot of new decision variables and constraints are produced. Since these additional derived decision variables and constraints make computation inefficient, we also design a preprocessing procedure to reduce problem size of the SPDP, e.g. the redundant decision variables and constraints, and a relation structured asymmetric travel cost matrix to avoid searching the infeasible solutions. There are 18 Solomon benchmark VRP problems transferred to PDPTW by using the method developed by Lau and Liang (2002). In order to show our contribution, we developed a simple Meta-Heuristic algorithm to solve both PDPTW and SPDP. According to the computation results, we can improve the accuracy by about 7.88% and save the computation time by about 88.1%.

並列關鍵字

Pickup and delivery problem with time windows ； Time window partitioning strategy ； Meta-heuristic algorithm

參考文獻

楊智凱(1995)。以門檻接受法改善TSP與VRP路網成本之研究(碩士論文)。交通大學土木研究所運工管組。

劉佩玲(2006)。在考量資源限制下國際快遞業服務中心位置選擇(碩士論文)。高雄第一科技大學運籌管理研究所。

韓復華、王國琛()。

韓復華、王國琛(2002)。巨集啟發式解法在求解大規模旅行推銷員問題之應用。運輸學刊。14(2)，1-14。

韓復華、楊智凱(1996)。門檻接受法在TSP 問題上之應用。運輸計劃季刊。25(2)，163-188。