Dynamic Pick-up Point Recommendation Based on Multi-modal Deep Forest and Iterative Kuhn-Munkres Algorithm

0
0
0

Dynamic Pick-up Point Recommendation Based on Multi-modal Deep Forest and Iterative Kuhn-Munkres Algorithm

Introduction

The rapid development of intelligent communication terminals has eliminated information barriers between passengers and ride-hailing drivers, enabling real-time matching and efficient pick-up point recommendations. After a passenger places an order and matches with a driver, both parties need to reach a designated pick-up point. An optimal pick-up point configuration can significantly improve service efficiency, reduce economic and time costs, and alleviate urban traffic congestion.

Existing research on ride-hailing services primarily focuses on demand prediction, matching and dispatching, and route planning, with limited attention given to pick-up point recommendations. Current studies mainly address three aspects: reducing passenger walking distance and time, optimizing pick-up point road conditions, and minimizing travel costs. However, most existing models consider only a single influencing factor, leading to suboptimal recommendations. Moreover, GPS data often fails to accurately reflect feasible pick-up locations, and matching algorithms typically optimize single recommendations rather than achieving global optimality, resulting in order backlogs and traffic congestion at certain pick-up points.

To address these challenges, this paper proposes a dynamic pick-up point recommendation algorithm based on multi-modal deep forest and iterative Kuhn-Munkres matching. The contributions include:

  1. Potential Pick-up Point Extraction: A road network matching method is introduced to extract feasible pick-up points by considering real-time traffic conditions and road constraints.
  2. Multi-Factor Recommendation Model: A comprehensive model is established, incorporating passenger walking distance, walking time, pick-up point road conditions, and estimated trip cost.
  3. Multi-modal Deep Forest Prediction Algorithm: This algorithm integrates decision trees with deep learning techniques to enhance prediction accuracy and generalization.
  4. Iterative Kuhn-Munkres Configuration Algorithm: A global optimization approach is proposed to efficiently allocate passengers to pick-up points while balancing multiple objectives.

Problem Definition and Modeling

Key Definitions

  1. Pick-up Point (b_i): Defined by its ID, longitude, latitude, current passenger count, average passenger volume, and whether it is the optimal pick-up point.
  2. Passenger (p_j): Characterized by ID, initial location coordinates, destination coordinates, order time, and boarding time.
  3. Spatio-temporal Trajectory Data (t_k): Records vehicle movement patterns, including timestamps, coordinates, speed, direction, and passenger status.
  4. Capacity Threshold (∂_b_i): The maximum number of passengers a pick-up point can accommodate, calculated based on historical data and a buffer factor.

Key Influencing Factors

  1. Walking Distance (WDIS): Computed using the Haversine formula to measure the distance between a passenger’s location and the pick-up point.
  2. Walking Time (TIME): The difference between order placement and boarding time, converted into minutes for consistency.
  3. Road Condition Indicator (TRCI): Derived from vehicle acceleration and directional changes, indicating traffic congestion levels.
  4. Estimated Trip Cost (COST): Calculated based on base fare, distance rate, and additional fees.

Mathematical Model

The pick-up point recommendation problem is formulated as a linear integer programming model, where the objective is to maximize the weighted sum of the four influencing factors. Constraints ensure that the number of passengers assigned to each pick-up point does not exceed its capacity and that each passenger is assigned to only one pick-up point.

This problem is NP-hard, and traditional methods struggle with large-scale instances due to computational complexity. The proposed solution leverages machine learning for prediction and an efficient matching algorithm for real-time decision-making.

Solution Methodology

Potential Pick-up Point Extraction

GPS data is processed to identify boarding events where a vehicle transitions from an empty to an occupied state. These events are clustered using density-based spatial clustering (DBSCAN) to form potential pick-up points.

Road Network Matching

To address GPS inaccuracies, a point-to-line matching method is employed. Candidate road segments are evaluated based on geometric distance and directional alignment, ensuring that selected pick-up points align with actual road conditions.

