PaperlayerView exact revision on arXiv

Source-linked AI summary

DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learning

Abubakr Alabbasi, Arnob Ghosh, Vaneet Aggarwal

arXiv:1903.03882v1cs.NEeess.SY

TL;DR

Ride-sharing platforms need efficient dispatch under uncertain demand, complex passenger constraints, and large-scale fleet operations. DeepPool addresses this with a distributed model-free DQN framework in which vehicles learn policies independently from environmental interaction and demand statistics. On New York City taxi-trip data, it outperforms strategies that omit pooling or future-demand dispatching and is presented as adaptable to dynamic environments.

  • Problem

    Large-scale ride-sharing dispatch must make rapid vehicle decisions under uncertain demand while accounting for passenger behavior, travel time, and difficult-to-specify system models.

  • Method

    DeepPool uses distributed model-free deep reinforcement learning, allowing each vehicle to learn its own DQN dispatch policy from environmental interaction and learned demand statistics.

  • Results

    DeepPool outperforms strategies that do not consider ride sharing or dispatch vehicles toward regions where future demand is anticipated, using real-world New York City taxi-trip records.

  • Takeaways & Limitations

    The distributed design enables rapid adaptation to dynamic environments without coordination among vehicles.

Abstract

from arXiv · show

The success of modern ride-sharing platforms crucially depends on the profit of the ride-sharing fleet operating companies, and how efficiently the resources are managed. Further, ride-sharing allows sharing costs and, hence, reduces the congestion and emission by making better use of vehicle capacities. In this work, we develop a distributed model-free, DeepPool, that uses deep Q-network (DQN) techniques to learn optimal dispatch policies by interacting with the environment. Further, DeepPool efficiently incorporates travel demand statistics and deep learning models to manage dispatching vehicles for improved ride sharing services. Using real-world dataset of taxi trip records in New York City, DeepPool performs better than other strategies, proposed in the literature, that do not consider ride sharing or do not dispatch the vehicles to regions where the future demand is anticipated. Finally, DeepPool can adapt rapidly to dynamic environments since it is implemented in a distributed manner in which each vehicle solves its own DQN individually without coordination.

I. INTRODUCTION

Ride-sharing dispatch is difficult because vehicles must make rapid decisions under uncertain demand while accounting for passenger behavior and travel-time constraints. The paper proposes DeepPool, a distributed model-free deep reinforcement-learning framework that learns vehicle-specific dispatch policies and targets efficient resource use.

  • Motivation: Large-scale ride-sharing dispatch requires instantaneous decisions for many drivers under uncertain future demand and passenger-dependent travel constraints.Vehicles may need to remain active or reposition toward anticipated demand while avoiding excessive detours and user travel times.
  • Motivation: Existing optimization approaches require prespecified demand, utility, and trip-cost models that are difficult to estimate and update in dynamic environments.Deep reinforcement learning is introduced to learn transition behavior dynamically through deep neural networks and Q-learning.
  • Proposed approach: DeepPool is a distributed model-free method in which each vehicle independently learns a DQN policy by interacting with the environment, without coordinating with all other vehicles.The approach is intended to reduce complexity while dispatching vehicles across a service area.
  • Objectives: The optimization formulation minimizes demand-supply mismatch, customer and future-demand travel time, pooling-related extra user time, and vehicle-resource use.Reducing vehicle use is linked in the formulation to lower fuel consumption and traffic congestion.
  • Evaluation setup: DeepPool uses a 15 million New York City taxi-trip dataset to build a modular simulator and train independently learning vehicle policies.Its modular architecture and per-vehicle learning are presented as mechanisms for scalability.
  • Results: Evaluation reports that DeepPool outperforms state-of-the-art and baseline strategies and reduces operating vehicles by at least 500 for the same request acceptance rate and passenger wait time.The reported vehicle reduction is presented as a capability to reduce traffic congestion.

III. PROBLEM STATEMENT

