本研究探討週期性車輛派遣問題,除了要最小化派遣車輛的總數外,亦加入切合實際情形的運送量平衡限制式。不含平衡限制式之週期性車輛派遣問題已被証明屬於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.