時間相依且軟性時窗限制下之車輛途程問題研究

Time Dependent Vehicle Routing Problem with Soft Time Windows

黃正賢(Cheng-Hsien Huang)

指導教授 ： 丁慶榮

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

摘要

車輛途程問題在現今物流配送業發達下，已成為主要課題。而道路上之車流特性存在著一定程度的時性且週期性變化，使得在運送至消費者的過程中，往往會遇到行駛速率變動的因素，但在過去的文獻中，一般皆假設各路段的行駛時間均以相同速率計算，此與實際的狀況有些不符。因此本研究探討尖、離峰交通特性，並須符合消費者要求的時窗限制下，亦即時間相依及軟性時窗限制下的車輛途程問題(Time Dependent Vehicle Routing Problem with Soft Time Windows，TDVRPSTW)，使車輛途程問題達到最佳化。
本研究運用基因演算法(Genetic Algorithm)之菁英政策(Elitism Strategy)，解析TDVRPSTW。以Solomon硬性時窗題庫測試所發展的演算法，並和其他相關研究及最佳解比較，結果發現本研究對於C1及在較寬的時窗範圍（C2、R2及RC2）類型題庫有較佳的結果；以所有6類題庫結果的平均而言，本研究所使用的基因演算法之菁英政策優於其他相關研究。另外，在時間相依含軟性與硬性時窗限制之車輛途程問題中，利用5種速率進行測試，當尖峰速率遞減時，平均成本、平均行駛時間、平均等待時間及平均處罰成本均增加，且當尖峰速率愈低影響愈大。在使用車輛數方面，R109及RC106題目上，當尖峰速率為離峰速率的1/5時，所使用的車輛數較離峰速率所使用的車輛數增加2至3倍。因此在實際配送貨物時，應考量速率在路段上的變化，使錯估的相關成本能降至最低。

關鍵字

基因演算法 ； 車輛途程問題 ； 時窗限制 ； 時間相依

並列摘要

The vehicle routing problem with time windows (VRPTW) is an important problem in logistics management. Previous research has been devoted to time independent VRPTW that assumes the travel time between two customers or between a customer and the depot only depends on the distance between the points. For real life application some composite of modified measure of travel cost may be used. This research extends the VRPTW to account for urban congestion and soft time windows. The time dependent vehicle routing problem with soft time windows (TDVRPSTW) treats the travel time functions as step functions. In case of soft time windows that permit service earlier or later than the time window specified at each customer location, penalties will be added into the total travel cost function.
As a generalization of the VRPTW, the TDVRPSTW belongs to the class on NP-complete problems for which polynomial time exact algorithms are unlikely to be developed. A genetic algorithm incorporating the elitism strategy is proposed in this research. For elitism strategy we compare the best members of reproduction, crossover and mutation and select the best individuals. The best members of each generation are copied into the succeeding generation. The results of VRPTW are discussed in comparison with earlier findings. On well-known benchmark VRPTW instances, we obtain better results than those reported by other researchers using genetic algorithms. For TDVRPSTW, we test some of the VRPTW instances by adding penalties for early and late deliveries. The speed of the peak period is set to be a fraction of that of off-peak period. The results show that average costs, average travel times, and average number of vehicles increase when the speed of peak period decreases. The number of vehicles that serves the customers is doubled when the speed during peak period is one fifth of that of off-peak period. This indicates that larger vehicle fleet size should be considered in the presence of roadway speed variation.

並列關鍵字

Genetic Algorithm ； Vehicle Routing Problem ； Time Window ； Time Dependent

參考文獻

19.顏成佑，「基因演算法解算軟性時窗車輛途程問題之研究」，私立元智大學工業工程所，碩士論文，2000。

15.敖君瑋，「禁制搜尋法於軟性時窗限制之車輛途程問題研究」，私立元智大學工業工程所，碩士論文，1999。

21.Blumenfeld, D. E., L. D. Burns , J. D. Diltz and C. F. Daganzo, “Analyzing Trade-offs Between Transportation, Inventory and Production Costs on Freight Networks,” Transportation Research, Vol. 19B, No. 5, pp. 361-380, 1985.

23.Burns, L. D., R. W. Hall , D. E. Blumenfeld and C. F. Daganzo, “Distribution Strategies that Minimize Transportation and Inventory Costs,” Operations Research, Vol. 33, No. 3, pp. 469-490, 1985.

24.Campbell, J. F., “One-to-Many Distribution with Transshipments: An Analytic Model,” Transportation Science, Vol. 27, No. 4, pp. 330-340, November 1993.