The static bicycle relocation problem with demand intervals

G Erdogan, Gilbert Laporte, Roberto Wolfler Calvo

Research output: Contribution to journalArticlepeer-review

111 Citations (SciVal)
212 Downloads (Pure)


This study introduces the Static Bicycle Relocation Problem with Demand Intervals (SBRP-DI), a variant of the One Commodity Pickup and Delivery Traveling Salesman Problem (1-PDTSP). In the SBRP-DI, the stations are required to have an inventory of bicycles lying between given lower and upper bounds and initially have an inventory which does not necessarily lie between these bounds. The problem consists of redistributing the bicycles among the stations, using a single capacitated vehicle, so that the bounding constraints are satisfied and the repositioning cost is minimized. The real-world application of this problem arises in rebalancing operations for shared bicycle systems. The repositioning subproblem associated with a fixed route is shown to be a minimum cost network problem, even in the presence of handling costs. An integer programming formulation for the SBRP-DI are presented, together with valid inequalities adapted from constraints derived in the context of other routing problems and a Benders decomposition scheme. Computational results for instances adapted from the 1-PDTSP are provided for two branch-and-cut algorithms, the first one for the full formulation, and the second one with the Benders decomposition.
Original languageEnglish
Pages (from-to)451-457
Number of pages7
JournalEuropean Journal of Operational Research
Issue number2
Early online date18 Apr 2014
Publication statusPublished - 16 Oct 2014


  • Traveling salesman
  • pickup and delivery
  • branch-and-cut


Dive into the research topics of 'The static bicycle relocation problem with demand intervals'. Together they form a unique fingerprint.

Cite this