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

ABOD and its PyOD python module

Angle based detection By  Hans-Peter Kriegel, Matthias Schubert, Arthur Zimek  Ludwig-Maximilians-Universität München  Oettingenstr. 67, 80538 München, Germany Ref Link PyOD By  Yue Zhao   Zain Nasrullah   Department of Computer Science, University of Toronto, Toronto, ON M5S 2E4, Canada  Zheng Li jk  Northeastern University Toronto, Toronto, ON M5X 1E2, Canada I am combining two papers to summarize Anomaly detection. First one is Angle Based Outlier Detection (ABOD) and other one is python module that  uses ABOD along with over 20 other apis (PyOD) . This is third part in the series of Anomaly detection. First article exhibits survey that covered length and breadth of subject, Second article highlighted on data preparation and pre-processing.  Angle Based Outlier Detection. Angles are more stable than distances in high dimensional spaces for example the popularity of cosine-based similarity measures for text data. Object o is an out
Post a Comment
Read more

TableSense: Spreadsheet Table Detection with Convolutional Neural Networks

 - By Haoyu Dong, Shijie Liu, Shi Han, Zhouyu Fu, Dongmei Zhang Microsoft Research, Beijing 100080, China. Beihang University, Beijing 100191, China Paper Link Abstract Spreadsheet table detection is the task of detecting all tables on a given sheet and locating their respective ranges. Automatic table detection is a key enabling technique and an initial step in spreadsheet data intelligence. However, the detection task is challenged by the diversity of table structures and table layouts on the spreadsheet. Considering the analogy between a cell matrix as spreadsheet and a pixel matrix as image, and encouraged by the successful application of Convolutional Neural Networks (CNN) in computer vision, we have developed TableSense, a novel end-to-end framework for spreadsheet table detection. First, we devise an effective cell featurization scheme to better leverage the rich information in each cell; second, we develop an enhanced convolutional neural network model for tab
2 comments
Read more

DEEP LEARNING FOR ANOMALY DETECTION: A SURVEY

-By  Raghavendra Chalapathy  University of Sydney,  Capital Markets Co-operative Research Centre (CMCRC)  Sanjay Chawla  Qatar Computing Research Institute (QCRI),  HBKU  Paper Link Anomaly detection also known as outlier detection is the identification of rare items, events or observations which raise suspicions by differing significantly from the majority of the data. Typically the anomalous items will translate to some kind of problem such as bank fraud, a structural defect, medical problems or errors in a text. Anomalies are also referred to as outliers, novelties, noise, deviations and exceptions Hawkins defines an outlier as an observation that deviates so significantly from other observations as to arouse suspicion that it was generated by a different mechanism. Aim of this paper is two-fold, First is a structured and comprehensive overview of research methods in deep learning-based anomaly detection. Furthermore the adoption of these methods
1 comment
Read more