A Decomposition Algorithm to Solve the Multi-Hop Peer-to-Peer Ride-Matching Problem

In this paper, we mathematically model the multi-hop Peer-to-Peer (P2P) ride-matching problem as a binary program. We formulate this problem as a many-to-many problem in which a rider can travel my transferring between multiple drivers, and a driver can carry multiple riders. We propose a pre-processing procedure to reduce the size of the problem, and devise a decomposition algorithm to solve the original ride-matching problem to optimality by means of solving multiple smaller problems. We conduct extensive numerical experiments to demonstrate the computational efficiency of the proposed algorithm and show its practical applicability to reasonably-sized dynamic ride-matching contexts. Finally, in the interest of even lower solution times, we propose heuristic solution methods, and investigate the trade-offs between solution time and accuracy.

• Publication year

  2017

• Venue

  arXiv.org

• Publication date

  2017-04-22

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1016/j.trb.2017.01.004arXiv 1704.06838
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Optimization of a city logistics transportation system with mixed passengers and goods

  2017influential reference
• The benefits of meeting points in ride-sharing systems

  2015cited by this paper
• The Dial-A-Ride Problem with Transfers

  2014influential reference
• Ridesharing with passenger transfers

  2014cited by this paper
• Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots

  2014cited by this paper
• The shared-taxi problem: Formulation and solution methods

  2014cited by this paper
• Mathematical Programming Guides Air-Ambulance Routing at Ornge

  2013cited by this paper
• Ridesharing: The state-of-the-art and future directions

  2013cited by this paper
• Ridesharing in North America: Past, Present, and Future

  2012cited by this paper
• Optimization for dynamic ride-sharing: A review

  2012cited by this paper
• A genetic and insertion heuristic algorithm for solving the dynamic ridematching problem with time windows

  2012cited by this paper
• Dynamic Rideshare Optimized Matching Problem

  2012cited by this paper
• Ant Colony vs. Genetic Multiobjective Route Planning in Dynamic Multi-hop Ridesharing

  2011cited by this paper
• Dynamic ride-sharing: A simulation study in metro Atlanta

  2011cited by this paper
• Comparison of multiobjective evolutionary algorithms for solving the multiobjective route planning in dynamic multi-hop ridesharing

  2011cited by this paper
• Implementing Real-time Ridesharing in the San Francisco Bay Area

  2010influential reference
• The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method

  2010cited by this paper
• Sustainable Passenger Transportation: Dynamic Ride-Sharing

  2010influential reference
• Thinking Outside the Bus: Understanding User Perceptions of Waiting and Transferring in Order to Increase Transit Use

  2009cited by this paper
• The dial-a-ride problem: models and algorithms

  2006cited by this paper
• An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation

  2004cited by this paper
• A distributed geographic information system for the daily car pooling problem

  2004cited by this paper
• A decision support system for the bimodal dial-a-ride problem

  1996cited by this paper
• The General Pickup and Delivery Problem

  1995cited by this paper
• A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows

  1986cited by this paper
• An Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time Windows

  1983cited by this paper
• Scheduling Dial-a-Ride Transportation Systems

  1978cited by this paper

• Ride-sharing matching and route planning based on adjustable passenger pick-up and drop-off points

  2026cites this paper
• A multi-agent reinforcement learning scheduling algorithm integrating state graph and task graph structural modeling for ride-sharing dispatching

  2026cites this paper
• Quantum modeling of the dynamic ride-sharing problem: Development of quantum benders decomposition methods

  2026cites this paper
• The critical role of the value of time in peer-to-peer ridesharing models

  2025cites this paper
• An Optimization Framework for the Time-Dependent Electric Vehicle Routing Problem with Shared Mobility: A Step Toward Smart Cities

  2025cites this paper
• Research on Multi-hop Inference Optimization of LLM Based on MQUAKE Framework

  2025cites this paper
• Profit-Aware Graph Framework for Cross-Platform Ride-Sharing: Analyzing Allocation Mechanisms and Efficiency Gains

  2025cites this paper
• Optimal matching for ridesharing systems with endogenous and flexible user participation

  2025cites this paper
• Optimizing multi-modal ride-matching with transfers

  2025cites this paper
• The Taxi‐Sharing: User Equilibrium, System Optimum and Pricing Scheme Design

  2025cites this paper
• Joint matching and pricing for taxi drive-by sensing

  2025cites this paper
• Optimal pricing and vehicle allocation in local ride-sharing markets with user heterogeneity

  2025cites this paper
• A Matching Model for Ride-Sharing: A Non-Cooperative Game Approach Between Drivers and Riders

  2025cites this paper
