Project: Drone Delivery Kaggle

The Task

This was a practice kaggle that features the qualification problem from Google’s 2016 annual code competition. You are given a hypothetical fleet of drones, a list of customer orders, and the availability of specific products in warehouses, and your job is to schedule drone operations to complete the orders as soon as possible.

The approach

The first thing I did was simple, I just sorted the orders so that all the orders with fewest items were first, which made a huge difference in the overall score. The next thing was to batch multiple orders together so that you can fulfill part of an order while fulfilling another order.

Then from that order pool, it’ll find an order cluster or a point where orders are conveniently located near each other. This will be done stochastically, by randomly selecting a sample cluster point on the map, finding the closest orders that can be fulfilled by that cluster by a single drone, and then scoring the value of each cluster based on the total weight compared to the average distance. The cluster with the highest value will be selected. For that order cluster, it’ll also figure out the corresponding closest warehouse for each order’s product.

Then since the total warehouse and order drop offs are low, it’ll brute force run through every permutation to figure out the best route through those warehouses and orders. (Note: When I stopped working on this I had only run permutations of routes where all warehouses were first and then all the order drop offs were afterwards. But a better way would be to screen the routes where the warehouse product pick up is before the order product drop off, and then select the best permutation to allow intermixed pick ups and drop offs).

Overall, the structure of the code has aspects like a simulator and a scheduler. The scheduler will pool orders, find order clusters, and determine an optimum route for a drone. However, the simulation aspects will keep track of everything the state of the warehouses, drones, and orders. And basically the simulation works by pulling orders off the list, routing it, assigning it to the closest available drone, letting the drones randomly distribute themselves across the map, and then let them keep working until there are no more orders. The drone object itself keeps track of whether it’s busy, how long it’ll be busy for, where it is, and what’s in it’s hold. The order object itself keeps track of its location, the status of the various products in its order, and whether it’s complete. And likewise the warehouse object keeps track of its inventory and location.

Final SCORE

My final score was 101674 with the top score being 114399, and my final ranking was 69 out of 130. However, this was without looking at other people’s code. The top scorer shared their answer and there are 36 positions above me with scores all within 13 points of each other. I also stopped working on it once I broke the 100,000 mark =)

All in all it was a fun exercise in object orientated programming and algorithm development.