具平衡之週期性車輛派遣問題的探討

The Study of Vehicle Periodic Delivery Problem with Balance Consideration

李新秋(Shin-Chiou Lee)

指導教授 ： 謝益智

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2010年)

摘要

本研究探討週期性車輛派遣問題，除了要最小化派遣車輛的總數外，亦加入切合實際情形的運送量平衡限制式。不含平衡限制式之週期性車輛派遣問題已被証明屬於NP-hard問題，因此，本研究探討的具平衡之週期性車輛派遣問題亦屬於NP-hard問題。本研究應用免疫演算法、基因演算法與粒子群演算法來求解此具平衡之週期性車輛派遣問題，此問題的目標為最小化(i)派遣車輛的總數、(ii)各車輛運送總量差異與(iii)每日車輛運送總量差異。

本研究提出一個新的兩階段來求解此問題，第一階段為最小化派遣車輛的總數、各車輛運送總量差異與每日車輛運送總量差異，第二階段為微調各車輛運送總量。本研究試驗三種演算法於不同參數組合的求解表現，數值結果顯示，本文之兩階段可有效的求解此具平衡之週期性車輛派遣問題，尤其當問題複雜度較高時，免疫演算法表現優於基因演算法與粒子群演算法。

關鍵字

週期性車輛派遣問題 ； 基因演算法 ； 免疫演算法 ； 粒子群演算法

並列摘要

This thesis studies the problem of vehicle minimization for periodic deliveries (VMPD). The problem aims to minimize the total number of vehicles with balance consideration. As known, vehicle periodic delivery problem is an NP-hard. Therefore, the studied vehicle periodic delivery problem with balance consideration is also NP-hard. In this thesis, we will apply three artificial intelligence algorithms, namely, immune algorithm, genetic algorithm and partical swarm optimization, for solveing the problem. The objective of the problem is to minimize (i) the summation of total number of vehicles, (ii) the deviation of total delivery quantities for each vehicle, (iii)the deviation of total delivery quantities for each day.

In this thesis, a new two-phase approach is proposed to solve for the vehicle periodic delivery problem with balance consideration. In the first phase, we aim to minimize the (i) the summation of total number of vehicles, (ii) the deviation of total delivery quantities for each vehicle, (iii) the deviation of total delivery quantities for each day. In the second, we aim to adjust the deviation of total delivery quantities for each day. In this thesis, we apply the three algorithms for solving the problem under various combinations of parameters. Numerical results show that the immune algorithm performs better than the other two approaches, especially when the problem size is larger.

並列關鍵字

Vehicle Periodic Delivery ； Immune Algorithm ； Genetic Algorithm ； Particle Swarm Optimization

參考文獻

7. 林豐澤(2005)，「演化式計算下篇: 基因演算法以及三種應用實例」，東北大學資訊科學與工程學院系統工程學報，3卷，2期，頁29-56。

10. 黃若蘋(2007)，啟發式演算法於資料分群問題之比較，大同大學資訊經營研究所，碩士論文。

9. 張奕謙(2008)，具衰退性產品之不定點銷售問題的探討，虎尾科技大學工業工程與管理研究所，碩士論文。

11. Beltrami E.J. & Bodin L.D. (1974), “Networks and vehicle routing for municipal waste collection”, Networks, Vol.4, pp. 65–94.

13. Chao I.M., Golden B.L.& Wasil E. (1995), “An Improved Heuristice for the Period Vehicle Routing Problem”, Networks, Vol. 26, N0. 1, pp. 747-765.