具載貨量與時窗限制取卸貨車輛途程問題的遺傳演算為基啟發式求解法

Genetic Algorithm Based Heuristic Method for Time Window and Capacity Constrained Pickup and Delivery Vehicle Routing Problem

賴青杉(Ching-Shan Lai)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.03089

摘要

隨著都會區定點間物流快遞服務的需求急遽增加，具載貨量與時窗限制的一對一取卸貨途程規劃問題日益重要。本文首先詳細定義本研究問題再提出以遺傳演算法為基的啟發式求解法。本問題是由車輛途程問題加上一對一先取後卸限制、載貨量上限限制、及時窗限制形成。前面二者在本研究中以硬式限制處理，而後者則以軟式限制視之。因此求解目標除了車行途程距離望小外，也期望時窗違反量最小。為處理載貨量及一對一先取後卸的硬式限制，本研究中開發一名為「導引併入式的演算法」以支援遺傳演算技術求解本問題。此演算程序可用於執行本問題的交配演算、修補傳統遺傳交配、突變產生的不合理解、以及建構符合硬式條件的初始解。因本問題尚無標竿問題可用，在不改變最佳解的狀態下，本研究藉由添加一對一取卸關係、衡量給定的載貨量上限、及設定最早和最晚服務時間，轉換TSPLIB中數個已知最佳路徑的旅行推銷員問題，作為測試對象。測試模式包括典型GA、GA加上本研究提示的導引併入式演算修補法、以及導引併入式的交配演算子三個模式。數值測試結果以模式二最佳且雖然模式三是使用本研究提示的新交配演算子，求解結果顯示新交配演算子仍有改善空間。

關鍵字

時窗限制 ； 旅行推銷員問題 ； 導引併入式演算法 ； 遺傳演算法

並列摘要

Due to the increasing demand of point-to-point parcel deliveries in metropolitan area, a time window and capacity constrained one-to-one pickup and delivery single vehicle routing problem arises. This paper rigorously defined this problem and then proposed GA-based heuristic methods for the problem. In this problem, pickup and delivery points are exclusively defined and paired with a one-on-one and pickup-delivery relationship. The time window constraint for the pickup/delivery service times imposed on each point is regarded as soft constraints in this problem. Therefore, the goal of the problem is to find a route with a minimal routing distance and a minimal amount of time window violation. To assure a route satisfying the capacity and one-on-one pickup and delivery constraints, this paper presents a heuristic operation named as “guided merge operation (GMO).” GMO can be used to generate hard constraints satisfied routes to serve as the initial population for a GA-based solving model. It can be used to repair constraint-violated routes generated from traditional GA crossover and mutation operations. In addition, GMO is further enhanced to serve as a GA crossover operator that can generate two constraint-satisfied child routes from two parent ones. Without changing the optimal route, several benchmarks from the TSPLIB were adapted and transformed into sample problems for the problem by adding pickup/delivery one-on-one attribute and the earliest and latest service times to each city. Three GA computation models were constructed for the numerical tests: a simple GA, a GA+GMO-based repairing, and a GA with the GMO-crossover operator. Results indicated that the model with GMO repairing model outperformed others. However, the GMO-crossover operation requires further improvement.

並列關鍵字

Time Window Constraints ； TSP ； Guided Merge Operation ； Genetic Algorithm

參考文獻

19. 黃馨怡，2006，具載貨量限制取卸貨途程問題的啟發式演算法，碩士論文，國立台灣大學工業工程學研究所。

1. Anily, S. and G. Mosheiov, The traveling salesman problem with delivery and backhauls. Operations Research Letters, 1994.

2. Bruun, A., U. Worsøe, and M.H. Pagh, Traveling Salesman With Pickup and Delivery. 2003.

3. Gendreau, M., A. Hertz, and G. Laporte, The traveling salesman problem with backhauls. Computers & Operations Research, 1996. 23(5): p. 501-509.

4. Gendreau, M., G. Laporte, and D. Vigo, Heuristics for the traveling salesman problem with pickup and delivery Computers & Operations Research, 1999. 26(7): p. 699-714.