時窗限制車輛途程問題

Abstract

車輛途程與排程問題 (Vehicle Routing and Scheduling Problems)﹐在過去四十年中﹐已成為一重要的研究與應用領域。由於這些問題至今大多無法在多項式的計算時間 (Polynomial Time Complexity) 內求得其最佳解﹐是以近來學者大都集中在如何尋找一些高效率與高品質的近似最佳解法 (Near-optimal Solution Methods)。本論文則是針對下述三種具有時窗限制的車輛途程問題進行研究。(1) 單一車種之時窗限制的車輛途程問題 (Vehicle Routing Problem with Time Windows, VRPTW); (2) 單一車種之時窗與回程取貨雙重限制的車輛途程問題 (Vehicle Routing Problem with Time Windows and Backhauls, VRPTWB); (3) 多車種之時窗限制的車輛途程問題 (Vehicle Routing Problem with Time Windows and Multiple Vehicle Types, VRPTWMVT)。本研究中所求之近似解必須滿足時窗限制式﹐亦即所謂的硬式時窗(Hard Time Windows) 。為評估所發展之演算法的效能﹐文中進行許多測試比較。關於 VRPTW 及VRPTWB 等測試問題係擷取至已發表之文獻中﹐而就我們所知文獻關於 VRPTWMVT之測試問題尚付之闕如。因此﹐我們自行產生168 個VRPTWMVT問題﹐以測試所發展之解法的優劣。除此之外﹐文中亦針對 VRP, VRPB 及 VRPMVT等問題與文獻中已知之最佳解進行比較。大體而言﹐測試結果顯示出我們所發展之演算法優於文獻中已發表之方法﹐或至少可產生與之具競爭性的高品質之解。 茲將本論文之主要貢獻略述於下: (1) 文中就如何求解車輛途程等問題﹐提出了路線鄰域 (Route Neighborhoods) 的觀念。藉由調整路線鄰域的範圍﹐我們可以對可行解區域進行較完整的系統化搜尋。 (2) 文中就如何在追求使用最少車輛數之主要目標下﹐建議了一規劃架構。我們並提出了複式平行路線構建 (Nested Parallel Route Construction)暨終端效應處理 (End Effect Handling)等觀念。 (3) 在處理VRPTWMVT問題中﹐為防止插入式節省法 (Insertion-based Savings Method) 因時窗限制而導致大量過短路線或偏向使用較小車種的現象產生﹐我們提出了一個表示相對於路線循序構建(Sequential Route Construction)的強度參數試以控制路線構建之演進狀態﹐此參數之引入對於解之品質產生了明顯的效益。

This research involves developing heuristic solution methods for three types of time window constrained vehicle routing problems. They are the Vehicle Routing Problem with Time Windows (VRPTW), the Vehicle Routing Problem with Time Windows and Backhauls (VRPTWB), and the Vehicle Routing Problem with Time Windows and Multiple Vehicle Types (VRPTWMVT). The time windows considered in this study constitute hard constraints. Extensively computational results are reported. Benchmark problems for VRPTW and VRPTWB are taken from the literature. A total of 168 sample problems for VRPTWMVT have been newly created to evaluate the performance of our heuristics. Furthermore, we also compare our results for VRP, VRPB, and VRPMVT with the best-known solutions found in the literature. In overall, computational studies show that our heuristics in terms of both solution quality and computation time are superior to or at least competitive with all other heuristics published. The primary contributions of this dissertation are summarized as follows. (1) A new neighborhood structure is introduced in dealing with VRPs. Instead of the traditional way in constructing neighborhoods using a node(s)-to-node(s) relationship, we generate a set of route-neighborhoods by focusing on a node(s)-to route(s) relationship. Through the adjustment of the size of route-neighborhoods, one might obtain near optimal solutions due to a thorough exploitation of solution space. (2) An operational framework for minimizing the number of vehicles used is proposed. A key component in the framework is the introduction of an end-effect-handling procedure. When only a small number of customers is left with no feasible positions with respect to the existing set of routes, a specially designed procedure is applied on them such that feasible positions can possibly be found among the current routes instead of immediately constructing a new route for them. Information extracted from previous construction history is used in defining the end-effect-threshold for justifying what is a small number of customers. In addition, we present a scheme for constructing routes in a nested parallel manner. (3) Several insertion-based savings heuristics that generalize the traditional combining-based savings approach are first addressed to solve the VRPTWMVT. The introduction of a parameter referring to the degree of sequential route construction has substantially improved the solution quality.