Heuristics for the Design of Safe Humanitarian Aid Distribution Itineraries
Heuristics for the Design of Safe Humanitarian Aid Distribution Itineraries
Jos´e M. Ferrer1(B), M. Teresa Ortu˜no2, Gregorio Tirado2,
and Bego˜na Vitoriano2
1 Secci´on Departamental de Estad´ıstica e Investigaci´on Operativa,
Facultad de Medicina, Universidad Complutense de Madrid,
Plaza de Ram´on y Cajal, 28040 Madrid, Spain
jmferrer@pdi.ucm.es
2 Departamento de Estad´ıstica e Investigaci´on Operativa,
Facultad de Matem´aticas, Universidad Complutense de Madrid,
Plaza de Ram´on y Cajal, 28040 Madrid, Spain
{tortuno,gregoriotd,bvitoriano}@mat.ucm.es
Abstract. After a disaster strikes, one of the main activities to be developed
from a logistics point of view is the design of humanitarian aid
distribution plans. In this work the problem of designing safe feasible
itineraries for last-mile distribution under the risk of being assaulted, as
well as assuring the equity of the distribution, is addressed. The task of
simply finding feasible solutions for this problem is highly complex. In
this paper we present a constructive randomized heuristic to generate
a variety of solutions within a small computational time, and we also
provide some ideas of how to modify this constructive algorithm in order
to use it within a metaheuristic framework.
Keywords: Humanitarian logistics · Heuristics · Distribution planning
Introduction
Nowadays, disasters are often seen as the consequence of inappropriately managed
risk, being these risks the product of hazards and vulnerability. In this way,
developing countries, due to their greater vulnerability, suffer the greatest costs
when a disaster occurs.
Once a disaster strikes a country, the distribution of humanitarian aid to a
population affected is one of the most fundamental operations in what is nowadays
called “Humanitarian Logistics”, defined as the process of planning, implementing
and controlling the efficient, cost-effective flow and storage of goods and
materials as well as related information, from the point of origin to the point of
consumption, for the purpose of meeting the end beneficiaries requirements and
alleviate the suffering of vulnerable people, [the Humanitarian Logistics Conference,
2004 (Fritz Institute)]. In the last decade it has been an increasing interest
in the study of this field, pointing out the similarities and differences between
humanitarian and business logistics [1] and developing new models valid for the
special characteristics of this kind of problems. See [7] for a survey on Decision
Aid Models and Systems for Humanitarian Logistics, which can give an idea of
the last developments in the field.
As stated by several authors (see [5,6,8], among others), traditional logistic
objectives, such as minimizing operation cost, are not the most relevant ones in
humanitarian operations. Other factors, such as time of operation, or the design
of safe and equitable distribution plans, come to the front, and new models and
algorithms are needed to cope with these special features.
Problem Description
The problem addressed in this work concerns last-mile distribution in disaster
relief operations, which is the final stage of a humanitarian relief chain. It refers
to delivery of goods from local distribution centers to the people in need. In
particular, the problem addressed consists of designing routes for vehicles among
nodes that have an available quantity of goods or have a demand of those goods,
choosing the most suitable types of vehicles and determining the flow of the
aid. More specifically, the problem addressed is described through the following
elements:
humanitarian aid is distributed, meeting the following set of conditions:
In a goal programming static flow model to deal with a variant of this
problem is presented, providing an approximation to the best distribution plan
using up to six conflicting criteria. The model presented does not consider the
individual movement of vehicles through the network, but gives an idea of the
flow of the vehicles and load. In this work the model is extended to allow a more
detailed planning, which explicitly considers the movement of vehicles along
time, and a heuristic procedure is proposed.
To illustrate the functioning of the constructive algorithm introduced in the
following section, we will use a small instance whose logistic network is described
in Fig. 1. There are 2 depots with 15 + 15 tons of humanitarian aid available,
3 demand nodes needing 10, 15 and 15 tons and 2 connection nodes. We will
have two types of vehicles, with different capacities and velocities as stated in
Fig. 1, and 2 vehicles of each type available at each depot and at one connection
node. Finally, the planned amount of humanitarian aid to be distributed in the
operation is 25 tons.
Constructive Algorithm
The requirement of vehicles having to travel together forming a convoy on every
trip of the plan in order to increase the safety of the itineraries, together with
the combination of other limitations such as the vehicle and humanitarian aid
availability, make it very hard to build not only optimal, but even just feasible
solutions for the problem. For this reason, the development of heuristics for this
problem is especially difficult. This section introduces a constructive algorithm
we have developed for the design of feasible distribution itineraries for aid distribution
in the context described before. It generates feasible solutions from
scratch, adding new elements to the partial solution constructed at each iteration
until a final feasible plan is constructed. However, differently as it happens
in many other combinatorial optimization problems, in which generating feasible
solutions can be done in a very fast and simple way, this constructive algorithm is
far from trivial.
Ensuring the feasibility of the solution at each iteration is highly
complex, especially due to the precedence constraints induced on the vehicle and
humanitarian aid flow by the requirement of vehicles traveling together. Besides,
the algorithm makes use of some randomization mechanisms when choosing the
new elements to be added to the current partial solution, with the aim of being
able to provide a variety of feasible solutions when run several times. In what
follows the constructive algorithm will be described.
Preprocess. First of all, a preprocess is performed in order to facilitate the
resolution of the problem. It comprises several tasks, such as checking some
simple conditions that may indicate that the problem is infeasible or simplifying
the logistic network by removing unnecessary links. Besides, the cheapest
return path from each demand node back to the depots is calculated before the
construction of the solution is initiated.
Vehicle Itineraries. The itineraries to be followed by the vehicles are designed
iteratively. At each iteration, the vehicle to be moved and the next link to be
traversed by that vehicle are selected randomly, repeating this process until all
itineraries are complete. However, the candidate links that can be traversed
by each vehicle may change at each iteration, due to the precedence relations
induced by the requirement of vehicles traveling together forming a convoy and
thus having to depart and arrive at the same time. This precedence relations must
be updated at each iteration based on the new link added to the itineraries. When
all itineraries are completed, the convoys traversing each link are determined,
together with their departure and arrival times at the nodes. Note that the
speed of a convoy is determined by the slowest vehicle, and for that reason the
final schedules of the vehicles cannot be calculated until all itineraries are fully
determined.
Jos´e M. Ferrer1(B), M. Teresa Ortu˜no2, Gregorio Tirado2,
and Bego˜na Vitoriano2
1 Secci´on Departamental de Estad´ıstica e Investigaci´on Operativa,
Facultad de Medicina, Universidad Complutense de Madrid,
Plaza de Ram´on y Cajal, 28040 Madrid, Spain
jmferrer@pdi.ucm.es
2 Departamento de Estad´ıstica e Investigaci´on Operativa,
Facultad de Matem´aticas, Universidad Complutense de Madrid,
Plaza de Ram´on y Cajal, 28040 Madrid, Spain
{tortuno,gregoriotd,bvitoriano}@mat.ucm.es
Abstract. After a disaster strikes, one of the main activities to be developed
from a logistics point of view is the design of humanitarian aid
distribution plans. In this work the problem of designing safe feasible
itineraries for last-mile distribution under the risk of being assaulted, as
well as assuring the equity of the distribution, is addressed. The task of
simply finding feasible solutions for this problem is highly complex. In
this paper we present a constructive randomized heuristic to generate
a variety of solutions within a small computational time, and we also
provide some ideas of how to modify this constructive algorithm in order
to use it within a metaheuristic framework.
Keywords: Humanitarian logistics · Heuristics · Distribution planning
Introduction
Nowadays, disasters are often seen as the consequence of inappropriately managed
risk, being these risks the product of hazards and vulnerability. In this way,
developing countries, due to their greater vulnerability, suffer the greatest costs
when a disaster occurs.
Once a disaster strikes a country, the distribution of humanitarian aid to a
population affected is one of the most fundamental operations in what is nowadays
called “Humanitarian Logistics”, defined as the process of planning, implementing
and controlling the efficient, cost-effective flow and storage of goods and
materials as well as related information, from the point of origin to the point of
consumption, for the purpose of meeting the end beneficiaries requirements and
alleviate the suffering of vulnerable people, [the Humanitarian Logistics Conference,
2004 (Fritz Institute)]. In the last decade it has been an increasing interest
in the study of this field, pointing out the similarities and differences between
humanitarian and business logistics [1] and developing new models valid for the
special characteristics of this kind of problems. See [7] for a survey on Decision
Aid Models and Systems for Humanitarian Logistics, which can give an idea of
the last developments in the field.
As stated by several authors (see [5,6,8], among others), traditional logistic
objectives, such as minimizing operation cost, are not the most relevant ones in
humanitarian operations. Other factors, such as time of operation, or the design
of safe and equitable distribution plans, come to the front, and new models and
algorithms are needed to cope with these special features.
Problem Description
The problem addressed in this work concerns last-mile distribution in disaster
relief operations, which is the final stage of a humanitarian relief chain. It refers
to delivery of goods from local distribution centers to the people in need. In
particular, the problem addressed consists of designing routes for vehicles among
nodes that have an available quantity of goods or have a demand of those goods,
choosing the most suitable types of vehicles and determining the flow of the
aid. More specifically, the problem addressed is described through the following
elements:
- Transportation Network. Nodes representing the locations of pick-up, delivery or connection, and main links characterized by distance and average velocity.
- Goods. Information about the amount of aid available or required at eachnnode.
- Vehicles. Several types are considered, characterized by capacity, average velocity, variable and fixed costs and availability in each node of the network. Fixed costs represent the cost of moving the vehicle one unit of length, while variable costs represent the cost of transporting one unit of aid through one unit of length, for each type of vehicle.
- Operation elements. They include the global quantity to be distributed in the operation and the budget available, as well as the knowledge about the state of the roads or the safety of each zone.
humanitarian aid is distributed, meeting the following set of conditions:
- All nodes can be used for transshipment of goods among vehicles.
- Availability of connections can be unknown when planning. The disaster may have blocked or destroyed some roads, but that information is usually not fully available. The design of routes will take this fact into account by trying to choose connections with greater probability of being available.
- Under extreme conditions, as the ones arising after a disaster in highly vulnerable places, the vehicles could be assaulted during the mission. Assuming that a single vehicle has greater probability of being assaulted than a convoy, and that the greater the number of vehicles traveling together the lesser the probability of being robbed, all vehicles traveling through a link will be forced to travel together forming a convoy.
- Each vehicle can pass several times through a node, but only once through an arc.
- As usual in this type of situations, the available goods are not enough to cover the demand. Then, equity in the distribution will be sought, by trying to attend similar percentages of demand in all demand nodes.
- In some situations help can be more urgently needed in some places than in others. A graduation on the priority of the nodes can be considered.
- Reducing operation costs is not the main objective, but this must be taken into account by ensuring that the available budget is not exceeded.
- After the delivery, vehicles return to their origin nodes following the cheapest possible path. No risk of being assaulted will be considered for empty vehicles.
In a goal programming static flow model to deal with a variant of this
problem is presented, providing an approximation to the best distribution plan
using up to six conflicting criteria. The model presented does not consider the
individual movement of vehicles through the network, but gives an idea of the
flow of the vehicles and load. In this work the model is extended to allow a more
detailed planning, which explicitly considers the movement of vehicles along
time, and a heuristic procedure is proposed.
To illustrate the functioning of the constructive algorithm introduced in the
following section, we will use a small instance whose logistic network is described
in Fig. 1. There are 2 depots with 15 + 15 tons of humanitarian aid available,
3 demand nodes needing 10, 15 and 15 tons and 2 connection nodes. We will
have two types of vehicles, with different capacities and velocities as stated in
Fig. 1, and 2 vehicles of each type available at each depot and at one connection
node. Finally, the planned amount of humanitarian aid to be distributed in the
operation is 25 tons.
Constructive Algorithm
The requirement of vehicles having to travel together forming a convoy on every
trip of the plan in order to increase the safety of the itineraries, together with
the combination of other limitations such as the vehicle and humanitarian aid
availability, make it very hard to build not only optimal, but even just feasible
solutions for the problem. For this reason, the development of heuristics for this
problem is especially difficult. This section introduces a constructive algorithm
we have developed for the design of feasible distribution itineraries for aid distribution
in the context described before. It generates feasible solutions from
scratch, adding new elements to the partial solution constructed at each iteration
until a final feasible plan is constructed. However, differently as it happens
in many other combinatorial optimization problems, in which generating feasible
solutions can be done in a very fast and simple way, this constructive algorithm is
far from trivial.
Ensuring the feasibility of the solution at each iteration is highly
complex, especially due to the precedence constraints induced on the vehicle and
humanitarian aid flow by the requirement of vehicles traveling together. Besides,
the algorithm makes use of some randomization mechanisms when choosing the
new elements to be added to the current partial solution, with the aim of being
able to provide a variety of feasible solutions when run several times. In what
follows the constructive algorithm will be described.
Preprocess. First of all, a preprocess is performed in order to facilitate the
resolution of the problem. It comprises several tasks, such as checking some
simple conditions that may indicate that the problem is infeasible or simplifying
the logistic network by removing unnecessary links. Besides, the cheapest
return path from each demand node back to the depots is calculated before the
construction of the solution is initiated.
Vehicle Itineraries. The itineraries to be followed by the vehicles are designed
iteratively. At each iteration, the vehicle to be moved and the next link to be
traversed by that vehicle are selected randomly, repeating this process until all
itineraries are complete. However, the candidate links that can be traversed
by each vehicle may change at each iteration, due to the precedence relations
induced by the requirement of vehicles traveling together forming a convoy and
thus having to depart and arrive at the same time. This precedence relations must
be updated at each iteration based on the new link added to the itineraries. When
all itineraries are completed, the convoys traversing each link are determined,
together with their departure and arrival times at the nodes. Note that the
speed of a convoy is determined by the slowest vehicle, and for that reason the
final schedules of the vehicles cannot be calculated until all itineraries are fully
determined.
0 Response to "Heuristics for the Design of Safe Humanitarian Aid Distribution Itineraries"
Post a Comment