05MER_Capitol3

3.Formulacin del problema

M. Estrada (2007) 79

3. FORMULACIN DEL PROBLEMA La asignacin de flujos de mercancas al conjunto de rutas de la red troncal se puede expresar como un problema de programacin matemtica, con la identificacin de una funcin objetivo de costes a minimizar y varias restricciones. En este contexto, debido a la consolidacin de la carga de los clientes en las terminales y delegaciones, algunos de los flujos entre delegaciones suelen tener una masa crtica suficiente para justificar un envo directo entre stas. Sin embargo, en algunas relaciones con poca demanda, los envos pueden resultar ms eficientes si se realiza una ruta con paradas mltiples o con alguna transferencia y cambio de vehculo en una terminal. En este captulo se abordar el problema de programacin matemtica mediante la definicin de las variables, restricciones y la funcin de costes asociada a una red de distribucin de muchos orgenes a muchos destinos con la posibilidad de estrategias de envos directos, con paradas mltiples o va hub. El problema general se descompondr en dos fases: en la primera etapa se realizar la asignacin de envos a carga completa con los distintos vehculos disponibles, mientras que en la segunda etapa se planificarn todos los envos con carga inferior a la capacidad del vehculo. La descomposicin es obvia porque si qij es el flujo entre el origen i y el destino j y Ck la capacidad de un vehculo de tipo k, se cumple la ecuacin (3.1):

kk

ijk

k

ijij CC

qC

Cq

q

+

=

(3.1)

Anlisis de estrategias eficientes en la logstica de distribucin de paquetera

80 M. Estrada (2007)

donde [ ] indica la parte entera por defecto y {} la parte fraccionaria. Cualquier consolidacin de la carga [ ] kkij CCq / implica mayores costes que enviar [ ]kij Cq / vehculos de tipo k llenos.

3.1. CONDICIONANTES Y ATRIBUTOS A CONSIDERAR EN LA ASIGNACIN DE FLUJOS EN LA RED TRONCAL

Para la formulacin del problema, se parte de un grafo completo G(N,E) donde el conjunto N de nodos representa la ubicacin de las delegaciones y E los arcos entre las delegaciones. Se debe definir de forma complementaria el conjunto H de terminales que actuarn como hub, HN. Las dimensiones de los conjuntos N y H determinan respectivamente el nmero de delegaciones del sistema NT= N y el nmero de terminales hub h= H . La distancia a

recorrer para el transporte de mercanca entre las delegaciones i,jN viene representada mediante la variable definida positiva Di,j. Adicionalmente, la velocidad de recorrido en cada arco eE viene definida por la variable ve>0 y el volumen de mercanca total a transportar entre las delegaciones (i,j) es representado por la variable positiva Wij. Las restricciones a cumplir que se han considerado en el problema son: La capacidad de los vehculos, C. Se ha considerado una flota homognea de

vehculos para la red troncal, de forma que cada uno de ellos tiene un volumen mximo igual a C (m3; la restriccin ms habitual en este tipo de envos es por volumen ms que por peso) disponibles para la carga de la mercanca.

Las ventanas temporales de servicio de cada delegacin (h1,i ; h2,i). La variable h1,i representa el tiempo de apertura en la delegacin origen i para iniciar la carga de los vehculos, mientras que h2,i representa el tiempo mximo de entrada a la delegacin i para proceder a la descarga de los vehculos.

Plazo de distribucin, Pf. El problema a estudiar considera un plazo de entrega de la mercanca fijo para todas las demandas de servicio y que el envo entre una delegacin origen y una delegacin destino se produzca en un mismo ciclo de reparto o plazo de distribucin (en un mismo da, varios das, etc.) para cumplir las restricciones (h1O;h2,D).

El nmero de muelles de carga en delegaciones para distribuir la mercanca, im . En cada delegacin i, el nmero mximo de muelles destinado para el uso de los vehculos utilizados en la red troncal es fijo y se representa por la variable im .



