W were interested in learning about optimization algorithms.
What it does
Our algorithm finds the optimal order in which to collect deals. It can also map optimal product placement given anticipated traffic heat-map.
How we built it
First, we had to create a custom cost function that could approximate travel time between two points. We treated this as a version of the Dynamic Traveling Salesman (TDP) problem and applied a stochastic arc cost algorithm to compute an optimized route. Our custom cost function approximated travel time by incorporating friction into calculations of distance for use in our optimization algorithm. First we applied a convolution of probable path filters to the friction matrix, and were able to approximate the travel time by taking the most efficient of these paths.
The reason behind this rough approximation is to be able to map way-points without the computation intensive calculation of all possible optimal routes. We feel this approximation is justified because of the low gradient across the friction map. Due to this smoothness, it is safe to assume that the resistance across an approximated path is very close to any path within its vicinity.
We added this friction term to the actual distance of the path traveled, and used a hyper-parameter to weight the importance of this friction. By tuning this hyper-parameter, we were able to find an optimal order in which to collect the products in a relatively short time across the entire map, using fifty randomly spawned product locations.
By finding this set of way-points, the problem is simplified to a two-point traversal optimization problem with a resistive component. Because of the computational efficiency of this algorithm, we were also able to use it to estimate the optimal product placement given an anticipated traffic heat-map. We were able to do this by first creating a two-dimensional probability distribution corresponding to the friction map. We then sampled using this distribution over low-friction areas to generate an evenly dispersed product placement such that the products avoid high-traffic areas. Although a dense clustering of products does not negatively effect the model with the given parameters of this challenge, it would in actual practice change the traffic flows around these clusters. Then, using this product placement, we took the average approximate customer travel time of 50 customers using our original cost function. After collection 200 product placement samples with 50 customers per sample, we found the minimum mean travel time and chose this as our optimal product placement.
Challenges we ran into
Originally, we found that calculating the actual travel time of every possible optimal route between all targets to be computationally prohibitive. To overcome this, we were able to create a metric that closely approximates the most probable paths and the travel time for these, which we used as our cost function. This approximation greatly reduced our computation time and allowed us to verify our model on thousands of customer routing samples in order to generate an optimal product placement map.
Accomplishments that we are proud of
We were able to create a custom cost function that approximated travel time by incorporating friction into calculations for optimizing the route. We were also able to use this same algorithm to find the optimal placement of products given the traffic map.
What we learned
Learned about routing optimization and cost functions
What's next for Walmart Challenge
Need to implement pixel-by-pixel routing