運用粒子群演算法求解依時性綠色貨運車輛途程問題

Particle Swarm Optimization for A Time-dependent Green Vehicle Routing Problem

徐鴻源(Hung-Yuan Hsu)

指導教授 ： 林耘竹

中原大學/工學院/土木工程研究所/碩士(2021年)

https://doi.org/10.6840/cycu202100814

摘要

為分析碳稅對物流業者之影響，本研究探討一含時窗限制之依時性綠色車輛途程問題 (Time-dependent Green Vehicle Routing Problem with Time Windows, TDGVRP-TW)，將車輛行駛排放之溫室氣體所產生之碳排放成本，以及貨運車輛於尖峰小時行駛速度受限納入考量，以最小化車輛營運成本(包括碳排放成本、能源消耗成本與員工加班成本)為目標，決定車輛之最佳服務路線與行駛速度。本研究使用異質性粒子群演算法 (Heterogeneous Particle Swarm Optimization, HPSO)，進行模式求解。以Solomon (1987) 所設計之測試題庫C2、R2、RC2例題進行測試。測試結果顯示，使用容量較小之貨車其碳排放成本與油耗成本會因載重比增加而上升，路網擁塞時段愈長，所造成的綠色成本增加的問題就越嚴重；相對而言，使用容量較大之貨車其在綠色成本上是較為節省。另一方面，因為路網擁塞造成行駛速度降低，物流業者為了滿足顧客的服務時窗限制，必須使用更多的車輛進行服務，又會更加惡化交通擁塞問題。所以，未來碳稅制度上路之後，物流業者除了必須調整其車輛派遣路線安排策略之外，也必須同時檢討其特定時窗服務之指定方式。

關鍵字

綠色物流 ； 依時性車輛途程問題 ； 粒子群演算法 ； 固定車隊

並列摘要

This study explores a Time-dependent Green Vehicle Routing Problem with Time Windows (TDGVRP-TW) to analyze the impact of the carbon tax on logistics companies. Considering the carbon emission costs of greenhouse gases emitted by freight vehicles and the limited speed of freight vehicles during peak hours, the proposed model would determine the vehicle’s best service route and driving speed. The objective function is to minimize vehicle operating costs (including carbon emission, energy consumptions, and employee overtime costs). This study uses Heterogeneous Particle Swarm Optimization (HPSO) to solve the model. The sample questions C2, R2, and RC2 of the question bank designed by Solomon (1987) were modified. The testing results show that the carbon emission cost and fuel consumption cost of trucks with a smaller capacity will increase due to the increase in loading ratio. The longer the congestion period of the road network, the more serious the increase in green costs caused; relatively speaking, the use of larger capacity trucks is more economical in terms of green costs. On the other hand, because the road network congestion causes the travel speed to decrease, the logistics company must use more vehicles to meet the customer’s service window limit. It will worsen the traffic congestion problem. Therefore, if the carbon tax system is implemented in the future, logistics companies must adjust their vehicle dispatch routing strategy and review their designation methods of specific time window service.

並列關鍵字

Green VRP ； Time-dependent Vehicle Routing Problem ； Particle Swarm Optimization ； Fixed fleets

參考文獻

1. Bektaş, T., Laporte, G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological, 45(8), 1232-1250.

2. Demir, E., Bektaş, T., Laporte, G. (2012). An adaptive large neighborhood search heuristic for the Pollution-Routing Problem. European Journal of Operational Research, 223(2), 346-359.

3. Demir, E., Bektaş, T., Laporte, G. (2014). The bi-objective pollution-pouting problem. European Journal of Operational Research, 232(3), 464-478.

4. Engelbrecht, A. P. (2010). Heterogeneous particle swarm optimization. Paper presented at the International Conference on Swarm Intelligence. Springer, Berlin, Heidelberg.

5. Franceschetti, A., Demir, E., Honhon, D., Van Woensel, T., Laporte, G., Stobbe, M. (2017). A metaheuristic for the time-dependent pollution-routing problem. European Journal of Operational Research, 259(3), 972-991.