共享单车调配路线优化问题研究
|
摘要
随着共享单车的普及,投放数量在急剧增加。由于公共资源有限,导致共享单车乱停乱放现象严重,因此需要合理控制各站点单车的库存量。共享单车的调配路线优化是优化站点库存量的主要手段之一。同时,共享单车种类也越来越多(如单人车、双人车以及带婴儿座椅单车等等),为了满足用户多样化的需求,在调配过程中需要考虑各类型共享单车的均衡问题。研究了一类时变环境下的多类型共享单车调配路线优化问题,结合不同类型单车之间的替代特性,建立了混合整数规划模型,并设计了混合禁忌搜索算法对问题进行求解。数值实验表明替代策略既可以有效减少调运总成本,混合禁忌搜索能求解大规模算例,并且能得到质量较好的解。
With the popularity of shared bicycle in major cities in China,the amount of bikes is increasing rapidly.The serious public resources insufficiency leads to a confusion in bicycle parking.However,the optimization of shared bikes is a key mean to realize the reasonable inventory level at stations.Meanwhile,more and more kinds of bicycles,such as single-seat bike,double-seat bike and baby-seat bike among others,is emerging.The balance of different types of bicycles in the allocation process is needed,on the purpose of satisfying the diverse demands.In order to maintain the bike sharing system efficiently,a multiple type bicycle repositioning problem with substitution strategies of different shared bikes in time-varying environment was proposed.A mixed integer model was developed and a hybrid tabu search algorithm was designed to solve this problem.Numerical studies were adopted to analyze the problem characteristics and the method performance.The results show that substitution strategy makes transportation decision more flexible and can reduce the transportation cost.The proposed hybrid tabu search can solve large networks and obtain high-quality solutions.
With the popularity of shared bicycle in major cities in China,the amount of bikes is increasing rapidly.The serious public resources insufficiency leads to a confusion in bicycle parking.However,the optimization of shared bikes is a key mean to realize the reasonable inventory level at stations.Meanwhile,more and more kinds of bicycles,such as single-seat bike,double-seat bike and baby-seat bike among others,is emerging.The balance of different types of bicycles in the allocation process is needed,on the purpose of satisfying the diverse demands.In order to maintain the bike sharing system efficiently,a multiple type bicycle repositioning problem with substitution strategies of different shared bikes in time-varying environment was proposed.A mixed integer model was developed and a hybrid tabu search algorithm was designed to solve this problem.Numerical studies were adopted to analyze the problem characteristics and the method performance.The results show that substitution strategy makes transportation decision more flexible and can reduce the transportation cost.The proposed hybrid tabu search can solve large networks and obtain high-quality solutions.
引文
[1]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.
[2]Chemla D,Meunier F,Calvo R W.Bike sharing systems:Solving the static rebalancing problem[J].Discrete Optimization,2013,10(2):120-146.
[3]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.
[4]Erdo gan 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.
[5]Raviv T,Tzur M,Forma I A.Static repositioning in a bikesharing system:models and solution approaches[J].EUROJournal on Transportation and Logistics,2013,2(3):187-229.
[6]Rainer-Harbach M,Papazek P,Hu B,et al.Balancing Bicycle Sharing Systems:A Variable Neighborhood Search Approach[M].Springer Berlin Heidelberg,2013:121-132.
[7]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.
[8]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.
[9]Contardo C,Morency C,Rousseau L M.Balancing a dynamic public bike-sharing system[M].Montreal:Cirrelt,2012.
[10]Raviv T,Tzur M,Forma I A.Static repositioning in a bikesharing system:models and solution approaches[J].EUROJournal on Transportation and Logistics,2013,2(3):187-229.
[11]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.
[12]Shui C S,Szeto W Y.Dynamic green bike repositioning problem-A hybrid rolling horizon artificial bee colony algorithm approach[J].Transportation Research Part D:Transport and Environment,2018,60:119-136.
[13]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.
[14]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.
[15]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.
[16]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.
[17]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.
[18]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.
[19]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.
[20]Nguyen P K,Crainic T G,Toulouse M.A tabu search for timedependent multi-zone multi-trip vehicle routing problem with time windows[J].European Journal of Operational Research,2013,231(1):43-56.
[2]Chemla D,Meunier F,Calvo R W.Bike sharing systems:Solving the static rebalancing problem[J].Discrete Optimization,2013,10(2):120-146.
[3]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.
[4]Erdo gan 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.
[5]Raviv T,Tzur M,Forma I A.Static repositioning in a bikesharing system:models and solution approaches[J].EUROJournal on Transportation and Logistics,2013,2(3):187-229.
[6]Rainer-Harbach M,Papazek P,Hu B,et al.Balancing Bicycle Sharing Systems:A Variable Neighborhood Search Approach[M].Springer Berlin Heidelberg,2013:121-132.
[7]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.
[8]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.
[9]Contardo C,Morency C,Rousseau L M.Balancing a dynamic public bike-sharing system[M].Montreal:Cirrelt,2012.
[10]Raviv T,Tzur M,Forma I A.Static repositioning in a bikesharing system:models and solution approaches[J].EUROJournal on Transportation and Logistics,2013,2(3):187-229.
[11]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.
[12]Shui C S,Szeto W Y.Dynamic green bike repositioning problem-A hybrid rolling horizon artificial bee colony algorithm approach[J].Transportation Research Part D:Transport and Environment,2018,60:119-136.
[13]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.
[14]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.
[15]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.
[16]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.
[17]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.
[18]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.
[19]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.
[20]Nguyen P K,Crainic T G,Toulouse M.A tabu search for timedependent multi-zone multi-trip vehicle routing problem with time windows[J].European Journal of Operational Research,2013,231(1):43-56.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |