Degree

Bachelor of Science (Computer Science)

Department

Department of Computer Science

School

School of Mathematics and Computer Science (SMCS)

Advisor

Dr. Syed Ali Raza, Assistant Professor, Department of Computer Science

Keywords

Algorithms, Cloud Integration, Google Maps, Geospatial Indexing, S2 Geometry, Constraint Satisfaction, Dynamic Fare Calculation

Abstract

University students in Pakistan face daily transportation challenges due to rising fuel costs, un- reliable public transit, and unstructured carpooling options. Informal platforms such as WhatsApp and Facebook groups are widely used, but lack essential features such as scheduling, safety protocols, and consistent pricing. To address these issues, our project introduces Vroo, a context-aware, university-focused ride-sharing application designed to optimize daily com- mutes while promoting cost savings and sustainability. Vroo provides a comprehensive solution through features such as verified university email- based authentication, dynamic fare estimation, real-time location tracking, and an AI-powered recommendation system. Our architecture follows an event-driven modular monolith pattern using Node.js, Flask microservices, and Firebase integrations for real-time communication and authentication. The core back-end services are hosted on the cloud, with persistent data stored in MongoDB Atlas and PostgreSQL. The ride-matching algorithm uses spatial (S2 cell-based route matching) and temporal con- straints to pair riders with compatible drivers, while also considering gender preferences, seat availability, and detour feasibility. The recommendation engine applies a content-based approach to rank matched drivers by analyzing route similarity, travel time preferences, reliability, ride frequency, user ratings, and previous successful matches, ensuring personalized and trustworthy suggestions. In addition, the fare estimation algorithm incorporates distance, time, fuel prices, and vehicle mileage for accurate cost calculation. The project also emphasizes usability with a mobile-first user interface featuring intuitive ride management and communication tools. Comprehensive test cases ensure reliability, security, and user satisfaction. The initial results of the prototype testing demonstrate a successful match of the ride and reduced CO2 emissions through shared travel. By addressing key gaps in the Pakistani carpooling ecosystem, Vroo offers a scalable, se- cure, and user-centric commuting solution aligned with global environmental and technological standards.

Tools and Technologies Used

  • Flutter
  • Node (Express)
  • Flask (Python)
  • MongoDB with Mongoose ODM
  • Firebase
  • FCM
  • JWT
  • Postgres
  • Nextjs
  • Google Maps Platform
  • Together AI, Azure

Methodology

Carpool matching is a complex, real-world problem that extends beyond finding the nearest driver. It involves dynamically satisfying multiple hard constraints that are spatial, temporal, and preference-based - within strict time and resource limits. The system must make real-time decisions in an environment where each incoming request can dynamically affect the feasibility of current assignments. These interactions are highly contextual and often non-monotonic, which means that the inclusion of one element can have ripple effects. Moreover, the problem becomes more complicated by the fact that both riders and drivers operate within individual limitations and expectations Goyal et al. (2024). This makes the solution space fragmented and sensitive to constraint violations. As a result, conventional approaches such as those that rely on spatial proximity, single-objective or static scoring functions, fail to capture the operational complexity and responsiveness needed in practical deployment scenarios. This project approaches the problem by drawing conceptual motivation from the Multiple Criteria Carpool Optimization (MCCO) framework proposed by Filˇcek et al. (2017). MCCO established that matching decisions in carpooling must consider multiple interrelated factors, including but not limited to social acceptability, detour tolerance, comfort, and timeliness. While MCCO applied utility-based optimization through multi-attribute utility theory (MAUT), our system adapts that philosophy but diverges architecturally. We move away from continuous utility scoring and global optimization, as those are computationally infeasible in high-speed, real-time systems. Instead, we adopted a hybrid, rule-based approach where the core idea is to treat the problem as a constrained assignment task, leveraging feasibility-first logic without requiring full CSP solvers. Rather than relying on traditional CSP algorithms such as backtracking search or arc consistency techniques, we take a different approach. Even though these methods are powerful and expressive, they are typically too slow and memory-intensive for real-time, production- scale systems. Instead, we implement a high-performance, modular architecture that combines constraint pruning, spatial indexing, and lightweight heuristic matching. This design allows us to maintain efficiency and scalability without compromising on constraint enforcement. Spatial compatibility is checked using (S2 Geometry Project, nd), which encodes the pickup 2 and drop-off locations as well as the driver’s route as hierarchical cells. To reduce the candidate space, only drivers whose routes intersect both the pickup and destination cells of a rider are considered for further evaluation. Next, temporal feasibility is enforced by finding the driver’s expected arrival time at the rider’s pickup location and ensuring that it falls within the rider’s defined availability window. Similarly, the rider’s drop-off must not violate their own maximum arrival time, the driver’s deadline, or cause any delay for existing passengers. Importantly, all time calculations account for cascading effects, such as adding a new rider to a route requires verifying that no existing passengers’ constraints are violated as a result. This constraint propagation ensures global consistency across the driver’s current pool of matches. In addition to spatial and temporal compatibility, the system enforces constraints on maxi- mum detour. If accommodating a new rider would exceed the driver’s declared detour thresh- old, the match is rejected early. Moreover, rider-defined gender preferences are enforced as hard filters: if the driver or existing passengers does not meet the rider’s acceptable gender criteria, they are excluded from consideration. Each of these constraints is implemented as an independent validation module, allowing them to be composed, extended, or reweighted as business rules or policies evolve. The matching engine follows a feasibility-first paradigm; i.e. instead of generating all pos- sible driver-rider combinations and scoring them, we eliminate infeasible matches at the earliest possible stage. This enables the system to scale to large numbers of requests while maintaining low latency. The matching logic incorporates heuristic prioritization but is not purely greedy. It builds candidate matches iteratively, ensuring at each step that both the individual and collec- tive constraints remain satisfied. When a feasible match is found, it is added to the result set; otherwise, the algorithm moves on without degrading prior solutions. To evaluate the effectiveness and efficiency of the system, we decompose the matching pipeline into distinct operational stages: candidate retrieval, constraint evaluation, solution space pruning, and feasible match selection. Each stage is instrumented to measure both its filtering efficiency and its contribution to final match quality. Candidate retrieval focuses on narrowing the search space using spatial cell overlap and basic eligibility checks such as seat availability, while constraint evaluation enforces time windows, detour limits, ETA calculations, and gender preferences. Solution space pruning removes all combinations that violate even a single hard constraint. This further confirms the correctness of the match set. Through staged filtering, the system achieves fast response times, minimizes unnecessary computations, and ensures that only high-quality, constraint-compliant matches are returned.

Document Type

Restricted Access

Submission Type

BSCS Final Year Project

Download

Share

COinS