The static bike relocation problem with multiple vehicles and visits

Teobaldo Bulhões , Anand Subramanian, Güneş Erdoğan, Gilbert Laporte

Research output: Contribution to journalArticle

19 Citations (Scopus)
70 Downloads (Pure)

Abstract

This paper introduces the static bike relocation problem with multiple vehicles and visits, the objective of which is to rebalance at minimum cost the stations of a bike sharing system using a fleet of vehicles. The vehicles have identical capacities and service time limits, and are allowed to visit the stations multiple times. We present an integer programming formulation, implemented under a branch-and-cut scheme, in addition to an iterated local search metaheuristic that employs efficient move evaluation procedures. Results of computational experiments on instances ranging from 10 to 200 vertices are provided and analyzed. We also examine the impact of the vehicle capacity and of the number of visits and vehicles on the performance of the proposed algorithms.

Original languageEnglish
Pages (from-to)508-523
Number of pages16
JournalEuropean Journal of Operational Research
Volume264
Issue number2
Early online date15 Jun 2017
DOIs
Publication statusPublished - 16 Jan 2018

    Fingerprint

Keywords

  • Bike sharing
  • Pickup and delivery
  • Routing
  • Shared mobility systems

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this