Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorZhu, Tiantian
dc.identifier.citationZhu, T. (2018). Optimization in static repositioning activities of bike-sharing systems. Doctoral thesis, Nanyang Technological University, Singapore.
dc.description.abstractBike-sharing systems have become increasingly popular in cities all over the world. Satisfying the fluctuating and asymmetric demand is a crucial problem for bike-sharing systems. In order to ensure a good quality of user service, repositioning activities are conducted by a fleet of vehicles. This study focuses on the static repositioning problem, which usually happens at night and assumes no demand occurs during the period of repositioning operatIons. The goal is to determine the routes and loading instructions of vehicles with the minimal total time cost. In this thesis, first, new constraints are developed to speed up the Integer Programming (IP) model of the static repositioning problem. Tests on the IP model and the IP model with new constraints have been done to show the performance improvement by adding these new constraints. Then, a novel IP model with two commodities is formulated, which considers transferring both bikes and docking lockers, since movable docking stations are in a developing trend. After conducting a numerical experiment with small-sized simulated data, some patterns of computation time are pointed out and discussed. As the static repositioning problem is NP-hard, in the following study, two novel heuristics are put forward to handle larger-sized instances. One is called IP model based heuristic, which includes forming an undirected graph with less costly arcs and running IP model by setting the upper bound of decision variables based on the graph. The testing results of this IP model based heuristic show that this method can efficiently handle medium-sized instances with 40-90 stations. The other is called Set-Partitioning (SP) based heuristic, which includes generating a pool of feasible routes, selecting the best combination of feasible routes by SP model, modifying the solution of SP model, and rerunning the SP model after adding new modified feasible routes back to the pool of feasible routes. The process of solution modification and SP model rerun keeps repeating until the stopping criterion is reached. To our best knowledge, it is the first time that the SP model is implemented in the repositioning problem of bike-sharing systems. It is worth noting that the number of vehicles becomes an output instead of input in this SP model based heuristic. As a result, the computation time will not be affected by the increase of fleet size. In the numerical experiment, the maximum size of tested instances is 500 stations with 10 vehicles needed. The computational results show that all of the instances from 50 stations up to 200 stations can be solved in 7 minutes with a gap less than 7%. For the instances with 300-500 stations, the maximum computation time is up to 20 minutes.en_US
dc.format.extent122 p.en_US
dc.subjectDRNTU::Engineering::Industrial engineering::Operations researchen_US
dc.titleOptimization in static repositioning activities of bike-sharing systemsen_US
dc.contributor.supervisorChen Chun-Hsienen_US
dc.contributor.schoolSchool of Mechanical and Aerospace Engineeringen_US
dc.description.degreeDoctor of Philosophy (MAE)en_US
dc.contributor.organizationDepartment of Engineering Science, University of Aucklanden_US
item.fulltextWith Fulltext-
Appears in Collections:MAE Theses
Files in This Item:
File Description SizeFormat 
thesis.pdf1.1 MBAdobe PDFThumbnail

Page view(s) 50

Updated on Jul 20, 2024

Download(s) 20

Updated on Jul 20, 2024

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.