Algorithmic approaches for Optimization problems in bike sharing and security control

Abstract

Most public-bike sharing systems consist of rental stations distributed among a city. These systems are designed for short-term use and single trips, i.e., bikes can be rent and returned at any station in the system. Thus, the problem of rebalancing the system arises, which is denoted as balancing bike sharing system problem. This problem is addressed with various (meta)heuristics and exact methods within this thesis. Moreover, when planning a new system or extending an existing one, the problem of selecting appropriate locations and con gurations for stations arises. Hereby, budget restrictions and other constraints need to be considered and the expected user bene t should be maximized. This problem is referred to as the bike sharing station planning problem. In practice, large instances of this problem must be solved, and it is necessary to come up with a solution method that is able to \overlook the problem as a whole" | classical local-search methods or basic greedy construction methods would not be meaningful. We propose a solution method based on the multilevel re nement paradigm, which utilizes a hierarchically clustered input data. The third combinatorial optimization problem considered in this thesis is the Districting and Routing Problem for Security Control. The optimization goal is to minimize the number of routes that are necessary to perform speci ed visits of buildings. To this end, we propose a smart district elimination algorithm. Lastly, we also study this problem with soft time windows and suggest a fast hybrid heuristic based on dynamic programming, which can frequently yield proven optimal solutions in short times.