Major Technical Projects (undertaken by B.Tech. final year students)

Firefly algorithm for TDMA scheduling in wireless sensor networks

Varun Bansal and Rajat Mehra

Finding good solutions for NP Hard problems is a highly researched area, as most of these problems have many real life applications. Bio-inspired meta-heuristics like Genetic Algorithm and Ant Colony Optimization for these NP Hard optimization problems like the Travelling Salesman Problem (TSP) and Vertex Cover have proved to provide much better results in reasonable amount as compared to algorithms based on other techniques.

In this project, we focus mainly on Firefly Algorithm which is one of the less studied bio-inspired algorithm and apply the algorithm on some of these optimization problems and thereby analyze the performance by comparing the results with other well known algorithms. We first try the algorithm on an unconstrained continuous optimization function to gain an understanding of the algorithm and it’s parameters, and later move on to the standard TSP and modify the firefly algorithm to incorporate the discrete nature of the TSP and compare the results with an implementation of the well known Ant Colony Optimization Algorithm. Finally, we study the Time Division Multiple Access(TDMA) Scheduling Problem which can be considered as a modified version of the standard Graph Coloring problem and compare the performance of our implementation of the firefly algorithm with an implementation of the Maximum Independent Set based approach for the problem.

Project report (in pdf format), Poster (in pdf format) and codes(in a zip file) For details please contact Varun and Rajat

RIDESHARING: Fair Cost Distribution

Shashank Sethi and Kumar Ashutosh

Ridesharing refers to the sharing of vehicles by different passengers. It reduces vehicle trips, traffic congestion, and automobile emission. This makes ridesharing highly desirable in terms of economic and environmental sustainability. Our focus is on real-time ridesharing, in which passengers are matched using a mobile or web application to participate in ridesharing. More specifically, how the cost should be distributed among them, when they do so.

To characterize the routes for ‘fair’ cost distribution, we use the notion of Sequential Individual Rationality (SIR) introduced in [1]. However, this work is not focused on the routing aspect of ridesharing, but on how the cost should be distributed among the passengers participating in ridesharing.

The first case comprises using an existing cost sharing framework that uses SIR for single drop-off scenario. After making appropriate modification in SIR, this framework is extended for single-pickup, multiple drop-off scenario. The effectiveness of the framework in these scenarios is evident by simulating multiple instances of ridesharing on a grid-like structure that comprises the passenger space. Finally, the framework is extended for multiple-pickup, multiple-dropoff scenario and the effectiveness is shown, not by means of mathematical proofs, but by using multiple instances of simulations.

[1] Gopalakrishnan, Ragavendran, Koyel Mukherjee, and Theja Tulabandhula. “The costs and benefits of ridesharing: Sequential individual rationality and sequential fairness.” arXiv preprint arXiv:1607.07306 (2016).

Project reports (in a zip file), Poster (in pdf format) and codes(in a zip file)

For details please contact Shashank and Kumar