Lecture Notes in Mobility Jan Brinkmann Active Balancing of Bike Sharing Systems Lecture Notes in Mobility Series Editor Gereon Meyer, VDI/VDE Innovation und Technik GmbH, Berlin, Germany More information about this series at http://www.springer.com/series/11573 Jan Brinkmann Active Balancing of Bike Sharing Systems 123 Jan Brinkmann Institut für Wirtschaftsinformatik Technische UniversitätBraunschweig Braunschweig, Germany ISSN 2196-5544 ISSN 2196-5552 (electronic) Lecture Notesin Mobility ISBN978-3-030-35011-6 ISBN978-3-030-35012-3 (eBook) https://doi.org/10.1007/978-3-030-35012-3 ©SpringerNatureSwitzerlandAG2020 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission orinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfrom therelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained hereinorforanyerrorsoromissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregard tojurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Foreword Vehicle sharing has received a remarkable attention as a new means of urban transportation.Practicehasshownthattheone-wayuseofvehiclesfollowsmobility patterns of people leading to temporal and spatial imbalances with respect to the distributionofvehiclesinthecity.Instation-basedbikesharingsystems,customers sufferfromtheabsenceofbikesincaseofapotentialrentalandtheabsenceofbike racks in the case of a bike return. Station-less systems have claimed to offer flex- ibility; however, they have failed to overcome the deficiency of bike imbalances. System operators see the requirement of redistributing bikes between city areas overthedayatsignificantexpenses.Amethodologicalsupportofbikelogisticshas concentrated on static optimization models. These models are typically fed with data of historic bike usage. Since history does not repeat itself, optimal solutions obtained from static model cannot be implemented due to stochastics with respect to actual bike usage. Jan Brinkmann focuses on a control approach deciding dynamically about bike imbalances to be resolved. He combines control with an anticipation of future redistribution demand by means of online simulation. The simulation takes into account the driving time needed to arrive at the respective station, the loading or unloadingtimeatthisstationaswellastheavoidanceoffuturefailsresultingfrom bike inventory changes. The informative value of the simulation strongly depends on the simulation horizon. A short horizon may not reflect the utility of the station visit. Simulating over a long horizon may report on customer fails, which no longer relate to the respective station visit. Jan Brinkmann is able to provide evidence that a suitable simulation horizon is by no means fixed, but depends on the particular situation, i.e., the time of day. To this end, he develops an approximate dynamic program- ming approach determining heterogeneous simulation horizons iteratively. The above consideration applies to the one vehicle case only. Whenever a fleet of trucks is employed for bike redistribution, the decentral decisions of the trucks arenolongerindependentofeachother.Sinceallofthemfollowthesamedecision model,itmayhappenthatdemandingstationsmayaccidentallybevisitedmultiple times.JanBrinkmannsuggestsdifferentlevelsofcoordinationcomingalongwitha v vi Foreword slightly growing need for information exchange. The trucks operate independently ofeachotherandtakedecisionfortheirownoperation.Likeintheonevehiclecase before, decisions comprise the number of bikes to be loaded or unloaded at the current station and the station to be visited next. The control approaches developed are carefully validated for real-world instances of bike sharing systems. Promising results are obtained for all instances considered.Inparticular,theapproachisbestsuitedforbikesharingsystemswhich donotshowaregularstructureofbikeimbalancesduetocommutertravel.Regular flows from residential areas to office districts in the morning and reverse flows in thelateafternoonarerelativelyeasytopredictandtocounteract.Morechallenging are complex mobility patterns consisting of mixed work, shopping, and leisure activities. Results obtained indicate that these complex interactions can be sup- ported much better by control than by static optimization. JanBrinkmann pioneersonlinecontrolmodelsfor theredistributionlogistics of bike sharing systems. The work bases on a solid understanding of bike sharing system, business models, and related activities. The control approach pursued has been well received by the transportation research community as well as by col- leaguesworking inOperations Research. Thisbooksummarizes researchofrecent years by giving a comprehensive introduction into control approaches for today’s and forthcoming vehicle sharing systems. Braunschweig, Germany Dirk C. Mattfeld January 2019 Preface Many cities suffer from discomforts caused by individual and motorized traffic. Therefore,cityadministrationsimplementsustainablesharedmobilityservicessuch asbikesharingsystems(BSSs).InBSSs,usersareallowedtorentandreturnbikes on short notice at stations. Data analysis reveals that rental and return requests follow spatio-temporal patterns such as commuter usage and leisure activities. In the morning, commuter usage is indicated by mainly rental requests in residential areas and mainly return requests in working areas. This behavior inverts in the courseoftheday.Theresultingunequalrequestsleadstationstobecomeemptyor full. Requests to rent bikes will fail at empty stations. At full stations, requests to return bikes will fail. Providers counteract these inconveniences bymeans of balancing. Inthis work, wefocusontheoperationalmanagement'sviewonthebalancingofBSSs.Thatis, theproviderschedulestransportvehiclesrelocatingbikesbetweenstationsinorder to minimize the amount offailed requests. As requests are uncertain, the resulting challenge is to identify stations with a lack or a surplus of bikes. To this end, we introduce approaches simulating future requests and approximating expected amountsoffailedrequests.Then,anticipationisenabledbymeansofincludingthe approximations in the decision making process. Weevaluateourapproachesincasestudiesbasedonreal-worlddata.Theresults point out that our approaches are able to reduce the amount of failed requests significantly compared to common benchmarks from literature. Braunschweig, Germany Jan Brinkmann January 2019 vii Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Part I Preliminaries 2 Bike Sharing Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1 Urban Mobility. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Benefits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Reduction of Traffic. . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Improvement of Health. . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.3 Increase in Tourists Attractiveness . . . . . . . . . . . . . . . . 9 2.3 Functionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.1 Free-Floating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.2 Station-Based. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 Request Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4.1 Seasons and Weather . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.2 Commuters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.3 Leisure and Tourists. . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.5 Management Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.5.1 Strategical Management . . . . . . . . . . . . . . . . . . . . . . . . 13 2.5.2 Tactical Management . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5.3 Operational Management . . . . . . . . . . . . . . . . . . . . . . . 17 3 Optimization Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1 Vehicle Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.1 Traveling Salesman Problem. . . . . . . . . . . . . . . . . . . . . 19 3.1.2 Capacitated Vehicle Routing Problem . . . . . . . . . . . . . . 20 3.1.3 Vehicle Routing Problem with Time Windows . . . . . . . 20 3.1.4 Pickup-and-Delivery Problem . . . . . . . . . . . . . . . . . . . . 20 3.1.5 Inventory Routing Problem. . . . . . . . . . . . . . . . . . . . . . 20 ix x Contents 3.2 Inventory Routing for Bike Sharing Systems . . . . . . . . . . . . . . 21 3.2.1 No Request . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.2 Request. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4 Dynamic Decision Making . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.1 Markov Decision Processes. . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Approximate Dynamic Programming . . . . . . . . . . . . . . . . . . . . 35 4.2.1 Myopic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2.2 Lookahead. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2.3 Value Function Approximation. . . . . . . . . . . . . . . . . . . 38 Part II Application 5 The Stochastic-Dynamic Multi-Vehicle Inventory Routing Problem for Bike Sharing Systems . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.1 Narrative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Infrastructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.3 Markov Decision Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.4 Example. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.5 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6 Lookahead Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.1 Outline. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.2 Definition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.2.1 Simulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.2.2 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.3 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 6.3.1 Lookahead Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 6.3.2 Online Simulations. . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.3.3 Offline Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.3.4 Matrix Maximum Algorithm. . . . . . . . . . . . . . . . . . . . . 67 7 Dynamic Lookahead Horizons . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7.1 Outline. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7.2 Definition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.2.1 Sequences of Lookahead Horizons . . . . . . . . . . . . . . . . 72 7.2.2 Value Function Approximation. . . . . . . . . . . . . . . . . . . 73 7.2.3 Boltzmann Exploration. . . . . . . . . . . . . . . . . . . . . . . . . 74 7.3 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 7.3.1 Value Function Approximation. . . . . . . . . . . . . . . . . . . 77 7.3.2 Boltzmann Exploration. . . . . . . . . . . . . . . . . . . . . . . . . 79