應用人工智慧演算法探討多車種之送貨路徑規劃問題

Artificial Intelligence Approaches for the Heterogeneous Fleet Vehicle Routing Problem

黃偉綱(Wei-Gang Huang)

指導教授 ： 謝益智

國立虎尾科技大學/管理學院/工業管理系工業工程與管理碩士班/碩士(2017年)

摘要

本研究探討多車種車輛路徑問題(Heterogeneous Fleet Vehicle Routing Problem，HFVRP)，此問題為傳統車輛路徑問題(Vehicle Routing Problem，VRP)的延伸應用問題，HFVRP目前廣泛運用在物流上，HFVRP與VRP之主要不同處為其考慮多種車種進行送貨，當使用的車種不同，車輛成本亦不相同。本研究將需求點分列為兩類：(1)需求點單一種貨物需求，(2)需求點包含兩種貨物需求；需求點三種情境：(1)一般貨物需求=冷凍貨物需求(2)一般貨物需求>冷凍貨物需求(3)一般貨物需求<冷凍貨物需求。HFVRP應用包括宅急便、花朵運送、高科技3C零件運送等等。
本研究以台北市某區域為例，將各需求點假設為單一貨物的需求、兩種貨物的需求，運用三種不同類型的車輛：一般貨車、冷凍貨車、綜合貨車，並提出新的編碼方式同時解決貨物的送貨路徑順序，再以不同的情境、車輛容量、目標權重，應用基因演算法(Genetic Algorithms，GA)、免疫演算法(Immune Algorithms，IA)、粒子群演算法(Particle Swarm Optimization，PSO)，來求解此問題，使路徑總距離為最短(目標1)及最小化各車輛間路徑距離的差距(目標2)。測試數值結果顯示，免疫演算法與基因演算法求解平均最佳解優於粒子群演算法。

關鍵字

多車種 ； 車輛路徑問題 ； 基因演算法 ； 免疫演算法 ； 粒子群演算法 ； 田口方法

並列摘要

The goal of logistics is to deliver goods to customers efficiently. This thesis explored the heterogeneous fleet vehicle routing problem (HFVRP). This problem is also an extension of the vehicle routing problem. The main difference is that this study assumes different types of goods and demand quantity for each point. Additionally, a delivery problem with two types of different goods demand is studied, including single type goods demand or mixed type goods demand,. Moreover, three types of demand quantity for demand points are assumed for each demand point, namely, (1) general goods demand=frozen goods demand for points, (2) general goods demand > frozen goods demand, (3) general goods demand < frozen goods demand. Applications of this considered problem include 7-11 delivery service, flower delivery and 3C delivery.
In this thesis, we explored an example in Taipei City in which three types of vehicle are assumed, namely, (1) general truck, (2) frozen truck, (3) composite truck (which can deliver both general goods and frozen goods simultaneously). In addition, we propose a new encoding method to solve the considered problem under various combinations including different demands for points, different vehicle capacities, different weights of objective etc. In this thesis, we applied genetic algorithm (GA), immune algorithm (IA), particle swarm algorithm (PSO) to solve this problem. Numerical results show that these three algorithms can schedule the demand points and the routes effectively such that the total routing distance (objective 1) is minimized and the gap of routing distance among the three types vehicles (objective 2) is minimized. Numerical results also show that immune algorithm and genetic algorithm are superior to particle swarm algorithm for most of test instances.

並列關鍵字

Heterogeneous Fleet Vehicle ； Vehicle Routing Problem ； Genetic Algorithm ； Immune Algorithm ； Particle Swarm Optimization ； Taguchi Method

參考文獻

[17] 簡銓蔚(2013)，粒子群演算法應用於具容量限制的開放式車輛途程問題，元智大學工業工程與管理研究所，碩士論文。

[6] 胡智維(2013)，粒子群演算法應用於多車種固定車隊之車輛途程問題，元智大學工業工程與管理研究所，碩士論文。

[7] 徐志明、陳子安、李漢宗(2011)，以基因規劃和人工免疫演算法最佳化薄型晶圓片切割參數，明新學報，37卷，2期，頁165-183。

[4] 林義清(2016)，應用田口方法於回收溶劑蒸餾參數最適化研究，國立屏東科技大學工業管理系研究所，碩士論文。

[12] 許正良(2013)，應用人工智慧法於居家照顧服務排程路徑規劃問題，虎尾科技大學工業工程與管理研究所，碩士論文。