隨著公共自行車路網的擴大與使用人數增加，熱門時段容易出現缺車缺位狀況。因此，如何在一區域內進行適切的調度，並在最低運輸成本或最少供需失調的狀況下滿足用路人的需求即為一個重要課題。
　　過去公共自行車調度相關研究多為混合不同巨集啟發式演算法，以同時具收送貨問題之車輛途程方式求解。本研究提出公共自行車調度分區之概念，結合區位途程問題，同時決定最少調度分區、最少運補車輛數與最小途程成本。規劃之數學模型因限制式中存有最佳化問題且結果相互影響，故分為三階層並使用模擬退火法求解。
　　由第三層數學模型之測試範例可得知，在各租借站總需求為正的情況下，以缺車數最多之需求作為起始載運量有最少行駛距離；各租借站總需求為負的情況下，運補車滿載出發有最少行駛距離。
　　本研究以台北市YouBike實際路網及座標資料作為數值範例，探討調度中心設置、運補車輛配置及運補途程成本間之權衡(trade-off)，尋求最佳解。考量調度中心最長服務時間限制、運補車容量與最長服務時間限制、時窗限制與懲罰成本等因素，分別設計5個情境，進行分析並探討對於調度分區、運補車配置數以及車輛途程之影響。結果顯示，違反時窗限制雖可以減少派遣車輛數，但因服務品質下降致產生龐大的懲罰成本；增加運補車容量會提高車輛購置成本，但服務租借站數的增加可減少派遣車輛數而降低車輛購置成本；擴大調中心服務範圍雖會增加運補車輛的配置，但可減少調度中心之建置成本。藉由實證分析結果驗證模型具可操作性，測試範例展現不同需求下之最佳起始載運車輛數。研究之成果可供相關營運者在規劃方面以系統化角度進行調度策略之研擬，提升運補效率。

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.

目錄
第一章　緒論	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

