One-way Vehicle Sharing Systems (VSS), such as Velib' Paris, have a poor performance without regulation. We want to improve the efficiency of VSS using design strategies or pricing as incentive. Stochastic models are intractable for the size of systems we want to tackle. We therefore discuss a scenario-based approach, i.e. off-line deterministic optimization problems on a given stochastic realization (scenario). This deterministic model could be used to provide heuristics and bound for on-line stochastic optimization. This approach raises a new constraint the First Come First Served constrained flow (FCFS flow). We derive three problems based on FCFS flows: a design problem, optimizing station capacities, and two operational problems setting static prices. We show that they are all APX-Hard. We study the upper bound given by the classical Max Flow problem and prove its poor worst case ratio.