El transporte de los volmenes de mercanca Wij asociados a todos los pares de delegaciones origen-destino (i,j) constituye un conjunto de tareas a realizar por los recursos del sistema (vehculos, conductores e instalaciones). De este modo, se puede hablar indistintamente de tareas o envos que tendrn un origen y un destino especfico y por lo tanto constituirn un problema de scheduling o de programacin puro. Si bien las restricciones temporales condicionarn el nmero mximo de tareas y volumen de mercancas entre delegaciones, la capacidad de los vehculos juega un papel fundamental en la asignacin de los recursos a las tareas o envos de transporte. En este punto, se debe diferenciar el problema de envos completos de los envos con volumen de carga inferior a la capacidad. Los envos completos se realizan cuando todo el volumen de mercanca entre un origen y un destino puede ser transportado en un solo vehculo sin violar las restricciones del sistema (capacidad o restricciones temporales). Sin embargo, cuando la demanda de mercanca entre un origen y destino supera la capacidad del vehculo, la mercanca se divide o fracciona en distintos envos asociados a distintas rutas para cumplir la restriccin de capacidad. En estos casos, al igual que los envos con una carga muy inferior a la capacidad, habr como mnimo un vehculo que presentar una ocupacin baja, al no aprovechar toda su capacidad potencial para el transporte. Estos casos, conocidos como Less than TruckLoad (LTL), constituyen un campo estratgico para aplicar estrategias de consolidacin. Cabe mencionar que en algunos sistemas de distribucin tambin se puede realizar el fraccionamiento de un envo con un volumen inferior a la capacidad vehicular. Este caso sucede cuando existen varios vehculos LTL con servicio entre el punto origen y destino del envo y con unos factores de carga bajos; de forma que el fraccionamiento puede llenar la capacidad de stos. De este modo, los envos entre delegaciones con volmenes de carga inferiores a la capacidad del vehculo (generan vehculos LTL) constituyen el principal aspecto de optimizacin de los recursos del sistema. Con el fin de evaluar el transporte fraccionado de una carga Wij (Wij >C) en unidades adecuadas a la capacidad del vehculo, se debe calcular la variable nij mediante la ecuacin (3.2). La variable nij representa el nmero de envos mnimo entre (i,j) para satisfacer el volumen Wij. , siendo el operador [x]+ el valor entero superior a x.



+

=C

Wn ijij (3.2)

Por lo tanto, el transporte de la mercanca entre las delegaciones (i,j) con una carga Wij >0 exige un total de nij tareas o envos para cumplir con la restriccin de capacidad de la flota de vehculos. En el caso que entre dos delegaciones (i,j) no exista volumen de carga (Wij=0) se considerar nij=0. Cuando Wij>C y Wij pC ( p ), se supone que existir como mnimo un solo envo con carga inferior a la capacidad (LTL), representado por la fraccin 0



costes de transferencia de vehculo en la terminal hub y los costes asociados a los tiempos muertos en que los vehculos esperan en las terminales o delegaciones a que un muelle quede libre para efectuar la carga o descarga. En este sentido se definen los siguientes parmetros: Coste de servicio de un vehculo de transporte en el sistema (F). Se asocia al coste

temporal que representa a la empresa el alquiler diario de un vehculo si realiza la subcontratacin del servicio. En el caso de flota propia, este parmetro representa principalmente al coste diario de amortizacin del recurso, salario del conductor, seguro, etc.

Coste unitario de recorrido de un vehculo (cd). Es el coste asociado a la superacin de una unidad de distancia con el vehculo, e integra los costes de carburantes y mantenimiento. En el problema de anlisis, este coeficiente se considera constante independientemente del volumen de mercanca transportada.

Coste unitario de transferencia (ct,i). Es el coste que representa la transferencia de una unidad de volumen de mercanca en la terminal hub i entre dos vehculos. Esta operacin suele requerir operaciones de manipulacin de la mercanca, maquinaria y tecnologa diferencial al tratamiento de la mercanca sin transferencia. Este coste solamente afecta a aquellas mercancas que se transportan en estrategias hubbing con cambio de vehculo en una terminal.

Coste de parada (cp). Es el coste que representa la parada de un vehculo en una delegacin para efectuar la carga y/o descarga de mercanca.

Coste unitario de congestin en delegacin (cw). Es el coste de penalizacin que supondra el hecho de tener un vehculo en la delegacin durante una unidad de tiempo a la espera de que un muelle de carga quedase libre para efectuar la carga y/o descarga de mercanca.

