-By Xinghua Zheng1, Ming Tang1, Hankz Hankui Zhuo1*, Kevin X. Wen
Abstract
Bike Sharing Systems (BSSs) have been adopted in many major cities of the world due to traffic congestion and carbon emissions. Although there have been approaches to exploiting either bike trailers via crowdsourcing or carrier vehicles to reposition bikes in the “right” stations in the “right” time, they do not jointly consider the usage of both bike trailers and carrier vehicles. In this paper, we aim to take advantage of both bike trailers and carrier vehicles to reduce the loss of demand with regard to the crowdsourcing of bike trailers and the fuel cost of carrier vehicles. In the experiment, we exhibit that our approach outperforms baselines in several datasets from bike sharing companies.
Bike-sharing systems (BSSs) typically have a set of base stations that are strategically placed throughout a city and each station has a fixed number of docks, e.g., Capital Bike-share, Bluebikes, Mobike, BIXI, etc. At the beginning of the day, each station is stocked with a pre-determined number of bikes. Customers can pick and drop bikes from any station and are charged depending on the hiring duration. Due to the individualistic and uncoordinated movements of customers, there is often starvation (empty base stations precluding bike pickup) or congestion (full base stations precluding bike return) of bikes at certain stations, which results in a significant loss of customer demand. To address this problem, a variety of systems employ the idea of repositioning idle bikes with the help of carrier vehicles during the day, by taking into account the movement of bikes by customers. While previous approaches of repositioning can help reduce imbalance, repositioning idle bikes using carrier vehicles incurs substantial routing and fuel costs while covering entire stations. In addition, repositioning idle bikes using bike trailers just carries a few of bikes once and the moving distance is limited, which restrict the usage of bike trailers to reposition bikes among stations.
In this paper, we propose an optimization model called (DRRPVT), which stands for Dynamically Repositioning and Routing Problem with carrier Vehicles and bike Trailers, to jointly consider the usage of carrier vehicles and bike trailers. We aim to better optimize the overall profit of hired bikes and consequently reduce the expected loss of demand. Specifically, we build a profit objective function to calculate the value of carrier vehicle routing (i.e., fuel cost) and bike trailers (i.e., payment for the users of bike trailers), by considering a variety of constraints with respect to carrier vehicle routing and bike repositioning. Jointly considering both carrier vehicles and bike trailers is challenging in the sense that we need to introduce new constraints to encode relations between carrier vehicles and bike trailers, and build a novel objective function to minimize the cost of repositioning (and routing) and the loss of demand. Besides, to improve the efficiency of our approach with respect to large scale stations (as well as carrier vehicles and bike trailers), we need to design an effective mechanism for computing main base stations to help reduce the computation time.
In summary, our contributions are two folds.
We first propose an optimization model to improve the performance of dynamic bike repositioning by exploiting both carrier vehicles and bike trailers simultaneously, which is different from previous approaches which only consider either trailers or carrier vehicles, but not both. To do this, we build a novel profit objective function and new constraints considering relationships between carrier vehicles and bike trailers.
Second, we design a clustering mechanism for computing main base stations to help improve the efficiency of solving the optimization model regarding large-scale stations and carrier vehicles and bike trailers
Related work
Static repositioning using carrier vehicles - finding routes for a fleet of vehicles to reposition bikes at the end of the day to achieve a predetermined inventory level at the stations.
Dynamic repositioning using carrier vehicles - a scalable online repositioning solution using multistage stochastic optimization with an online anticipatory algorithm
Dynamic repositioning using bike trailers - Proposes a pricing mechanism that takes the global view of the repositioning requirements and incentives the execution of bike-trailer tasks within the budget constraints.
DRRPVT approach aims to leverage the advantage of using both carrier vehicles, which is able to take a large number of bikes and move to longer distance, and bike trailers, which is able to move to short distance with limited cost and allow self-sustaining, by considering the expected profit and the loss demands reduction of repositioning and routing solution
Assumptions
1. We assume that users who carry bikes and trailers at decision epoch t always return their bikes at the beginning of the decision epoch t+ 1. The duration of each decision epoch is 30 minutes 7;2. We sampled the empirical distribution of the real historical data of customer requests to simulate customer requests for future time steps. We assume that the lost demand at the time of return. Once the distribution of bikes across the stations for time step t + 1 is obtained, we utilize this information to compute the repositioning strategy for trailers and vehicles for time step t + 1. This iterative process continues until we reach the last decision epoch;
3. Customers can rent a bike for 30 minutes or more, and they have to know in advance at which station they will return the bike. On the other hand, they return their bikes to the nearest available station if the destination station is full, and they leave the system if they encounter an empty station.
Constraints
C1: Preservation of Bike Flows in and out of the station
C2: Preservation of Bikes Flows between any two stations follow the transition dynamics observed in the data
C3: Value of task for the bike trailer.
C4: Ensuring Budget Feasibility.
C5: Preservation of Bikes Flows in and out of vehicles.
C6: Preservation of Vehicles Flows in and out of stations
C7: A maximum of one vehicle can be present in one station at any time step.
C8: Vehicles can only pick up or drop off bikes at a station if they are present at that station.
C9: Trailer capacity is not exceeded while picking up bikes.
C10: Total number of bikes picked up from a station is less than the available bikes
C11: Station capacity is not exceeded while dropping off bikes
C12: Total travelling distance for a trailer is bounded by a threshold value.
C13: A trailer can only pick up or drop off bikes at exactly one station.
C14: A trailer should return the exact number of bikes picked up.
C15: Station and vehicle capacities are not exceeded when repositioning bikes
DRRPVT Approach
- Identifying the right constraints to be dualized
- Extraction of a primal solution from an infeasible dual solution
- Decompose the original problem into a master problem and two slaves (SOLVEREDEPLOY and SOLVEROUTING)
- Calculating Main Stations
- Repositioning Bikes and Routing for Vehicles
- Incentivize Trailer Tasks
Result
Comments