考慮碳排放之短租車調度

Abstract

這份研究探討考慮碳排放的車輛調度問題。對傳統租車公司而言，各站點的不同需求可能造成車輛不平衡的狀況，因此需要適當的車輛調度計畫，以接受更多訂單、賺取更多收益。隨著環境意識的提升，租車公司在營運計畫中考慮碳排放量愈來愈重要。在此研究中，租車公司除了具有預先指定車型的非彈性訂單外，也考慮未預先指定車型的彈性訂單，增加了問題的複雜程度。此研究的目標是協助決策者決定接受哪些訂單、如何將車輛分配給訂單，以及車輛調度的策略，在考慮碳排放量的狀況下盡可能最大化利潤，以同時實現盈利與環境永續目標。 為解決此問題，我們建構一個整數規劃（integer program）模型，考慮多種碳排放量的車型，並具備將車型分配給彈性訂單的機制。彈性訂單為不預先指定車型，且能接受任何車型的訂單。雖然整數規劃模型可以確保問題得到最佳解，但整數規劃模型相當耗時，因此，我們設計以時間-空間網路模型（time-space network model）為基礎的解決方案。若所有訂單都為有預先指定車型的非彈性訂單，時間-空間網絡模型能快速獲得與整數規劃模型相同的最佳解；若至少包含一張彈性訂單，我們使用兩種方法為這些彈性訂單分配車型，生成多組方案透過時間-空間網絡模型求解，以獲得近似最佳解。透過數值實驗，實驗顯示我們提出的方法能夠得到近似最佳解，幫助決策者在賺取利潤與減少碳排放量間取得平衡。

In this study, we address the rental car relocation problem considering carbon emissions. This problem arises due to imbalances in car demand across different stations in a traditional rental car company. With increasing environmental awareness, it is important for companies to consider carbon emissions in their operations. In addition to inflexible orders with pre-assigned car types, we also consider flexible orders, where car types are not pre-assigned, adding complexity to the problem. Our goal is to help decision-makers determine order acceptance, car assignments to orders, and vehicle relocation strategies to optimize business operations and achieve both economic and environmental goals. To solve this problem, we develop an integer programming (IP) model that accommodates multiple car types with varying carbon emission levels and includes a mechanism for assigning car types to flexible orders. Due to the time-consuming nature of solving the IP model, we design a solution approach based on the time-space network (TSN) model to address our problem. For instances involving only inflexible orders, the TSN model allows us to rapidly obtain optimal solutions matching those of the IP model. For instances containing at least one flexible order, we apply two methods to generate several assignments for these orders and then solve the TSN model with these assignments to attain near-optimal solutions. Our numerical experiments demonstrate that these methods achieve near-optimal solutions in reasonable time. Our approach balances profitability and environmental impact by considering carbon emissions.