Transportation Dissertation
Title | Solning a Pickup and Delivery Problem with Time Window Constraints |
---|---|
Year | 2006 |
Summary | Hsin-Hsiang Huang, 2006.06 Department of Transportation Technology and Management National Chiao Tung University This research focuses on the modeling and solution trchnique 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 grneration 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. |