[[alternative]]Location routing model of public bike-sharing system

碩士[[abstract]]隨著公共自行車路網的擴大與使用人數增加，熱門時段容易出現缺車缺位狀況。因此，如何在一區域內進行適切的調度，並在最低運輸成本或最少供需失調的狀況下滿足用路人的需求即為一個重要課題。 過去公共自行車調度相關研究多為混合不同巨集啟發式演算法，以同時具收送貨問題之車輛途程方式求解。本研究提出公共自行車調度分區之概念，結合區位途程問題，同時決定最少調度分區、最少運補車輛數與最小途程成本。規劃之數學模型因限制式中存有最佳化問題且結果相互影響，故分為三階層並使用模擬退火法求解。 由第三層數學模型之測試範例可得知，在各租借站總需求為正的情況下，以缺車數最多之需求作為起始載運量有最少行駛距離；各租借站總需求為負的情況下，運補車滿載出發有最少行駛距離。 本研究以台北市YouBike實際路網及座標資料作為數值範例，探討調度中心設置、運補車輛配置及運補途程成本間之權衡(trade-off)，尋求最佳解。考量調度中心最長服務時間限制、運補車容量與最長服務時間限制、時窗限制與懲罰成本等因素，分別設計5個情境，進行分析並探討對於調度分區、運補車配置數以及車輛途程之影響。結果顯示，違反時窗限制雖可以減少派遣車輛數，但因服務品質下降致產生龐大的懲罰成本；增加運補車容量會提高車輛購置成本，但服務租借站數的增加可減少派遣車輛數而降低車輛購置成本；擴大調中心服務範圍雖會增加運補車輛的配置，但可減少調度中心之建置成本。藉由實證分析結果驗證模型具可操作性，測試範例展現不同需求下之最佳起始載運車輛數。研究之成果可供相關營運者在規劃方面以系統化角度進行調度策略之研擬，提升運補效率。[[abstract]] The expanding network of public bike-sharing system and increasing number of users leads to imbalances in the distribution of bikes causing full or empty station, especially during peak hours. Hence, bike sharing systems need to be properly rebalanced to meet the demand of users and to operate successfully. Literatures showed several hybrid meta-heutistics to solve Vehicle Routing Problem with Simultaneously Pickup and Delivery. In this study, we present a concept of bike distribution area and combine Location Routing Problem, for determining the least number of distribution centers and vehicles, as well as minimum routing cost simultaneously. The proposed model have an optimization problem in each constraint, each results are interdependence, hence is decomposed into three sub-problems and solved by Simulated Annealing Algorithms. The test example in model level three shows that if the total demand for each stations is positive, the minimum demand as the vehicle initial carry bikes cause minimum routing distance. If the total demand for each station is negative, the loaded vehicles result in minimum routing distance. In this study, we use the reality network and coordinate of Taipei YouBike as a numerical example, discussing the trade-off between location of distribution centers, number of vehicles and routing cost. Crucial factors are longest service time of distribution centers and vehicles, vehicles capacity, time window and penalty cost. It is therefore we design five scenarios respectively, discussing the effect on distribution centers, number of vehicles and routing cost. The result shows that it can decrease vehicles by breaking time window, but resulting in lower service level and huge penalty cost. Enhance vehicle capacity leads to a higher vehicle purchase cost, but the increasing numbers of service stations can decrease the number of vehicles. Enlarge distribution centers service scale can increase the number of vehicles, though reducing building cost of distribution centers. The test example shows the optimal vehicle initial carry bikes on different demand, and the proposed model is proved to be operable, therefore can be used by relevant operators for planning dispatch strategy systematically to improve operation efficiency.[[tableofcontents]]目錄 第一章 緒論 1 1.1 研究背景與動機 1 1.2 研究目的 3 1.3 研究範圍與對象 4 1.4 研究流程 4 第二章 文獻回顧 6 2.1 國內有關公共自行車之研究 6 2.2 國外對於自行車運補之研究 8 2.2.1 單一貨物的收送貨車輛路徑問題 8 2.2.2 靜態平衡 9 2.2.3 動態平衡 10 2.3 土方平衡之定義與研究 11 2.3.1 土方平衡定義 11 2.3.2 國內土方平衡相關之研究 11 2.3.3 國外土方平衡相關之研究 12 2.4 區位途程 13 2.4.1 設施區位與最大涵蓋區位問題 14 2.4.2 車輛途程問題 16 2.4.3 區位途程問題 19 2.5 模擬退火法 25 2.6 文獻小結 26 第三章 模式建構 28 3.1 問題描述 28 3.2 模型建立 30 3.2.1 第三層數學模型 33 3.2.2 第二層數學模型 35 3.2.3 第一層數學模型 36 第四章 求解演算法 37 4.1 模型演算與求解步驟 37 4.2 第三層模型求解策略 40 4.2.1 節省法 40 4.2.2 測試範例 43 4.2.3 小結 45 4.3 第二層模型求解策略 46 4.3.1 測試範例 48 4.3.2 小結 51 4.4 第一層模型求解策略 51 4.4.1 模擬退火法 52 4.4.2 測試範例 54 4.4.3 小結 55 第五章 數值範例 56 5.1 路網基本資料 56 5.1.1 範例假設 56 5.1.2 測試範例之控制變數參數值 58 5.2 執行結果 60 5.2.1 分區數 60 5.2.2 運補車輛數與途程分析 62 5.3 敏感度分析 69 5.3.1 情境2 69 5.3.2 情境3 74 5.3.2 情境4 81 5.3.3 情境5 84 5.4 小結 91 第六章 結論與建議 93 6.1 結論 93 6.2 建議 95 參考文獻 97 附錄一 租借站資料 102 附錄二 程式碼 108 表目錄 表2-1 2007-2013年每年有關區位途程問題主要研究方向的論文數 13 表2-2 常見設施區位整理表 16 表2-3 區位途程問題分類 20 表2-4 土方平衡與公共自行車調度之關係 27 表4-1 測試範例座標與需求 43 表4-2 各範例不同起始車輛數設定之途程計算結果 44 表4-4 各分區之服務租借站 49 表4-5 初始途程 49 表4-6 計算最少車輛數 50 表4-7 確定車輛數後之途程 50 表4-8 途程改善 50 表4-9 各區計算過程總成本比較 51 表4-10 迭代5次之分區結果 55 表5-1 各情境參數設定 60 表5-2 情境1執行模擬退火法之分區數與最小總成本 61 表5-3 情境1各溫度層最佳目標值 64 表5-4 情境1分區狀況 65 表5-5 情境1車輛途程 66 表5-6 情境1總成本 69 表5-7 情境2車輛途程 71 表5-8 情境2總成本 74 表5-9 情境1與情境2綜合比較 74 表5-10 情境3車輛途程 76 表5-11 情境3-1總成本 79 表5-12 情境1與情境3-1綜合比較 79 表5-13 情境3-2違反時窗總成本 79 表5-14 情境3是否違反時窗綜合比較 80 表5-15 情境2與情境3-2綜合比較 80 表5-16 情境4車輛途程 82 表5-17 情境4總成本 84 表5-18 情境1與情境4綜合比較比較 84 表5-19 情境2各溫度層最佳目標值 86 表5-20 情境5分區狀況 87 表5-21 情境5車輛途程 88 表5-22 情境5總成本 90 表5-23 情境1與情境5綜合比較 91 表5-24 情境綜合比較 92 圖目錄 圖1-1 研究流程圖 5 圖2-1 節省法示意圖 18 圖2-2a 設施區位問題(決定場站位置) 21 圖2-2b 區位途程問題(決定場站位置與車輛途程) 21 圖2-2c 雙階段設施區位問題(決定製造廠與倉儲位置) 21 資料來源：池昆霖(2006) 22 圖2-2d 雙階段設施區位途程問題(決定製造廠、倉儲位置與車輛途程) 22 圖3-1 設施區位、車輛數與路線的關係圖 29 圖3-2 多場站車輛途程示意圖 30 圖3-3 區位途程示意圖 30 圖4-1 模型演算流程圖 37 圖4-2 模型求解流程圖 38 圖4-3 求解前後對照圖 40 圖4-4 節省法法演算流程 42 圖4-4 路線調整演算流程 48 圖4-5 分區演算流程 53 圖4-6a 模擬退火法演算分區示範圖 54 圖4-6b 模擬退火法演算分區示範圖 54 圖5-1 情境1執行模擬退火法之分區數與最小總成本變化圖 62 圖5-2 各情境最適分區數 62 圖5-3 情境1個溫度層總成本變化圖 63 圖5-4 情境2各溫度層總成本變化圖 85[[note]]學號: 602660333, 學年度: 10