考虑损坏自行车回收的共享单车调度问题
|
摘要
在共享单车系统中,各站点的自行车需要不断地再平衡以满足用户的需求。同时由于各种因素作用(如自然损耗、人为破坏等),共享单车系统中经常出现大量损坏自行车。为了有效利用卡车装载空间以减少运营商运营成本,提出了一类再平衡可用自行车过程中,对损坏自行车进行回收的共享单车调度问题。以运营商总成本最小化为目标建立了混合整数线性规划模型,并针对问题特性提出了一种混合禁忌搜索算法。数值实验对问题特性和算法性能进行了分析。结果表明回收惩罚系数能改变站点回收优先级,对于调配需求和回收需求都很大的站点,变大回收惩罚系数可以增加站点损坏自行的回收量,所提出算法能有效求解各种规模的问题。
In bike sharing systems, bicycles at each site need to be constantly rebalanced to meet the needs of users. Due to various factors(wear and tear, damage, etc.), a number of broken bikes regularly found in bike sharing systems. This study introduces a bike repositioning problem with broken bikes in order to effectively utilize trucks to reduce the operation cost. A mixed integer linear programming model is proposed to minimize the total cost. A hybrid tabu search is developed to solve the proposed problems. Computation experiments are performed to illustrate problem properties and the performance of the proposed algorithm. Numerical results show that for different stations, the increase of the collection penalty can improve collection priority. For a station with large allocation and collection demands, the increase of the collection penalty can increase the collection number of broken bikes. The proposed solution method can put forward high-quality solutions within short computing time.
In bike sharing systems, bicycles at each site need to be constantly rebalanced to meet the needs of users. Due to various factors(wear and tear, damage, etc.), a number of broken bikes regularly found in bike sharing systems. This study introduces a bike repositioning problem with broken bikes in order to effectively utilize trucks to reduce the operation cost. A mixed integer linear programming model is proposed to minimize the total cost. A hybrid tabu search is developed to solve the proposed problems. Computation experiments are performed to illustrate problem properties and the performance of the proposed algorithm. Numerical results show that for different stations, the increase of the collection penalty can improve collection priority. For a station with large allocation and collection demands, the increase of the collection penalty can increase the collection number of broken bikes. The proposed solution method can put forward high-quality solutions within short computing time.
引文
[1] Dell'Amico M,Hadjicostantinou E,Iori M,et al.The bike sharing rebalancing problem:Mathematical formulations and benchmark instances[J].Omega,2014,45:7-19.
[2] Castro A.The contribution of bike-sharing to sustainable mobility in Europe[D].Doctoral thesis.Vienna University of Technology,2011.
[3] Kaspi M,Raviv T,Tzur M.Detection of unusable bicycles in bike-sharing systems[J].Omega,2016a,65:10-16.
[4] Kaspi M,Raviv T,Tzur M.Bike-sharing systems:User dissatisfaction in the presence of unusable bicycles[J].IISE Transactions,2017,49(2):144-158.
[5] Wang Y,Szeto W Y.Static green repositioning in bike sharing systems with broken bikes[J].Transportation Research Part D:Transport and Environment,2018,65:438-457.
[6] Alvarez-Valdes R,Belenguer J M,Benavent E,et al.Optimizing the level of service quality of a bike-sharing system[J].Omega,2016,62:163-175.
[7] 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.
[8] 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.
[9] 徐国勋,张伟亮,李妍峰.共享单车调配路线优化问题研究[J].工业工程与管理,2019,24(01):80-86.
[10] Osaba E,Carballedo R,Lopez-Garcia P,et al.Comparison between Golden Ball Meta-heuristic,Evolutionary Simulated Annealing and Tabu Search for the Traveling Salesman Problem[C].On Genetic & Evolutionary Computation Conference Companion.2016.
[11] Soto M,Sevaux M,Reinholz A,et al.Multiple neighborhood search,tabu search and ejection chains for the multi-depot open vehicle routing problem[J].Computers & Industrial Engineering,2017,107:211-222.
[12] 傅成红,符卓.一种毗邻信息改进的车辆路径问题禁忌搜索算法[J].系统工程,2010,28(05):81-84.
[13] Grimault A,Bostel N,Lehuédé F.An adaptive large neighborhood search for the full truckload pickup and delivery problem with resource synchronization[J].Computers & Operations Research,2017,88:1-14.
[14] Hernández-Pérez H,Rodríguez-Martín I,Salazar-González JJ.A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem[J].European Journal of Operational Research,2016,251(1):44-52.
[15] 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.
[16] 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] Castro A.The contribution of bike-sharing to sustainable mobility in Europe[D].Doctoral thesis.Vienna University of Technology,2011.
[3] Kaspi M,Raviv T,Tzur M.Detection of unusable bicycles in bike-sharing systems[J].Omega,2016a,65:10-16.
[4] Kaspi M,Raviv T,Tzur M.Bike-sharing systems:User dissatisfaction in the presence of unusable bicycles[J].IISE Transactions,2017,49(2):144-158.
[5] Wang Y,Szeto W Y.Static green repositioning in bike sharing systems with broken bikes[J].Transportation Research Part D:Transport and Environment,2018,65:438-457.
[6] Alvarez-Valdes R,Belenguer J M,Benavent E,et al.Optimizing the level of service quality of a bike-sharing system[J].Omega,2016,62:163-175.
[7] 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.
[8] 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.
[9] 徐国勋,张伟亮,李妍峰.共享单车调配路线优化问题研究[J].工业工程与管理,2019,24(01):80-86.
[10] Osaba E,Carballedo R,Lopez-Garcia P,et al.Comparison between Golden Ball Meta-heuristic,Evolutionary Simulated Annealing and Tabu Search for the Traveling Salesman Problem[C].On Genetic & Evolutionary Computation Conference Companion.2016.
[11] Soto M,Sevaux M,Reinholz A,et al.Multiple neighborhood search,tabu search and ejection chains for the multi-depot open vehicle routing problem[J].Computers & Industrial Engineering,2017,107:211-222.
[12] 傅成红,符卓.一种毗邻信息改进的车辆路径问题禁忌搜索算法[J].系统工程,2010,28(05):81-84.
[13] Grimault A,Bostel N,Lehuédé F.An adaptive large neighborhood search for the full truckload pickup and delivery problem with resource synchronization[J].Computers & Operations Research,2017,88:1-14.
[14] Hernández-Pérez H,Rodríguez-Martín I,Salazar-González JJ.A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem[J].European Journal of Operational Research,2016,251(1):44-52.
[15] 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.
[16] 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.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |