Fleetly

Inspiration

We noticed similarity between task statement and "Assignment problem" (special case of famous stable marriage problem). We adjusted general algorithm solving this problem, so that it fits our task, but managed to keep its strongly polynomial time complexity for average test case.

What it does

We match vehicles to awaiting customers. We focused on minimizing total sum of driving times of all cars By that we mean time spent on traveling with customer to destination and driving to pickup customer, but not the time when taxi is idle. We picked such cost function to minimize energy consumption, and so cost for company.

How we built it

We have set time intervals to get updates from endpoints. This allows precise visualization. Aside from that we also predict when the vehicles (based on their velocity and position) arrive at the destination and and update also then, to send the car to the next customer as swiftly as possible.

Challenges we ran into

Getting everything to work with Java, creating a frontend in Java, throwing it over completely

Accomplishments that we're proud of

Graph algorithms like A*, DFS, etc. that are popular choices for optimization problems, but are not really suited for problems like this one, where we need to optimize sum of paths. In contrast, our adaptation of Hungarian algorithm is uniquely designed to deal with such cases. Fleetly also handles some interesting corner cases, such as: Let's say there are two taxis, A and B. A is idle, B is traveling with customer. There is only one customer left to pick up. In our approach we do not immediately assign A to this customer, just because it's the only idle taxi. Instead we compare time A would need to get to this last customer with the time B would need to get current customer to destination and from this point travel to pick up the last customer. As it turns out, it is quite often the case, that leaving one taxi idle and letting another one handle multiple customers is more optimal.