The seventh Assignment in DSL810: Prototyping in IoT, was about the applications for Covid 19. We should upload the write-up about developing a concept of a digital/physical solution for COVID-19 or post COVID-19 India based on the applications of what we have learnt in this course. For this project, I and Ayush Pandey decided to work on the problem of Transportation of Essential Goods. Most of the ideation and the final solution was done together for this project, with equal contribution from both students, with my work slightly inclined towards the research side and my partner's slightly towards the technical side.
Motivation for the problem
The Government of India has imposed lockdowns several times in the past few months to control the spread of n-COVID-19. The government wants to take up the 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 6 AM and groceries are ready for delivery by 8 AM. 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.
User Research
We started the project identifying the primary stakeholders. For our problem, the primary users are the managers of the warehouses who will assign The first stage of the Design Thinking process is to gain an empathic understanding of this problem. This heavily involved secondary research to find out more about the area of concern through observing, engaging and empathizing with people to understand their experiences and motivations, as well as immersing ourrselves in the physical environment so you can gain a deeper personal understanding of the issues involved. Empathy is crucial to a human-centered design process such as Design Thinking, and empathy allowed us to set aside our own assumptions about the world in order to gain insight into users and their needs. Due to the constraints of the lockdown, primary research such as interviews was not possible. But based on the secondary research, a substantial amount of information is gathered which is used during the next stages and to develop the best possible understanding of the users, their needs, and the problems that underlie the development of the final product.
Persona
Based on our user research, we created a persona to represent target user groups. Persona made the design task at hand less complex and guided the ideation processes, and it helped to achieve the goal of creating a good user experience for target user group.
Traveling Salesman Problem
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:
• Assign a set of stops and associated demand to a set of delivery agents, based on their capacity
• Develop an optimal route for each delivery agent.
The user interface should be a simple, no-frills one which takes as input:
• The set of delivery agents, with their associated capacity
• 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.
In this typical Transportation Routing Problem, a manager or analyst must schedule an existing fleet of vehicles, each with a capacity constraint, to visit a set of stops or destinations and deliver or pick up goods or services at each stop such that one and only one vehicle visits each stop. The problem is to assign these vehicles to the stops so as to minimize total cost which is assumed to be directly proportional to the total distance traveled. Much work has been done on this problem and heuristic as well as optimal seeking methods have been developed. This solution examines the problem, develops a standard formulation, an interface and mentions some new approaches.
Ideas Generated
• A simple interactive interface to assign tasks:
Designing a simple, easy to use interface to feed the input and get the optimized routes as output.
• Categorizing Users based on location:
Categorising users, and starting collection points based on the location, at the time of login itself, to make the database private to a specific location and reducing hassle in further steps.
• A usability oriented solution for the input platform:
Can input agent data, consumers data having information of commodities required, agents available, etc.
• Sending the planned routes to corresponding delivery agents:
Having options in the interface to send routes to delivery agents on their phones to let them know which path and commodities to take.
• An efficient backend algorithm to properly optimize paths:
To combine the front end with efficient backend algorithms so as to get routes as planned using linear integer programming to get an optimal solution to the problem subject to given constraints.
• A secure database:
Letting the user login and register, and saving the session information and login credentials on online servers.
Backend Algorithm
Our backend algorithm is can be related to a vehicle routing problem. However, it does more than a vehicle routing problem can do. It allows multiple delivery agents to visit the same consumer in order to complete their demand. This is a huge advantage as even the most popular models today do not allow this. We have taken some assumptions while developing our algorithm:
(1) One delivery agent makes only one trip. To give an example, suppose that there only one consumer with a demand of 20 and there is only one delivery agent, with a capacity of 10. Then, this is an unsolved problem because we do not take into account that the delivery agents can make two trips to the consumer. However, it is a reasonable assumption as the travelling salesman problem(TSP), the vehicle routing problem(VRP), the capacitated vehicle routing problem(CVRP) and the multi-compartment vehicle routing problem(MCVRP) also take this consideration into account.
2) We do not believe that there is a certain path which is preferred by any delivery agent. Suppose a delivery agent does not want to take a certain path (maybe due to some bias) then that is not accounted for. Every delivery agent is believed to take any path that would be allotted to him/her.
3) When we talk about the capacity of the delivery agent, we believe it to be the maximum amount of commodities it can carry. The maximum distance that the vehicle can travel without refuelling is not taken into account at any time. But this is a reasonable assumption as we are not considering very large regions (For example, Hauz Khas is not a geographically large region) so it is sensible to assume that the vehicle can travel all the distance it needs to without any refuelling (which in turn would also have changed more factors since distances corresponding to the petrol pumps would also have needed to be taken into account).
The problem with the general solutions of the vehicle routing problems is that they do not allow multiple vehicles to be sent to the same point even if that resolves the problem of demand not being fulfilled at that point. We were also facing similar problems. So, what we did was that if the model is unsolvable (despite demand<=supply) then each point is split into two points with demands of the two points being half the demand at our original point. Understanding with an example: There are two delivery trucks - each with a capacity of 30 and the demands to be met at our two consumers are 20(A) and 40(B). Now, with only one vehicle being allowed to go to one consumer, this problem is unsolvable. However, we split the points into two points (A1,A2,B1,B2) with demands (10,10,20,20). Now Truck 1 can visit A1,B1 and Truck 2 can visit A2,B2 or other combinations according to wherever the distances travelled are minimized. If a location with a odd demand (example 15) is to be split, it is split into the two integers closest to its half. It will be split into Point 1 and Point 2 with demands 7 and 8. In the end, if any vehicle is travelling to points which were derived, through splitting, from the same original point, then we say that it is travelling to that original point with demand equal to the sum of these derived points. Example, if vehicle is to visit A10 and A17 with demands 12 and 13 then we say that the vehicle is to visit A with demand 25.
Link to the codes:
Envisaged Solution
To address the problems identified in the UX Research, I decided to come up with a digital solution in the form of a Web Application: Navigo.
Information Architecture
We made the Information architecture (IA) is, a blueprint, a visual representation of our product’s infrastructure, features, and hierarchy.
Wireframes
We made the website's wireframe which acted as a visual guide that represented the skeletal framework of the website .
High Fidelity Prototypes
LOGIN/REGISTER SCREEN
User Login and Registration available, data gets saved in online servers. A feature is given to select the area you wish to login for, enabling security.
INFORMATION UPLOAD SCREEN
Uploading the three necessary Information ie. Agents, Available Commodities and Consumers data.
MAIN SCREEN
Divided into three sections, delivery agent, consumers and a map view which shows every route with their stop markers.
Interactive Prototype
Link to the interactive prototype:
Usability Testing
For the usability testing, we sent the link for the interactive prototype to a user, and asked him to perform certain tasks on the the app. This was done over a zoom call for about 15 mins. We’ve noted down the insights from the testing and listed them down below. The following is the feedback that we recieved during the testing:
• The consumers can know who all delivery agents will be coming to their place and with how much commodities. A seperate login for the
• We can have a feature to track the delivery agents. The personnel at the central warehouse can track the locations of all the agents whereas each consumer can track the delivery agents which would be reaching his/her house.
Future Scope: Machine Learning
We can further incorporate machine learning to make our solution more efficient. After we have done generating routes for the delivery persons and have gathered the time they take , say, on assigning any particular route. We can analyse the data carefully and invisage ML to better assign the routes to the delivery persons. The model will improve itself overtime and the planned routes will start becoming user-friendly. The need of this arises, because after all the delivery persons are humans, they have a bias over a certain route. But since we cannot assign anyone to a particular route, we can however, assign them the route they best fit on. Another application of machine learning could be to better calculate the time it takes for a particular user to reach a particular location, taking into account the traffic and several such variables.
References
• Routific Demo: Route Optimization & Delivery Route Planning
• 5 Stages in the Design Thinking Process
• Extract the distances between points
• CPLEX & Python. Capacitated vehicle routing problem
• Think Aloud Usability Testing