The Fifth Elephant 2019

At each Flipkart Delivery hub, an important task is determining the assignment of shipments to vehicles and the specific routes taken by vehicles to deliver the items to customers. Informally, a good assignment is one that minimizes the total distance while also distributing the shipments evenly across the different vehicles and does not have too many overlapping or criss-crossing routes. We formulate the problem statement as a variant of the classic Vehicle Routing Problem (VRP) and build a solution engine from scratch that implements a set of computational heuristics to solve the problem.

Outline

1. Description of the context at the Flipkart delivery hub.
2. Solution constraints - customer time window, maximum number of shipments per vehicle.
3. Defining a non-standard cost function - total travel time, route outliers, compactness of routes.
4. Formulating the problem as a variant of VRPTW (vehicle routing problem with time windows).
5. Computational complexity: NP-hard (generalization of Traveling Salesman Problem)
6. Overview of some exact algorithms.
7. Heuristics - (a) construction of routes and (b) route improvement
8. Description of our construction step and iterative computational procedure to improve solutions.
9. Discussion of results

Requirements

Nothing in specific, but it helps to have some understanding of optimization procedures.

Speaker bio

Venkateshan Kannan is a data scientist with the Logistics and Insight team at Flipkart. With a PhD. in statistical physics and postdoc in systems biology, Venkateshan has worked on problems spanning multiple domains in academia and industry. He enjoys approaching problems from first principles.

Slides

https://drive.google.com/file/d/1MROJoIrCeyNkLtWYanQV5FYDfmGVX1JM/view?usp=sharing