Skip to main content

Bike sharing Dynamic Re-positioning

-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

Post a Comment

Popular posts from this blog

DDSP: DIFFERENTIABLE DIGITAL SIGNAL PROCESSING

 -By Google Research {jesseengel,hanoih,gcj,adarob}@google.com Paper Link Code Demo Abstract Most generative models of audio directly generate samples in one of two domains: time or frequency. While sufficient to express any signal, these representations are inefficient, as they do not utilize existing knowledge of how sound is generated and perceived. A third approach (vocoders/synthesizers) successfully incorporates strong domain knowledge of signal processing and perception, but has been less actively researched due to limited expressivity and difficulty integrating with modern auto-differentiation-based machine learning methods. In this paper, we introduce the Differentiable Digital Signal Processing (DDSP) library, which enables direct integration of classic signal processing elements with deep learning methods. Focusing on audio synthesis, we achieve high-fidelity generation without the need for large autoregressive models or adversarial losses, demonstrating that DDSP enable...
Post a Comment
Read more

Capsule Neural Networks

-By Sara Sabour, Nicholas Frosst,  Geoffrey E. Hinton  Google Brain Toronto Paper Link Abstract   A capsule is a group of neurons whose activity vector represents the instantiation parameters of a specific type of entity such as an object or an object part. We use the length of the activity vector to represent the probability that the entity exists and its orientation to represent the instantiation parameters. Active capsules at one level make predictions, via transformation matrices, for the instantiation parameters of higher-level capsules. When multiple predictions agree, a higher level capsule becomes active. We show that a discrimininatively trained, multi-layer capsule system achieves state-of-the-art performance on MNIST and is considerably better than a convolutional net at recognizing highly overlapping digits. To achieve these results we use an iterative routing-by-agreement mechanism: A lower-level capsule prefers to send its output to higher...
1 comment
Read more

Detecting Anomaly in Big Data System Logs Using Convolutional Neural Network

By - Siyang Lu, Xiang Wei, Yandong Li, Liqiang Wang Department of Computer Science, University of Central Florida, Orlando, FL, USA School of Software Engineering, Beijing Jiaotong University, China Paper Link Previous week we did a scan of the survey of Anomaly detection   , that covers breath of the topic (Types of Anomalies, Types of Models and their applications). In this summary paper, we look in to the core Heavy lifting part of Detecting Anomaly in Big Data System Logs Using Convolutional Neural Network. Abstract Nowadays, big data systems are being widely adopted by many domains for offering effective data solutions, such as manufacturing, healthcare, education, and media. Big data systems produce tons of unstructured logs that contain buried valuable information. However, it is a daunting task to manually unearth the information and detect system anomalies. A few automatic methods have been developed, where the cutting-edge machine lear...
Post a Comment
Read more