隨機需求下租賃自行車佈署模式暨求解演算法之研究

NCUIR > Engineering College > Graduate Institute of Civil Engineering > Electronic Thesis & Dissertation > Item 987654321/64767

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/64767

Title:	隨機需求下租賃自行車佈署模式暨求解演算法之研究
Authors:	王銘鴻;Wang,Ming-hung
Contributors:	土木工程學系
Keywords:	租賃自行車;佈署;隨機需求;時空網路;啟發解法;多重貨物網路流動問題;Bicycle Sharing System;Deployment;Stochastic demand;Time-space network;Heuristic;Multiple commodity network flow problem
Date:	2014-07-11
Issue Date:	2014-10-15 14:23:03 (UTC+8)
Publisher:	國立中央大學
Abstract:	由於人口快速增加、科技不斷創新與工業活動蓬勃發展，促使溫室效應增強造成全球平均溫度的上升。因此人們環保意識提升，各國政府除推行大眾運輸政策外，亦發展租賃自行車之共享系統，可提供民眾最後一哩路亦能達到節能減碳之效果。而目前租賃自行車之佈署仍以人工經驗方式，未能以系統最佳化觀點進行佈署，除導致資源浪費，更造成服務率不佳。且實際營運時隨機租賃需求造成的擾動極大，使得佈署結果未能達最佳性。有鑑於此，本研究針對隨機需求下以服務最大化與利潤最大化等目標，建構兩個租賃自行車佈署模式，期能給予營運者決策佈署車輛之參考，並提高服務率與營運利潤。本研究藉由時空網路流動技巧建立二個隨機性需求自行車佈署模式，以定式租賃自行車流動之情形。本研究並修改隨機性需求為平均需求，建立其對應之確定性需求自行車佈署模式，此等模式皆為NP-hard問題。於求解方法上，兩個確定性模式皆可以C++程式語言配合數學規劃CPLEX進行模式求解，本研究兩個隨機性模式問題規模皆為龐大，無法直接使用數學規劃軟體求解。緣此，本研究發展一啟發式演算法有效地進行求解問題，並利用隨機性問題相關理論以評估模式之優劣與演算法之實用績效。最後，參考國內一租賃自行車業者的營運資料及合理假設產生範例，進行範例測試並對不同參數進行敏感度分析，測試結果顯示各模式與演算法均表現良好，可提供租賃自行車業者作為佈署決策之參考。 ;Due to the population growth and economic progress, the greenhouse effect is getting worse. In order to protect the environment, governments push not only the public transport policy, but also the bike-sharing system. In practice, the decision maker is used to deploy the rental bicycles based on his/her experience, which lakes the perspective of system optimization, in addition to wasting of resources. In actual operations, the demand is wildly changed leading to the deployment of rental bicycles that loses its optimality. Therefore, this research considers the stochastic demand occurring in actual operations, with the aim of maximizing profits and service volume, to construct two rental bike deployment models. With thesse models, the operator can effectively deploy the retinal bikes and improve the level of service and operating profits. In this research, the time-space network flow technique is used to show the potential movement of rental bikes under stochastic demand and to construct two stochastic demand and deployment models. We further consider the average demand to construct two deterministic demand models. These four models are formulated as integer multiple-commodity network flow problems, which are characterized as NP-hard. We utilize C computer language, coupled with the CPLEX mathematics programming solver, to solve the two deterministic models. For the two stochastic models, since their problem sizes are too huge to be directly solved by using mathematical programming software. Therefore, we developed a solution algorithm to efficiently solve the two stochastic models. We also utilized EVPI and VSS to evaluate the performance of these two stochastic models. Finally, we performed a case study using data from a bicycle rental corporation. The test results show that the proposed models and solution algorithm could be useful for deploying the rental bicycles.
Appears in Collections:	[Graduate Institute of Civil Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	642	View/Open

社群 sharing

Loading...