RIVIGO Coding Championship: India’s Top Coders’ Quest to Solve the Impossible

3 September 2018
Technology

The RIVIGO Coding Championship 2018 saw 8,000+ young coders from across Indian engineering campuses compete as they solved a relay-inspired challenge over a week. This article provides a brief about the championship, the problem, possible solutions and the way forward.

 

Introduction

At RIVIGO, we are on a mission to solve the most challenging problems of our times by creating a series of seemingly inconceivable firsts at an unimaginable scale. We are committed to re-imagining logistics and supply chain for India and the world and building a larger ecosystem that is conducive to knowledge sharing and breeds a culture of innovation.

In the same spirit, we launched the first edition of the RIVIGO Coding Championship (RCC) on August 1st, 2018. The challenge was built with a two-pronged objective. Firstly, to give an opportunity to India’s best young coders to try their hands on a real-life problem and in the process, discover novel solutions to some of the biggest challenges out there. Secondly, to identify students from across engineering campuses who have the mettle to build great technology solutions for India and the world.

The challenge saw 8,000+ registrations from final and pre-final year students from 300+ engineering campuses. In teams of two, participants worked over one week (August 11 – August 18) to submit their solutions. The competition was intense, and the shortlisted teams went through a rigorous discussion round where they got an opportunity to present their solutions to a panel. Teams from IIT Kanpur, IIT Delhi and IIT BHU secured the top three ranks respectively. Members of these teams will receive mentorship from RIVIGO’s technology leadership team, cash prizes and an opportunity to join the team after graduation. Other notable solutions came from teams from campuses like DTU, NSIT, IIT Madras, IIT Roorkee etc. The winners will also be felicitated in an AI Conference that is scheduled to be organized in December 2018 in Gurgaon, India.

The problem that the participants worked on was broken into two parts. In this note, we will share both the problems and some noteworthy approaches presented by the participants.

 

The Problem

The problem given to participants was inspired by RIVIGO’s unique relay model wherein a pilot (truck driver) drives from one pitstop to another, which is usually 4-5 hours away, and returns to home location by driving another vehicle back in the opposite direction. This guarantees that every pilot drives only a certain number of hours and returns home the same day, while also ensuring fastest transit times.

Participants were asked to optimize for the ideal pilot wait time at pitstop by utilizing the trip buffer time (non-driving time) to schedule stoppages at the pitstops. Below is a brief of the problem context.

On the New Delhi to Chennai Highway, RIVIGO has setup 5 pitstops at a distance of 200-300 kilometers from each other. RIVIGO has trips driving in both directions.

Let us focus on the trips starting at New Delhi and going to Chennai. A pilot takes the trip from one pitstop to the next and then has to wait for another truck coming from the opposite direction to drive it back to his ‘home’ pitstop. This behavior occurs on each pitstop.

Each trip is assigned a schedule, which means it can start only after a stipulated time, say 1400 hrs on Day 1 (startTime) and is promised to reach Chennai before a certain time (endTime), say 0500 hrs on Day 4. This means it has 63 hours to complete the trip. The non-stop driving time from New Delhi to Chennai is 48 hours. This means that this trip has an extra buffer of 15 hours. Each trip has its own unique startTime and endTime, hence has its own buffer time.

Can we use the buffer time of each trip to schedule stoppages at the pitstops so that the overall wait time for pilots at pitstops is minimized? 

Let’s look at an example to clearly understand the scenario.

The left figure demonstrates the scenario when the vehicles do not make a stoppage at pitstops. We will have to allocate two pilots who will then have to wait at the destination pitstops for return trips. The right figure demonstrates that if we use Trip 2 buffer of 2 hours, pilot driving Trip T1 can take over Trip T2 to drive back home.

 

Problem Statement Part 1

Objective

Given the fixed schedules of the trips between two pitstops, find the “optimal” trip-trip match which provides minimal waiting time of the solution.

Solution

In this problem, trips from A->B have to be matched to some corresponding trips from B->A.

Let the set of trips from A->B be – $latex { f_1, f_2, f_3, …\,, f_N}&s=1$
and the set of trips from B->A be – $latex { b_1, b_2, b_3, …\,, b_M}&s=1$