3.2. ASIGNACIN DE FLUJOS A LA RED COMO PROBLEMA DE PROGRAMACIN MATEMTICA

La estrategia ms sencilla para efectuar el transporte de mercanca entre las delegaciones (i,j) se basa en envos directos en carga completa o con carga inferior a la capacidad del vehculo. Sin embargo, el transporte de la mercanca Wij entre una delegacin origen i y una delegacin destino j puede ser realizado con envos con paradas mltiples o envos con transferencias (hub). Cada ruta rR se definir por el subconjunto de nodos Nr visitados y el



conjunto de arcos Er formado por los pares de puntos (i,j) (i,j Nr) que se cubren de forma consecutiva, sin ninguna parada intermedia. Adicionalmente, se define el conjunto Ar como aquellos pares de nodos (i,j) que disponen de un envo o tarea a= kija asignada a la ruta r. El nmero total de arcos que contiene una ruta

rR queda determinado por la variable br, de forma que rr bE = . Finalmente, el vector nr(i) determina la delegacin visitada en la posicin i=1,..,br+1 de la ruta rR Para la resolucin del problema se han generado cuatro variables discretas 0-1 para identificar los siguientes tipos de estrategias de transporte entre las delegaciones (i,j):

Estrategia de envo directo de la carga o tarea a= kija sin ninguna parada intermedia en la ruta r (k=1,..,nij). La fraccin k de la mercanca entre delegaciones i,j N se enviar de forma directa sin paradas intermedias en la ruta r cuando la variable discreta raX presente un valor igual a 1 y con otra estrategia cuando la variable sea 0.

Estrategia de envo peddling de la carga o tarea a= kija en la ruta r (k=1,..,nij). El envo de la fraccin k de mercanca entre las delegaciones i,jN se realizar a travs de una ruta existente rR con paradas intermedias si la variable discreta raZ toma valor igual a 1. En este caso, el envo o tarea a= kija lo realiza la ruta r visitando todos

los nodos intermedios zNr entre las delegaciones i, jNr que aparecen en la ruta r; mientras que coge un valor igual a 0 en caso contrario.

Estrategia de envo de la carga o tarea a= kija (k=1,..,nij) con una transferencia de la ruta r a una ruta s en la terminal hub l. Para identificar esta posibilidad, se han creado las variables discretas ralY y

salB . La variable

ralY determina la primera etapa del

envo hub, presentando un valor de 1 si el envo o tarea a= kija entre delegaciones (i,j)

se realiza por la ruta r con origen en i y transferencia en la terminal l. Por su lado, la variable salB representa la segunda etapa del envo hub, con un valor de 1 si la

mercanca kijw , una vez ha hecho escala en la terminal l, se enva a travs de la ruta

sR hasta el punto j. En el resto de casos, el valor de estas variables es 0. Por otro lado, se han creado dos variables discretas 0-1 auxiliares para poder determinar los arcos por los que se transporta la mercanca kijw en cada ruta (equivalente a asignar la tarea

kija ); as como la correspondencia entre los segmentos y sus nodos respectivos en cada ruta:



Variables 1,baU y 2 ',baU . Estas variables se utilizan para identificar los arcos de la ruta por los que discurre cada envo 0kijw . La variable discreta 1,baU coge el valor de 1 en el caso que la tarea a= kija asociada al volumen de mercanca

kijw se transporta por

el arco b de la ruta rR a la que ha sido asignada y 0 en caso contrario. La estrategia de envo puede ser a travs de un envo directo ( riaX =1), envo con paradas mltiples

( raZ =1), o a travs de la primera etapa de un envo hub entre nodo i y la terminal de

transferencia l ( ralY =1). Cuando el envo de la mercanca kijw asociada a la tarea

a= kija se realiza con estrategia hub a travs de la transferencia en la terminal l entre

rutas rR y sR, cada arco b por el que circula la carga en la primera etapa (ruta r) se identifica con 1,baU =1, mientras que cada arco b de la segunda etapa (ruta s) se

determina por 2 ',baU =1.

Variable r bijS , . La variable discreta tiene un valor igual a 1 cuando el arco b Er de la ruta r tiene como extremos los nodos o delegaciones i,jN y 0 en caso contrario. Esta variable se genera para determinar una equivalencia entre arcos y nodos de cada ruta.

