Maximum Closeness Centrality k-Clubs: A Study of Dock-Less Bike Sharing

Abstract EN

In this work, we investigate a new paradigm for dock-less bike sharing.

Recently, it has become essential to accommodate connected and free-floating bicycles in modern bike-sharing operations.

This change comes with an increase in the coordination cost, as bicycles are no longer checked in and out from bike-sharing stations that are fully equipped to handle the volume of requests; instead, bicycles can be checked in and out from virtually anywhere.

In this paper, we propose a new framework for combining traditional bike stations with locations that can serve as free-floating bike-sharing stations.

The framework we propose here focuses on identifying highly centralized k-clubs (i.e., connected subgraphs of restricted diameter).

The restricted diameter reduces coordination costs as dock-less bicycles can only be found in specific locations.

In addition, we use closeness centrality as this metric allows for quick access to dock-less bike sharing while, at the same time, optimizing the reach of service to bikers/customers.

For the proposed problem, we first derive its computational complexity and show that it is NP-hard (by reduction from the 3-Satisfiability problem), and then provide an integer programming formulation.

Due to its computational complexity, the problem cannot be solved exactly in a large-scale setting, as is such of an urban area.

Hence, we provide a greedy heuristic approach that is shown to run in reasonable computational time.

We also provide the presentation and analysis of a case study in two cities of the state of North Dakota: Casselton and Fargo.

Our work concludes with the cost-benefit analysis of both models (docked vs.

dockless) to suggest the potential advantages of the proposed model.