Source-linked AI summary
Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state-space-time network representations
Monirehalsadat Mahmoudi, Xuesong Zhou
TL;DR
On-demand ride-sharing requires solving time-windowed pickup-and-delivery routing under congestion, capacity, and assignment constraints. The paper proposes state-space-time network and dynamic-programming methods combined with Lagrangian relaxation, with experiments showing convergence to about a 5% gap on the Chicago Network after 10–15 iterations.
Problem
Large-scale ride-sharing routing must jointly handle time-dependent congestion, vehicle capacity, passenger time windows, and passenger-to-vehicle assignment.
Method
The paper models VRPPDTW as a time-discretized state-space-time flow network, solves single-vehicle routing by forward dynamic programming, and decomposes multi-vehicle assignment using Lagrangian relaxation.
Results
After 10–15 iterations, the sub-gradient algorithm typically converges to a gap of about 5% for the Chicago Network.
Takeaways & Limitations
The framework jointly supports passenger matching, synchronized vehicle routing, and request pricing in congested urban networks.
Takeaways & Limitations
Future work is needed for heterogeneous ride-sharing capacities, vehicle-specific service preferences, and grouped transportation requests.
Abstract
from arXiv · showhide
Optimization of on-demand transportation systems and ride-sharing services involves solving a class of complex vehicle routing problems with pickup and delivery with time windows (VRPPDTW). This paper first proposes a new time-discretized multi-commodity network flow model for the VRPPDTW based on the integration of vehicles carrying states within space-time transportation networks, so as to allow a joint optimization of passenger-to-vehicle assignment and turn-by-turn routing in congested transportation networks. Our three-dimensional state-space-time network construct is able to comprehensively enumerate possible transportation states at any given time along vehicle space-time paths, and further allows a forward dynamic programming solution algorithm to solve the single vehicle VRPPDTW problem. By utilizing a Lagrangian relaxation approach, the primal multi-vehicle routing problem is decomposed to a sequence of single vehicle routing sub-problems, with Lagrangian multipliers for individual passengers requests being updated by sub-gradient-based algorithms. We further discuss a number of search space reduction strategies and test our algorithms, implemented through a specialized program in C++, on medium-scale and large-scale transportation networks, namely the Chicago sketch and Phoenix regional networks.
1 Introduction
Ride-sharing is presented as a response to congestion and resource constraints, while VRPPDTW provides a framework for jointly optimizing passenger requests, vehicle routes, and time-dependent travel conditions.
- Rising travel activity and congestion motivate demand-responsive transit and dynamic ride-sharing as transportation-management strategies.
- Ride-sharing coordinates travelers with different schedules through on-demand or prescheduled transportation requests.
- The proposed VRPPDTW model recognizes time-dependent link travel times caused by congestion at different times of day.
- The approach jointly matches passenger requests to providers, synchronizes vehicle routing, and determines request pricing through Lagrangian multipliers.
2 Literature review and research motivations
The paper addresses the difficulty of applying pickup-and-delivery routing models to large, congested transportation networks. It combines state-space-time modeling, dynamic programming, and Lagrangian relaxation to support multi-vehicle assignment and routing.
- PDPTW extends VRPTW by pairing each request’s pickup and drop-off, adding pickup or delivery time windows, and requiring service by one vehicle.
- Because VRPTW is NP-hard, the generalized PDPTW is also NP-hard, motivating specialized solution approaches.
- Existing methods address particular problem sizes, but exact optimization remains challenging for large-scale pickup-and-delivery problems.
- Large-scale deployment must account for regional-network congestion, road capacities, traffic delays, and signal timing.
- The paper formulates PDPTW on space-time transportation networks to represent complex time windows and incorporate practical waiting costs.
- Its contributions include a time-discretized multi-dimensional flow model, time-dependent single-vehicle dynamic programming, and Lagrangian decomposition.
- The framework integrates passenger matching, synchronized routing, and request pricing to balance demand satisfaction with transportation resources.
3 Problem statement based on state–space–time network representation
The paper formulates PDPTW on a time-dependent transportation network by combining vehicle routes with passenger-carrying states, dummy nodes, and time windows. This representation supports state enumeration and dynamic programming while accommodating capacity, sharing, and infeasible-demand safeguards.
- Network and service representation: The PDPTW is modeled on directed transportation networks with time-dependent link travel times, passenger pickup and delivery windows, and vehicle depot constraints.Each request requires pickup and drop-off, while vehicles may share trips subject to capacity and routing constraints.
- Network and service representation: Dummy nodes represent passenger origins, destinations, and vehicle depots, with connecting links interpreted as service or preparation time.These nodes distinguish service locations from physical transportation nodes and support time-window modeling.
- Space–time construction: Time is discretized into equal intervals, and vehicle paths through the space–time network encode feasible movement, waiting, pickup, and delivery decisions.The illustrated shortest paths show vehicle routes through transportation and dummy nodes over the discretized horizon.
- State representation: Dynamic programming defines each stage by time and each system state by the vehicle’s current node and passenger-carrying state.The carrying state records whether each passenger is riding, using passenger identifiers or dash symbols in an equivalent character representation.
- State representation: For three passengers and capacity two, feasible carrying states include the empty state, three one-passenger states, and three two-passenger states, while carrying all three is infeasible.The state examples include [p1 p2 _] for shared service and [_ p2 _] for serving one passenger.
- Feasibility and computation: Time-window incompatibility can eliminate otherwise possible carrying states, such as [p1 _ p3] when their pickup and delivery schedules cannot be jointly satisfied.The paper emphasizes feasible-state counts because they determine the computational effort of the dynamic-programming algorithm.
4 Time-discretized multi-commodity network flow programming model
The paper models VRPPDTW as a time-discretized multi-commodity flow problem on vehicle-specific state–space–time networks, integrating routing, passenger states, and time-dependent travel.
- Network representation: The model represents each vehicle’s route through state–space–time vertices indexed by location, time, and passenger-carrying state.Passenger pickups and drop-offs occur on service arcs, transportation links on transportation arcs, and waiting is represented by waiting arcs.
- Optimization model: Binary arc-use variables select vehicle movements, while flow-balance constraints connect each vehicle’s origin depot, intermediate vertices, and destination depot.Vehicles begin and end with the empty carrying state, and flow balance preserves route continuity.
- Optimization model: Passenger pickup constraints require every passenger to be picked up exactly once by either a physical or virtual vehicle.Because vehicles finish empty and state transitions include drop-offs, passenger delivery is enforced through route continuity.
- Optimization model: The objective minimizes total routing cost, while the state structure enforces feasible carrying states and vehicle capacity over time.Arc costs include transportation, service, and waiting costs, and feasible states limit passengers carried simultaneously.
- Network representation: Time-dependent travel is encoded on arcs, with arrival time s = t + TT(i,j,t).The formulation therefore propagates network travel time directly from departure time and traversed link.
5 Lagrangian relaxation-based solution approach
The solution approach relaxes passenger-assignment constraints with Lagrangian multipliers, decomposes the problem into vehicle-level path problems, and solves them using forward dynamic programming with search-space reduction.
- Lagrangian relaxation: Relaxing passenger pickup constraints with multipliers λ(p) converts the primal model into a Lagrangian problem with vehicle-network flow constraints retained.The relaxed objective incorporates passenger-specific multiplier terms into the routing formulation.
- Lagrangian relaxation: The simplified Lagrangian problem becomes a time-dependent least-cost path problem with generalized arc cost ξ = c + λ(p) on passenger-service arcs.Arcs outside the relevant passenger request retain their original routing cost c.
- Dynamic programming: Forward dynamic programming propagates labels through advancing time, feasible state transitions, and time-dependent arc costs to solve each single-vehicle path problem.The algorithm updates a downstream label when the new accumulated generalized cost is lower and stores predecessor information for reconstruction.
- Dynamic programming: The DP algorithm has worst-case complexity |V||T||A||W| across vehicle, time, link, and starting carrying-state dimensions.Transportation networks’ typical node out-degree of about 2–4 makes the link set much smaller than a complete graph.
- State representation: The proposed time-dependent state (w,i,t) focuses on the exact current time, contrasting with earlier cumulative or time-lagged passenger-state representations.The comparison emphasizes complete state representation while using carrying states that can exploit low vehicle capacity.
- Search region reduction: Three hard search-reduction rules eliminate infeasible vertices, and the practical overlap rule can reduce passenger-carrying states by more than half in the example.The fourth heuristic estimates the search-region reduction ratio; the example bounds the probability of more than two simultaneous sharing passengers below 43.75%.
6 Computational results and discussions
The experiments evaluate the proposed routing and assignment approach across small, medium, large, and randomly generated transportation networks. Results illustrate feasible ride-sharing assignments, passenger pricing, convergence behavior, and challenges caused by network and demand structure.
- Six-node transportation network: When one vehicle cannot serve both passengers, passenger p1 is selected because the driver prefers the least-cost service.This is the outcome reported for Scenario III, where overlapping time windows make serving both passengers impossible.
- Six-node transportation network: The six-node experiments cover scenarios with ride-sharing, vehicle waiting, unserved passengers, vehicle assignment, and competition between vehicles.The scenarios vary passenger and vehicle counts, origin–destination pairs, and departure and arrival time windows.
- Pricing mechanism: Lagrangian multipliers converge to specific values that can be interpreted as passenger service prices offered by the provider.The pricing mechanism is illustrated over 30 iterations for six passengers and one vehicle.
- Medium- and large-scale networks: The Chicago test network contains 933 nodes and 2,967 links, while the Phoenix network contains 13,777 nodes and 33,879 links.These networks are used for computational performance testing.
- Medium- and large-scale networks: After 10–15 iterations, the sub-gradient algorithm typically reaches a gap of about 5% for the Chicago network.The algorithm generally runs for a fixed number of iterations but may converge earlier.
- Randomly generated test instances: Randomly generated instances are converted into complete transportation digraphs, creating many links and difficult vehicle-to-passenger assignment conditions.Uniformly distributed passenger locations cause dense competition, unlike the naturally spatially sparse Chicago and Phoenix instances.
- Multi-vehicle assignment: The multi-vehicle problem uses set partitioning to enumerate passenger service patterns, with each passenger status encoded as waiting, onboard, or delivered.Binary variables select one pattern per vehicle while covering each passenger exactly once.
7 Conclusions
The paper targets ride-sharing optimization under time-dependent congestion and tight service constraints. It reformulates routing through space–time networks, combines assignment and routing with pricing, and identifies several extensions for future work.
- Motivation: Transportation network companies must handle time-dependent travel times, large-scale regional networks, and tight vehicle capacity and passenger service-time-window constraints.These requirements arise in planning and dispatching systems that connect travelers with different origins, destinations, and schedules.
- Proposed approach: The space–time reformulation directly solves routing and scheduling in congested transportation networks while avoiding explicit sub-tour elimination procedures.Virtual vehicles incorporate interactions between passenger demand and limited vehicle capacity.
- Practical implication: The joint optimization and pricing procedure helps providers quantify operating costs for spatially and temporally distributed trip requests.The resulting estimates are described as system-wide cost-benefit information for each request.
- Future work: Future work includes heterogeneous ride-sharing limits, vehicle-specific passenger preferences, grouped requests, and a comprehensive branch-and-bound algorithm.The paper also proposes evaluating capacity impacts through mesoscopic dynamic traffic simulation on large-scale regional networks.