Also, not all matchings $latex (f_i, b_j)&s=1$ are valid. For the matching to be valid either $latex a_i \leq d_j&s=1$ or $latex a_j \leq d_i&s=1$ , where $latex d_i, d_j&s=1$ denote the departure time of $latex f_i, b_j&s=1$ (from A and B respectively) and $latex a_i, a_j&s=1$ denote the arrival time of $latex f_i, b_j&s=1$ (at B and A respectively). Also, it is possible to keep some trips unmatched if either there are no other trips left to be matched or even if another matching is possible but keeping the trips unmatched leads to lower cost.

Now if $latex N, M&s=1$ were equal and each matching was possible and unmatching any trips was not an option, then this would have been the same as the Assignment Problem. To solve it, we would have constructed an $latex N \times N&s=1$ matrix and in each cell $latex i, j&s=1$ we would have put the matching cost of $latex f_i, b_j&s=1$ and applied the Hungarian Algorithm to get the optimal matching.

However, our problem is slightly more complicated. This is because, in our case not all matchings are not possible, and we have the option of keeping some trips unmatched. So, we construct an $latex N \times M&s=1$ matrix where each cell $latex m_{ij}&s=1$ denotes the matching cost of $latex f_i, b_j&s=1$ if the matching is possible. Otherwise, it is $latex \infty&s=1$. In addition, we have 2 vectors. One is of size $latex N&s=1$, where each element $latex u^f_i&s=1$ denotes the unmatched cost of trip $latex f_i&s=1$ . The other is of size $latex M&s=1$, where each element $latex u^b_j&s=1$ denotes the unmatched cost of trip $latex b_j&s=1$. These are shown below.

Now the constraint is for each $latex f_i&s=1$ we can either – choose any $latex b_j&s=1$ such that $latex m_{ij}&s=1$ is finite and the $latex j&s=1$th column in the matrix is chosen only once or, we choose $latex u^f_i&s=1$. Similarly, for $latex b_j&s=1$s as well. Taking these constraints into account we can construct another $latex (N+M) \times (N+M)&s=1$ as –

Now we apply the Hungarian algorithm on this matrix $latex \mathbf{M}&s=1$. If row $latex i&s=1$ (for $latex i \leq N&s=1$) matches with column $latex j&s=1$, if $latex j \leq M&s=1$ then that implies that trip $latex f_i&s=1$ is matched with trip $latex b_j&s=1$, otherwise if $latex j > M&s=1$ that implies that $latex f_i&s=1$ remains unmatched. Similarly if column $latex j&s=1$ (for $latex j \leq M&s=1$) matches with row $latex i&s=1$, if $latex i \leq N&s=1$ then that implies $latex f_i&s=1$ and $latex b_j&s=1$ are matched, otherwise if $latex i > N&s=1$ that implies $latex b_j&s=1$ remains unmatched.
It is not very hard to show that above solution is indeed optimal solution to our problem.

Also note, most implementations of the Hungarian algorithm allow only finite values in each of the matrix cell, but we have some cells whose value is $latex \infty&s=1$. This is actually not a problem. Let $latex L = &s=1$ sum of all finite entries in $latex \mathbf{M}&s=1$. For any entry in $latex \mathbf{M}&s=1$ which is $latex \infty&s=1$ we can replace that with any value $latex >L&s=1$ and the solution to the optimal assignment will still remain the same.

 

Problem Statement Part 2

Let’s look at the complete highway now and not just two adjacent pitstops. The available buffer time of any trip can be split across all the pitstops.

Objective

Utilize the buffer time of the trips to schedule stoppages at the pitstops. These stoppages should lead to a “feasible” trip-trip match for pitstop pairs to minimize the overall waiting time across all pitstop pairs.

Solutions

1.) Optimal Answer

The buffer for each journey leads to an exponential search space for optimal solution making this problem NP-hard. Searching through this space is runtime exhaustive and not an option to solve real time scenarios.

Therefore, if we can find a near-optimal solution in a ‘finite amount of time’, the algorithm can be applied in real use cases. Participating teams used several novel approaches for this problem. Some noteworthy approaches have been briefly summarized below. 

 

2.) Greedy Approaches

Approach 1 – Optimize one pitstop pair at a time

  1. Run the trips end-to-end without utilizing any buffer time. The trips start at their scheduled times.
  2. Randomly pick all pitstop pairs one by one.
  3. For each pitstop pair, find the optimally matched trips using Hungarian Algorithm.
    • Use the remaining buffer time of either of the two to reduce the interim wait time up to 0.
    • Adjust the remaining buffer time accordingly.
  4. Repeat the steps 2 and 3 until the process times out or all sequence of pitstop pairs have been considered.
  5. Report the solution with minimum waiting time.

