Background

Kulina, a food subscription startup has lunch subscription product where a person can get daily special lunch delivered to her place with price as cheap as $1.2 per menu. To be able to to that, they have partnership with local cafes and restaurants to sell and deliver their daily special menu to customers from the nearest supply partner.

Therefore, there’s problem in how to find the nearest supply partner and arrange the delivery. To be able to find the nearest supply partner will ensure food delivered on time and reduce delivery cost. In addition for reducing delivery cost, a delivery unit can deliver food to multiple customers in one journey. However, we need to be careful not to spend long journey since food should be delievered during lunch time

Solutions

To find the nearest supply partners and make and effective delivery process. There are three steps that will be implemented :

1. Construct KDTree for supply clustering

A KDTree, or k-dimensional tree, is a data structure used in computer science for organizing some number of points in a space with k dimensions. It is a binary search tree with other constraints imposed on it. KDTrees are very useful for range and nearest neighbor searches.

In here supply partners (big red dots) are mapped into KDTree to make it easier find the nearest supply partners to customer (in black dots). It is also easier by seeing this cluster to find regions that is poorly covered

Show KD Tree Clustering

2. Find the nearest supply partner

After KDTree was constructed, nearest neighbor search to find the nearest supply partner for a customer was performed. Supply partners that are considered the to be the nearest are visualized with purple color.

Nearest neighbor search in KDTree avoids scanning the whole database to find the nearest position (O (log n)). Besides to find the nearest neighbor. This marking can be used to monitor supply capacity from number of connections made into one supply partner

Show Prominent Partners

3. Lin–Kernighan Heuristics for delivery

Lin–Kernighan is one of the best heuristics for solving the symmetric travelling salesman problem. It involves swapping pairs of sub-tours to make a new tour. It is a generalization of 2-opt and 3-opt. 2-opt and 3-opt work by switching two or three paths to make the tour shorter

In here there will be several traveling routes based on the number of supply partners that will receive orders (considered as the nearest supply from previous step). Number of vehicles needed will depend on supply partners and time needed for one journey

Show Delivery Route

Output & Improvements

Solutions are visualized using Google Map API (specified below) where users can generate KD Tree clustering, find out nodes that are considered the nearest relative to customers, and traveling route suggested.

There are some limitations with Google Map API since there’s limited number of requests per day to get the exact route for the street. Because of than in current TSP result, it uses direct line between two nodes. Right now it assumes that the node sequence already represents the optimum route.

There are a lot of improvements that can be done. For example, Dividing journey that takes too long time into several trip at the same time from the same starting point