The paper formulates ride-sharing dispatch as sequential decisions over vehicle locations, availability, capacity, requests, and anticipated demand. The dispatcher seeks to balance service quality, resource use, and future demand coverage through discounted rewards.

  • System model: The system models vehicles, passengers, and zones over a finite planning horizon, dispatching available vehicles while accounting for capacity and future availability.Available vehicles have at least one vacant seat and may be sent to zones for current or anticipated requests.
  • State representation: Each vehicle state records its location, vacant seats, passenger pickup times, and destinations, while future vehicle availability is predicted from dispatch decisions.Future demand statistics are also incorporated into the environment representation.
  • Objectives: The dispatch objective minimizes demand-supply mismatch, customer waiting and dispatch times, ride-sharing detours, and the number of used vehicles.These objectives reflect service quality, operating efficiency, and resource use.
  • Decision process: At each time step, the solver observes the state and reward, chooses actions directing idle vehicles, and maximizes expected discounted future reward.The agent-environment interaction is represented as state and reward informing the next action.

IV. PROPOSED FRAMEWORK DESIGN

The proposed framework converts the multi-objective ride-sharing problem into a model-free distributed learning procedure. DeepPool learns vehicle dispatch and routing policies from environmental rewards while representing mismatch, delay, detours, and vehicle use in the objective.

  • Framework: DeepPool uses distributed deep Q-networks to learn dispatch and routing policies for individual vehicles without requiring an accurate system model.Future demand and customer statistics are learned to support dispatch decisions.
  • Objective: The objective combines demand-supply mismatch, dispatch time, extra passenger travel time, and the number of used vehicles through weighted terms.The weights determine the relative importance of these components.
  • Dispatch decisions: Available vehicles may be dispatched to a zone for current or potential future customers, with decisions restricted by vehicle availability and occupancy.A vehicle can reposition even without a current request when future demand is anticipated.
  • Passenger delay: The ride-sharing penalty measures additional passenger travel time caused by detours or route changes after adding customers.The baseline is the travel time the vehicle would have taken while serving that passenger alone.
  • Resource use: The framework also minimizes active vehicle count because serving passengers with fewer vehicles can reduce fuel use and traffic congestion.The resource term targets vehicles becoming active from an inactive state.

B. DeepPool framework

DeepPool is implemented as a simulator-linked distributed architecture in which a control unit maintains fleet state and vehicle-specific DQN policies select dispatch actions sequentially.

  • Architecture: The simulator updates vehicle locations, destinations, and occupancy at every time step based on dispatch and assignment decisions.The control unit maintains these fleet-wide states.
  • Distributed policy: Each vehicle learns its dispatch action with a distributed DQN while considering nearby vehicles’ current locations.The policy does not anticipate the future actions of other vehicles.

1) State:

DeepPool represents the environment with a state vector assembled from fleet status, predicted vehicle availability, and predicted demand. Vehicle actions decide whether to serve new customers and, when applicable, which zone to enter.

  • State: The state tuple contains current vehicle status, predicted vehicle counts over the horizon, and predicted demand over the horizon.These elements capture system updates and future operating conditions.
  • State: The state elements are combined into vector s_t and passed to the neural network when new ride requests arrive.The environment supplies the vector used for decision-making.
  • Action: A vehicle action determines whether a partially filled vehicle serves existing or new users and, if serving new users, which zone it enters.The zone choice is encoded by u_t,n,i.

2) Action:

DeepPool’s reward function balances serving more customers against detours, added passenger travel time, and vehicle activation. Its weights can shift the policy from carpooling toward non-carpooling service.

  • The reward is zero when a vehicle only serves its existing passengers; otherwise, it evaluates accepting a new user and taking a detour.
  • The reward counts served customers, detour time, additional carpooling time, and whether an empty vehicle becomes occupied.These components are weighted by β_i; b_t,n counts customers, c_t,n measures pickup detour time, δ_t,n,ℓ measures added passenger time, and e_t,n captures activation.
  • A sufficiently large β3 penalizes detours enough to recover a no-carpooling scenario similar to the cited baseline.
  • Serving more requests reduces supply–demand mismatch, linking the first reward term to the system objective.
  • The detour and added-travel-time terms represent pickup costs and passenger delay, while the activation term controls use of previously empty vehicles.Using an empty vehicle can be beneficial when otherwise passenger distance or trip time would increase.

