Distributed forecasting and ant colony optimization for the bike-sharing rebalancing problem with unserved demands

English version

Autoři: Yiwei Fan ^aff001; Gang Wang ^aff003; Xiaoling Lu ^aff001; Gaobin Wang ^aff004
Působiště autorů: Center for Applied Statistics, Renmin University of China, Beijing, China ^aff001; School of Statistics, Renmin University of China, Beijing, China ^aff002; Department of Decision & Information Sciences, Charlton College of Business, University of Massachusetts Dartmouth, MA, United States of America ^aff003; Invesco Great Wall Fund Management, Shenzhen, China ^aff004
Vyšlo v časopise: PLoS ONE 14(12)
Kategorie: Research Article
doi: https://doi.org/10.1371/journal.pone.0226204

Souhrn

Bike-sharing systems (BSS) have widely spread over many cities in the world as an environmentally friendly means to reduce air pollution and traffic congestion. This paper focuses on the bike-sharing rebalancing problem (BRP), which consists of two aspects: determining desired demands at each station and designing routes to redistribute bikes among stations. For the first task, we firstly apply the random forest, a very efficient machine learning algorithm, to forecast desired demands for each station, which can be easily implemented with distributed computing. For the second task, it belongs to the broad class of the vehicle routing problem with pickup and delivery (VRPPD). In most existing settings, all of the demands being strictly satisfied can lead to longer routes and add operational costs. In this paper, we propose a new model with unserved demands by relaxing demands satisfying constraints. Then, we design a distributed ant colony optimization (ACO) based algorithm with some specific modifications to increase its efficiency for the proposed model. We propose to use the percentage of average cost saving per bike as a metric to evaluate the performance of our method on cost-reducing and compare with existing methods and best-known values. Computational results on benchmarks show the advantage of our approach. Finally, we provide a real case study of BSS in Hangzhou, China, with insightful elaborations.

Klíčová slova:

Algorithms – Decision trees – Insertion mutation – Machine learning – Machine learning algorithms – Optimization – Pheromones

Zdroje

1. DeMaio P. Bike-sharing: History, Impacts, Models of Provision, and Future. Journal of Public Transportation. 2009;12(4):41–56. doi: 10.5038/2375-0901.12.4.3

2. Breiman L. Random Forests. Machine Learning. 2001;45(1):5–32. doi: 10.1023/A:1010933404324

3. Simchi-Levi D, Wu MX. Powering retailers’ digitization through analytics and automation. International Journal of Production Research. 2018;56(1-2):809–816. doi: 10.1080/00207543.2017.1404161

4. Dell’Amico M, Hadjicostantinou E, Iori M, Novellani S. The bike sharing rebalancing problem: Mathematical formulations and benchmark instances. Omega. 2014;45:7–19. doi: 10.1016/j.omega.2013.12.001

5. Berbeglia G, Cordeau JF, Gribkovskaia I, Laporte G. Static pickup and delivery problems: a classification scheme and survey. Top. 2007;15(1):1–31. doi: 10.1007/s11750-007-0015-2

6. Rixey R. Station-level forecasting of bikesharing ridership: Station Network Effects in Three US Systems. Transportation Research Record: Journal of the Transportation Research Board. 2013;(2387):46–55. doi: 10.3141/2387-06

7. Schuijbroek J, Hampshire RC, Van Hoeve WJ. Inventory rebalancing and vehicle routing in bike sharing systems. European Journal of Operational Research. 2017;257(3):992–1004. doi: 10.1016/j.ejor.2016.08.029

8. Hernández-Pérez H, Salazar-González JJ. A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discrete Applied Mathematics. 2004;145(1):126–139. doi: 10.1016/j.dam.2003.09.013

9. Sampaio AH, Urrutia S. New formulation and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks. International Transactions in Operational Research. 2017;24(1-2):77–98. doi: 10.1111/itor.12261

10. Erdoğan G, Battarra M, Calvo RW. An exact algorithm for the static rebalancing problem arising in bicycle sharing systems. European Journal of Operational Research. 2015;245(3):667–679. doi: 10.1016/j.ejor.2015.03.043

11. Borgnat P, Abry P, Flandrin P, Robardet C, Rouquier JB, Fleury E. Shared bicycles in a city: A signal processing and data analysis perspective. Advances in Complex Systems. 2011;14(03):415–438. doi: 10.1142/S0219525911002950

12. Chemla D, Meunier F, Calvo RW. Bike sharing systems: Solving the static rebalancing problem. Discrete Optimization. 2013;10(2):120–146. doi: 10.1016/j.disopt.2012.11.005

