A heuristic algorithm for a single vehicle static bike sharing rebalancing problem
From MaRDI portal
Publication:1652142
Abstract: The static bike rebalancing problem (SBRP) concerns the task of repositioning bikes among stations in self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes from a station (even all of them), thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This paper deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to find a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station should be appropriately determined in order to respect such constraints. We propose an iterated local search (ILS) based heuristic to solve the problem. The ILS algorithm was tested on 980 benchmark instances from the literature and the results obtained are quite competitive when compared to other existing methods. Moreover, our heuristic was capable of finding most of the known optimal solutions and also of improving the results on a number of open instances.
Recommendations
- Bike sharing systems: solving the static rebalancing problem
- The static bike relocation problem with multiple vehicles and visits
- An exact algorithm for the static rebalancing problem arising in bicycle sharing systems
- The static bicycle relocation problem with demand intervals
- A destroy and repair algorithm for the bike sharing rebalancing problem
Cites work
- scientific article; zbMATH DE number 23663 (Why is no real title available?)
- A Tabu Search Heuristic for the Vehicle Routing Problem
- A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery
- A destroy and repair algorithm for the bike sharing rebalancing problem
- A simple and effective metaheuristic for the minimum latency problem
- An exact algorithm for the static rebalancing problem arising in bicycle sharing systems
- An iterated local search heuristic for the split delivery vehicle routing problem
- Balancing the stations of a self service ``bike hire system
- Bike sharing systems: solving the static rebalancing problem
- Hybrid metaheuristics for the clustered vehicle routing problem
- Inventory rebalancing and vehicle routing in bike sharing systems
- PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems
- The case for strategic oscillation
- The static bicycle relocation problem with demand intervals
- Variable neighborhood search
Cited in
(25)- Vehicle driven approaches for non preemptive vehicle relocation with integrated quality criterion in a vehicle sharing system
- PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems
- Heuristic algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem
- The single-vehicle two-echelon one-commodity pickup and delivery problem
- Bike rebalancing: how to find a balanced matching in the k center problem?
- A feature correlation reinforce clustering and evolutionary algorithm for the green bike-sharing reposition problem
- An exact algorithm for the static rebalancing problem arising in bicycle sharing systems
- An adaptive tabu search algorithm embedded with iterated local search and route elimination for the bike repositioning and recycling problem
- Alternative evaluation functions for the cyclic bandwidth sum problem
- The static bicycle relocation problem with demand intervals
- Public transport for smart cities: recent innovations and future challenges
- The one-station bike repositioning problem
- A destroy and repair algorithm for the bike sharing rebalancing problem
- Inventory rebalancing and vehicle routing in bike sharing systems
- Balancing the stations of a self service ``bike hire system
- A branch-and-cut algorithm for the one-commodity pickup and delivery location routing problem
- Bike sharing systems: solving the static rebalancing problem
- Risk‐averse two‐stage stochastic programming for the inventory rebalancing of bike‐sharing systems
- Large neighborhood search for the bike request scheduling problem
- Factors affecting the final solution of the bike-sharing rebalancing problem under heuristic algorithms
- The static bike relocation problem with multiple vehicles and visits
- Stochastic optimization models for a bike-sharing problem with transshipment
- A branch-and-cut algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem
- A two-phase heuristic approach to the bike repositioning problem
- M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System
This page was built for publication: A heuristic algorithm for a single vehicle static bike sharing rebalancing problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1652142)