• A dynamic stable multi-rider ridesharing matching model considering the fairness of cost savings allocation

  2025cites this paper
• Sustainable ridesharing routing and scheduling problem: an efficient multi-objective adaptive large neighborhood search

  2025cites this paper
• The VCG pricing policy with unit reserve prices for ride-sourcing is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si251.svg" display="inline" id="d1e1633"><mml:mfrac><mml:mrow><mml:mn>3</mml:mn></mml:mrow><mml:mrow><mml:mn>4</mml:mn></mml:mrow></mml:mfrac></mml:math>-individual c

  2025cites this paper
• Feasibility assessment of ride-sharing system in mountainous area in Japan using a matching model

  2025cites this paper
• Optimizing passenger group vehicle assignment in ride sharing systems using greatest common divisor approach

  2025cites this paper
• Partnering with transportation network companies (TNCs) for low-demand service: is it viable and beneficial for transit agencies?

  2025cites this paper
• Designing an Autonomous Mobility-on-Demand Service for Transit Last-Mile Access

  2024cites this paper
• The Dial-a-Ride problem with meeting points: A problem formulation for shared demand–responsive transit

  2024cites this paper
• Freelance drivers with a decline choice: Dispatch menus in on-demand mobility services for assortment optimization

  2024cites this paper
• Semi-on-Demand Off-Peak Transit Services with Shared Autonomous Vehicles - Service Planning, Simulation, and Analysis in Munich, Germany

  2024cites this paper
• Internalizing sensing externality via matching and pricing for drive-by sensing taxi fleets

  2024cites this paper
• A novel approach for online B-ride-hailing service by Tan-Tum using pre-matching information scheme

  2024cites this paper
• A column and row generation approach to the crowd-shipping problem with transfers

  2024cites this paper
• Rolling horizon strategies for a dynamic and stochastic ridesharing problem with rematches

  2024cites this paper
• Dynamic Usage Allocation and Pricing for Curb Space Operation

  2024cites this paper
• An Analytical Model of Many-to-one Carpool System Performance Under Cost-based Detour Limits

  2024cites this paper
• On non-myopic internal transfers in large-scale ride-pooling systems

  2024cites this paper
• Order dispatching and vacant vehicles rebalancing for the first-mile ride-sharing problem

  2024cites this paper
• Public transport crowdshipping: moving shipments among parcel lockers located at public transport stations

  2024cites this paper
• D-SPAC: Double-Sided Preference-Aware Carpooling of Private Cars for Maximizing Passenger Utility

  2024cites this paper
• Conceptualizing customer experience in multi-actor platforms

  2024influential citation
• Increasing driver flexibility through personalized menus and incentives in ridesharing and crowdsourced delivery platforms

  2024cites this paper
• Optimization of ride-sharing with passenger transfer via deep reinforcement learning

  2023cites this paper
• Assessing the Potential of Carpooling for Reducing Vehicle Kilometers Traveled

  2023cites this paper
• A multimodal multi-provider market equilibrium model: A game-theoretic approach

  2023cites this paper
• Coalitional Double Auction For Ridesharing With Desired Benefit And QoE Constraints

  2023cites this paper
• Adaptive Large Neighborhood Search for Order Dispatching and Vacant Vehicle Rebalancing in First-Mile Ride-Sharing Services

  2023cites this paper
• Integration of ridesharing and activity travel pattern generation

  2023cites this paper
• Agent-Based Mobility Simulation for Potential Cost and Benefits of Subscription Services with Associated Cost Structures

  2023influential citation
• Mitigating information asymmetry to acquire venture capital financing for digital startups in China: The role of weak and strong signals

  2023cites this paper
• A Bilevel Approach for Compensation and Routing Decisions in Last-Mile Delivery

  2023cites this paper
• A dynamic graph-based many-to-one ride-matching approach for shared autonomous electric vehicles

  2023cites this paper
• Ridesharing: The Impact of Traffic Restrictions and Role Flexibility

  2023cites this paper
• A Survey of Machine Learning-Based Ride-Hailing Planning

  2023cites this paper
• Large-Scale Dynamic Ridesharing with Iterative Assignment

  2023cites this paper
• Modelling ride-sourcing matching and pickup processes based on additive Gaussian Process Models

  2022cites this paper
• Intelligent Shared Mobility Systems: A Survey on Whole System Design Requirements, Challenges and Future Direction

  2022cites this paper
• The vehicle routing problem of intercity ride-sharing between two cities

  2022cites this paper
• Environmental and social implications of incorporating carpooling service on a customized bus system

  2022cites this paper
• A Traveler Incentive Program for Promoting Community-Based Ridesharing

  2022cites this paper
• Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems

  2022cites this paper
• Carpooling in Connected and Autonomous Vehicles: Current Solutions and Future Directions

  2022cites this paper
• Day-to-day dynamics in a duopoly ride-sourcing market

  2022cites this paper
• Influence of dynamic congestion with scheduling preferences on carpooling matching with heterogeneous users

  2022cites this paper
• Prediction of Automobiles Prices Using Exploratory Data Analysis Based on Improved Machine Learning Techniques

  2022cites this paper
• A column generation approach for a dynamic ridesharing problem

  2022cites this paper
• Simulating Ride-Pooling Services with Pre-Booking and On-Demand Customers

  2022cites this paper
• The ridesharing problem without predetermined drivers and riders: formulation and heuristic

  2022cites this paper
• Optimizing Ridesharing with Transfers in Urban Areas

  2022cites this paper
• Decentralized coordination for truck platooning

  2022cites this paper
• Optimality-guaranteed algorithms on the dynamic shared-taxi problem

  2022cites this paper
• Bi Objective Peer-to-Peer Ridesharing Model for Balancing Passengers Time and Costs

  2022cites this paper
• A truthful subsidy scheme for a peer-to-peer ridesharing market with incomplete information

  2022cites this paper
• Developing an Optimal Peer-to-Peer Ride-Matching Problem Algorithm with Ride Transfers

  2022influential citation
• Evaluating the Environmental Benefits of Personalized Travel Incentives in Dynamic Carpooling

  2022cites this paper
• Access-Based Consumption in the Built Environment: Sharing Spaces

  2022cites this paper
• The Internet of Federated Things (IoFT)

  2021cites this paper
• Graph-based many-to-one dynamic ride-matching for shared mobility services in congested networks

  2021cites this paper
• Navigating the Landscape of the Sharing and Gig Economy Literature: A Systematic and Interdisciplinary Review

  2021cites this paper
• A state-of-the-art review of the sharing economy: Scientometric mapping of the scholarship

  2021cites this paper
• Parking management in the morning commute problem with ridesharing

  2021cites this paper
• Optimizing driver menus under stochastic selection behavior for ridesharing and crowdsourced delivery

  2021cites this paper
• Design and operation of efficient and budget-balanced shared-use mobility systems

  2021cites this paper
• A Matching Model for Door-to-Door Multimodal Transit by Integrating Taxi-Sharing and Subways

  2021cites this paper
• Pooling or not Pooling: the role of matching cost on mixed mode equilibria and VMT

  2021cites this paper
• A generalized ride-matching approach for sustainable shared mobility

  2021cites this paper
• Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks

  2021cites this paper
• Itinerary planning for cooperative truck platooning

  2021cites this paper
• A Study of the Factors Affecting Multimodal Ridesharing with Choice-Based Conjoint Analysis

  2021cites this paper
• Shared Mobility Problems: A Systematic Review on Types, Variants, Characteristics, and Solution Approaches

  2021cites this paper
• Coalitional Double Auction for Ride-Sharing with Buyout Ask Price

  2021cites this paper
• Understanding the impact of heterogeneous rider preferences on a shared autonomous vehicle system

  2020cites this paper
• A Data-Driven Optimization Approach For the Dynamic Shuttle Dispatching Problem

  2020cites this paper
• A passenger-to-driver matching model for commuter carpooling: Case study and sensitivity analysis

  2020cites this paper
• A path-based equilibrium model for ridesharing matching

  2020cites this paper
• Influence of Dynamic Congestion on Carpooling Matching

  2020cites this paper
• Modular transit: Using autonomy and modularity to improve performance in public transportation

  2020cites this paper
• A System Dynamics Model for Safety Supervision of Online Car-Hailing From an Evolutionary Game Theory Perspective

  2020cites this paper
• Who is more likely to get a ride and where is easier to be picked up in ride-sharing mode?

  2020cites this paper
• Using subsidies to stabilize peer-to-peer ridesharing markets with role assignment

  2020cites this paper
• Frontiers in Service Science: Ride Matching for Peer-to-Peer Ride Sharing: A Review and Future Directions

  2020cites this paper
• Nonprofit peer-to-peer ridesharing optimization

  2020cites this paper
• Clustered tabu search optimization for reservation-based shared autonomous vehicles

  2020cites this paper
• An algorithm for integrating peer-to-peer ridesharing and schedule-based transit system for first mile/last mile access

  2020influential citation
• Mechanism design for on-demand first-mile ridesharing

  2020cites this paper
• Pricing Carpool Rides Based on Schedule Displacement

  2020cites this paper
• A decomposition algorithm to solve dynamic city-scale ridesharing problem

  2020cites this paper