> ## Documentation Index
> Fetch the complete documentation index at: https://poolerz.mintlify.site/llms.txt
> Use this file to discover all available pages before exploring further.

# Optimization

> Information regarding the optimization algorithm of Poolerz.

## Overview

The carpool optimization algorithm clusters users into valid carpool groups based on availability, location, and vehicle capacity. It utilizes **DBSCAN (Density-Based Spatial Clustering of Applications with Noise)** for clustering and ensures valid and practical carpools with additional validation and corrections.

***

## **Inputs**

The optimizer takes a JSON input with the following structure:

```json theme={null}
{
    "carpoolId": "001",
    "carpoolName": "Midtown Soccer Club",
    "carpoolLocation": {
        "name": "Midtown High School",
        "address": "929 Charles Allen Dr NE",
        "city": "Atlanta",
        "state": "GA",
        "zipCode": "30309"
    },
    "carpoolDays": [2],
    "carpoolMembers": [1, 2, 3],
    "availabilities": [
        { "userId": "1", "availability": [0, 2, 4, 5] },
        { "userId": "2", "availability": [0, 1, 4, 6] },
        { "userId": "3", "availability": [1, 3, 4, 5, 6] }
    ],
    "users": [
        {
            "userId": "1",
            "name": "Selina Meyer",
            "numchildren": 2,
            "children": ["Neha", "Shriya"],
            "carCapacity": 4,
            "location": {
                "address": "120 North Avenue NW",
                "city": "Atlanta",
                "state": "GA",
                "zipCode": "30313"
            }
        }
    ]
}
```

***

## **Algorithm Steps**

### **1. Initialization**

* Extract user data and carpool details.
* Convert addresses to latitude/longitude using an API.
* Assign user availability and carpool days.
* Define algorithm parameters such as `min_cluster_size`, `max_cluster_size`, and `target_size`.

### **2. DBSCAN Clustering**

* Compute the **Haversine distance** between all pairs of users.
* Determine the `eps` value as the **5th-10th percentile** of all distances.
* Run DBSCAN with `getNeighbors()` and `expandCluster()` helpers.
* Calculate cluster centroids using `calculateCentroid()`.
* Ensure no user is both clustered and unclustered.

### **3. Validation & Splitting**

* Validate clusters based on:
  * **Car capacity**: Ensure at least one user can drive all members.
  * **Availability**: At least one driver is available per carpool day.
  * **Distance Threshold**: Ensure all users in a cluster are within `eps * distance_threshold_factor`.
* Split large clusters into subclusters using `splitLargeCluster()`:
  * Find the user minimizing the sum of distances to all others.
  * Form valid subclusters with nearest users.
  * Uncluster invalid formations.
* Uncluster invalid clusters.

### **4. Finalization & Schedule Creation**

* Validate clusters again.
* Assign **driving schedules**:
  * Map `{day -> [drivers]}` and `{driver -> count}`.
  * Assign the least-used eligible driver per day.
* Attempt to **re-cluster unclustered users** by selecting the user with the lowest sum of distances.
* Loop until no more users can be clustered.

***

## **Outputs**

The algorithm returns:

* **Initial Clusters** (Raw DBSCAN Output)
* **Validated Clusters** (After Splitting & Validation)
* **Final Clusters** (With Driving Schedule)
* **Unclustered Users** (Accumulated throughout validation)

Example output:

```json theme={null}
{
    "finalClusters": [
        {
            "users": ["1", "2"],
            "schedule": [
                { "userId": "1", "drivingDays": [1, 3] },
                { "userId": "2", "drivingDays": [2, 4] }
            ]
        }
    ],
    "unclusteredUsers": ["3"]
}
```