基於退火演算法之複合型電動車隊最佳路徑規劃
Abstract
本研究旨於開發基於退火演算法之複合型電動車隊最佳路徑規劃，首先利用先進車輛模擬軟體Advisor(Advanced Vehicle Simulator)中的車輛系統數據資料庫，將既有的車體參數、電動馬達數據、儲能系統數據、車輛傳動系統等，與本研究所參照的物流車型中華菱利電動車E300廂型車，建構出所需之整車系統模型，接續為電力源尺寸度數選配及整車系統能量管理，求得以34.28(kWh)之鋰三元電池搭配8.32(kWh)之磷酸鋰鐵電池作為本研究物流電動車之複合電力源，最終透過逐一調整距離及載重參數，記錄所對應之能耗，得到一距離/載重/能耗多維表。本研究設計基於最低能耗之車輛途程問題(Vehicle Routing Problem, VRP)數學模型: 本研究以先期路線規劃為主軸，探討車隊於單一物流中心出發前完成的路徑規劃，設計以最低能耗作為目標函數，探討具收貨順序限制之VRP及不具收貨限制之VRP。配送車輛由物流中心出發，依序至各客戶點完成收貨服務再回到物流中心，每個客戶點的收貨量為確定值，每個客戶點只由一臺車輛服務一次，不可有重複服務的情況。本文使用模擬退火演算法作最佳化路徑規劃，該演算法透過多次迭代，不斷生成鄰域解並根據接受準則選擇新的解，逐步尋找最低能耗的路徑，此演算法的核心在於模擬物理退火過程中的緩慢降溫，以利在全局範圍內找到最佳解，於本研究用以搜尋物流車輛執行收貨服務時，能根據最低能耗為目標作路徑規劃。本文探討收貨順序限制對於能耗之影響，透過所設計基於最低能耗之VRP數學模型中，限制物流車之收貨順序需依貨物重量輕重依序收取，對固定8、10、14個客戶數分別搭配不同數量之電動物流車，分析有無載貨順序限制對能耗表現之影響，透過實驗結果得知，於8個客戶點時，分配3、4、5臺車輛進行收貨服務，在無限制載貨順序時，能耗較有限制載貨順序時能耗可改善0.07%-2.07%;於10個客戶點時，分配2、3、4臺車輛進行收貨服務，在無限制載貨順序時，能耗較有限制載貨順序時能耗可改善1.66%-14.17%;於14個客戶點時，分配3、4、5、6臺車輛進行收貨服務，在無限制載貨順序時，能耗較有限制載貨順序時能耗可改善0.08%-12.23%。比較使用SA於無限制載貨順序及RB此兩種路徑規劃策略之結果，於固定8個客戶數分別搭配3、4、5臺電動物流車，SA較RB可分別改善14-19%;於固定10個客戶數分別搭配2、3、4臺電動物流車，SA較RB可分別改善22-29%;於固定14個客戶數分別搭配3、4、5、6臺電動物流車，SA較RB可分別改善29-33%。未來將加入動態即時路徑規劃及其他限制條件，並應用於實際地圖模型作物流車隊最佳路徑規劃。
This study aimed to develop an optimized routing plan for a hybrid-electric-energy vehicle fleet based on the simulated annealing algorithm. Firstly, used the vehicle system data database from the Advanced Vehicle Simulator (Advisor), the existed vehicle parameters, electric motor data, energy storage system data, and vehicle transmission system were integrated with the logistics vehicle model, the Mitsubishi EV E300 van, to constructed the necessary full-vehicle system model. Subsequently, the selection of power source sizing and full-vehicle system energy management was carried out, resulting in the combination of a 34.28 kWh lithium battery and an 8.32 kWh LFP battery (lithium iron phosphate, LFP) as the hybrid energy source for the logistics electric vehicle. Finally, by iteratively adjusting distance and load parameters, the corresponding energy consumption was recorded, resulting in a distance/load/energy consumption multi-dimensional table.This study designed a mathematical model for the Vehicle Routing Problem (VRP) based on the objective of minimum energy consumption: The study focused on pre-route planning, exploring the route planning completed by the fleet before departing from a single logistics center, with the objective function of minimizing energy consumption. It investigated the VRP with and without pickup order constraints. Delivery vehicles depart from the logistics center, complete pickup services at each customer point sequentially, and return to the logistics center. Each customer point had a fixed pickup quantity, and each customer point was serviced only once by one vehicle, with no repeated services allowed.The simulated annealing algorithm was used for optimal route planning in this study. The algorithm generated neighboring solutions through multiple iterations and selects new solutions based on acceptance criteria, gradually seeking the route with the minimum energy consumption. The core of this algorithm lied in simulating the slow cooling process of physical annealing to facilitate finding the optimal solution globally, and it was used in this study to plan routes for logistics vehicles executing pickup services based on the objective of minimum energy consumption.This study examined the impact of pickup order constraints on energy consumption. Through the designed VRP mathematical model based on minimum energy consumption, it restricted the pickup order of logistics vehicles to be sequential according to the weight of the goods. For fixed numbers of 8, 10, and 14 customers, different quantities of electric logistics vehicles were paired to analyze the impact of pickup order constraints on energy performance. Experimental results showed that for 8 customer points, assigning 3, 4, and 5 vehicles to perform pickup services, the energy consumption without pickup order constraints is improved by 0.07%-2.07% compared to with pickup order constraints. For 10 customer points, assigning 2, 3, and 4 vehicles to perform pickup services, the energy consumption without pickup order constraints was improved by 1.66%-14.17% compared to with pickup order constraints. For 14 customer points, assigning 3, 4, 5, and 6 vehicles to perform pickup services, the energy consumption without pickup order constraints was improved by 0.08%-12.23% compared to with pickup order constraints. In the future, dynamic real-time route planning and other constraints will be added, and the model will be applied to actual map models for optimal route planning of logistics fleets.
This study aimed to develop an optimized routing plan for a hybrid-electric-energy vehicle fleet based on the simulated annealing algorithm. Firstly, used the vehicle system data database from the Advanced Vehicle Simulator (Advisor), the existed vehicle parameters, electric motor data, energy storage system data, and vehicle transmission system were integrated with the logistics vehicle model, the Mitsubishi EV E300 van, to constructed the necessary full-vehicle system model. Subsequently, the selection of power source sizing and full-vehicle system energy management was carried out, resulting in the combination of a 34.28 kWh lithium battery and an 8.32 kWh LFP battery (lithium iron phosphate, LFP) as the hybrid energy source for the logistics electric vehicle. Finally, by iteratively adjusting distance and load parameters, the corresponding energy consumption was recorded, resulting in a distance/load/energy consumption multi-dimensional table.This study designed a mathematical model for the Vehicle Routing Problem (VRP) based on the objective of minimum energy consumption: The study focused on pre-route planning, exploring the route planning completed by the fleet before departing from a single logistics center, with the objective function of minimizing energy consumption. It investigated the VRP with and without pickup order constraints. Delivery vehicles depart from the logistics center, complete pickup services at each customer point sequentially, and return to the logistics center. Each customer point had a fixed pickup quantity, and each customer point was serviced only once by one vehicle, with no repeated services allowed.The simulated annealing algorithm was used for optimal route planning in this study. The algorithm generated neighboring solutions through multiple iterations and selects new solutions based on acceptance criteria, gradually seeking the route with the minimum energy consumption. The core of this algorithm lied in simulating the slow cooling process of physical annealing to facilitate finding the optimal solution globally, and it was used in this study to plan routes for logistics vehicles executing pickup services based on the objective of minimum energy consumption.This study examined the impact of pickup order constraints on energy consumption. Through the designed VRP mathematical model based on minimum energy consumption, it restricted the pickup order of logistics vehicles to be sequential according to the weight of the goods. For fixed numbers of 8, 10, and 14 customers, different quantities of electric logistics vehicles were paired to analyze the impact of pickup order constraints on energy performance. Experimental results showed that for 8 customer points, assigning 3, 4, and 5 vehicles to perform pickup services, the energy consumption without pickup order constraints is improved by 0.07%-2.07% compared to with pickup order constraints. For 10 customer points, assigning 2, 3, and 4 vehicles to perform pickup services, the energy consumption without pickup order constraints was improved by 1.66%-14.17% compared to with pickup order constraints. For 14 customer points, assigning 3, 4, 5, and 6 vehicles to perform pickup services, the energy consumption without pickup order constraints was improved by 0.08%-12.23% compared to with pickup order constraints. In the future, dynamic real-time route planning and other constraints will be added, and the model will be applied to actual map models for optimal route planning of logistics fleets.
Description
Keywords
最佳路徑規劃, 車輛途程問題, 能量管理策略, 模擬退火演算法, Optimal Path Planning, Vehicle Routing Problem, Energy Management Strategy, Simulated Annealing Algorithm