Free-floating bike-sharing systems: New repositioning rules, optimization models and solution algorithms

In this work different repositioning rules are investigated and compared in the context of free-floating bike-sharing systems. A static complete reposition setting is adopted, i.e., the system is operated (re-balanced) when the number of users riding bicycles can be neglected as it happens in many cities, for instance during the night. The popular ‘healthy or broken’ repositioning rule is revisited and examined along with two newly proposed rules, i.e., ‘pickup or delivery’ and ‘pickup and delivery’ rules. A discussion is also provided in terms of measuring the degree of an unbalancing in such a system. A mathematical model is proposed for each repositioning rule. Depending on the rule one will be facing a multi-trip vehicle routing or a multi-trip pickup and delivery vehicle routing problem, which is a problem not much investigated in the literature. An approximate algorithm is also devised for the problem, which is adapted to the multi-trip vehicle routing, and also suitable for multi-trip pickup and delivery vehicle routing problem with some corresponding adjustment. Computational tests are reported on to assess the methodological contributions of this work. These tests consider both randomly generated instances and two instances using real data. The results shown that ‘pickup and delivery’ rule is better than others when distribution degree of repositioning scenario is less than 0.5, while if the distribution degree exceeds 0.5, the ‘pickup or delivery’ rule is the most cost-effective one.