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

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

本研究利用時窗分割與整數化策略將時窗收卸貨問題（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%.