4) Learning Reward Function and Transition Probability:

DeepPool learns reward and transition dynamics with neural networks, then uses DQN action values to dispatch each vehicle. Its algorithm constructs vehicle states, selects reward-maximizing movements, and updates dispatches sequentially.

  • DeepPool learns the action–reward dependence and active-vehicle transition probabilities instead of specifying them explicitly.The learned reward distribution and transition probabilities are used to compute Q-values.
  • For each vehicle, DQN defines the optimal action-value as the maximum expected achievable reward and selects dispatch actions from network outputs.
  • The dispatcher feeds the current state to a neural network, whose Q-function approximation balances immediate and future rewards through the discount factor η.Small η emphasizes immediate reward, whereas large η emphasizes future reward.
  • Vehicles use ε-greedy exploration, choosing the highest-Q action with probability 1−ε and a random action otherwise; ε declines from 1 to 0.1.
  • Training uses a neural-network loss based on the difference between predicted and target Q-values, with weights updated through the learning process.
  • Algorithm 1 builds each state from requests and available vehicles, selects the argmax DQN action, assigns a destination, and updates the dispatch solution sequentially.Sequential updates allow later vehicles to consider earlier actions, although vehicles do not anticipate future actions by others.
  • The simulator matches requests to vehicles, sends dispatch orders, and moves vehicles along shortest paths while updating states and trajectories.

V. DEEPPOOL SIMULATOR DESIGN

DeepPool is evaluated in a simulator built from real Manhattan taxi-trip records. June 2017 data train the models, while one week of July 2017 data provides evaluation.

  • The simulator uses public Manhattan taxi-trip data containing pickup time, locations, passenger counts, and drop-off locations.These trip attributes are used to construct the travel-demand prediction model.
  • June 2017 records train the neural networks, and one week from July 2017 is reserved for evaluation.

A. Road Network and Estimated Time Models

The simulator represents Manhattan as a fine-grained road graph, estimates dispatch travel times with learned models, predicts future demand spatially, and trains vehicle policies with double Q-learning and replay.

  • Simulator procedure: The simulator initializes vehicle states, processes requests, assigns vehicles, updates each vehicle’s state, and sends the state vector to the agent for dispatch orders.
  • Simulator procedure: After dispatch, vehicles follow shortest paths, estimated travel times update trajectories, and the simulator advances the state vector.
  • Road network and travel time: The road network partitions the city into 212 × 219 service-area bins, each measuring 150m × 150m, and routes vehicles between nearby graph nodes using shortest paths.
  • Road network and travel time: Travel-time estimation uses a fully connected neural network trained on historical trip data to estimate travel time between dispatch locations.
  • Demand prediction: The demand CNN predicts expected requests 30 minutes ahead on a 212 × 219 output image, using demand from the previous two steps as input.
  • Road network and travel time: The road-network representation distinguishes locations within a zone because latitude and longitude can change dispatch and trip times.
  • Policy learning: Double Q-learning stores vehicle transitions in replay memory, samples random transitions for updates, and periodically synchronizes the target network.

C. DQN of DeepPool

DeepPool represents demand and vehicle supply as spatial feature maps and uses a convolutional Q-network to score dispatch actions. Distributed training uses experience replay, while changing environments require an additional action-probability parameter.

  • Q-network architecture: The vehicle’s action space contains 15 possible movements or dispatches represented by a 15 × 15 output map.Vehicles can move up to seven cells vertically or horizontally, or remain in place.
  • Q-network architecture: The network receives four 51x51 demand-and-supply planes, including predicted requests and expected available vehicles at 0, 15, and 30 minutes.Average pooling produces 23 × 23 × 4 feature maps before convolution.
  • Q-network architecture: Convolutional layers with 16, 32, 64, and 128 filters transform the feature maps before a 1x1 output layer produces action values.The first layer uses 5x5 filters; the next two use 3x3 filters.
  • Training procedure: Experience replay addresses instability from correlated action-value updates, while parameter α adapts action probabilities as each vehicle’s environment changes.Each vehicle runs its own DQN policy, so training conditions vary from the individual vehicle’s perspective.
  • Training behavior: As training progresses, predicted Q-values converge toward target values, while average maximum Q-values decrease after reaching about 90.The decrease is attributed to environmental variation reducing individual-vehicle returns.

