|
Christelle Guéret |
|
|
bidon |
A
pick-up and delivery problem with helicopter
Pierre DEJAX*, Christelle GUERET*, Christian Prins** and Nubia Milena VELASCO***
(*) Equipe Systèmes Logistiques et de Production, École des Mines de Nantes and IRCCyN (Nantes, France)
(**)Equipe Optimisation des Systèmes Industriels (OSI), Université de Technologie de Troyes and Institut Charles Delaunay (Troyes, France)
(***) Produccion
y logistica team (PyLo), Universidad de los Andes
(Bogota, Colombia)
The Pick-up and Delivery
Problem (PDP) is the one of finding a set of optimal routes for a fleet of
vehicles in order to serve a set of transportation requests. In the problem
considered here, passengers must be transported from one point to another by
one helicopter (1-PDP). The application specially studied is the personnel
transportation among oil platforms.
More precisely, a set of n
transportation requests must be satisfied. Each request k concerns one single
passenger who must be transported from a pick-up node p_k to a delivery node
d_k. A priority u_k (between 0 - the least important level - and 4 - the most
important level) is assigned to each transportation request considering its
urgence.
Each node i has a service
time s_i (for picking the passenger up and dropping him/her off) and an
approach capacity a_i (maximum number of passengers allowed to land at a time,
for security reasons). The travel time t_{ij} between any two nodes i and j is
pre-computed knowing the distances and the average helicopter speed. All data
are integers, except the t_{ij} which are real numbers.
Only one helicopter is
available to fulfill these requests. It is characterized by a capacity Q
(maximum number of passengers) and a maximum route duration T before refuelling
at the base node.
A typical helicopter route consists in leaving the base, visiting a
sequence of nodes, and returning to the base. The helicopter load is incremented
after each pick-up and decremented after
each delivery. The duration of a route is the sum of its travel and service
times. A feasible solution is a set of routes satisfying the following
classical PDP constraints:
- Pairing: for any request k, p_k
and d_k must be visited in the same route.
- Precedence: for any request k, p_k
must be visited before d_k.
- Capacity: the number of passengers
on board must not exceed Q.
Additionally, the two problem-specific constraints must also hold:
- Approach capacity: at most a_i
passengers aboard when landing on a site i.
- Maximum route duration: the total
duration of any route must not exceed the time T.
In the mono-objective
version, the objective is to minimize the total cost (variable cost + fixed
cost) of the routes. In the bi-objective version, the objective is to minimize
the total duration of the routes (objective 1) while satisfying the most urgent
transportation requests in priority (objective 2). All transportation requests must be satisfied.
|
- Last
modified: June 6 2006 by Christelle Jussien |