AI-Driven Smart Carpooling Framework for Optimal Route Planning and Resource Efficiency

Abstract

Carpooling is an effective approach to reduce traffic congestion, environmental impact, and energy consumption. However, optimizing the insertion of new ride requests into active carpool schedules remains a computational challenge due to the high time complexity of traditional insertion operators, typically O(n3). This research introduces a Dynamic Programming (DP)–based insertion technique that reduces the core scheduling computational complexity to O(n2) through a novel partitioning and state-space pruning framework. The proposed method efficiently determines optimal positions for new ride requests while considering capacity, route efficiency, and time constraints in real-time. Additionally, this DP core is integrated into a hybrid system that includes a two-stage heuristic for rapid meeting-point determination, enhancing real-time adaptability. Comparative analysis using a large taxi dataset (10,000 requests) demonstrates that the proposed dynamic programming model significantly improves both the efficacy and efficiency of carpool scheduling systems. Specifically, the DP approach achieved a 15% higher Matching Success Rate (92% vs. 80% for Branch and Bound) and reduced the Average Waiting Time by 3 minutes (from 6 to 3 minutes) compared to the next-best traditional method. Furthermore, the algorithm demonstrated a 50% reduction in CPU time (from 60 ms to 30 ms) in a balanced scenario compared to standard heuristics, validating the O(n2) complexity claim for the insertion module.