應用基因演算法以解決最小碳足跡之依時可選擇路徑之多車種車輛途程問題

Abstract

本研究提出考慮最小碳足跡之車輛途程問題規劃中同時考量車種選擇和路徑選擇的問題，並稱此問題為 「最小碳足跡之依時性可選擇道路之多車種車輛途程問題」(Minimizing Carbon Footprint for the Time-Dependent Heterogeneous Fleet Vehicle Routing Problem with Alternative Paths, CTHVRPP)，當中在目標式方面，為了因應目前日益嚴重的全球暖化與溫室氣體問題，因此不以過去常用的距離或時間為目標式，而改以最小碳足跡為目標。在比較了相關的依時性車輛途程問題之文獻及總結 CTHVRPP 的問題特性後，我們提出此問題的一個整數規劃的模型。如同過去車輛途程問題，CTHVRPP 亦為NP-Hard，因此我們進一步地發展出一套不同於以往的基因演算法的解決方法。藉由一套適當的編碼與解碼系統，本研究提出了序列型染色體與平行型染色體的編碼方式，其中序列型染色體較利於演算法中交配、突變等動作進行，而平行型染色體則是將序列型染色體進行解碼的動作，如此一來可簡化單一染色體進行交配與突變時複雜的動作。另外由於碳足跡的大小取決於車輛行駛時消耗的能源多寡而定，因本研究改良 Bektaş 等人 (2011) 所提出之能源消耗模型，使其能夠為本研究之多路徑多車種問題所使用。在實驗例題方面，我們以 Taillard (1999) 之測試例題為基礎，額外編制影響碳足跡之成本變數，包含了不同路徑下之車輛行駛速度、不同時區下之車輛行駛速度與不同車輛種類之空車重量與最大載重等變因，使其測試例題為本篇論文能夠使用。最後將具多重路徑供選擇之例題與無多重路徑供選擇之例題測試結果進行不同成本如碳足跡、時間或距離最小化之目標式之結果進行分析，與無多重路徑供選擇之例題測試結果進行比較。結果表明路徑選擇這個實驗因子對實驗結果是有顯著影響的，並且有路徑選擇之碳足跡實驗結果優於無路徑選擇之碳足跡實驗結果。在本篇論文中，提出基因演算法運算出優化的車輛排程，根據實驗結果表明，所提出的車輛排程結果在以最小碳足跡為目標的情況下具有較佳的實驗結果。

This study proposes a vehicle routing problem for minimizing carbon footprint by selecting the appropriate vehicles and routes. It is referred to as the “Minimizing Carbon Footprint for the Time-Dependent Heterogeneous Fleet Vehicle Routing Problem with Alternative Paths, CTHVRPP.” The objective of this problem is to minimize carbon footprint rather than distance or time. Thus, the resulting solution can help reduce greenhouse gas emissions and global warming. Since the vehicle routing problem is itself an NP-Hard problem, it can be inferred that CTHVRPP is also an NP-Hard problem. So we developed an enhanced genetic algorithm to resolve this problem. In the process of devising an appropriate coding and decoding system, this study developed a sequential chromosome coding method and a parallel chromosome decoding method. The sequential chromosome encoding method is best suited for crossover and mutation encoding operations, while the parallel chromosome decoding method is typically used in decoding sequentially encoded chromosomes. It is known that carbon footprint size is dependent on the vehicle energy consumption, thus this study improved the energy consumption model Bektaş et al. (2011) proposed, making this study possible. In our test scenario, we applied a test benchmark developed by Taillard (1999), which required the identification of cost variables that affect carbon footprint, including: vehicle speed, vehicle traveling on different paths during different time periods of the day, and the speed of each vehicle type when carrying an empty load and maximum load. The test results were then analyzed by applying various objectives such as carbon footprint minimization, time minimization, and distance minimization. These results were compared with results from scenarios without alternative routes available for selection. The results show that the alternative path in this experiment factor is has a significant impact on the experimental results. In this paper, the genetic algorithms optimization of vehicle scheduling, according to the experimental results, the proposed vehicle scheduling results with the experimental results better in minimum carbon footprint as the target case.