目前，自行車共享系統已被廣泛地使用在全球各大城市中。自行車共享系統所面對的主要問題之一，是要重新平衡各站點之間的腳踏車數量，使得使用者的需求能夠盡可能的被滿足。為了進行重新平衡的動作，營運商通常會安排一個有數台卡車的車隊在站點之間來回。當重新平衡的動作是在夜間被進行時，此時使用者的需求通常會小到可以忽略，這被視為靜態自行車再平衡問題。本文中，我們提出一個部份需求滿足的容量限制分群演算法來縮減靜態自行車再平衡問題的問題規模。所提出的PDF3C演算法能夠發掘例外站點並將剩餘的站點分成數群，其中那些需求較大的站點可被不同的集群所納入。最後，我們的分群結果會被用在多車輛路徑最佳化中。實驗結果驗證了我們的PDF3C演算法優於現存方法。

Nowadays, bike sharing systems have been widely used in major cities around the world. One of the major challenges of bike sharing systems is to rebalance the number of bikes for each station such that user demands can be satisfied as much as possible. To execute rebalancing operations, operators usually have a fleet of vehicles to be routed through stations. When rebalancing operations are executing at nighttime, user demands usually are small enough to be ignored and this is regarded as the static bike rebalancing problem. In this paper, we propose a Partial Demand Fulfilling Capacity Constrained Clustering (PDF3C) algorithm to reduce the problem scale of the static bike rebalancing problem. The proposed PDF3C algorithm can discover outlier stations and group remaining stations into several clusters where stations having large demands can be included by different clusters. Finally, the clustering result will be applied to multi-vehicle route optimization. Experiment results verified that our PDF3C algorithm outperforms existing methods.

1. Raviv, T., Tzur, M., Forma, I.A.: Static repositioning in a bike-sharing system: models and solution approaches. EJTL. 2(3), 187-229 (2013).
2. Schuijbroek, J., Hampshire, R.C., van Hoeve, W.J.: Inventory rebalancing and vehicle routing in bike sharing systems. EJOR. 257(3), 992-1004 (2017).
3. Kloimüllner, C., Papazek, P., Hu, B., Raidl, G.R.: A Cluster-First Route-Second Approach for Balancing Bicycle Sharing Systems. In: Roberto, M.D., Franz, P., Alexis, Q.A. (eds.) EUROCAST 2015, LNCS, vol. 9520, pp. 439-446. Springer, Heidelberg (2015).
4. Forma, I.A., Raviv, T., Tzur, M.: A 3-step math heuristic for the static reposition-ing problem in bike-sharing systems. Transport. Res. B-Meth. 71(Supplement C), 230-247 (2015).
5. Liu, J., Sun, L., Chen, W., Xiong, H.: Rebalancing Bike Sharing Systems: A Multi-source Data Smart Optimization. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1005-1014, ACM (2016).
6. Ho, S.C., Szeto, W.Y.: Solving a static repositioning problem in bike-sharing systems using iterated tabu search. Transport. Res. D-Tr.E. 69(Supplement C), 180-198 (2014).
7. Chemla, D., Meunier, F., and Calvo, R. W.: Bike sharing systems: Solving the static rebalancing problem. Discrete Optim. 10(2), 120-149 (2013).
8. Gaspero, L.D., Rendl, A., Urli, T.: Constraint-based approaches for Balancing Bike Sharing Systems. In: Christian, S. (ed.) CP 2013, LNCS, vol. 8124, pp. 758-773. Springer, Heidelberg (2013).
9. Szeto, W.Y., Liu, Y., Ho, S. C.: Chemical reaction optimization for solving a static bike repositioning problem. Transport. Res. D-Tr.E. 47(Supplement C), 104-135 (2016).
10. Rainer-Harbach, M., Papazek, P., Raidl, G. R., Hu, B., Kloim ̈ullner, C.: PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems. J. Global Optim. 63(3), 597-629 (2015).
11. Papazek, P., Kloimüllner, C., Hu, B., Raidl, G.R.: Balancing Bicycle Sharing Systems: An Analysis of Path Relinking and Recombination within a GRASP Hybrid In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014, Part XIII, LNCS, vol. 8672, pp. 792-801. Springer, Heidelberg (2014).
12. Benchimol, M., Benchimol, P., Chappert, B., De La Taille, A., Laroche, F., Meunier, F., Robinet, L.: Balancing the stations of a self service “bike hire” system. RAIRO-Oper. Res. 45(1), 37-61 (2011).
13. Raviv, T., Kolka, O.: Optimal inventory management of a bike-sharing station. IIE Transactions 45(10), 1077-1093 (2013).
14. Meddin, R., DeMaio, P.: The bike sharing world map (2017). http://www. metrobike.net
15. Gurobi Optimization, Inc.: Gurobi Optimizer Reference Manual (2016). http://www.gurobi.com
16. Ho, S.C., Szeto, W.Y.: A hybrid large neighborhood search for the static multi-vehicle bike-repositioning problem. Transport. Res. B-Meth. 95(Supplement C), 340-363 (2017).