13. Lenstra JK, Kan AHGR. Complexity of vehicle routing and scheduling problems. Networks. 1981;11(2):221–227. doi: 10.1002/net.3230110211

14. Bianchessi N, Righini G. Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Computers & Operations Research. 2007;34(2):578–594. doi: 10.1016/j.cor.2005.03.014

15. Koç Ç, Laporte G. Vehicle routing with backhauls: Review and research perspectives. Computers & Operations Research. 2018;91:79–91. doi: 10.1016/j.cor.2017.11.003

16. Kloimüllner C, Papazek P, Hu B, Raidl GR. A cluster-first route-second approach for balancing bicycle sharing systems. In: International Conference on Computer Aided Systems Theory. Springer; 2015. p. 439–446.

17. Torki A, Somhon S, Enkawa T. A competitive neural network algorithm for solving vehicle routing problem. Computers & Industrial Engineering. 1997;33(3):473–476. doi: 10.1016/S0360-8352(97)00171-X

18. Montané FAT, Galvao RD. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research. 2006;33(3):595–619. doi: 10.1016/j.cor.2004.07.009

19. Euchi J. Genetic scatter search algorithm to solve the one-commodity pickup and delivery vehicle routing problem. Journal of Modelling in Management. 2017;12(1):2–18. doi: 10.1108/JM2-10-2015-0077

20. Wang C, Mu D, Zhao F, Sutherland JW. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Computers & Industrial Engineering. 2015;83:111–122. doi: 10.1016/j.cie.2015.02.005

21. Ho SC, Szeto W. Solving a static repositioning problem in bike-sharing systems using iterated tabu search. Transportation Research Part E: Logistics and Transportation Review. 2014;69:180–198. doi: 10.1016/j.tre.2014.05.017

22. Dell’Amico M, Iori M, Novellani S, Stützle T. A destroy and repair algorithm for the bike sharing rebalancing problem. Computers & Operations Research. 2016;71:149–162. doi: 10.1016/j.cor.2016.01.011

23. Cruz F, Subramanian A, Bruck BP, Iori M. A heuristic algorithm for a single vehicle static bike sharing rebalancing problem. Computers & Operations Research. 2017;79:19–33. doi: 10.1016/j.cor.2016.09.025

24. Dorigo M, Maniezzo V, Colorni A. Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B. 1996;26(1):29–41. doi: 10.1109/3477.484436

25. Dorigo M, Gambardella LM. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions ON Evolutionary Computation. 1997;1(1):53–66. doi: 10.1109/4235.585892

26. Ciro GC, Dugardin F, Yalaoui F, Kelly R. Open shop scheduling problem with a multi-skills resource constraint: a genetic algorithm and an ant colony optimisation approach. International Journal of Production Research. 2016;54(16):4854–4881. doi: 10.1080/00207543.2015.1126371

27. Zhang S, Wong TN. Flexible job-shop scheduling/rescheduling in dynamic environment: a hybrid MAS/ACO approach. International Journal of Production Research. 2017;55(11):3173–3196. doi: 10.1080/00207543.2016.1267414

28. Bullnheimer B, Hartl RF, Strauss C. An improved Ant System algorithm for theVehicle Routing Problem. Annals of Operations Research. 1999;89:319–328. doi: 10.1023/A:1018940026670

29. Bell JE, McMullen PR. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics. 2004;18(1):41–48. doi: 10.1016/j.aei.2004.07.001

30. Mazzeo S, Loiseau I. An Ant Colony Algorithm for the Capacitated Vehicle Routing. Electronic Notes in Discrete Mathematics. 2004;18:181–186. doi: 10.1016/j.endm.2004.06.029

31. Lee CY, Lee ZJ, Lin SW, Ying KC. An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem. Applied Intelligence. 2010;32(1):88–95. doi: 10.1007/s10489-008-0136-9

32. Yu B, Yang ZZ, Yao B. An improved ant colony optimization for vehicle routing problem. European journal of operational research. 2009;196(1):171–176. doi: 10.1016/j.ejor.2008.02.028

33. Gajpal Y, Abad P. An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup. Computers & Operations Research. 2009;36(12):3215–3223. doi: 10.1016/j.cor.2009.02.017

34. Falcon R, Li X, Nayak A, Stojmenovic I. The one-commodity traveling salesman problem with selective pickup and delivery: An ant colony approach. In: Evolutionary Computation (CEC), 2010 IEEE Congress on. IEEE; 2010. p. 1–8.

