Phase-1 Objective Implement standard algorithms on a dynamic graph that supports periodic updates and queries. Queries Shortest Path: Minimizing distance Minimizing time with speed limit as a function of time (changing traffic) Constraints on edges/nodes (e.g., forbidden roads or restricted nodes) KNN (K Nearest Neighbors): Based on Euclidean Distance Based on Shortest Path Distance (not time)

Phase-2 Objective Implement advanced heuristic and approximate algorithms for routing queries. Queries K Shortest Paths (Exact) — by distance, for k between 2–20. The paths need to be simple paths, i.e., loopless paths, as in the real world, a user getting a looped path will be really annoyed.

For just this part, the constraint on both edges and vertices of the graph is 5000. K Shortest Paths (Heuristic) — penalize overlapping in the paths and paths that deviate too much from optimal, for k between 2-7 In the queries of type-1, you would have observed that the paths are very close to each other, but you know Google Maps does a lot better. So, the final output will be a heuristic of the closeness to the shortest distance and the variety of paths. In the algorithm, try to have parameter tuning so that you can increase or decrease the priority. On average, each query should be completed within 5 seconds, while the worst-case scenario per query is around 15 seconds. Any algorithm that is linear or with logarithmic factors is fine in part 2. This time limit is for both parts 1 and 2 of phase 2. Approximate Shortest Paths — prioritize speed over accuracy (batch queries performance test). Scoring is based on the accuracy–speed tradeoff across a large batch of queries. You will be provided a large number of queries in a small time interval. The MSE from the Shortest Path distances will be computed to score. The threshold error percentage will be used. It was always there in the appendix and the JSON format. There was just a mismatch between here and in the JSON. The time interval will be such that no linear or linear-Logarithmic algorithms will pass. If you have anything that is less than the 5-10% of the normal shortest path algorithm from phase 1, then you can be fairly confident that it will be under the constraints. I just want a 10-20x speedup. You need to handle queries one by one; if the combined query’s time crosses the budget time, the query will be rejected. Check the query JSON format once.

Phase-3: Delivery Scheduling Companies like Zomato, Swiggy, Zepto, and Blinkit face a complex and fundamental challenge — how to utilize their delivery fleet most efficiently. In this project, we present a simplified yet representative version of this real-world optimization problem. This task is closely related to the well-known Travelling Salesman Problem (TSP), an NP-hard problem in combinatorial optimization. While solving it optimally for large inputs is computationally infeasible, your objective is to explore and implement practical heuristics and state-of-the-art algorithms that perform well in realistic scenarios. You are expected to design algorithms that balance accuracy, computational speed, and scalability, taking advantage of the fact that the underlying graphs are Euclidean rather than arbitrary. The evaluation will be relative, based on the trade-off between execution time and solution quality. A detailed report should accompany your implementation, explaining your algorithmic choices, heuristics used, experimental results, and insights gained — particularly emphasizing the reasoning behind your design decisions and their real-world relevance. Problem Statement At time t = 0, there are n delivery boys all located at a central depot. There are m delivery orders, each having a pickup and delivery node. Each delivery boy can carry multiple orders and deliver them in any order — as long as pickup precedes delivery. Goal Minimize the total delivery time, defined as the sum of delivery completion times for all orders. Compare this with minimizing for the maximum delivery time, i.e., the max of the individual delivery completion times. For the phase-3, you can ignore the speed profiles and always use the average time. For just this part, the constraint on both edges and vertices of the graph is 5000. The time limit per query for this phase is 15s worst-case. A timeout for exceeding 15s. In this phase, >= 3 marks are for the kind of research, analysis, and extra ideas you explore on top of the problem. You can think of anything from real life and give an algorithm + analysis of the idea. For eg, if a driver gets into an accident, including the restaurant preparation time, the order is cancelled, optimizing based on the price of the order, etc. These were just some ideas. You are free to explore yours.