[Todos] Charla: Problemas de Ruteo de Vehículos

[Irene Loiseau]

Invitamos a la charla que  dictará el  Dr. Julián Aráoz el miércoles 4 de
octubre a las 15hrs en el Pabellón I (aula a determinar), titulada:

"Prize-collecting Arc Routing Problem (PARP)"
Julián Aráoz
Departament d’Estadística i Investigació Operativa, UPC.
and Universidad Simón Bolívar

(la charla se dictará en castellano,ver resumen abajo)

EXPOSITOR: el Dr. Julián Araóz es Computador Científico de la primera
generación recibida en nuestra facultad, y Dr. de la Universidad de
Waterloo, Canadá. Es un especialista de primer nível internacional en
temas de Optimización Combinatoria, en los cual ha hecho muy importantes
aportes originales. Ha realizado numerosas publicaciones y dirigido
alumnos de posgrado. Ha contribuído también muy significativamente a
impulsar y mejorar la enseñanza de la Computación en Venezuela, en Uruguay
y otros países de la región, y también en nuestro país donde tuvo una
activa participación en la ESLAI y una presencia permanente en congresos
nacionales, cursos de posgrado y otros eventos. En esta charla presentará
su trabajo actual en temas de ruteo de vehículos que son de gran
importancia práctica y al mismo tiempo presentan interesantes desafíos 
teóricos.


---------------------------------------------
RESUMEN
Prize-collecting Arc Routing Problem (PARP)
-----------
In this talk we deal with the Prize-collecting Arc Routing Problem (PARP)
and some extensions.
Problems of this type  are a generalization of Arc Routing Problems
(ARPs), which aim to determine a least-cost traversal of a specified arc
subset of a graph, with or without constraints. Typical ARPs constraints
require the routes to begin and finish at a given point (the depot), and
guarantee the connectivity of the solutions with the depot.
PARPs can be seen as the arc-routing counterpart of Prize-Collecting
Traveling Salesman Problems. PARPs can also be stated in directed and
mixed graphs. However, here we talk only of problems over undirected
graphs.

Some examples of Prize-collecting Arc Routing Problems are:

** Prize-collecting Rural Postman Problem (PRPP):  To find the most
profitable subtour passing through the depot.

** Clustered Prize-Collecting Arc Routing Problem (CPARP):Some subsets of
edges are grouped into clusters. Additional requirement: For each cluster
either all the edges are serviced or none of them are serviced.

** Generalized Prize-collecting Arc Routing Problem (GPARP):Some subsets
of edges are grouped into clusters. Additional requirement: For each
cluster exactly (at least) one edge must be serviced. (Arc routing version
of Generalized TSP)

** Weighted Prize-collecting Arc Routing Problem (WPARP): There is a
weight associated with servicing each edge and a limit on the total weight
that one route can service. Two versions depending on whether or not we
limit the number of routes to be performed.

Overwiew of the talk:
1.	Introduction and definition of classical problems
2.	Introduction and definition of PARP problems
3.	LP-based algorithms.
4.	Separation of inequalities
5.	Computational Experiments
6.	Comments and future work.

(Join work with Elena Fernández, Carles Franquesa (Departament
d’Estadística i Investigació Operativa, UPC), Oscar Meza (Departamento de
Computación y Tecnología de la Información, Universidad Simón Bolívar)).



-- 
Irene Loiseau
Departamento de Computación
Facultad de Ciencias Exactas y Naturales
Universidad de Buenos Aires
Pabellón I- Ciudad Universitaria
1428 Buenos Aires - ARGENTINA
TE/FAX: 54 11 4576 3359
TE: 54 11 4576 3390/96 int 711
e-mail: irene en dc.uba.ar