A heuristic algorithm for a single vehicle static bike sharing rebalancing problem

DOI10.1016/J.COR.2016.09.025zbMATH Open1391.90649arXiv1605.00702OpenAlexW2963578052MaRDI QIDQ1652142FDOQ1652142

Authors: Fábio Cruz, A. Subramanian, Bruno P. Bruck, Manuel Iori 

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1605.00702

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

zbMATH Keywords

vehicle routingiterated local searchsplit pickup and deliverybike-sharing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Transportation, logistics and supply chain management (90B06)

Cites Work

• Bike sharing systems: solving the static rebalancing problem
• Variable neighborhood search
• Inventory rebalancing and vehicle routing in bike sharing systems
• Balancing the stations of a self service ``bike hire system
• An exact algorithm for the static rebalancing problem arising in bicycle sharing systems
• Title not available (Why is that?)
• The static bicycle relocation problem with demand intervals
• 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 Tabu Search Heuristic for the Vehicle Routing Problem
• A simple and effective metaheuristic for the minimum latency problem
• The case for strategic oscillation
• An iterated local search heuristic for the split delivery vehicle routing problem
• Hybrid metaheuristics for the clustered vehicle routing problem
• PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems

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
• 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
• 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
• 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
• Inventory rebalancing and vehicle routing in bike sharing systems
• A destroy and repair algorithm for the bike sharing rebalancing problem
• 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
• Risk‐averse two‐stage stochastic programming for the inventory rebalancing of bike‐sharing systems
• Large neighborhood search for the bike request scheduling problem
• Bike sharing systems: solving the static rebalancing 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)