The Fifth Elephant 2019

Gathering of 1000+ practitioners from the data ecosystem

Tickets

Solving the vehicle routing problem for optimizing shipment delivery

Submitted by Venkateshan (@venky1729) on Thursday, 11 April 2019

Session type: Full talk of 40 mins

View proposal in schedule

Abstract

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

Comments

  • Anwesha Sarkar (@anweshaalt) Reviewer 4 months ago

    Thank you for submitting the proposal. Submit your slides and preview video by 20th April (latest) it helps us to close the review process.

  • Abhishek Balaji (@booleanbalaji) Reviewer 2 months ago

    Here’s the feedback from your rehearsal:

    • Time taken: 39 mins (Needs to go down to 35 mins)
    • Flow of the talk is good except for some parts in the middle such as insertion cost. This can be made more crisp
    • Mention more about the conditions and reasons why you built your own heuristic instead of using the existing solver.
    • Explain/Highlight the novelty in your talk at the beginning, so the audience knows what to expect.
    • Add points on what is the sensitivity of the model/algorithm towards predictions.
    • Add a couple of points showing how your model/algo performs in real life.
    • Mention about the computationally intensive processes and how they affected your decisions.

    Do update your slides based on the feedback and get back to us by Jun 14, 2019. We’ll evaluate the proposal and get back to you on the next steps.

Login with Twitter or Google to leave a comment