matching

matching / TaxiMatching / 0.1.2

README.md

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
    }
  }
]