“红包车”机制下的共享单车调度问题

徐国勋, 李妍峰, 金大祥, 李军

系统工程理论与实践 ›› 2020, Vol. 40 ›› Issue (2) : 426-436.

PDF(798 KB)
PDF(798 KB)
系统工程理论与实践 ›› 2020, Vol. 40 ›› Issue (2) : 426-436. DOI: 10.12011/1000-6788-2018-0884-11
研究论文

“红包车”机制下的共享单车调度问题

    徐国勋1,2, 李妍峰2, 金大祥2, 李军2
作者信息 +

A user-based method for the static bike repositioning problem

    XU Guoxun1,2, LI Yanfeng2, JIN Daxiang2, LI Jun2
Author information +
文章历史 +

摘要

共享单车具有随取随放的优点,但用户的租还车使站点之间经常出现供需不平衡现象.为了有效缓解运营商调度压力,提出了一种顾客参与调度的共享单车调度方式.将某些闲置的共享单车设置为红包车,鼓励用户将红包车骑到需求旺盛的区域,用户完成调度后可以获得红包奖励.以运营商运输成本,红包奖励支出以及未满足站点需求的惩罚成本最小为目标建立了混合整数规划模型,并设计了混合禁忌搜索算法对模型进行了求解.数值实验表明:红包车机制可有效减少运营商总成本;混合禁忌搜索算法可以有效求解大规模问题.

Abstract

Shared bike can be retrieved and parked at any station in the bike-sharing system. One of the most important challenge is the demand for bikes is always deviated from the supply. This paper proposed a new user-based method for shared bike repositioning problem. In the proposed problem, some excess bikes are set as lucky bikes which are relocated by users to unsaturated nodes. Users can gain the monetary rewards after the completion of the relocations. A mixed integer programming model is formulated to minimize the total transportation cost, the total reward payouts and the total penalties due to unmet demand. To solve this problem, a hybrid tabu search is developed. The numerical experiments show that the user-participating mechanism can effectively reduce the total cost. The hybrid tabu search can effectively solve the large networks of the proposed problem.

关键词

红包车 / 用户参与 / 共享单车调度问题 / 混合禁忌搜索

Key words

lucky bike / user-based / bike repositioning problem / hybrid tabu search

引用本文

导出引用
徐国勋 , 李妍峰 , 金大祥 , 李军. “红包车”机制下的共享单车调度问题. 系统工程理论与实践, 2020, 40(2): 426-436 https://doi.org/10.12011/1000-6788-2018-0884-11
XU Guoxun , LI Yanfeng , JIN Daxiang , LI Jun. A user-based method for the static bike repositioning problem. Systems Engineering - Theory & Practice, 2020, 40(2): 426-436 https://doi.org/10.12011/1000-6788-2018-0884-11
中图分类号: F253.4   

参考文献