Con las variables definidas hasta el momento, se puede formular unvocamente el problema de asignacin de envos a rutas considerando exclusivamente los condicionantes de capacidad de los vehculos, sin tener en cuenta las limitaciones temporales del problema ni las limitaciones de capacidad de las instalaciones (muelles de crossdocking). Por este motivo, la formulacin completa del problema de asignacin necesita generar una serie de variables relacionadas con estas limitaciones:

La variable rbp representa el tiempo muerto total que un vehculo perteneciente a la ruta rR debe esperar en el nodo extremo superior del arco b Er para que se libere alguno de los muelles por problemas de congestin.

La variable rbt representa el tiempo de viaje en el arco b de la ruta r a una velocidad v.

La variable rbT determina el tiempo inicio de carga del vehculo en la delegacin origen del arco b de la ruta r (delegacin i) para dirigirse a la delegacin final del arco (nodo j) cuando (i,j) Ar y 1, =r bijS .

La variable rbl representa el tiempo total de carga en la delegacin situada en el nodo origen del arco b de la ruta rR.



La variable rbu representa el tiempo total de descarga en la delegacin ubicada en el nodo final del arco b de la ruta rR.

Finalmente, los parmetros li , ui determinan respectivamente los tiempos unitarios de carga y descarga por volumen en la delegacin iN.

De este modo, la funcin objetivo del problema que se plantea responde a la minimizacin de los costes totales del sistema de distribucin Z1 con envos con paradas mltiples, con transferencia o envos directos. La citada funcin a minimizar se determina mediante la ecuacin (3.4).

( )

+

= =

++++=

Rr

b

bp

Aa Noa

roaot

b

b Ni Nj

rbij

rbwijd

r

g r

r

r r

cwYcSpcDcFZ1

1

',,

1,1 min (3.4)

El primer trmino de la funcin objetivo hace referencia a los costes fijos asociados a la prestacin del servicio de un vehculo para cubrir la ruta rR. El segundo trmino hace referencia a los costes variables proporcionales a la distancia y los costes de espera por congestin de la delegacin en todos los arcos b=1,..,br servidos con todas las estrategias de envo. El tercer trmino evala el coste de manipulacin en las transferencias de toda la mercanca con envos hub. Finalmente, el cuarto trmino determina los costes asociados a

todas las paradas efectuadas en cada ruta rR. En este caso, la formulacin propuesta para el problema es ms compleja que la propuesta en Aykin (1995a) y otras contribuciones relativas a localizacin ya que aquellas proponan un problema basado en flujos, hecho que permita desacoplar el problema de asignacin de envos a la red del problema de rutas y asignacin de vehculos. En el caso que nos ocupa, es necesaria la determinacin del nmero de vehculos utilizados y las rutas para cumplir las restricciones temporales y de capacidad. El conjunto de restricciones a considerar en el problema se detallan en las ecuaciones (3.5)-(3.13), y han sido adaptadas a partir del anlisis de problemas de rutas realizado en Desaulniers et al. (2002).

gA 12

=

+++

aBYZX

Rr No

rao

raor

ara

r

(3.5)

( ) ( ) 111 2,*,1,*,1 ,*1,*1,*1,* =

+

+

+

g rggAa Noba

roaba

roa

Adbd

rdba

ra

Acbc

rcba

ra UBUYUZUZUXUX

1,...,1 ;* = rbbRr

(3.6)



+ =rr Aji

rbij

Aqj

