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)- The single-vehicle two-echelon one-commodity pickup and delivery problem
- Heuristic algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem
- Balancing the stations of a self service ``bike hire system
- Vehicle driven approaches for non preemptive vehicle relocation with integrated quality criterion in a vehicle sharing system
- A branch-and-cut algorithm for the one-commodity pickup and delivery location routing problem
- A two-phase heuristic approach to the bike repositioning problem
- Bike sharing systems: solving the static rebalancing problem
- The one-station bike repositioning problem
- Alternative evaluation functions for the cyclic bandwidth sum problem
- Stochastic optimization models for a bike-sharing problem with transshipment
- An exact algorithm for the static rebalancing problem arising in bicycle sharing systems
- PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems
- Factors affecting the final solution of the bike-sharing rebalancing problem under heuristic algorithms
- M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System
- A branch-and-cut algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem
- An adaptive tabu search algorithm embedded with iterated local search and route elimination for the bike repositioning and recycling 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
- Inventory rebalancing and vehicle routing in bike sharing systems
- The static bicycle relocation problem with demand intervals
- A destroy and repair algorithm for the bike sharing rebalancing problem
- The static bike relocation problem with multiple vehicles and visits
- Risk‐averse two‐stage stochastic programming for the inventory rebalancing of bike‐sharing systems
- Large neighborhood search for the bike request scheduling problem
- Public transport for smart cities: recent innovations and future challenges
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)