VI. EVALUATION RESULTS

The evaluation uses one week of New York City taxi traces to compare DeepPool with policies differing in dispatching, ride-sharing, and demand anticipation. Across examined metrics, DeepPool reduces waiting and idle time, uses fewer vehicles, and performs close to actual-demand dispatch.

  • Evaluation setup: The evaluation uses real-world traces from the first week of July 2017 and compares DeepPool with multiple dispatch and ride-sharing baselines.The baselines include no-dispatch, no-ride-sharing, minimum-distance pooling, actual-demand dispatch, and centralized control policies.
  • Evaluation setup: The reward tracks supply-demand mismatch, dispatch time, ride-sharing extra travel time, and used vehicles, with reject rate measuring mismatch.A request is rejected when no nearby or available vehicle can serve it.
  • Reject and waiting outcomes: Increasing β1 decreases reject rate across all algorithms because the reward assigns greater weight to minimizing that metric.Waiting time is then evaluated across different accept rates, defined as 100% minus reject rate.
  • Resource utilization: DeepPool achieves the lowest idle time in the low-accept-rate regime by dispatching toward anticipated demand and pooling multiple customers.The paper connects this result to reduced gasoline cost and higher vehicle utilization.
  • Overall metric trade-offs: DeepPool uses fewer active vehicles and achieves the smallest waiting times compared with the other baselines.The paper attributes this combination to pooling capacity and optimized dispatching.
  • Overhead trade-offs: Higher travel-time overhead δt reduces waiting and reject rates but increases idle time as vehicles pool more customers.The gain over NoDS-RS is reported for all δt values, including small overheads.
  • Policy comparison: On Sunday from 6pm to 6am, DeepPool consistently performs best for waiting and idle time, remaining close to actual-demand dispatch.With 6000 vehicles, it also achieves better mean and minimum utilization than the other approaches.

C. Discussion

DeepPool’s distributed, model-free design offers practical advantages for individual vehicle decisions and rapid action selection, while extensions to heterogeneous users and vehicles remain future work.

  • Practical advantages: DeepPool lets each vehicle choose actions to maximize its own revenue, making the framework more realistic and practical than centralized and traditional methods.The discussion also notes that centralized methods may optimize the whole system better while failing to select each vehicle’s individually optimal action.
  • Practical advantages: Its distributed architecture takes less time than centralized approaches when selecting an action.
  • Practical advantages: DeepPool supports cost sharing among passengers and better vehicle-seat utilization, which can reduce traffic congestion.
  • Future extensions: The framework can be extended to multiple user classes and vehicle-specific reward weights, but complete analysis of these extensions remains future work.The proposed extensions include user-specific carpooling penalties or incentives and vehicle-specific parameters capturing driver preferences.

VII. CONCLUSIONS

The conclusions present DeepPool as a distributed model-free framework that learns dispatch policies from environmental interaction and demand statistics. On New York City taxi data, it outperforms strategies that omit ride sharing or anticipated future-demand dispatch, while rapid adaptation and several extensions remain important directions.

  • VII. CONCLUSIONS: DeepPool combines deep neural networks and reinforcement learning to learn vehicle dispatch policies through interaction with the external environment.The framework also incorporates travel-demand statistics and deep-learning models for ride-sharing vehicle management.
  • VII. CONCLUSIONS: On real-world New York City taxi-trip records, DeepPool performs better than strategies that omit ride sharing or future-demand-based vehicle positioning.
  • VII. CONCLUSIONS: Because DeepPool is distributed, it can adapt rapidly to dynamic environments.
  • VII. CONCLUSIONS: Future directions include interactions among service providers, multi-hop passenger service, and incentive mechanisms for carpooling adoption.
Loading 1903.03882v1…