[Back]

C. Kloimüllner, G. Raidl:
"Hierarchical Clustering and Multilevel Refinement for the Bike-Sharing Station Planning Problem";
Talk: Conference Proceedings of Learning and Intelligent Optimization Conference, onference Proceedings of Learning and Intelligent Optimization Conference; 06-19-2017 - 06-21-2017; in: "Conference Proceedings of Learning and Intelligent Optimization Conference", (2017), ISBN: 978-3-319-69404-7; 1 - 16.

Abstract.
We investigate the Bike-Sharing Station Planning Problem
(BSSPP). A bike-sharing system consists of a set of rental stations, each
with a certain number of parking slots, distributed over a geographical
region. Customers can rent available bikes at any station and return them
at any other station with free parking slots. The initial decision process
where to build stations of which size or how to extend an existing system
by new stations and/or changing existing station con gurations is crucial
as it actually determines the satis able customer demand, costs, as well
as the rebalancing e ort arising by the need to regularly move bikes from
some stations tending to run full to stations tending to run empty. We
consider as objective the maximization of the satis ed customer demand
under budget constraints for xed and variable costs, including the costs
for rebalancing. As bike-sharing stations are usually implemented within
larger cities and the potential station locations are manifold, the size
of practical instances of the underlying optimization problem is rather
large, which makes a manual decision process a hardly comprehensible
and understandable task but also a computational optimization very
challenging. We therefore propose to state the BSSPP on the basis of
a hierarchical clustering of the considered underlying geographical cells
with potential customers and possible stations. In this way the estimated
existing demand can be more compactly expressed by a relatively sparse
weighted graph instead of a complete matrix with mostly small non-zero
entries. For this advanced problem formulation we describe an e cient
linear programming approach for evaluating candidate solutions, and for
solving the problem a rst multilevel re nement heuristic based on mixed
integer linear programming. Our experiments show that it is possible
to approach instances with up to 2000 geographical cells in reasonable
computation times.

http://publik.tuwien.ac.at/files/publik_266991.pdf