多类型公共自行车调运问题
|
摘要
公共自行车是我国正大力发展的低碳交通出行模式,加强公共自行车调运优化是提升自行车出行吸引力的关键要素。通过对公共自行车调运背景分析,提出了一类多类型公共自行车的调运优化问题。针对现实生活中租赁站点内公共自行车不均衡的情况,建立了以总成本最小为目标的混合整数线性规划模型,并提出一种改进的混合禁忌搜索对问题进行求解。通过数值实验分析了问题特性并验证了算法性能。实验结果表明非均衡惩罚系数决定了租赁站点各类自行车的装卸载数量,并影响了调配车辆的运行路线,是实现多类型公共自行车均衡优化的关键因素。不同类型自行车的替代策略使得调运决策更加灵活。混合禁忌搜索可以求解更大规模的问题,并能在短时间内求得较好质量的解。
Public bike sharing system has been developing rapidly in China,encouraging people to cycle and use this low-carbon transport mode to make trips. It is therefore important to strengthen the public bike repositioning optimization in order to increase the attractiveness of cycling in Chinese cities. Based on the analysis of the background of public bike,we introduce a multiple type bike repositioning Problem. According to the shortage or excess of public bicycle in real life,we formulate a mixed-integer linear programming Problem to minimize the total cost. A hybrid tabu search is proposed to solve this Problem. The numerical experiments are performed to analyze the characteristics of the Problem and performance of the hybrid tabu search. The results show that the unbalanced penalty coefficient determines the amount of loading and unloading of bikes,and has an effect on the vehicle routing,which is the key factor to the optimization of the multiple type bike repositioning. Substitution strategy makes transportation decision more flexible. The hybrid tabu search can solve much larger network and obtain better quality solutions compared with the exact method.
Public bike sharing system has been developing rapidly in China,encouraging people to cycle and use this low-carbon transport mode to make trips. It is therefore important to strengthen the public bike repositioning optimization in order to increase the attractiveness of cycling in Chinese cities. Based on the analysis of the background of public bike,we introduce a multiple type bike repositioning Problem. According to the shortage or excess of public bicycle in real life,we formulate a mixed-integer linear programming Problem to minimize the total cost. A hybrid tabu search is proposed to solve this Problem. The numerical experiments are performed to analyze the characteristics of the Problem and performance of the hybrid tabu search. The results show that the unbalanced penalty coefficient determines the amount of loading and unloading of bikes,and has an effect on the vehicle routing,which is the key factor to the optimization of the multiple type bike repositioning. Substitution strategy makes transportation decision more flexible. The hybrid tabu search can solve much larger network and obtain better quality solutions compared with the exact method.
引文
[1]王梅.城市公共自行车发展迷思[J].交通与港航,2016,2:010.
[2]倪康康,李科群,崔国民.绿色出行——城市公共自行车发展的探讨[J].上海节能,2015(4):204-7.
[3] Contardo C,Morency C,Rousseau L M. Balancing a dynamic public bike-sharing system[M]. Montreal:Cirrelt,2012.
[4] Caggiani L,Ottomanelli M. A dynamic simulation based model for optimal fleet repositioning in bike-sharing systems[J]. Procedia-Social and Behavioral Sciences,2013,87:203-210.
[5] Chemla D,Meunier F,Pradeau T,et al. Self-service bike sharing systems:simulation,repositioning,pricing[J]. Dynamic Routing,2013.
[6] Pfrommer J,Warrington J,Schildbach G,et al. Dynamic vehicle redistribution and online price incentives in shared mobility systems[J]. Intelligent Transportation Systems IEEE Transactions on, 2013, 15(4):1567-1578.
[7] Kloimüllner C,Papazek P,Hu B,et al. Balancing bicycle sharing systems:an approach for the dynamic case[C]. Evolutionary Computation in Combinatorial Optimization,2014:73-84.
[8] 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.
[9] Lin J H,Chou T C. A Geo-aware and VRP-based Public bicycle redistribution system[J]. International Journal of Vehicular Technology,2012,2012.
[10] Chemla D, Meunier F, Calvo R W. Bike sharing systems:solving the static rebalancing problem[J].Discrete Optimization,2013,10(2):120-146.
[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&Transportation Review,2014,69(3):180-198.
[12] Erdogan G,Laporte G,Calvo R W. The one commodity pickup and delivery traveling salesman problem with demand intervals[J]. 2013.
[13] Erdogan 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.
[14] 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.
[15] Rainer-Harbach M,Papazek P,Hu B,et al. Balancing bicycle sharing systems:a variable neighborhood search approach[M]. Evolutionary Computation in Combinatorial Optimization. Springer Berlin Heidelberg,2013:121-132.
[16] Papazek P,Raidl G R,Rainer-Harbach M,et al. A PILOT/VND/GRASP hybrid for the static balancing of public bicycle sharing systems[M]. Computer Aided Systems Theory-EUROCAST 2013. 2013:372-379.
[17] 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.
[18]董红召,赵敬洋,郭海锋,等.公共慢行系统的动态调度建模与滚动时域调度算法研究[J].公路工程,2009,34(6):68-71.
[19]刘登涛,方文道,章坚民,等.公共自行车交通系统调度算法[J].计算机系统应用,2011,20(9):112-116.
[20]柳祖鹏,李克平,朱晓宏.基于蚁群算法的公共自行车站间调度优化[J].交通信息与安全,2012,30(4):71-74.
[21]张建国.城市公共自行车车辆调运问题研究[D].西南交通大学,2013.
[22]刘臻.城市公共自行车运营中的多车场车辆调运优化研究[D].北京交通大学,2014.
[23]管娜娜.公共自行车调度路径优化问题研究[D].西南交通大学,2015.
[24] 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.
[25] Ho S C,Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J]. Computers&Operations Research,2004,31(12):1947-1964.
[26] Cordeau J F,Laporte G. A tabu search heuristic for the static multi-vehicle dial-a-ride problem[J]. Transportation Research Part B Methodological,2003,37(6):579-594.
[27] Kirchler D, Calvo R W. A granular tabu search algorithm for the dial-a-ride problem[J]. Transportation Research Part B Methodological, 2013, 56(10):120-135.
[28] 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.
[29] 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.
[30] Hernández-Pérez H, Rodríguez-Martín I, SalazarGonzález J J. A hybrid heuristic approach for the multicommodity pickup-and-delivery traveling salesman problem[J]. European Journal of Operational Research,2016,251(1):44-52.
[31] 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.
[2]倪康康,李科群,崔国民.绿色出行——城市公共自行车发展的探讨[J].上海节能,2015(4):204-7.
[3] Contardo C,Morency C,Rousseau L M. Balancing a dynamic public bike-sharing system[M]. Montreal:Cirrelt,2012.
[4] Caggiani L,Ottomanelli M. A dynamic simulation based model for optimal fleet repositioning in bike-sharing systems[J]. Procedia-Social and Behavioral Sciences,2013,87:203-210.
[5] Chemla D,Meunier F,Pradeau T,et al. Self-service bike sharing systems:simulation,repositioning,pricing[J]. Dynamic Routing,2013.
[6] Pfrommer J,Warrington J,Schildbach G,et al. Dynamic vehicle redistribution and online price incentives in shared mobility systems[J]. Intelligent Transportation Systems IEEE Transactions on, 2013, 15(4):1567-1578.
[7] Kloimüllner C,Papazek P,Hu B,et al. Balancing bicycle sharing systems:an approach for the dynamic case[C]. Evolutionary Computation in Combinatorial Optimization,2014:73-84.
[8] 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.
[9] Lin J H,Chou T C. A Geo-aware and VRP-based Public bicycle redistribution system[J]. International Journal of Vehicular Technology,2012,2012.
[10] Chemla D, Meunier F, Calvo R W. Bike sharing systems:solving the static rebalancing problem[J].Discrete Optimization,2013,10(2):120-146.
[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&Transportation Review,2014,69(3):180-198.
[12] Erdogan G,Laporte G,Calvo R W. The one commodity pickup and delivery traveling salesman problem with demand intervals[J]. 2013.
[13] Erdogan 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.
[14] 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.
[15] Rainer-Harbach M,Papazek P,Hu B,et al. Balancing bicycle sharing systems:a variable neighborhood search approach[M]. Evolutionary Computation in Combinatorial Optimization. Springer Berlin Heidelberg,2013:121-132.
[16] Papazek P,Raidl G R,Rainer-Harbach M,et al. A PILOT/VND/GRASP hybrid for the static balancing of public bicycle sharing systems[M]. Computer Aided Systems Theory-EUROCAST 2013. 2013:372-379.
[17] 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.
[18]董红召,赵敬洋,郭海锋,等.公共慢行系统的动态调度建模与滚动时域调度算法研究[J].公路工程,2009,34(6):68-71.
[19]刘登涛,方文道,章坚民,等.公共自行车交通系统调度算法[J].计算机系统应用,2011,20(9):112-116.
[20]柳祖鹏,李克平,朱晓宏.基于蚁群算法的公共自行车站间调度优化[J].交通信息与安全,2012,30(4):71-74.
[21]张建国.城市公共自行车车辆调运问题研究[D].西南交通大学,2013.
[22]刘臻.城市公共自行车运营中的多车场车辆调运优化研究[D].北京交通大学,2014.
[23]管娜娜.公共自行车调度路径优化问题研究[D].西南交通大学,2015.
[24] 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.
[25] Ho S C,Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J]. Computers&Operations Research,2004,31(12):1947-1964.
[26] Cordeau J F,Laporte G. A tabu search heuristic for the static multi-vehicle dial-a-ride problem[J]. Transportation Research Part B Methodological,2003,37(6):579-594.
[27] Kirchler D, Calvo R W. A granular tabu search algorithm for the dial-a-ride problem[J]. Transportation Research Part B Methodological, 2013, 56(10):120-135.
[28] 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.
[29] 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.
[30] Hernández-Pérez H, Rodríguez-Martín I, SalazarGonzález J J. A hybrid heuristic approach for the multicommodity pickup-and-delivery traveling salesman problem[J]. European Journal of Operational Research,2016,251(1):44-52.
[31] 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.