Multi-modal Deep Forest Prediction Algorithm

The prediction algorithm consists of two stages:

  1. Multi-Grained Scanning (MGS): Sliding windows of varying sizes scan the input features to capture relationships between different dimensions.
  2. Cascade Forest (CF): A hierarchical structure processes the scanned features, combining predictions from multiple decision trees to enhance accuracy.

The algorithm integrates multi-modal random forests (MRF) and composite random forests (CRF). MRF combines random forests with gradient boosting to iteratively reduce prediction errors, while CRF introduces polynomial feature transformations to model nonlinear relationships.

Iterative Kuhn-Munkres Configuration Algorithm

The passenger-pick-up point assignment is modeled as a weighted bipartite graph, where edge weights represent the recommendation score. The iterative Kuhn-Munkres (IKM) algorithm optimizes global matching by:

  1. Initialization: Assigning initial labels to nodes based on maximum recommendation scores.
  2. Auxiliary Graph Construction: Selecting edges that satisfy weight conditions to form a subgraph for matching.
  3. Iterative Matching: Adjusting weights and augmenting paths to improve the solution until optimality is achieved.

IKM reduces computational complexity by focusing on local augmentations and early termination, making it suitable for large-scale problems.

Experimental Analysis

Dataset and Parameters

Experiments were conducted using Shanghai taxi GPS data and ride-hailing order records. Key parameters included:

• Earth radius: 6,371 km

• Pick-up point capacity threshold: 5 passengers

• Error threshold for road matching: 1 meter

• Time interval: 1 minute

Prediction Algorithm Evaluation

The multi-modal deep forest regression (MDFR) was compared against baseline models, including gradient boosting trees, random forests, linear regression, and neural networks. Performance metrics included mean absolute error (MAE), root mean squared error (RMSE), coefficient of determination (R²), and explained variance (EV).

Results showed that MDFR outperformed other models, reducing MAE by 2.705 and RMSE by 5.915 while improving R² by 0.214 and EV by 0.195. Ablation studies confirmed the contributions of MRF and CRF to prediction accuracy.

Configuration Algorithm Evaluation

Two scenarios were tested:

  1. Passenger Quantity Advantage (PQA): More passengers than pick-up points.
  2. Pick-up Point Quantity Advantage (PPQA): More pick-up points than passengers.

Three strategies were compared:

  1. Pick-up Point Priority Strategy (PPPS): Prioritizes road conditions and trip cost.
  2. Passenger Priority Strategy (PPS): Minimizes walking distance and time.
  3. Comprehensive Strategy (CS): Balances all factors.

Under PQA, CS achieved the highest average score (0.7648), outperforming PPPS by 2.04%. Under PPQA, PPS performed best (0.8917), with PPPS trailing by 4.14%.

IKM demonstrated superior efficiency, solving large-scale instances 64.97% faster than traditional Kuhn-Munkres while maintaining solution quality.

Travel Time Comparison

IKM reduced average passenger walking time and total trip duration compared to traditional methods. For instance, with 1,000 passengers, IKM reduced walking time by 3.95 minutes (vs. 7.10 minutes) and total trip time by 22.01 minutes (vs. 30.88 minutes).

Conclusion

This paper presents a dynamic pick-up point recommendation system that integrates multi-modal deep forest prediction and iterative Kuhn-Munkres matching. The proposed approach addresses the limitations of existing methods by:

  1. Accurately extracting feasible pick-up points from GPS data.
  2. Incorporating multiple influencing factors for comprehensive recommendations.
  3. Leveraging ensemble learning for robust prediction.
  4. Optimizing global passenger allocation efficiently.

Future work will explore incorporating driver perspectives and automated parameter tuning to further enhance performance.

doi.org/10.19734/j.issn.1001-3695.2024.04.0123

Was this helpful?

0 / 0