參考文獻
1.	白詩滎(2012)，「臺北公共自行車使用行為特性分析與友善環境建構之研究」，國立政治大學地政研究所學位論文。
2.	池昆霖(2006)，「區位途程與易腐性商品排程之研究」，中央大學土木工程學系學位論文。
3.	周荻傑(2012)，「應用地理知悉與車輛途程技術之公用自行車調度系統」，逢甲大學資訊電機工程碩士在職專班碩士論文。
4.	林緯帆(2013)，「探討激勵機制設計對多站點自行車租賃服務系統的影響」，屏東科技大學工業管理系所學位論文。
5.	張勻威(2011)，「自行車租賃佈署暨調度最佳之化之研究」，中央大學土木工程學系學位論文。
6.	張立蓁(2010)，「都會區公共自行車租借系統之設計與營運方式研究」，成功大學工業與資訊管理學系學位論文。
7.	張易晟(2014)，「 B2C 電子商務下都會區配送模型之研究」，臺灣大學工業工程學研究所學位論文。
8.	陳俊成(2008)，「營建工地土石方調派最佳化模式之研究」，中央大學土木工程學系碩士在職專班學位論文。
9.	陳柏僑(2014)，「公共自行車租賃站使用需求之研究-以高雄市公共自行車為例」，臺灣大學土木工程學研究所學位論文。
10.	楊大輝、林振榮、顏亞琪(2015)，「公共腳踏車租借站點及路網之設計」，運輸學刊，第二十七卷第一期，頁29-48。
11.	楊秉蒼、呂淑鈴(2000)，「以類神經網作資源受限營建土方調配最適化之研究」，Journal of Cheng-Shiu Institute of Technology(正修學報)Vol.13，pp.69-78
12.	楊瑞宇(2012)，「穩健公共自行車租用系統車輛配置模式」，臺北科技大學資訊與運籌管理研究所學位論文。
13.	趙文(2014)，「公共自行車租賃站區位配置-以高雄市為例」，國立高雄第一科技大學運籌管理研究所學位論文。
14.	賴怡君(2006)，「土方運輸卡車車隊安排模式之研究」，朝陽科技大學營建工程系博碩士論文。
15.	簡德和(2004)，「開發區域內土方工程最佳調派決策模式之研究」，中央大學土木工程學系在職專班博碩士論文。
16.	顧梓承(2002)，「土石方工程調派最佳決策模式之研究」，中央大學土木工程學系在職專班博碩士論文。
1.	Branco, I. M., & Coelho, J. D. (1990). The Hamiltonian p-median problem. European Journal of Operational Research, 47(1), 86-95. 
2.	Contardo, C., Morency, C., & Rousseau, L. M. (2012). Balancing a dynamic public bike-sharing system (Vol. 4). CIRRELT. 
3.	Rudloff, C., & Lackner, B. (2013). Modeling demand for bicycle sharing systems–neighboring stations as a source for demand and a reason for structural breaks. Tech. rep, Austrian Institute of Technology, Vienna, Austria. 
4.	Kloimüllner, C., Papazek, P., Hu, B., & Raidl, G. R. (2014). Balancing bicycle sharing systems: An approach for the dynamic case. In Evolutionary Computation in Combinatorial Optimisation (pp. 73-84). Springer Berlin Heidelberg. 
5.	Henderson, D., Vaughan, D. E., Jacobson, S. H., Wakefield, R. R., & Sewell, E. C. (2003). Solving the shortest route cut and fill problem using simulated annealing. European Journal of Operational Research, 145(1), 72-84. 
6.	Fukunaga, K., & Short, R. D. (1978). Generalized clustering for problem localization. Computers, IEEE Transactions on, 100(2), 176-181. 
7.	Erdoğan, G., Laporte, G., & Calvo, R. W. (2014). The static bicycle relocation problem with demand intervals. European Journal of Operational Research, 238(2), 451-457. 
8.	Hernández-Pérez, H., & Salazar-González, J. J. (2004). A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discrete Applied Mathematics, 145(1), 126-139. 
9.	Hernández-Pérez, H., Rodríguez-Martín, I., & Salazar-González, J. J. (2009). A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem. Computers & Operations Research, 36(5), 1639-1645. 
10.	Karaoglan, I., Altiparmak, F., Kara, I., & Dengiz, B. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40(4), 465-477. 
11.	Nassar, K., & Hosny, O. (2011). Solving the Least-Cost Route Cut and Fill Sequencing Problem Using Particle Swarm. Journal of Construction Engineering and Management, 138(8), 931-942. 
12.	Caggiani, L., & Ottomanelli, M. (2013). A dynamic simulation based model for optimal fleet repositioning in bike-sharing systems. Procedia-Social and Behavioral Sciences, 87, 203-210. 
13.	Caggiani, L., & Ottomanelli, M. (2012). A modular soft computing based method for vehicles repositioning in bike-sharing systems. Procedia-Social and Behavioral Sciences, 54, 675-684. 
14.	Liao, K., & Guo, D. (2008). A Clustering‐Based Approach to the Capacitated Facility Location Problem1. Transactions in GIS, 12(3), 323-339.
15.	Dell'Amico, M., Hadjicostantinou, E., Iori, M., & Novellani, S. (2014). The bike sharing rebalancing problem: Mathematical formulations and benchmark instances. Omega, 45, 7-19. 
16.	Madsen, O. B. (1983). Methods for solving combined two level location-routing problems of realistic dimensions. European Journal of Operational Research, 12(3), 295-301. 
17.	Mehrjerdi, Y. Z., & Nadizadeh, A. (2013). Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands. European Journal of Operational Research, 229(1), 75-84.
18.	Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5), 377-386. 
19.	Murray, A. T., & Gerrard, R. A. (1997). Capacitated service and regional constraints in location-allocation modeling. Location Science, 5(2), 103-118. 
20.	Mladenović, N., Urošević, D., & Ilić, A. (2012). A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem. European Journal of Operational Research, 220(1), 270-285. 
21.	Papazek, P., Raidl, G. R., Rainer-Harbach, M., & Hu, B. (2013). A PILOT/VND/GRASP hybrid for the static balancing of public bicycle sharing systems. In Computer Aided Systems Theory-EUROCAST 2013 (pp. 372-379). Springer Berlin Heidelberg. 
22.	Vogel, P., Saavedra, B. A. N., & Mattfeld, D. C. (2014). A hybrid metaheuristic to solve the resource allocation problem in bike sharing systems. In Hybrid Metaheuristics (pp. 16-29). Springer International Publishing. 
23.	Papazek, P., Kloimüllner, C., Hu, B., & Raidl, G. R. (2014). Balancing Bicycle Sharing Systems: An Analysis of Path Relinking and Recombination within a GRASP Hybrid. In Parallel Problem Solving from Nature–PPSN XIII (pp. 792-801). Springer International Publishing. 
24.	Perl, J., & Daskin, M. S. (1985). A warehouse location-routing problem. Transportation Research Part B: Methodological, 19(5), 381-396. 
25.	Easa, S. M. (1988). Earthwork allocations with linear unit costs. Journal of Construction Engineering and Management, 114(4), 641-655. 
26.	Benarbia, T., Labadi, K., Darcherif, A. M., Barbot, J. P., & Omari, A. (2013, October). Real-time inventory control and rebalancing in bike-sharing systems by using a stochastic Petri net model. In Systems and Control (ICSC), 2013 3rd International Conference on (pp. 583-589). IEEE.
27.	Vincent, F. Y., Lin, S. W., Lee, W., & Ting, C. J. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58(2), 288-299. 
28.	Vincent, F. Y., & Lin, S. W. (2014). Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery. Applied Soft Computing, 24, 284-290. 
29.	Wang, C., Mu, D., Zhao, F., & Sutherland, J. W. (2015). A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Computers & Industrial Engineering, 83, 111-122.