應用非支配排序簡化群體演算法於多目標全通路零售之汙染路徑問題

Non-dominated Sorting Simplified Swarm Optimization for Multi-Objective Omni-Channel of Pollution Routing Problem

梁茲晴(Tzu-Ching Liang)

指導教授 ： 葉維彰

國立清華大學/工學院/工業工程與工程管理學系/碩士(2021年)

摘要

溫室氣體 (Greenhouse gas, GHG)的產生主要來自於運輸部門，當交通運輸劇烈成長，全球汙染亦迅速飆升，同時導致人體健康之負面影響；為減少溫室氣體之排放，有效提出解決方法以降低車輛的燃料消耗，於車輛路徑問題(Vehicle routing problem, VRP)基礎上，加入環境因素考慮，延伸出汙染路徑問題 (Pollution routing problem, PRP) 。另一方面，零售分銷系統將考慮到全通路零售(Omni-channel)下的運輸方式，顧客可使用任意管道購買產品，於任何時間、地點皆可以下單及取貨，並由一組數個零售店使用一組同質車隊，車輛從倉庫出發將產品送至零售店，再從零售店取貨配送給顧客，整合此兩分銷階段使用同一台車運送，以減少燃料消耗及提升運輸效能。
本研究結合兩個VRP變形問題，考慮了多目標的全通路零售之汙染路徑問題 (PRP in Omni-Channels, OCPRP)，為最小總運輸成本與最少燃料消耗，旨在降低經濟成本及環境永續的同時，亦能從全通路零售虛實結合的模式下，使顧客便利地購物及取物。本研究為NP-Hard問題，將使用非支配排序簡化群體演算法(Non-dominated Sorting Simplified Swarm Optimization, NSSSO)來求解，應用PRP之Benchmark數據集，並比較兩個多目標進化式演算法:非支配排序基因演算法(Non-dominated Sorting Genetic Algorithm-II, NSGAⅡ)、非支配排序粒子演算法(Non-dominated Sorting Particle Swarm Optimization, NSPSO)，證實NSSSO在此問題具有更好的解決方案及更快的收斂性。

關鍵字

汙染路徑問題 ； 全通路零售 ； 非支配排序簡化群體演算法 ； 多目標優化

並列摘要

Greenhouse gas (GHG) is mainly generated from the transportation sector. When transportation sector grows rapidly, global pollution will be soaring, and causing a negative impact on human health at the same time. To reduce the emissions of greenhouse gas and propose effective solutions that reduce vehicles of fuel consumption, environmental factors are taken into consideration along with the basis of Vehicle Routing Problem(VRP). As a result, Pollution Routing Problem(PRP) is derived. On the other hand, the retail distribution system will consider using Omni-channel as a transportation mode. In that case, customers can purchase products through any channel, with no limitations on time and place to order and pick up goods. Several retail stores use a group of homogeneous fleets. The vehicles will start from the depot to deliver products to the retail store, and then pick up the goods to deliver them from the retail stores to customers. The two distribution systems are integrated using the same vehicles to reduce fuel consumption and improve transportation efficiency.
The study combines two variations of VRP problems. We have considered PRP in Omni-Channel with multi-objectives, which are minimization of total traveling cost, and minimization of fuel consumption. The purposes are to reduce economic cost, pursue environmental sustainability, and provide customers with convenience of shopping and pickup through the integration mode of online and offline. The research is an NP-Hard problem which will be solved by Non-dominated Sorting Simplified Swarm Optimization (NSSSO). The PRP benchmark dataset will be applied and be compared with two multi-objective evolutionary algorithms (MOEA) which are Non-dominated Sorting Genetic Algorithm-II (NSGAII) and Non-dominated Sorting Particle Swarm Optimization (NSPSO). The results are confirmed that NSSSO has better feasibility, better solutions, and faster convergence.

並列關鍵字

Pollution Routing Problem ； Omni-channel ； Non-dominated Sorting Simplified Swarm Optimization ； Multi-objective

參考文獻

[1] E. E. Agency, "EMEP/EEA air pollutant emission inventory guidebook," 2019. https://www.eea.europa.eu/themes/air/air-pollution-sources-1/emep-eea-air-pollutant-emission-inventory-guidebook.

[2] G. B. Dantzig and J. H. Ramser, "The truck dispatching problem," Management science, vol. 6, no. 1, pp. 80-91, 1959.

[3] T. Bektaş and G. Laporte, "The pollution-routing problem," Transportation Research Part B: Methodological, vol. 45, no. 8, pp. 1232-1250, 2011.

[4] E. P. A. E. Yuan.R.O.C. "Taiwan six important GHG." https://ghgregistry.epa.gov.tw/ghgenglish/report.asp (accessed.

[5] M. Asghari and S. M. J. M. Al-e, "Green vehicle routing problem: A state-of-the-art review," International Journal of Production Economics, p. 107899, 2020.