tesis vrp

Encaminamiento de camiones
recolectores de basura

1.

Representación de la ciudad

E

N

este punto se definirá el problema de retiro de desechos domiciliarios

de una manera formal. El proble-ma de recolectar desechos

domiciliarios es del tipo VRPTW, y en específico
para la comuna de Chillán es del tipo AVRPTW con ventas de tiempo estrictas, asimétrico debido a la distribuciónde sus calles y del tráfico en ellas
conocido como tablero de damero1 , esto se puede ver en la figura 6.1 y con
1

Esquema de distribución de calles de una ciudad heredado de los españoles, y que consta
de distribuir las calles de forma que estas se corten en ángulo recto, semejante a un tablero
de dama.

1

ventanas estrictas ya que la atención a los ciudadanos no puede anticiparse
niexceder ciertos horarios. Por lo que el grafo G que representará a la ciudad de Chillán de define a través de la tupla (V, A), donde V es el conjunto de
vértices del grafo, los cuales ,

representan a los clientes. En esta

representación del problema estos serán cuadras de la ciudad de Chillán, las
cuales son los espacios de una calle comprendidos entre dos esquinas de un
lado de unamanzana y A el conjunto de arcos que representarán a los
trayectos a recorrer entre cua-dras, como se representa en la figura 6.2. Se
debe entender que el tránsito de vehículos se realizará por un segmento de la
calle llamado calzada, el cual está restringido en su sentido de circulación,

Cuadra

Manzana

Independencia

 Cuadra
Sargento Aldea

Constitución

Isabel Riquelme

5 de AbrilBulnes

Avenida Libertad

El roble

Cuadra

Avenida Ecuador

Arauco

18 de Septiembre

Avenida Ecuador

Cuadra

Carrera

como se explica a continuación.

Avenida Collin
Avenida Collin

Figura 6.1: Distribución de las calles de la comuna de Chillán
Los arcos A del grafo G serán asimétricos; esto por la distribución similar
a un tablero de ajedrez de la comuna, dondeexisten calles que se pueden

2

transitar en un solo sentido, y otras que se hace en ambos sentidos, como
es el caso de las avenidas Ecuador y Collin que se muestra en la figura 6.1,
se por esto que para representar esta diversidad en los sentidos de circulación de las calles se debe considerar un grafo dirigido, así a las calles que
se pueden recorrer en un solo sentido de tránsito, se lesdeberá prohibir o

El roble

Manzana

Independencia

Constitución

Cuadra

Trayecto
Sargento Aldea

Avenida Libertad

Isabel Riquelme

Bulnes
5 de Abril

Arauco

Avenida Ecuador

Cuadra

18 de Septiembre

Avenida Ecuador

Trayecto

Carrera

desincentivar a los vehículos la circulación en sentido contrario.

Avenida Collin
Avenida Collin

Figura 6.2:Representación del problema en un grafo

2.

Sobre las variables de representación.

Sobre las variables que ayudaron a definir el problema del VRPTW , la
mayoría de estas sufrirán modificaciones sólo en su interpre-tación. Por
ejemplo, di que reflejaba la demanda de un vértice i (cliente) por un bien o
servicio, ahora va a representar la demanda de varios clientes.

3

Esto debido a queen una cuadra hay ubicados casas y negocios, que son los
demandantes del retiro de desecho domiciliario, están comprendidos entre
dos esquinas de una cuadra, siendo di la representación de la demanda acumulada de todos los clientes de una cuadra. En el caso del tiempo de servicio
si, q, en éste modelo la variable representa el tiempo de servicio necesa-rio
para atender a todos los clientes dela cuadra que representa el vértice i. Las
variables restantes cij , k, [ai, bi], tij , si, wik, xijk, no sufrirán cambios en su
sentido,

Con respecto a cómo se calculará el costo de recorrer el trayecto de una
cuadra a otra, estará dado por cij = (sj + tij ) T C, donde T C será el costo de
utilización de un vehículo k por unidad de tiempo. Se debe entender a cij
como el costo acumulado...