The static bicycle relocation problem with demand intervals

• A variant of the One-Commodity Pickup and Delivery Traveling Salesman Problem is studied.
• The supply/demand of a vertex is represented by an interval rather than a single value.
• An integer programming formulation and a branch-and-cut algorithm are developed.
• Valid inequalities have been adapted from 1-PDTSP and Covering Tour Problem.
• The algorithm is capable of solving instances with up to 50 customers within two hours of CPU time.

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.