The static bicycle relocation problem with demand intervals

G Erdogan, Gilbert Laporte, Roberto Wolfler Calvo

Research output: Contribution to journalArticle

68 Citations (Scopus)
152 Downloads (Pure)

Abstract

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
Volume238
Issue number2
Early online date18 Apr 2014
DOIs
Publication statusPublished - 16 Oct 2014

Keywords

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

Cite this