有時窗限制的收送貨問題之研究

Abstract

對於貨運業者來說，有效率且有效的車輛派遣有許多優點。首先，有效率的車輛派遣可以減少派遣所需的時間，使得人力資源可以有更充分的利用；而縮減車輛的旅行距離可以減少車輛的維修成本；另外，貨運業者可以因為較好的車輛利用率而去服務更多的顧客以增加利潤。因此，發展一個最佳化模式來協助貨運業者進行車輛派遣的決策是相當重要的。 本研究針對有時窗限制的收送貨問題構建了數學規劃的模式，並且針對非線性的時窗限制式做放鬆與緊縮，使得模式成為兩個線性的混合整數規劃(MIP)模型。放鬆時窗限制式使我們得到一個最佳解的下界，而緊縮時窗限制式可得到最佳解的上界(亦為一可行解)，由於兩種模式都為線性規劃，因此可利用一般的數學規劃解題軟體來分別求解以得到上下界。另外，本研究亦使用切割時窗(Time Window Partitioning)的方式來縮減上界與下界之間的差距，當兩者收斂至重合時，代表已經獲得最佳解，然而切割時窗雖然會減小上下界的差距，也會增加問題的規模，因此使用切割時窗法必須在解的品質與求解時間當中做取捨。 本研究利用一個自行設計的小範例來驗證模式的正確性與合理性。此外，由於在文獻上並沒有發現適合本研究的標竿題庫，因此本研究擷取Solomon於1987年針對有時窗限制的車輛路線問題(VRPTW)所設計的題庫，做部分的修正來產生所需的測試範例，以用來觀察使用不同的切割時窗寬度時，問題規模成長以及上下界收斂的情形。測試結果顯示本研究的模式及所使用的求解方法適用於求解此問題。

It is important for cargo carriers to dispatch their vehicles efficiently and effectively. There are several advantages for efficient and effective dispatches. First, shortening the dispatching time could save the personnel expenses and make better human resources utilization. Secondly, shortening the travel distance of vehicles can reduce the operation and maintenance costs of vehicles. Moreover, the cargo carrier could serve more customers and increase their revenues due to higher utilization rate. Therefore, it is important to develop optimization models and algorithms for such decision making. We construct an optimization model for pickup and delivery problem with time windows in this research. This model is based on the dispatching rule, and takes current operation status into account. We apply the over-constrained and under-constrained method to deal with the nonlinear time window constraint. The over-constrained method offer an upper bound (a feasible solution) while the under-constrained method provides a lower bound for the solution. In order to approximate the optimal solution, we use the time window partitioning method to narrow the gap between the upper bound and lower bound. In addition, we use a small example to verify the accuracy and rationality of our model. We also generate our test instances from Solomon’s benchmark test samples for VRPTW to evaluate our solving method. The testing results show that our proposed model and solution techniques are suitable for solving this problem.