OR to the aid again! As I stated in my last blog message every Operations Research professional should offer his or her support to initiatives of the UN or other humanitarian organizations to help improve their operations. This way more lives can be saved. Last week I got the chance to put my money where my mouth is.
By coincidence I got in touch with the UNJLC, the United Nations Joint Logistics Centre. They were asked to provide a schedule for delivering relief supplies to schools and settlements in the Amuria district of Uganda. This as part of the Uganda flood response. As you might have read in the newspaper, large parts of eastern Uganda are flooded. At this moment the situation in flood-affected parts of Uganda continues to worsen. The first priorities of the aid are to stabilize the initial food security situation, preventing disease outbreaks, ensuring capacity to respond to health emergencies and re-opening schools.
The task of the UNJLC is to help with the food supply. Tons of cereals, sugar and vegetable oil needs to be transported to schools and settlements. Because the locations cannot be reached by road, helicopters are used to deliver the relief supplies. The helicopter flies from a central point in the area to the locations of the schools and settlements. For each of the locations it is known how much of the relief supplies need to be delivered. The helicopter however has a maximum carrying capacity, which is lower than the demand of some of the schools and settlements. This means that the helicopter has to perform several flights and attend several locations more than once. For each flight it has to be decided which locations to attend and how much of the relief supplies to be delivered at the locations visited. The helicopter range wasn’t an issue in this case, so the length of the flight wasn’t a restriction. You might guess that under the pressure of many people in need no time should be lost in finding the best possible solution. Your (and mine) first reaction would be to load a helicopter and start delivering the supplies. The people at UNJLC wandered if it would be possible to construct the schedules automatically, so the best possible routes could be constructed in the least possible time. A challenge I could not resist.
There are several ways to find the optimal solution. Of course you could startup MS Excel and construct the routes by hand. This can be a very good way when the number of locations to attend is not large. Another way is to use brute force techniques like a set covering approach. In that case you generate all possible routes and use a LP model to select the best routes, assigning the amount of supplies to each of the routes in the same model. I used a Network flow model in which all the nodes in the network represent demand points except the central point (Origin) from which all flights departed. I constructed a complete network, i.e. all demand nodes in the network were connected with directed arcs. The origin was connected to all the demand points in one direction. By setting the appropriate capacity constraints on the arcs, the maximum carrying capacity was modeled. In the objective function the length of the arcs in the network was used as a proxy for cost of using the arc. A flow in the model represents a route, including the amount of relief supplies to be transported. Solving the model was easy and took only a few seconds. The optimal routes are much better than the routes used until now. They save time and money, allowing for more relief supplies to be delivered and therefore lives to be saved. OR to the Aid!
By coincidence I got in touch with the UNJLC, the United Nations Joint Logistics Centre. They were asked to provide a schedule for delivering relief supplies to schools and settlements in the Amuria district of Uganda. This as part of the Uganda flood response. As you might have read in the newspaper, large parts of eastern Uganda are flooded. At this moment the situation in flood-affected parts of Uganda continues to worsen. The first priorities of the aid are to stabilize the initial food security situation, preventing disease outbreaks, ensuring capacity to respond to health emergencies and re-opening schools.
The task of the UNJLC is to help with the food supply. Tons of cereals, sugar and vegetable oil needs to be transported to schools and settlements. Because the locations cannot be reached by road, helicopters are used to deliver the relief supplies. The helicopter flies from a central point in the area to the locations of the schools and settlements. For each of the locations it is known how much of the relief supplies need to be delivered. The helicopter however has a maximum carrying capacity, which is lower than the demand of some of the schools and settlements. This means that the helicopter has to perform several flights and attend several locations more than once. For each flight it has to be decided which locations to attend and how much of the relief supplies to be delivered at the locations visited. The helicopter range wasn’t an issue in this case, so the length of the flight wasn’t a restriction. You might guess that under the pressure of many people in need no time should be lost in finding the best possible solution. Your (and mine) first reaction would be to load a helicopter and start delivering the supplies. The people at UNJLC wandered if it would be possible to construct the schedules automatically, so the best possible routes could be constructed in the least possible time. A challenge I could not resist.
There are several ways to find the optimal solution. Of course you could startup MS Excel and construct the routes by hand. This can be a very good way when the number of locations to attend is not large. Another way is to use brute force techniques like a set covering approach. In that case you generate all possible routes and use a LP model to select the best routes, assigning the amount of supplies to each of the routes in the same model. I used a Network flow model in which all the nodes in the network represent demand points except the central point (Origin) from which all flights departed. I constructed a complete network, i.e. all demand nodes in the network were connected with directed arcs. The origin was connected to all the demand points in one direction. By setting the appropriate capacity constraints on the arcs, the maximum carrying capacity was modeled. In the objective function the length of the arcs in the network was used as a proxy for cost of using the arc. A flow in the model represents a route, including the amount of relief supplies to be transported. Solving the model was easy and took only a few seconds. The optimal routes are much better than the routes used until now. They save time and money, allowing for more relief supplies to be delivered and therefore lives to be saved. OR to the Aid!
