應用蟻群最佳化演算法求解航空快遞員途程問題

Ant Colony Optimization Based Heuristics for the On-road Air-express Courier Routing Problem

藍唯誠(Wilson W. Lan)

指導教授 ： 丁慶榮

元智大學/工程學院/工業工程與管理學系/碩士(2008年)

https://doi.org/10.6838/YZU.2008.00065

摘要

陸運取件與遞送乃航空快遞業重要之核心作業，而正確的路線規劃方針不僅可擴大快遞員之服務範圍，公司亦可藉此節省人力資源及成本。面對與日俱增的勞動及燃料成本，有效率的途程規劃對航空快遞業是不可或缺的。本研究針對物流特性之不同，將郊區之快遞員途程問題視為旅行推銷員問題(traveling salesman problem, TSP)；而將都市之快遞員途程問題視為多停點區位途程問題(multi-stop location-routing problem, MSLRP)。
針對郊區之快遞員途程問題，快遞員必須以最短行車路線行經所有顧客點一次，以滿足配送與取件要求。其中送件顧客點位置在路線規劃前已知，而取件需求之顧客於快遞員配送途程中隨機出現。本研究提出逐步蟻群最佳化(stepwise-ACO, SACO) 及最低成本插入式逐步蟻群最佳化(cheapest insertion stepwise-ACO, CISACO)兩種求解方法，並以三種不同型態的取件要求進行實驗。測試結果顯示在1-點更新規則下CISACO法優於SACO法，且兩者皆較傳統之最低成本插入法(cheapest insertion, CI)更能節省總行車距離。文中亦針對累積n-取件點始更新路線進行測試，結果顯示部分n-點更新規則可進一步改善1-點更新規則之最短路徑，CISACO法求得之結果均不劣於SACO法，且兩者皆遠優於CI法。
針對都市之快遞員途程問題，快遞員必須以最低成本尋找適當的停車位置，並以徒步方式服務至附近顧客端。因問題之複雜程度較高，此處僅針對送件之顧客點進行路線求解，而不考慮隨機出現之取件需求。本研究提出序列(sequential)及精煉(refined)兩種求解方法。由序列法可獲得初步的停車位置及顧客點指派，並決定徒步及車輛之路線規劃，再由精煉法進一步改善途程效率。由實驗結果顯示停車點個數及總行車距離皆伴隨徒步門檻增大而減少；而總步行距離隨著徒步門檻增大而增加。針對較大的徒步門檻，精煉法更能有效降低序列法求解之總配送成本及時間；本文亦針對三種顧客分佈型態，探討對求解效果之影響。
為提昇作業效率並降低公司成本，建議航空快遞業可將本研究提出之途程規劃方法應用於快遞員之日常取件與遞送流程，並將演算法求解之最佳途程規劃視為執行方針，用以替代快遞員或管理人員主觀之個人經驗。

關鍵字

蟻群最佳化 ； 航空快遞員 ； 旅行推銷員問題 ； 多停點區位途程問題

並列摘要

The on-road courier routing operation is the most critical part of air-express companies. With good routing guidelines, couriers can serve larger areas, thus the company can save the labor cost and the vehicle routing cost. Facing the ever-increasing labor and fuel costs, finding good solutions to the on-road courier routing problems becomes imperatively important to the air-express companies. This study treats the courier routing problem in suburban areas and dense urban areas as traveling salesman problem (TSP) and multi-stop location-routing problem (MSLRP), respectively.
In suburban areas, the courier routing problem is formulated such that the couriers would drive to visit each customer point (delivery or pickup) exactly once to minimize the total traveled distance. Two novel approaches: stepwise-ACO (SACO) and cheapest insertion stepwise-ACO (CISACO) are proposed. Three pickup emerging patterns are tested in the numerical experiments. The results under 1-update rule show that CISACO is superior to SACO, and both approaches are better than the cheapest insertion (CI) heuristic in terms of total traveled distance. Further experiments on n-update rules show that the 1-update rule cannot guarantee the minimum total traveled distance by the three routing approaches. However, it is rather robust that CISACO approach performs no worse than the SACO approach, which is far superior to the CI approach, regardless of the updated rules or pickup patterns.
In dense urban areas, the courier routing problem is formulated in such a way that the couriers would find appropriate locations of vehicle stops, each stop covering several customer ends by a foot route, to minimize the total system costs. Two solving strategies are proposed: sequential and refined strategies. The sequential strategy is used to obtain the preliminary solutions for locating the vehicle stops, assigning the customer points to each vehicle stop, and determining the foot tours and vehicle tour. The refined strategy is to further improve the routing efficiency based on the results of the sequential strategy. The numerical experiments show that the number of vehicle stops decreases with the threshold value, regardless of the strategies used. The total vehicle routing distance also decreases with the threshold value. However, the total foot routing distance will increase with the threshold value. The refined strategy is superior to the sequential strategy in terms of total delivery costs and time, for larger threshold value. Moreover, the influences of different customer distributions on the final results are also investigated with three different instance types.
The air-express companies are recommended to introduce our proposed routing algorithms to examine their on-road couriers’ operations. The minimum routing distance or cost obtained by our proposed algorithms can benchmark the couriers’ and managers’ objective experiences in the on-road courier routing operations.

並列關鍵字

ant colony optimization ； air-express courier ； traveling salesman problem ； multi-stop location-routing problem

參考文獻

1. Albareda-Sambola, M., Fernández, E. and Laporte, G. (2007) “Heuristic and Lower Bound for a Stochastic Location-routing Problem,” European Journal of Operational Research, Vol. 179, 940-955.

2. Ambrosino, D. and Scutellà M. G. (2005) “Distribution Network Design: New Problems and Related Models,” European Journal of Operational Research, Vol. 165, 610-624.

3. Baker, B. M. and Ayechew, M. A. (2003) “A Genetic Algorithm for the Vehicle Routing Problem,” Computers & Operations Research, Vol. 30, 787-800.

4. Barreto, S., Ferreira, C., Paixão, J. and Santos, B. S. (2007) “Using Clustering Analysis in Capacitated Location-routing Problem,” European Journal of Operational Research, Vol. 179, 968-977.

5. Berger, R. T., Coullard, C. R. and Daskin, M. S. (2007) “Location-routing Problems with Distance Constraints,” Transportation Science, Vol. 41, 29-43.