基因演算法解算軟性時窗車輛途程問題之研究

A genetic algorithm for the vehicle routing problem with soft time windows

顏成佑(Cheng-Yu Yen)

指導教授 ： 徐旭昇

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

摘要

在車輛途程的問題中，時窗的限制往往為一項重要的考量，如能在時窗限制的時間外接受服務將更具有彈性，這也就是所謂的軟性時窗車輛途程問題。而本文的主旨為發展一套適用於軟性時窗車輛途程問題的啟發性解法，本研究以最鄰近法為根據建構兩種初始解法：最鄰近法＋兩點交 換、最鄰近法＋隨機法；並用基因演算法以階段性的方式來改善，最後利用Solomon在1987年所建構之車輛途程題庫進行測試；至於演算法的參數設定問題，則是透過田口實驗進行設計，以找出最穩健合適的參數組合。
最後本研究之結果與目前之最佳解做一比較，結果發現本研究在車輛數的改善上表現較佳，而初始解法則以最鄰近法＋兩點交換為初始解法所得到的改善解值較佳。

關鍵字

時窗 ； 基因演算法 ； 車輛途程問題 ； 田口方法

並列摘要

This research describes a two-phase genetic algorithm for the vehicle routing problem with soft time windows. In this problem, earliness and lateness at customer locations is allowed although a penalty is incurred and added to the objective value. By adding large penalty cost, the vehicle routing problem with hard time windows can be addressed as well. In our search algorithm, the goal of Phase I is to find a feasible dispatching tour satisfying all customers’ demand with minimum number of vehicles. The goal of Phase II is to find an optimum dispatching tour given the number of vehicles set in Phase I. In both phases, genetic algorithms are used to reach the goals, and Taguchi method is applied in order to obtain the best parameter settings for both algorithms. The performance of the algorithm is tested through the data set of Solomon''s vehicle routing test problems. Our experiment shows that the Phase I algorithm works well on R2 and RC2 test problems, but in average there is 12.8% cost more than the present best solution due to the limitation of using the number of vehicles obtained in Phase I.

並列關鍵字

Time Window ； Vehicle Routing Problem ； Genetic algorithm ； Taguchi Method

參考文獻

trading heuristic for solving vehicle routing problems,”

Discrete Applied Mathematics 65,pp.47-72,1996.

[2]Balakrishnan,N.,”Simple Heuristic for the Vehicle Routing

Traveling Salesman Algorithms,”Operation Research,Vol.28

Computers & Operations Research,Vol.10,pp.63-211,1983.