35. Çatay B. A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications. 2010;37(10):6809–6817. doi: 10.1016/j.eswa.2010.03.045

36. Di Gaspero L, Rendl A, Urli T. A hybrid ACO+CP for balancing bicycle sharing systems. In: International Workshop on Hybrid Metaheuristics. Springer; 2013. p. 198–212.

37. Papazek P, Raidl GR, Rainer-Harbach M, Hu B. A PILOT/VND/GRASP hybrid for the static balancing of public bicycle sharing systems. In: International Conference on Computer Aided Systems Theory. Springer; 2013. p. 372–379.

38. Raviv T, Tzur M, Forma IA. Static repositioning in a bike-sharing system: models and solution approaches. EURO Journal on Transportation and Logistics. 2013;2(3):187–229. doi: 10.1007/s13676-012-0017-6

39. Doerner K, Gutjahr WJ, Hartl RF, Strauss C, Stummer C. Pareto ant colony optimization: A metaheuristic approach to multiobjective portfolio selection. Annals of operations research. 2004;131(1-4):79–99. doi: 10.1023/B:ANOR.0000039513.99038.c6

40. Alaya I, Solnon C, Ghedira K. Ant colony optimization for multi-objective optimization problems. In: Tools with Artificial Intelligence, 2007. ICTAI 2007. 19th IEEE International Conference on. vol. 1. IEEE; 2007. p. 450–457.

41. Hernández-Pérez H, Salazar-González JJ. Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transportation Science. 2004;38(2):245–255. doi: 10.1287/trsc.1030.0086

42. Feng Y, Wang S. A forecast for bicycle rental demand based on random forests and multiple linear regression. In: 2017 IEEE/ACIS 16th International Conference on Computer and Information Science (ICIS). IEEE; 2017. p. 101–105.

43. Hastie T, Tibshirani R, Friedman J. The Elements of Statistical Learning. 2nd ed. New York, USA: Springer New York Inc.; 2001.

44. Stützle T, Hoos HH. MAX–MIN ant system. Future generation computer systems. 2000;16(8):889–914. doi: 10.1016/S0167-739X(00)00043-1

45. Ellabib I, Calamai P, Basir O. Exchange strategies for multiple Ant Colony System. Information Sciences. 2007;177(5):1248–1264. doi: 10.1016/j.ins.2006.09.016

46. Yu B, Yang ZZ, Xie JX. A parallel improved ant colony optimization for multi-depot vehicle routing problem. Journal of the Operational Research Society. 2011;62(1):183–188. doi: 10.1057/jors.2009.161

47. Zhou Y, He F, Hou N, Qiu Y. Parallel ant colony optimization on multi-core SIMD CPUs. Future Generation Computer Systems. 2018;79:473–487. doi: 10.1016/j.future.2017.09.073

48. Stützle T. Parallelization strategies for Ant Colony Optimization. In: Parallel Problem Solving from Nature—PPSN. Berlin, Heidelberg: Springer Berlin Heidelberg; 1998. p. 722–731.

49. Bullnheimer B, Kotsis G, Strauß C. Parallelization strategies for the ant system. In: High Performance Algorithms and Software in Nonlinear Optimization. Boston, MA: Springer US; 1998. p. 87–100.

50. Hadian A, Shahrivari S, Minaei-Bidgoli B. Fine-grained Parallel Ant Colony System for Shared-Memory Architectures. International Journal of Computer Applications. 2012;53(8):8–13. doi: 10.5120/8439-2223

51. Yang Z, Yu B, Cheng C. A Parallel Ant Colony Algorithm for Bus Network Optimization. Computer-Aided Civil and Infrastructure Engineering. 2006;22(1):44–55. doi: 10.1111/j.1467-8667.2006.00469.x

52. Ishwaran H, Kogalur UB, Gorodeski EZ, Minn AJ, Lauer MS. High-dimensional variable selection for survival data. Journal of the American Statistical Association. 2010;105(489):205–217. doi: 10.1198/jasa.2009.tm08622

Distributed forecasting and ant colony optimization for the bike-sharing rebalancing problem with unserved demands

Souhrn

Klíčová slova:

Zdroje

PLOS One

Současné pohledy na riziko v parodontologii

Svět praktické medicíny 3/2024 (znalostní test z časopisu)

Kardiologické projevy hypereozinofilií

Střevní příprava před kolonoskopií

Aktuální možnosti diagnostiky a léčby litiáz