Background: Recently the Government of India has imposed a curfew of 21 days to control the spread of n-COVID-19. The government wants to take up delivery of groceries and other essential items so as to prevent people from venturing on the road. In New Delhi, the government has identified certain areas that can serve as warehouses and from where a set of delivery agents will take up the delivery and deliver it to individual homes. One such warehouse is in Hauz Khas and it has its set of delivery agents. Each delivery agent has a motorbike and it can hold up to a certain capacity of groceries. The demand (homes) is distributed throughout Hauz Khas. Every morning the supply vehicle comes at around 6AM and groceries are ready for delivery by 8AM. The groceries have to be delivered to homes by 10 AM. The problem is to allocate routes for individual vehicles so that the demand allocated to that vehicle is satisfied and the total demand in Hauz Khas is also satisfied.
Tasks and deliverables for students: This takes the form of a traveling salesman problem, and the challenge is to develop a user interface that the government or any other stakeholder can use to (a) assign a set of stops and associated demand to a set of delivery agents, based on their capacity; (b) develop an optimal route for each delivery agent. The user interface should be a simple, no-frills one which takes as input (a) the set of delivery agents, with their associated capacity; (b) the Google Maps locations (in the form of coordinates) of each stop (including the warehouse), with associated demand. The application should calculate the distance between each location using Google Maps and then solve the TSP and provide the load to be carried and optimal route for each delivery agent. Utilize an existing integer programming formulation of the TSP and use a solver such as CPLEX (which has APIs for multiple programming languages such as Python, Java, C++, etc.) to solve the problem.