運用差別演化式演算法求解考量時窗限制之機率旅行推銷員問題

Using Differential Evolution Algorithms to Solve the Probabilistic Traveling Salesman Problem

劉祐興(Yu-Hsin Liu)

《管理學術研討會》 第十六屆 (2018/11) Pp. 82-91

https://doi.org/10.29893/NCUTMAN.201811.0015

摘要

近年來，物流公司著重於提供指定時間送達之寄送服務以提升服務品質，增加其在同業間之競爭力，例如國內之黑貓宅急便與台灣宅配通提供指定送達時段的服務；國際物流龍頭UPS與Fedex所提供的隔日送達保證的服務。根據資料顯示，近十幾年來指定時間送達之寄送服務持續成長，同時根據問卷訪查結果顯示高達95%的托運人表示準時寄送為選擇物流公司的最重要因素。因此，考量時窗限制之隨機路徑規劃，即成為研究物流運送的重要議題。本計畫擬運用差別演化式演算法（differential evolution, DE）求解考量時窗限制之隨機路徑規劃問題，以比較並分析於其尋解效能。研究結果顯示本研究所提出之求解方法中，初始解產生方法採用最遠鄰居—最近鄰居法則（NN2），確能在部分案例有效地求取更好的結果。此研究結果將可提供具時間限制的隨機網路問題之實務應用之參考。

關鍵字

差別演化式演算法 ； 時窗限制 ； 機率旅行推銷員問題

並列摘要

Freight delivery business data revealed that freight volume associated with time-definite services was growing in the past ten years. One survey held by the Colography Group, Inc., the industry leader in trend forecasting in transportation and logistics, indicated that 95% of shippers mentioned ＂on-time＂ delivery as the most important factor in carrier selection. Therefore, the probabilistic traveling salesman problem with deadlines (PTSPD) becomes an important research topic. Although it is important to reevaluate the design of a priori tour by considering these time constraints, consideration of these constraints in a priori route construction is very limited in the academic literature. Recent studies have showed its potential to deal with problems requiring numerous calculations. In light of all these, this research developed a solution procedure based on differential evolution (DE) for solving PTSPD. The results obtained showed that the adoption of nearest neighborhood rule in generating initial solutions under DE framework yielding promising results. The comparative results obtained can substantiate the potential of the proposed algorithm in solving the PTSPD.

並列關鍵字

differential evolution ； time window ； probabilistic traveling salesman problem