Distributed forecasting and ant colony optimization for the bike-sharing rebalancing problem with unserved demands
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
prolekare.web.journal.doi_sk:
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 – Optimization – Machine learning algorithms – Machine learning – Pheromones – Decision trees – Insertion mutation
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
Článok vyšiel v časopise
PLOS One
2019 Číslo 12
- Metamizol jako analgetikum první volby: kdy, pro koho, jak a proč?
- Nejasný stín na plicích – kazuistika
- Masturbační chování žen v ČR − dotazníková studie
- Těžké menstruační krvácení může značit poruchu krevní srážlivosti. Jaký management vyšetření a léčby je v takovém případě vhodný?
- Fixní kombinace paracetamol/kodein nabízí synergické analgetické účinky
Najčítanejšie v tomto čísle
- Methylsulfonylmethane increases osteogenesis and regulates the mineralization of the matrix by transglutaminase 2 in SHED cells
- Oregano powder reduces Streptococcus and increases SCFA concentration in a mixed bacterial culture assay
- The characteristic of patulous eustachian tube patients diagnosed by the JOS diagnostic criteria
- Parametric CAD modeling for open source scientific hardware: Comparing OpenSCAD and FreeCAD Python scripts