## 0. TL;DR

This is a taxi matching algorithm that gives you an optimal matching between available cars and customers.

## 1. Introduction

There are many online services that offer on-demand "ride-hailing" or "ride-booking" services. Today Uber and Lyft are the prime examples of how these services use car-customer matching algorithms.

This taxi matching algorithm is built on top of another algorithm called The Stable Marriage Algorithm. The Taxi Matching algorithm creates a preference list based on the proximity for each car and customer. It then passes these preference lists to the Stable Marriage Algorithm and gets a optimal matching between the cars and customers.

If one group outnumbers the other group, the algorithm will match the maximum number of pairs possible.

### Input

• (Required) A list of car objects.
• (Required) A list of person objects.

### Output

• A list of matching car and person objects.

## 2. A car object

A car object: A dictionary that could have up to 5 attributes:

• (Required) Coordinates: Latitude and longitude of the car.
• (Optional) Plate number: The car plate number.
• (Optional) Driver name: Name of the driver.
• (Optional) Car model: Corresponding car model.
• (Optional) Rating: The overall rating of the car.

Example of a car object:

```{
"plateNumber": "UMY341",
"driverName": "James Black",
"carModel": "Tesla Model S",
"rating": 4.95,
"coordinates": {
"lat": 47.601324,
"long": -122.331820
}```

## 3. A person object

A person object: A dictionary that could have up to 3 attributes:

• (Required) Coordinates: Latitude and longitude of the person.
• (Optional) Name: Name of the given person.
• (Optional) Rating: Rating of the given person.

Example of a person object:

```{
"name": "Zeus da Deus",
"rating": 4.88,
"coordinates": {
"lat": 47.601023,
"long": -122.333751
}
}```

## 4. Output

A list of matching car and person objects: Gives a matching between the group of cars and people. The matching is optimal.

Example of an output:

```[
{
"customer": {
"rating": 4.88,
"name": "Customer 2",
"coordinates": {"lat": 47.608575, "long": -122.324481}
},
"car": {
"carModel": "Audi A6",
"plateNumber": "ABC762",
"driverName": "Driver 1",
"coordinates": {
"lat": 47.607731,
"long": -122.323537
},
"rating": 4.88
}
},
{
"customer": {
"rating": 4.88,
"name": "Customer 1",
"coordinates": {"lat": 47.601023, "long": -122.333751}
},
"car": {
"carModel": "Tesla Model S",
"plateNumber": "UMY341",
"driverName": "Driver 3",
"coordinates": {"lat": 47.601324, "long": -122.33182},
"rating": 4.95
}
},
{
"customer": {
"rating": 4.55,
"name": "Customer 4",
"coordinates": {"lat": 47.663577, "long": -122.379627}
},
"car": {
"carModel": "Porsche Macan",
"plateNumber": "HJK827",
"driverName": "Driver 4",
"coordinates": {"lat": 47.66728, "long": -122.383575},
"rating": 4.99
}
},
{
"customer": {
"rating": 4.55,
"name": "Customer 3",
"coordinates": {"lat": 47.616474, "long": -122.347827}
},
"car": {
"carModel": "Porsche Macan",
"plateNumber": "HJK827",
"driverName": "Driver 2",
"coordinates": {
"lat": 47.618209,
"long": -122.350101
},
"rating": 4.99
}
}
]```

## 5. Examples

### Example 1:

• Parameter 1: A list of car objects.
• Parameter 2: A list of person objects.
```{
"cars": [
{
"plateNumber": "UMY341",
"driverName": "Driver 3",
"carModel": "Tesla Model S",
"rating": 4.95,
"coordinates": {
"lat": 47.601324,
"long": -122.331820
}
},
{
"plateNumber": "ABC762",
"driverName": "Driver 1",
"carModel": "Audi A6",
"rating": 4.88,
"coordinates": {
"lat": 47.607731,
"long": -122.323537
}
},
{
"plateNumber": "HJK827",
"driverName": "Driver 2",
"carModel": "Porsche Macan",
"rating": 4.99,
"coordinates": {
"lat": 47.618209,
"long": -122.350101
}
},
{
"plateNumber": "HJK827",
"driverName": "Driver 4",
"carModel": "Porsche Macan",
"rating": 4.99,
"coordinates": {
"lat": 47.667280,
"long": -122.383575
}
},
{
"plateNumber": "HJK827",
"driverName": "Driver 5",
"carModel": "Porsche Macan",
"rating": 4.99,
"coordinates": {
"lat": 47.670286,
"long": -122.306843
}
}
],
"customers": [
{
"name": "Customer 1",
"rating": 4.88,
"coordinates": {
"lat": 47.601023,
"long": -122.333751
}
},
{
"name": "Customer 2",
"rating": 4.88,
"coordinates": {
"lat": 47.608575,
"long": -122.324481
}
},
{
"name": "Customer 3",
"rating": 4.55,
"coordinates": {
"lat": 47.616474,
"long": -122.347827
}
},
{
"name": "Customer 4",
"rating": 4.55,
"coordinates": {
"lat": 47.663577,
"long": -122.379627
}
}
]
}```

Output:

```[
{
"customer": {
"rating": 4.88,
"name": "Customer 2",
"coordinates": {"lat": 47.608575, "long": -122.324481}
},
"car": {
"carModel": "Audi A6",
"plateNumber": "ABC762",
"driverName": "Driver 1",
"coordinates": {
"lat": 47.607731,
"long": -122.323537
},
"rating": 4.88
}
},
{
"customer": {
"rating": 4.88,
"name": "Customer 1",
"coordinates": {"lat": 47.601023, "long": -122.333751}
},
"car": {
"carModel": "Tesla Model S",
"plateNumber": "UMY341",
"driverName": "Driver 3",
"coordinates": {"lat": 47.601324, "long": -122.33182},
"rating": 4.95
}
},
{
"customer": {
"rating": 4.55,
"name": "Customer 4",
"coordinates": {"lat": 47.663577, "long": -122.379627}
},
"car": {
"carModel": "Porsche Macan",
"plateNumber": "HJK827",
"driverName": "Driver 4",
"coordinates": {"lat": 47.66728, "long": -122.383575},
"rating": 4.99
}
},
{
"customer": {
"rating": 4.55,
"name": "Customer 3",
"coordinates": {"lat": 47.616474, "long": -122.347827}
},
"car": {
"carModel": "Porsche Macan",
"plateNumber": "HJK827",
"driverName": "Driver 2",
"coordinates": {
"lat": 47.618209,
"long": -122.350101
},
"rating": 4.99
}
}
]```
Contents