An adaptive tabu search algorithm embedded with iterated local search and route elimination for the bike repositioning and recycling problem. (English) Zbl 1458.90156
Summary: The bike repositioning and recycling problem (BRRP) is significant to develop a sustainable bike-sharing system and can effectively reduce the imbalance between demand and supply. This study investigates the static repositioning and recycling problem of a bike-sharing system, which is formulated as an integer linear programming model. The BRRP is a variant of the multi-depot simultaneous pickup and delivery problem with multi-commodity demand. To solve the proposed model, an adaptive tabu search (ATS) algorithm combined with six neighborhood structures is developed. Moreover, an iterated local search (ILS) and a route elimination operator are both embedded to reduce the number of routes. The performance of the proposed ATS is evaluated by comparing it with tabu search (TS) and variable neighborhood search (VNS). The experimental results show that the proposed algorithm performs better than TS and VNS in terms of the solution quality. The proposed ATS was used to analyze the bicycle system in New York City. Finally, a free solver is developed for the bike repositioning and recycling problem, which is named the BRRP Solver.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
bike-sharing system; bike repositioning and recycling problem; adaptive tabu search algorithm; BRRP solverReferences:
| [1] | Alvarez-Valdes, R.; Belenguer, J. M.; Benavent, E.; Bermudez, J. D.; Muñoz, F.; Vercher, E.; Verdejo, F., Optimizing the level of service quality of a bike-sharing system, Omega, 62, 163-175 (2016) |
| [2] | Baldacci, R.; Bartolini, E.; Mingozzi, A., An exact algorithm for the pickup and delivery problem with time windows, Oper. Res., 59, 414-426 (2011) · Zbl 1233.90058 |
| [3] | Berbeglia, G.; Cordeau, J. F.; Gribkovskaia, I.; Laporte, G., Static pickup and delivery problems: a classification scheme and survey, TOP, 15, 1-31 (2007) · Zbl 1121.90001 |
| [4] | Brandão, J., A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem, Eur. J. Oper. Res., 284, 559-571 (2020) · Zbl 1441.90020 |
| [5] | Bulhões, T.; Subramanian, A.; Erdoğan, G.; Laporte, G., The static bike relocation problem with multiple vehicles and visits, Eur. J. Oper. Res., 264, 508-523 (2018) · Zbl 1375.90034 |
| [6] | Caggiani, L.; Camporeale, R.; Ottomanelli, M.; Szeto, W. Y., A modeling framework for the dynamic management of free-floating bike-sharing systems, Transp. Res. Part C, 87, 159-182 (2018) |
| [7] | Chang, S.; Song, R.; He, S.; Qiu, G., Innovative bike-sharing in china: Solving faulty bike-sharing recycling problem, J. Adv. Transp., 2018, 1-10 (2018) |
| [8] | Chemla, D.; Meunier, F.; Calvo, R. W., Bike sharing systems: Solving the static rebalancing problem, Discrete Optim., 10, 120-146 (2013) · Zbl 1284.90040 |
| [9] | Chen, Y.; Wang, D.; Chen, K.; Zha, Y.; Bi, G., Optimal pricing and availability strategy of a bike-sharing firm with time-sensitive customers, J. Clean. Prod., 228, 208-221 (2019) |
| [10] | Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Oper. Res., 12, 568-581 (1964) |
| [11] | Daugherty, G.; Reveliotis, S.; Mohler, G., Optimized multiagent routing for a class of guidepath-based transport systems, IEEE Trans. Autom. Sci. Eng., PP, 1-19 (2018) |
| [12] | Dell’Amico, M.; Hadjicostantinou, E.; Iori, M.; Novellani, S., The bike sharing rebalancing problem: mathematical formulations and benchmark instances, Omega, 45, 7-19 (2014) |
| [13] | Dell’Amico, M.; Iori, M.; Novellani, S.; Stützle, T., A destroy and repair algorithm for the bike sharing rebalancing problem, Comput. Oper. Res., 71, 149-162 (2016) · Zbl 1349.90082 |
| [14] | Dell’Amico, M.; Iori, M.; Novellani, S.; Subramanian, A., The bike sharing rebalancing problem with stochastic demands, Transp. Res. Part B: Methodol., 118, 362-380 (2018) |
| [15] | Drexl, M., Applications of the vehicle routing problem with trailers and transshipments, Eur. J. Oper. Res., 227, 275-283 (2013) |
| [16] | Drexl, M.; Schneider, M., A survey of variants and extensions of the location-routing problem, Eur. J. Oper. Res., 241, 283-308 (2015) · Zbl 1339.90004 |
| [17] | Forma, I. A.; Raviv, T.; Tzur, M., A 3-step math heuristic for the static repositioning problem in bike-sharing systems, Transp. Res. Part B: Methodol., 71, 230-247 (2015) |
| [18] | Gillett, B.; Miller, L., A heuristic algorithm for the vehicle dispatching problem, Oper. Res., 22 (1974) · Zbl 0274.90013 |
| [19] | Guo, Y.; He, S. Y., Built environment effects on the integration of dockless bike-sharing and the metro, Transp. Res. Part D, 83, Article 102335 pp. (2020) |
| [20] | Hernández-Pérez, H.; Rodríguez-Martín, I.; Salazar-González, J. J., A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem, Eur. J. Oper. Res., 251, 44-52 (2016) · Zbl 1346.90124 |
| [21] | Hernández-Pérez, H.; Salazar-González, J. J.; Santos-Hernández, B., Heuristic algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem, Comput. Oper. Res., 97, 1-17 (2018) · Zbl 1391.90656 |
| [22] | Ho, S. C.; Szeto, W., Solving a static repositioning problem in bike-sharing systems using iterated tabu search, Transp. Res. Part E, 69, 180-198 (2014) |
| [23] | Karakatič, S.; Podgorelec, V., A survey of genetic algorithms for solving multi depot vehicle routing problem, Appl. Soft Comput., 27, 519-532 (2015) |
| [24] | Lalla-Ruiz, E.; Expósito-Izquierdo, C.; Taheripour, S.; Voß, S., An improved formulation for the multi-depot open vehicle routing problem, OR Spectrum, 38, 175-187 (2015) · Zbl 1336.90019 |
| [25] | Li, C.; Gong, L.; Luo, Z.; Lim, A., A branch-and-price-and-cut algorithm for a pickup and delivery problem in retailing, Omega, 89, 71-91 (2019) |
| [26] | Li, J.; Wang, R.; Li, T.; Lu, Z.; Pardalos, P. M., Benefit analysis of shared depot resources for multi-depot vehicle routing problem with fuel consumption, Transp. Res. Part D, 59, 417-432 (2018) |
| [27] | Li, Y.; Soleimani, H.; Zohal, M., An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives, J. Clean. Prod., 227, 1161-1172 (2019) |
| [28] | Li, Y.; Szeto, W.; Long, J.; Shui, C., A multiple type bike repositioning problem, Transp. Res. Part B, 90, 263-278 (2016) |
| [29] | Liu, A.; Ji, X.; Xu, L.; Lu, H., Research on the recycling of sharing bikes based on time dynamics series, individual regrets and group efficiency, J. Clean. Prod., 208, 666-687 (2019) |
| [30] | Liu, R.; Xie, X.; Augusto, V.; Rodriguez, C., Heuristic approaches for a special simultaneous pickup and delivery problem with time windows in home health care industry, IFAC Proc. Vol., 45, 345-350 (2012) |
| [31] | Lu, Y.; Benlic, U.; Wu, Q., A population algorithm based on randomized tabu thresholding for the multi-commodity pickup-and-delivery traveling salesman problem, Comput. Oper. Res., 101, 285-297 (2019) · Zbl 1458.90115 |
| [32] | Ma, Y.; Lan, J.; Thornton, T.; Mangalagiu, D.; Zhu, D., Challenges of collaborative governance in the sharing economy: the case of free-floating bike sharing in shanghai, J. Clean. Prod., 197, 356-365 (2018) |
| [33] | Maggioni, F.; Cagnolari, M.; Bertazzi, L.; Wallace, S. W., Stochastic optimization models for a bike-sharing problem with transshipment, Eur. J. Oper. Res., 276, 272-283 (2019) · Zbl 1430.90107 |
| [34] | Mahmoudi, M.; Zhou, X., Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: a dynamic programming approach based on state-space-time network representations, Transp. Res. Part B, 89, 19-42 (2016) |
| [35] | Masson, R.; Ropke, S.; Lehuédé, F.; Péton, O., A branch-and-cut-and-price approach for the pickup and delivery problem with shuttle routes, Eur. J. Oper. Res., 236, 849-862 (2014) · Zbl 1304.90039 |
| [36] | Meddin, R., DeMaio, P., 2020. The bike-sharing world map.http://www.bikesharingmap.com/ (accessed on 2 March 2020). |
| [37] | Meeus, J., 1991. Astronomical Algorithms. Willmann-Bell. |
| [38] | Mladenović, N.; Urošević, D.; Hanafi, S.; Ilić, A., A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem, Eur. J. Oper. Res., 220, 270-285 (2012) · Zbl 1253.90200 |
| [39] | Montané, F.; Galvão, R., A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service, Comput. Oper. Res., 33, 595-619 (2006) · Zbl 1077.90058 |
| [40] | Montoya-Torres, J. R.; Franco, J. L.; Isaza, S. N.; Jiménez, H. F.; Herazo-Padilla, N., A literature review on the vehicle routing problem with multiple depots, Comput. Ind. Eng., 79, 115-129 (2015) |
| [41] | Motivate International Inc., 2019. Experience nyc in a whole new way.https://layer.bicyclesharing.net/map/v1/nyc/map-inventory (accessed on 21 May 2019). |
| [42] | Motivate International Inc., 2020. Experience nyc in a whole new way.https://www.citibikenyc.com/how-it-works (accessed on 19 February 2020). |
| [43] | Pal, A.; Zhang, Y., Free-floating bike sharing: solving real-life large-scale static rebalancing problems, Transp. Res. Part C, 80, 92-116 (2017) |
| [44] | Qiu, M.; Fu, Z.; Eglese, R.; Tang, Q., A tabu search algorithm for the vehicle routing problem with discrete split deliveries and pickups, Comput. Oper. Res., 100, 102-116 (2018) · Zbl 1458.90130 |
| [45] | Ramos, T. R.P.; Gomes, M. I.; Póvoa, A. P.B., Multi-depot vehicle routing problem: a comparative study of alternative formulations, Int. J. Logist. Res. Appl., 23, 103-120 (2019) |
| [46] | Raviv, T.; Tzur, M.; Forma, I. A., Static repositioning in a bike-sharing system: models and solution approaches, EURO J. Transp. Logist., 2, 187-229 (2013) |
| [47] | Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transp. Sci., 40, 455-472 (2006) |
| [48] | Schuijbroek, J.; Hampshire, R.; van Hoeve, W. J., Inventory rebalancing and vehicle routing in bike sharing systems, Eur. J. Oper. Res., 257, 992-1004 (2017) · Zbl 1394.90046 |
| [49] | Shui, C.; Szeto, W., Dynamic green bike repositioning problem – a hybrid rolling horizon artificial bee colony algorithm approach, Transp. Res. Part D, 60, 119-136 (2018) |
| [50] | Silvestrin, P. V.; Ritt, M., An iterated tabu search for the multi-compartment vehicle routing problem, Comput. Oper. Res., 81, 192-202 (2017) · Zbl 1391.90085 |
| [51] | Soto, M.; Sevaux, M.; Rossi, A.; Reinholz, A., Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem, Comput. Ind. Eng., 107, 211-222 (2017) |
| [52] | Sun, P.; Veelenturf, L. P.; Hewitt, M.; Woensel, T. V., The time-dependent pickup and delivery problem with time windows, Transp. Res. Part B, 116, 1-24 (2018) |
| [53] | Szeto, W.; Shui, C., Exact loading and unloading strategies for the static multi-vehicle bike repositioning problem, Transp. Res. Part B, 109, 176-211 (2018) |
| [54] | Tang, Q.; Fu, Z.; Qiu, M., A bilevel programming model and algorithm for the static bike repositioning problem, J. Adv. Transp., 2019, 1-19 (2019) |
| [55] | Tilk, C.; Goel, A., Bidirectional labeling for solving vehicle routing and truck driver scheduling problems, Eur. J. Oper. Res., 283, 108-124 (2020) · Zbl 1431.90071 |
| [56] | Wang, Y.; Szeto, W., Static green repositioning in bike sharing systems with broken bikes, Transp. Res. Part D, 65, 438-457 (2018) |
| [57] | Wang, Z.; Sheu, J. B., Vehicle routing problem with drones, Transp. Res. Part B, 122, 350-364 (2019) |
| [58] | Zhang, D.; Zhan, Q.; Chen, Y.; Li, S., Joint optimization of logistics infrastructure investments and subsidies in a regional logistics network with CO2 emission reduction targets, Transp. Res. Part D, 60, 174-190 (2018) |
| [59] | Zhang, J.; Meng, M.; David, Z. W., A dynamic pricing scheme with negative prices in dockless bike sharing systems, Transp. Res. Part B, 127, 201-224 (2019) |
| [60] | Zhang, L.; Zhang, J.; yu Duan, Z.; Bryde, Z., Sustainable bike-sharing systems: characteristics and commonalities across cases in urban china, J. Clean. Prod., 97, 124-133 (2015) |
| [61] | Zhang, Z.; Cheang, B.; Li, C.; Lim, A., Multi-commodity demand fulfillment via simultaneous pickup and delivery for a fast fashion retailer, Comput. Oper. Res., 103, 81-96 (2019) · Zbl 1458.90157 |
| [62] | Zhao, D.; Ong, G. P.; Wang, W.; Hu, X. J., Effect of built environment on shared bicycle reallocation: a case study on nanjing, china, Transp. Res. Part A, 128, 73-88 (2019) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
