Source-linked AI summary
A Decomposition Algorithm to Solve the Multi-Hop Peer-to-Peer Ride-Matching Problem
Neda Masoud, R. Jayakrishnan
TL;DR
The paper addresses multi-hop P2P ride-matching in which riders can transfer between drivers and drivers can carry multiple riders. It develops a binary-programming model with preprocessing and decomposition to solve the problem to optimality. Experiments report higher efficiency and throughput for multi-hop matching, while the algorithm is positioned for real-time and multimodal applications within tested computational limits.
Problem
P2P ride-matching must coordinate drivers carrying multiple riders and riders transferring between vehicles while meeting time, capacity, and transfer requirements.
Method
The paper models many-to-many multi-hop matching as a binary program, reduces its inputs through preprocessing, and solves it to optimality by iteratively solving smaller subproblems.
Results
Experiments found higher efficiency and throughput for multi-hop ridesharing, with the value of multi-hop solutions more prominent when driver routes are system-determined.
Takeaways & Limitations
Independent subproblems can be computed in parallel, supporting real-time applications, while unlimited transfers also support multimodal networks.
Takeaways & Limitations
A 100-station static instance could not be solved to optimality because of memory limits and required a heuristic solution.
Abstract
from arXiv · showhide
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 by 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.
1 Introduction
The paper motivates P2P ridesharing as a way to use empty vehicle capacity amid transportation pressures, enabled by improved communications and flexible multi-hop matching.
- P2P ridesharing uses existing passenger-movement capacity to address transportation demand that is costly to meet through infrastructure expansion.
- Earlier ridesharing systems struggled because of inadequate marketing, limited flexibility and convenience, and insufficient technology.
- GPS-enabled phones improved access to participant locations and security, supporting greater accessibility and interest in newer ridesharing systems.
- Average vehicle occupancy was 1.7 of 4 available seats in 2009, falling to 1.2 for work-based trips.
- The paper defines dynamic P2P ridesharing as one-time, on-the-fly or pre-arranged rideshares between peer drivers and riders.
- Unlike traditional carpooling, dynamic ridesharing does not rely on extended-duration shared trips or non-real-time matching.
- Drivers may carry multiple riders, while riders may transfer between vehicles through multi-hop itineraries.
- The system matches participants subject to time windows, maximum ride times, transfer limits, vehicle capacities, and short re-optimization periods.
2 Literature Review
The literature places multi-hop P2P matching among increasingly flexible pickup-and-delivery and ridesharing models, while motivating an exact many-to-many formulation with scalable solution procedures.
- The multi-hop P2P ride-matching problem is a special case of the general pickup-and-delivery problem.
- Dial-a-ride models: Basic DARP assumes shared depot origins and destinations, homogeneous vehicles, and no transfers, while later variants add time windows, multiple depots, and heterogeneity.
- Dial-a-ride models: DARPT extends dial-a-ride models by allowing passengers to transfer between vehicles or transportation modes, with prior studies imposing limited transfer structures.
- Ride-matching models: Ride-matching systems can be spatiotemporally sparse because drivers have distinct origins, destinations, capacities, and narrow travel-time windows.
- Ride-matching models: Prior ridesharing models range from one-to-one matching to many-to-one systems that let drivers carry multiple riders.
- Many-to-many matching: Many-to-many matching allows multiple passengers per driver and rider transfers, but earlier exact work solved only a small instance with 6 requests, 2 vehicles, and 1 transfer point.
- Paper contribution: The proposed methodology can also support multimodal networks in which public transport lines act as fixed-route drivers.
- Paper contribution: The paper formulates many-to-many matching as a binary program in a time-expanded network, preprocesses inputs, and decomposes the problem into smaller subproblems solved to optimality.
3 Ridesharing System
The ridesharing system represents participants and movement in a time-expanded network, then periodically re-optimizes matches using stations, time windows, capacities, and transfer constraints.
- Participants are divided into riders seeking trips and drivers providing rides, with drivers potentially having different participation incentives.
- Stations are designated locations where participants start and end trips and riders transfer between drivers or other transportation modes.
- Each participant supplies origin and destination stations, acceptable departure and arrival times, a maximum ride time, and a notification deadline.
- Drivers announce vehicle capacity, while riders specify the maximum number of transfers they will accept.
- The study horizon is discretized into time intervals to support time-dependent travel-time matrices and construct feasible participant paths.
- A time-expanded network represents a node by a time interval and station, and a link by departure station-time and arrival station-time.
- A link sequence represents movement through the network, such as traveling from station 1 at time 1 to station 4 at time 3.
- A dummy driver represents waiting at stations when riders are not physically accompanied during transfers.
4 The Multi-hop P2P Ride-Matching Problem
The paper formulates multi-hop ride-matching as a binary optimization model that routes drivers and riders while enforcing matching, capacity, time, and transfer requirements; direct solution is computationally prohibitive.
- The ride-matching problem devises itineraries by optimally routing drivers while satisfying rider transfers, vehicle capacities, travel windows, and maximum ride times.
- Four sets of decision variables represent rider-link-driver assignments, rider matching, and driver contributions to rider itineraries.
- The objective primarily maximizes the number of served riders and secondarily minimizes transfers through a weighted transfer term.
- Driver constraints route vehicles from their origins to destinations and enforce flow conservation across the time-expanded network.
- Rider variables indicate which driver carries a rider on each link, while the dummy driver represents station waiting during transfers.
- Rider constraints ensure successful matching, driver accompaniment, vehicle-capacity compliance, and limits on each rider’s transfers.
- The formulation can incorporate alternative objectives, matched-driver variables, and service times through additional terms, variables, and constraints.
- Directly solving the optimization model is computationally prohibitive even for small instances, so the paper introduces preprocessing and iterative subproblem decomposition.
5 Pre-processing Procedure
The pre-processing procedure narrows each participant’s accessible links and removes spatiotemporally incompatible matches without changing the ride-matching problem’s optimality. It combines reduced network graphs, forward and backward link generation, and rider–driver compatibility filtering.
- Optimality preservation: The reduced input sets preserve optimality because the procedure removes no feasible links or eligible potential drivers.The refined link, rider, and driver sets can therefore replace the original sets in the optimization problem without affecting its optimum.
- Reduced graphs: Participant origin, destination, maximum ride time, and travel-time window define an elliptical reduced graph that excludes inaccessible stations.The transverse diameter is set to the maximum distance reachable within the participant’s travel-time window, ensuring excluded stations are inaccessible.
- Link reduction: The link-reduction algorithm constructs each participant’s accessible link set through iterative forward and backward movements.Forward movement generates reachable links from the origin, while backward movement removes links leading to infeasible destination arrival times.
- Forward movement: Forward movement records reachable stations and time intervals using shortest-path and dynamic travel times within the participant’s reduced graph.The procedure initializes reachable-time and terminating-link sets, then expands active stations and constructs outgoing links.
- Backward movement: Backward movement removes links whose arrival times exceed the participant’s latest feasible arrival and recursively removes predecessor links that depend on them.In the example, links ending at time intervals 41 and 42 are removed when the latest feasible arrival is time 40.
- Compatibility filtering: The resulting link sets filter riders without compatible drivers and identify potential rider–driver matches through nonempty intersections of their accessible links.A rider must have spatiotemporal proximity to at least one driver at both origin and destination stations.
6 Decomposition Algorithm
The decomposition algorithm repeatedly solves smaller rider-subproblem models, resolves conflicts and loops, and stops when driver assignments are conflict-free. At termination, the union of subproblem solutions is globally optimal; the illustrative example reaches this point in iteration 4.
- Algorithm mechanics: The algorithm iteratively solves smaller sub-problems and terminates when their solutions contain no driver-assignment conflicts.When conflicts remain, applicable sub-problems are formed; unchanged or independently recoverable sub-problems need not be solved again.
- Algorithm mechanics: Intermediate sub-problems combine looping sub-problems to prevent repeated iteration sets.The algorithm checks whether the current sub-problem set matches one from an earlier iteration and combines contributing sub-problems when a loop is detected.
- Computational implementation: Sub-problems in each iteration can be solved independently, making parallel computing implementations possible.The method may solve a large problem immediately or progressively combine smaller sub-problems until the original problem is resolved.
- Illustrative example: In the six-rider, four-driver example, iteration 4 produces the global solution after 9 sub-problems are solved.The first iteration contains six active sub-problems that could be solved simultaneously; an intermediate sub-problem resolves the loop before conflicts disappear.
- Illustrative example: The simplified algorithm reaches the optimum in fewer iterations and less time in this example, although lower solution time is not generally expected.Its next iteration combines the sub-problems associated with riders 1, 3, 6, and 5 after identifying conflicting paths through driver 2.
- Optimality and bounds: At the final iteration, conflict-free driver routes yield the first feasible solution, which is optimal for the relaxation and, under the stated conditions, the original problem.Pre-processing does not harm optimality when excluded drivers lack spatiotemporal proximity; if objectives beyond rider-related terms are primary, the algorithm provides a bound instead.
7 Numerical Study
Numerical experiments evaluate preprocessing, matching designs, transfer patterns, decomposition performance, and sensitivity across randomly generated ride-matching instances. The results show that preprocessing and decomposition improve computational tractability, while flexible routing and transfers increase matching potential under the tested settings.
- 7.1 Pre-processing: 420 instances required at most 3.5 seconds of preprocessing, which reduced participants’ average feasible-link sets to 0.01 of the original size.Preprocessing time includes generating feasible participant links and feasible drivers for riders.
- 7.2 Value of a Multi-hop Solution: Flexible-route methods produced considerable improvements in matches, while allowing transfers added further benefits, especially when driver routes were not pre-specified.Fixed-route multi-hop matching was only slightly better than fixed-route single-hop matching, whereas flexible routing had a larger effect.
- 7.2 Value of a Multi-hop Solution: Multi-hop methods served more riders and engaged more drivers than their single-hop counterparts, while matched multi-hop drivers carried slightly more riders on average.The results also report higher occupancy in multi-hop fixed-route systems because matched drivers tend to operate on popular routes.
- 7.3 Percentage of Satisfied Riders’ Requests: For 100 randomly distributed riders requiring at least 40% service, the experiments indicated a need for at least 230 drivers, or 330 total participants.These percentages use uniformly distributed origin-destination patterns, described as a worst-case scenario relative to real networks.
- 7.4 Algorithm Performance: The decomposition algorithm solved every tested instance to optimality in no more than 7 iterations and achieved considerable solution-time savings without sacrificing accuracy.The comparisons were performed after preprocessing; most raw instances could not be solved without reducing their size because of memory limits.
- 7.5 Transfers: Over 90% of problem instances could fully serve riders with no more than two transfers, while transfers became more necessary when drivers were relatively scarce.The experiments assumed riders were comfortable with up to three transfers.
- 7.6 Sensitivity Analysis: At five-minute re-optimization periods, all sensitivity-analysis instances were solved in less than one minute, while higher spatial proximity improved served riders more than higher temporal proximity.Longer re-optimization periods generally reduced rider transfers and transfer waiting time, while matched-driver counts also decreased.
8 Application in Practice
The paper examines practical scalability of multi-hop ride matching through graph reduction, restricted transfer stations, coarser time intervals, and heuristic stopping. These approaches target lower solution times while measuring resulting solution quality.
- Scalability: Larger coverage areas and participant populations can increase solution times, weakening the algorithm’s effectiveness in dynamic applications.Reduced participant graphs limit stations to those within typical travel circumferences; longer trips can use selected inter-city stations and matching drivers.
- Transfer-station restriction: Restricting transfers to the top 80% of transfer stations kept served riders within 95% of the unrestricted solution on average.The experiment used 420 randomly generated instances and compared all-station transfers with transfers limited to the most frequently used stations.
- Time discretization: Larger time intervals create competing effects: they reduce pre-processed link sets but can increase temporal proximity among trips and solution times.The study evaluates 5-minute intervals against the paper’s 1-minute discretization.
- Time discretization: Five-minute intervals appear appropriate for schedules commonly reported in five-minute increments, but suitability depends on the application’s timing precision.The supplied discussion identifies minute-level transit integration as a contrasting setting.
- Heuristics: Heuristic solutions can be retrieved by stopping decomposition at a time limit, using the best feasible solution available from each iteration.The method obtains heuristic feasible solutions by solving set-packing problems during decomposition.
- Heuristics: Beyond 240 seconds, additional served riders were negligible, while 120 seconds produced results higher than or comparable to four alternative matching methods.Several instances required only 60 seconds, supporting short computational cutoffs for dynamic applications.
9 Conclusion
The paper formulates multi-hop P2P ride matching as a binary program and solves it with preprocessing and an exact decomposition algorithm. Experiments report higher efficiency and throughput for multi-hop matching, while heuristic and structural variants support dynamic, multi-modal applications.
- Formulation and algorithm: The binary formulation has a tight linear relaxation, while preprocessing reduces input sets and decomposition solves the problem through smaller sub-problems.The decomposition is exact and finite.
- Practical applicability: Independent sub-problems can be solved in parallel, producing computational savings relevant to real-time applications.The method permits as many transfers as necessary, supporting multi-modal networks.
- Empirical findings: Experiments comparing five matching algorithms found higher efficiency and throughput for the multi-hop ridesharing system.The comparisons used different degrees of matching flexibility.
- Practical applicability: Clustering trips in time and space and extracting heuristic solutions during iterations are proposed for dynamic, real-life-sized problems.These approaches are presented as ways to improve practical applicability.
A Proof of Proposition
The proof section explains how the formulation represents rider connections and collectively registers the drivers forming each itinerary. It also shows why the objective favors fewer transfers in a specific repeated-driver case.
- Proposition 1: A rider’s number of connections can be represented using the number of drivers on the itinerary when a driver does not pick up that rider multiple times.The paper uses an undesirable itinerary as a contradiction example for repeated pickup behavior.
- Proposition 1: If the same driver appears on separated itinerary links, the rider could accompany that driver across the intervening trip and reduce transfers.The example reduces two transfers to zero.
- Proposition 1: The objective term involving the rider’s transfer weight selects the zero-transfer route in that contradiction example.The paper notes that post-processing could alternatively refine the solution.
- Proposition 2: Constraint sets (5k) and (5l) register all drivers that collectively form each rider’s itinerary.Constraint (5k) forces the relevant driver indicator to one, while (5l) imposes its lower bound when the associated variable is active.
B Decomposition Algorithm
The decomposition algorithm begins with one active sub-problem per rider, repeatedly solves active sub-problems, reorganizes them across iterations, removes redundant work, and terminates when driver itineraries stabilize.
- Sub-problem construction: Next-iteration sub-problems are formed by grouping riders sharing matched drivers and carrying forward riders not assigned to newly formed groups.The construction updates the rider sets and applicability status of new sub-problems.
- Pattern handling and reuse: The algorithm detects repeated sub-problem patterns and creates intermediate sub-problems to prevent cycling between iterations.It then identifies active sub-problems; previously solved or conflict-free unions reuse existing solutions.
- Pattern handling and reuse: Active sub-problems are solved again, while solutions for identical or conflict-free composite sub-problems are derived from earlier iterations.The six-step summary cycles from active-sub-problem identification back to solving.
- Initialization and iteration: The first iteration creates one sub-problem for each rider and marks every sub-problem active.The algorithm then solves the active sub-problems before checking termination.
- Initialization and iteration: Each iteration solves active sub-problems and records matched drivers, rider itineraries, and rider-match indicators.These sets track the information needed for subsequent iteration construction and termination checks.
- Termination: The termination test stops when every driver has the same itinerary across the relevant sub-problems.Otherwise, the algorithm forms sub-problems for the next iteration.
C Revised version of the P2P multi-hop matching problem
Each decomposition iteration solves every sub-problem using optimization model (10). The rider and driver sets for sub-problem k in iteration i are denoted Rκ and Dκ.
- Every sub-problem k in iteration i is solved using optimization model (10).
- For simpler notation, the rider set in sub-problem k is denoted Rκ.
- The driver set in sub-problem k is denoted Dκ.