rbjq SS

),(,

),(1, 0 1,...,1 ;* = rbbRr (3.7)

( ) rAa No

bar

oabar

oabaraba

raa bbRrCUBUYUZUXw

g r

,..,1;* *

2,

*,

1,

*,

1,

*1,

*' =

+++

(3.8)

rr

bijAji

irb

rb

rbij

Ajii bbRrShlTSh

rr

,...,1;* *,),(

,2**

,),(

,1 =+

(3.9)

**,

),(,2

******,

),(,1 ,...,1;* r

rbij

Ajij

rb

rb

rb

rb

rb

rbij

Ajij bbRrShptulTSh

rr

=++++

donde:

( ) ( ) ( )( )

+++=

g r rAa Aji Nobaba

raobaba

roababa

raba

raail

rbij

rb UUBUUYUUZUXwSl

),(

21,

2,

11,

1,,

11,

1,

1,

',, 111

( ) ( ) ( )( )

+++

+++=

g r rAa Aji Nobaba

raobaba

roababa

raba

raaju

rbij

rb UUBUUYUUZUXwSu

),(

21,

2,

11,

1,,

11,

1,

1,

',, 111

1;Aa 1;1

;Aa 1;1g2

1,1

1,

g21,

11,

======

++

bUU

bbUU

baba

rbaba

(3.10)

( ) scrbrbrrbrb TputlT b ++++ { } { } { } 1;1;,..,1;,..,1 ;, ,,,, == s cas cojsaor bar bioraosrsr USBUSYNNobcbbRsr

(3.11)

{ }( )( ) ( )[ ] ( )( )[ ]

r

Avii

scij

sc

rbiv

rb

rb

rbiv

rb

scij

sc

Aji sRr

aaRs

mSTSlTHSTSTHrs

,..,1;*

) 1-( ),(

*,

*,,

*,

*

, *

=+

(3.12)

1raX ; 1raZ ; 1raoY ; 1raoB ; 11, baU ; 12, baU ; 1, r aijS { } ),(; ;,..,1; ; rrrg AjiNo bbAaRr =

(3.13)

La ecuacin (3.5) hace referencia a que el transporte de la carga o tarea aAg por la ruta rR slo puede ser realizada con una estrategia de envo directo ( raX =1), con estrategia de



paradas mltiples ( raZ, =1) o con estrategia de envo a hub utilizando dos rutas r,s R

( 1;1 == saorao BY ). La ecuacin (3.6) se exige para garantizar que no existe ningn arco de una ruta por el que no se transporte mercanca (no se permiten los desplazamientos sin carga durante la jornada laboral). Por su lado, la ecuacin (3.7) pretende reproducir la condicin que en el servicio de dos arcos correlativos de una ruta debe existir un nodo comn. La restriccin de capacidad de los vehculos se establece en la desigualdad (3.8), donde se consideran conjuntamente las cargas de envos directos, paradas mltiples y envos hubs para un mismo arco b=1,,br de la ruta rR . Por otro lado, las restricciones (3.9), (3.10) y (3.11) hacen referencia a las restricciones temporales del problema. En el cubrimiento del arco b=1,..,br de la ruta rR que corresponde al transporte entre dos puntos i,jNr que se visitan consecutivamente (i,j) Ar, la ecuacin (3.9) exige que el tiempo de ocupacin para la efectuar la carga de mercanca en la delegacin i est dentro de la ventana temporal (h1i; h2i). Bajo estas condiciones, en la ecuacin (3.10) se obliga a que el tiempo de ocupacin para la descarga de mercanca en la delegacin j siendo transportada desde el punto i debe verificar la ventana temporal admisible de la delegacin. En el caso de mercancas en transferencia en una terminal oNr, la restriccin temporal (3.11) obliga a que la descarga de mercanca de un vehculo de la ruta r en el hub o (r: ruta entrante al hub) se realice previamente a la carga a la ruta s (s: ruta saliente al hub). Finalmente, la ecuacin (3.12) hace referencia a que el nmero de vehculos que estn en la delegacin durante la carga y descarga de la mercanca sea inferior o igual al nmero total de muelles mi para efectuar la distribucin, siendo H() la funcin escaln de Heaviside que tiene como expresin la ecuacin (3.14). Las restricciones determinadas en la ecuacin (3.13) definen el rango de variacin de las variables enteras de decisin del modelo.

=

a x0a x1

)( axH (3.14)



3.3. DESCOMPOSICIN DEL PROBLEMA La resolucin del problema implica la consideracin de un alto nmero de soluciones posibles y constituye un problema de optimizacin combinatoria. Tal y como ya se ha avanzado, el problema de optimizacin combinatoria anteriormente descrito es NP-Hard. Este hecho implica que el tiempo de computacin para resolverlo es superior a cualquier polinomio del tamao del problema (NT), hecho que supone una dificultad computacional muy elevada. Con la finalidad de simplificar su resolucin, se propone la descomposicin del problema Z1 de asignacin de flujos a las rutas en un problema de identificacin de las rutas directas entre delegaciones con vehculo a carga completa (P1) y el problema de envos entre delegaciones a carga inferior a capacidad (Less than TruckLoad, LTL) con estrategias a paradas mltiples en origen o destino, envos directos con carga inferior a la capacidad y la posibilidad que la mercanca realice una transferencia de vehculo en una terminal hub (P2). Dado el conjunto de tareas de puntos a visitar a carga completa, el problema (P1) en cuestin se reconoce como un problema de scheduling puro ya que el nico factor a tener en cuenta es la asignacin de tareas (trayectos asociados a las demandas de carga) a recursos (vehculos) para poder satisfacer las restricciones temporales del problema. Debido que la ocupacin del vehculo siempre es mxima, no existen posibilidades de transporte mltiple de mercanca asociada a distintos pares de puntos, por lo que la componente de ruteo no es el factor determinante del coste. Adicionalmente, la estrategia hubbing no tiene ningn sentido ya que no se puede consolidar ms mercanca en el trayecto de un vehculo ya que este siempre se realiza a mxima ocupacin. Sin embargo, la resolucin del problema P2 admite y se beneficia de la aplicacin de todas las estrategias de envo existentes, por lo que el orden de visita de los puntos en una misma ruta puede influir en la optimizacin de la ocupacin de la carga del vehculo. A partir de las ecuaciones (3.2) y (3.3), la carga total Wij a transportar entre dos puntos i,jN se puede descomponer en (nij -1) envos o tareas a carga completa kija k=1,..,nij-1 y un solo envo o tarea ijnija con carga inferior a la capacidad segn la expresin (3.15).

=

==ij

ij

nk si

)1(n 1,...,k si

CnWC

wijij

kij (3.15)

El reparto de las fracciones de la carga Wij segn los valores de la ecuacin (3.15) con un servicio exclusivo de envos directos a carga completa permite simplificar la funcin



objetivo del problema P1 a la ecuacin (3.16). Las restricciones asociadas a este problema tambin sufren una simplificacin significativa y se caracterizan por las expresiones (3.17-3.19) y las expresiones definidas para el problema Z1 (3.7), (3.9), (3.10) y (3.12).

( )

+

==

+++=

Rr

b

bp

b

b Ni Nj

rbij

rbwijd

rr

r r

cSpcDcF Min1

11,P1 (3.16)

rAa 1)( = Rr

raX (3.17)

( ) 11,* =

gAaba

ra UX 1,...,1 ;* = rbbRr (3.18)

1raX ; 11, baU ; 1, r aijS { } ),( ;,..,1; ; rrg Aji bbAaRr = (3.19)

En el caso de la restriccin (3.10), las variables rbl y rbu se simplifican con las expresiones

(3.20) y (3.21): ( )

=

g rAa Ajiba

raail

rbij

rb UXwSl

),(

1,

',, 1,...,1 ;* = rbbRr (3.20)

( )

=g rAa Aji

baraaju

rbij

rb UXwSu

),(

1,

',, 1,...,1 ;* = rbbRr (3.21)

En este caso, las variables de decisin de las estrategias de envo del problema se reducen a

raX que toma un valor igual a 1 cuando la tarea a=

kija , k=1,..,nij-1 es enviada por la ruta r y

0 en caso contrario.

Con todo, si se define AC como el conjunto de tareas o cargas cuyo volumen asociado kijw es

igual a la capacidad C, la resolucin se basar en la asignacin de estos envos o tareas a un conjunto de rutas Rc que determinarn la solucin del problema. Cada ruta r estar compuesta por un conjunto rCA de pares de puntos (i,j)N con tareas asociadas kija servidas con estrategia directa. De este modo, tambin se construir un conjunto de nodos

(delegaciones) rCN que forman el esqueleto de la ruta r. La resolucin para el problema P2

se realizar considerando la formulacin matemtica general, con todas las restricciones y las variables de decisin propias de estrategias de envos directos, hub y de paradas mltiples detalladas en las expresiones (3.4)- (3.14).

05MER_Capitol3

Documents

Transcript of 05MER_Capitol3