Uncertainty-aware multi-objective optimization for rebalancing bike shared systems

Abstract

Overnight rebalancing in dock-based bike-sharing systems requires routing a limited fleet of trucks before user activity begins. This article formulates static rebalancing problem under stochastic demand uncertainty as a bi-objective combinatorial optimization problem that selects truck routes and visited stations. The first objective minimizes total travel distance. The second objective minimizes scenario-weighted unmet demand under a finite set of demand scenarios derived from historical station-status data. A deterministic recourse evaluation simulates truck loads and station inventories along each route and computes unmet demand for visited and unvisited stations. The article applies two multi-objective evolutionary algorithms, NSGA-II and MOEA/D, using a permutation–partition encoding and relocate-based operators that implement a 1–0 relocate neighborhood between routes. A roulette-wheel-based relocation operator (BB2) biases move selection by the induced change in route distance. Experiments on the Barcelona Bicing network with 518 stations and on clustered subinstances show that NSGA-II attains higher hypervolume and larger non-dominated sets, whereas MOEA/D attains lower runtime; an ablation analysis shows that BB2 improves coverage and proximity indicators.