Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Probabilistic Approach for Demand-Aware Ride-Sharing Optimization
82
0
0.0
(
0
)
Added by
Qiulin Lin
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Ride-sharing is a modern urban-mobility paradigm with tremendous potential in reducing congestion and pollution. Demand-aware design is a promising avenue for addressing a critical challenge in ride-sharing systems, namely joint optimization of request-vehicle assignment and routing for a fleet of vehicles. In this paper, we develop a probabilistic demand-aware framework to tackle the challenge. We focus on maximizing the expected number of passenger pickups, given the probability distributions of future demands. The key idea of our approach is to assign requests to vehicles in a probabilistic manner. It differentiates our work from existing ones and allows us to explore a richer design space to tackle the request-vehicle assignment puzzle with a performance guarantee but still keeping the final solution practically implementable. The optimization problem is non-convex, combinatorial, and NP-hard in nature. As a key contribution, we explore the problem structure and propose an elegant approximation of the objective function to develop a dual-subgradient heuristic. We characterize a condition under which the heuristic generates a $left(1-1/eright)$ approximation solution. Our solution is simple and scalable, amendable for practical implementation. Results of numerical experiments based on real-world traces in Manhattan show that, as compared to a conventional demand-oblivious scheme, our demand-aware solution improves the passenger pickups by up to 46%. The results also show that joint optimization at the fleet level leads to 19% more pickups than that by separate optimizations at individual vehicles.
rate research
Read More
Sharing economy is a transformative socio-economic phenomenon built around the idea of sharing underused resources and services, e.g. transportation and housing, thereby reducing costs and extracting value. Anticipating continued reduction in the cost of electricity storage, we look into the potential opportunity in electrical power system where consumers share storage with each other. We consider two different scenarios. In the first scenario, consumers are assumed to already have individual storage devices and they explore cooperation to minimize the realized electricity consumption cost. In the second scenario, a group of consumers is interested to invest in joint storage capacity and operate it cooperatively. The resulting system problems are modeled using cooperative game theory. In both cases, the cooperative games are shown to have non-empty cores and we develop efficient cost allocations in the core with analytical expressions. Thus, sharing of storage in cooperative manner is shown to be very effective for the electric power system.
We propose a formal graph-theoretic model for studying the problem of matching rides online in a ride-sharing platform. Unlike most of the literature on online matching, our model, that we call {em Online Windowed Non-Bipartite Matching} ($mbox{OWNBM}$), pertains to online matching in {em non-bipartite} graphs. We show that the edge-weighted and vertex-weight
Large-scale ride-sharing systems combine real-time dispatching and routing optimization over a rolling time horizon with a model predictive control (MPC) component that relocates idle vehicles to anticipate the demand. The MPC optimization operates over a longer time horizon to compensate for the inherent myopic nature of the real-time dispatching. These longer time horizons are beneficial for the quality of relocation decisions but increase computational complexity. Consequently, the ride-sharing operators are often forced to use a relatively short time horizon. To address this computational challenge, this paper proposes a hybrid approach that combines machine learning and optimization. The machine-learning component learns the optimal solution to the MPC on the aggregated level to overcome the sparsity and high-dimensionality of the solution. The optimization component transforms the machine-learning prediction back to the original granularity through a tractable transportation model. As a consequence, the original NP-hard MPC problem is reduced to a polynomial time prediction and optimization, which allows the ride-sharing operators to consider a longer time horizon. Experimental results show that the hybrid approach achieves significantly better service quality than the MPC optimization in terms of average rider waiting time, due to its ability to model a longer horizon.
Accurate estimation of parameters is paramount in developing high-fidelity models for complex dynamical systems. Model-based optimal experiment design (OED) approaches enable systematic design of dynamic experiments to generate input-output data sets with high information content for parameter estimation. Standard OED approaches however face two challenges: (i) experiment design under incomplete system information due to unknown true parameters, which usually requires many iterations of OED; (ii) incapability of systematically accounting for the inherent uncertainties of complex systems, which can lead to diminished effectiveness of the designed optimal excitation signal as well as violation of system constraints. This paper presents a robust OED approach for nonlinear systems with arbitrarily-shaped time-invariant probabilistic uncertainties. Polynomial chaos is used for efficient uncertainty propagation. The distinct feature of the robust OED approach is the inclusion of chance constraints to ensure constraint satisfaction in a stochastic setting. The presented approach is demonstrated by optimal experimental design for the JAK-STAT5 signaling pathway that regulates various cellular processes in a biological cell.
On-demand ride-pooling (e.g., UberPool) has recently become popular because of its ability to lower costs for passengers while simultaneously increasing revenue for drivers and aggregation companies. Unlike in Taxi on Demand (ToD) services -- where a vehicle is only assigned one passenger at a time -- in on-demand ride-pooling, each (possibly partially filled) vehicle can be assigned a group of passenger requests with multiple different origin and destination pairs. To ensure near real-time response, existing solutions to the real-time ride-pooling problem are myopic in that they optimise the objective (e.g., maximise the number of passengers served) for the current time step without considering its effect on future assignments. This is because even a myopic assignment in ride-pooling involves considering what combinations of passenger requests that can be assigned to vehicles, which adds a layer of combinatorial complexity to the ToD problem. A popular approach that addresses the limitations of myopic assignments in ToD problems is Approximate Dynamic Programming (ADP). Existing ADP methods for ToD can only handle Linear Program (LP) based assignments, however, while the assignment problem in ride-pooling requires an Integer Linear Program (ILP) with bad LP relaxations. To this end, our key technical contribution is in providing a general ADP method that can learn from ILP-based assignments. Additionally, we handle the extra combinatorial complexity from combinations of passenger requests by using a Neural Network based approximate value function and show a connection to Deep Reinforcement Learning that allows us to learn this value-function with increased stability and sample-efficiency. We show that our approach outperforms past approaches on a real-world dataset by up to 16%, a significant improvement in city-scale transportation problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