Approach 2 – Move linearly ahead in time trying to match trip-segments with available drivers

Definitions used in the algorithm are given below :

Schedule – A schedule is defined by startNode, endNode, currentNode, tripId, startBy_FromCurrentNode, arriveBy_AtEndNode

Driver – A driver is defined by firstTripId, secondTripId, arrivalTimeAtWaitingPitstop, departureTimeAtWaitingPitstop

Algorithm:

  1. Maintain a priority queue of Schedules, say schedule_queue, ordered on departure time from the initial pitstop.
  2. Initialize schedule_queue with the first trip segment information of all trips.
  3. Maintain two queues per pitstop, each maintaining drivers who have to go in left and right direction.
  4. Repeat the steps till the schedule_queue is NOT empty.
    1. Pop out a schedule.
    2. Check in the driver queue of the schedule.startNode pointing towards schedule.endNode.
    3. If there is an available driver, match the trip with the driver and record the waiting time of the driver.
    4. If there is no driver,
      1. If remaining trip buffer is > 0, delay the schedule of the trip by one hour and push it back to the schedule_queue.
      2. Else assign a new driver to the trip and add it to the driver queue of the schedule.endNode pointing towards schedule.startNode.
    5. Push the next trip segment of the current trip into the schedule_queue.
  5. Sum the waiting times of the drivers to report the final waiting time of the output.

 

3.) Metaheuristic Models

A Metaheuristic is a heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem. Metaheuristics use Explore-Exploit Strategies to traverse through the search space.

  • Exploitation consists of accepting better neighbors of a solution as a way to explore the solutions space. By doing so, it probes a  a limited (but promising) region of the search space. This methodology is also referred to as local search.
  • Exploration consists of accepting worse neighbors with the hope of finding other promising solutions that are yet to be refined. By doing so, it probes a much larger search space. This methodology is also referred to as global search.

Three most widely used types of heuristics :

  1. Tabu Search
    • Employs memory of past solutions, but strategically.
  2. Randomized Methods such as Simulated Annealing and  Monte Carlo Simulation
    • Ignores past memory and uses random searching.
  3.  Genetic Algorithm
    • Evolutionary with randomization.
    • Generates a ‘population’ of solutions and keeps on creating better generations from the current one.

a.) Formulating Approach using Simulated Annealing Heuristic:

  1. For each trip, split the buffer randomly across all intermediate pitstops. This gives us a solution.
  2. For each pitstop pair, find the optimal matched trips using Hungarian Algorithm.
  3. Compute the total waiting cost across all pitstop pairs.
  4. If the final cost < minimum cost so far, pick this as the next solution (Local search / Exploitation).
  5. If the final cost > minimum cost so far, pick this as the next solution based on a probability distribution function (Global Search / Exploration).
  6. From the next solution, pick k trips randomly and again split the total buffer randomly across all intermediate pitstops
  7. Repeat Steps 2 to 6 until the process times out or cost converges.

b.) The approach for other heuristics can also be formulated in a similar way, which we leave for the interested readers to try out.

 

Way Forward for the RCC 

The first series of the RCC has given us immense confidence in the innovation powerhouse that the young coders of India are. Through the following series of the RCC, we want to create an Olympiad for extraordinary minds where participants get to solve some of the toughest never-before-done problems of our times.

The next championship which is set to be launched in a couple of months from now, will be for experienced coders and will be open for folks globally, giving Indian engineers an opportunity to compete with the Silicon Valley’s best.

We are hopeful that with platforms like these, not only will young talent get the right platform to test out their mettle but also help apply and engrain first-principle problem solving to tough challenges.

 

The winners of the RCC 2018 were: Fenil Fadadu and Shiv Kumar from IIT Kanpur (1st position), Ayush Gupta and Udayin Biswas from IIT Delhi (2nd position) and Saurabh Rathi and Sujal Maheshwari from IIT BHU (3rd position). To view the details of the championship and the list of top 30 teams, you may visit the RCC page here.

 

Abhishek Kedia, Software Development Engineer at RIVIGO, has also contributed to this article.