[1] Li Y, Szeto W Y, Long J, et al. A multiple type bike repositioning problem[J]. Transportation Research Part B:Methodological, 2016, 90:263-278.
[2] Di Gaspero L, Rendl A, Urli T. A hybrid ACO+ CP for balancing bicycle sharing systems[C]//International Workshop on Hybrid Metaheuristics. Berlin, Heidelberg:Springer, 2013:198-212.
[3] Di Gaspero L, Rendl A, Urli T. Balancing bike sharing systems with constraint programming[J]. Constraints, 2016, 21(2):318-348.
[4] Raidl G R, Hu B, Rainer-Harbach M, et al. Balancing bicycle sharing systems:Improving a VNS by efficiently determining optimal loading operations[C]//International Workshop on Hybrid Metaheuristics. Berlin, Heidelberg:Springer, 2013:130-143.
[5] Rainer-Harbach M, Papazek P, Hu B, et al. Balancing bicycle sharing systems:A variable neighborhood search approach[C]//European Conference on Evolutionary Computation in Combinatorial Optimization. Berlin, Heidelberg:Springer, 2013:121-132.
[6] Rainer-Harbach M, Papazek P, Raidl G R, et al. PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems[J]. Journal of Global Optimization, 2015, 63(3):597-629.
[7] Benchimol M, Benchimol P, Chappert B, et al. Balancing the stations of a self-service “bike hire” system[J]. RAIRO-Operations Research, 2011, 45(1):37-61.
[8] Chemla D, Meunier F, Calvo R W. Bike sharing systems:Solving the static rebalancing problem[J]. Discrete Optimization, 2013, 10(2):120-146.
[9] Erdoğan G, Laporte G, Calvo R W. The static bicycle relocation problem with demand intervals[J]. European Journal of Operational Research, 2014, 238(2):451-457.
[10] Nair R, Miller-Hooks E, Hampshire R C, et al. Large-scale vehicle sharing systems:Analysis of Vélib'[J]. International Journal of Sustainable Transportation, 2013, 7(1):85-106.
[11] Ho S C, Szeto W Y. Solving a static repositioning problem in bike-sharing systems using iterated tabu search[J]. Transportation Research Part E:Logistics and Transportation Review, 2014, 69:180-198.
[12] Ho S C, Szeto W Y. A hybrid large neighborhood search for the static multi-vehicle bike-repositioning problem[J]. Transportation Research Part B:Methodological, 2017, 95:340-363.
[13] Raviv T, Tzur M, Forma I A. Static repositioning in a bike-sharing system:Models and solution approaches[J]. EURO Journal on Transportation and Logistics, 2013, 2(3):187-229.
[14] Forma I A, Raviv T, Tzur M. A 3-step math heuristic for the static repositioning problem in bike-sharing systems[J]. Transportation Research Part B:Methodological, 2015, 71:230-247.
[15] Szeto W Y, Liu Y, Ho S C. Chemical reaction optimization for solving a static bike repositioning problem[J]. Transportation Research Part D:Transport and Environment, 2016, 47:104-135.
[16] Szeto W Y, Shui C S. Exact loading and unloading strategies for the static multi-vehicle bike repositioning problem[J]. Transportation Research Part B:Methodological, 2018, 109:176-211.
[17] Chemla D, Meunier F, Pradeau T, et al. Self-service bike sharing systems:Simulation, repositioning, pricing[R]. Technical Report, hal-00824078, Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), 2013.
[18] Pfrommer J, Warrington J, Schildbach G, et al. Dynamic vehicle redistribution and online price incentives in shared mobility systems[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(4):1567-1578.
[19] Singla A, Santoni M, Bartók G, et al. Incentivizing Users for Balancing Bike Sharing Systems[C]//Twenty-Ninth AAAI Conference on Artificial Intelligence. Austin:AAAI Press, 2015:723-729.
[20] Kadri A A, Kacem I, Labadi K. A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems[J]. Computers & Industrial Engineering, 2016, 95:41-52.
[21] Gendreau M, Laporte G, Semet F. A tabu search heuristic for the undirected selective travelling salesman problem[J]. European Journal of Operational Research, 1996, 106(2-3):539-545.
[22] Silvestrin P V, Ritt M. An iterated tabu search for the multi-compartment vehicle routing problem[J]. Computers & Operations Research, 2017, 81:192-202.
[23] Paquette J, Cordeau J F, Laporte G, et al. Combining multicriteria analysis and tabu search for dial-a-ride problems[J]. Transportation Research Part B:Methodological, 2013, 52(6):1-16.
[24] Nanry W P, Barnes J W. Solving the pickup and delivery problem with time windows using reactive tabu search[J]. Transportation Research Part B:Methodological, 2000, 34(2):107-121.
[25] Talarico L, Sörensen K, Springael J. Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem[J]. European Journal of Operational Research, 2015, 244(2):457-470.
[26] Nguyen P K, Crainic T G, Toulouse M. A tabu search for time-dependent multi-zone multi-trip vehicle routing problem with time windows[J]. European Journal of Operational Research, 2013, 231(1):43-56.

基金

国家自然科学基金面上项目(71571150,71671146);西南交通大学“双一流”建设项目(交通软科学类)研究成果(JDSYLZD2018003);四川省哲学社会科学重点研究基地项目(QGXH15-05);海南省自然科学基金(718MS033)
PDF(798 KB)

683

Accesses

0

Citation

Detail

段落导航
相关文章

/