解決具時間窗限制的提送貨問題

Abstract

本研究將探討具時間窗限制的提送貨問題(Pickup and Delivery Problem with Time Windows Constraints, PDPTW)，目的為針對PDPTW問題建構一數學模式而後求解。首先將PDPTW問題建構為集合分割(Set Partition)的整數規劃問題，在考慮貨運需求點、優先限制(Precedence Constraints)、提送貨時間窗、貨物材積、司機人員下班時間等貨運特性下，找出一組時間成本最小的可行車輛路徑組合。 本研究提出一個以變數產生法為基礎的啟發式解法求解這個集合分割問題。於求解過程中將子問題設計為考慮多種提送貨特性的最短路徑問題，以產生可改善主問題目標式的變數(Column)，並提出一個修正後的Dijkstra’s演算法來求解子問題。 由測試結果可知變數產生法非常適用於求解PDPTW這類變數數量多(規模大)的問題，能在合理的運算時間下求出不錯的路徑組合。

This research focuses on the modeling and solution technique of Pickup and Delivery Problem with Time Windows Problems (PDPTW). We first formulate PDPTW as a set partitioning model. This model takes customer requests, service precedence, time windows, vehicle capacity, and working time into account. The objective is to find a set of feasible routes with minimum cost. A column generation based heuristic method is developed to solve this model. A shortest path problem with multiple side constraints is formulated as the sub-problem in order to find columns which could improve the objective function of the master problem. We also propose a modified Dijkstra’s algorithm to solve this shortest path problem. Numerical experiments indicate that the proposed solution method is sound and promising. The testing results also demonstrate that this method is good for large scale problems.