Hay tres enfoques diferentes principales para modelar las formulaciones de flujo del vehículo VRP

1. : utiliza variables enteras asociadas con cada arco que cuentan el número de veces que un vehículo atraviesa el borde. Se utiliza generalmente para VRPs básicos. Esto es bueno para los casos en los que el costo de la solución se puede expresar como la suma de los costos asociados con los arcos. Sin embargo, no se puede usar para manejar muchas aplicaciones prácticas.
2. Formulaciones de flujo de productos básicos: se asocian variables enteras adicionales con los arcos o bordes que representan el flujo de productos básicos a lo largo de las rutas recorridas por los vehículos. Esto solo se ha utilizado recientemente para encontrar una solución exacta.
3. Problema de partición de conjuntos: Estos tienen un número exponencial de variables binarias que están asociadas a un circuito factible diferente. El VRP se formula entonces como un problema de partición establecido que pregunta cuál es la colección de circuitos con un costo mínimo que satisface las restricciones VRP. Esto permite costos de ruta muy generales.

Vehículo de flujo formulationsEdit

La formulación de la TSP por Dantzig, Fulkerson y Johnson fue extendida para crear los dos índice vehículo de flujo de las formulaciones para el VRP

min ∑ i ∈ V ∑ j ∈ V c i j x i j {\displaystyle {\text{min}}\sum _{i\in V}\sum _{j\in V}c_{ij}x_{ij}}

objeto

∑ i ∈ V x i j = 1 ∀ j ∈ V ∖ { 0 } {\displaystyle \sum _{i\in V}x_{ij}=1\quad \forall j\in V\backslash \left\{0\right\}}

(1)

∑ j ∈ V x i j = 1 ∀ i ∈ V ∖ { 0 } {\displaystyle \sum _{j\in V}x_{ij}=1\quad \forall i\in V\backslash \left\{0\right\}}

(2)

∑ i ∈ V x i 0 = K {\displaystyle \sum _{i\in V}x_{i0}=K}

(3)

∑ j ∈ V x 0 j = K {\displaystyle \sum _{j\in V}x_{0j}=K}

(4)

∑ i ∉ S ∑ j ∈ S x i j ≥ r ( S ) , ∀ S ⊆ V ∖ { 0 } , S ≠ ∅ {\displaystyle \sum _{i\notin S}\sum _{j\in S}x_{ij}\geq r(S),~~\forall S\subseteq V\setminus \{0\},S\neq \emptyset }

(5)

x i j ∈ { 0 , 1 } ∀ i , j ∈ V {\displaystyle x_{ij}\in \{0,1\}\quad \forall i,j\in V}

(6)

In this formulation c i j {\displaystyle c_{ij}}

represents the cost of going from node i {\displaystyle i}

to node j {\displaystyle j}

, x i j {\displaystyle x_{ij}}

is a binary variable that has value 1 {\displaystyle 1}

if the arc going from i {\displaystyle i}

a j {\displaystyle j}

se considera como parte de la solución y 0 {\displaystyle 0}

en caso contrario, K {\displaystyle K}

es el número de vehículos disponibles y r ( S ) {\displaystyle r(S)}

corresponde al mínimo el número de vehículos necesarios para servir conjunto S {\displaystyle S}

. También estamos suponiendo que 0 {\displaystyle 0}

es el depósito de nodo. Las restricciones

1 y 2 indican que entra exactamente un arco y sale exactamente uno de cada vértice asociado a un cliente, respectivamente. Las restricciones 3 y 4 dicen que el número de vehículos que salen del depósito es el mismo que el número que entra. Las restricciones 5 son las restricciones de reducción de capacidad, que imponen que las rutas deben estar conectadas y que la demanda en cada ruta no debe exceder la capacidad del vehículo. Por último, las restricciones 6 son las restricciones de integralidad.

Una restricción arbitraria entre el 2 | V | {\displaystyle 2|V|}

restricciones es en realidad implícita por el resto 2 | V | − 1 {\displaystyle 2|V|-1}

así se la puede quitar. Cada corte se define por un cliente en el conjunto S {\displaystyle S}

está atravesada por una serie de arcos no menor que r ( s ) {\displaystyle r(s)}

(mínimo número de vehículos necesarios para servir conjunto S {\displaystyle S}

).

Se puede obtener una formulación alternativa transformando las restricciones de corte de capacidad en restricciones de eliminación de suburbano generalizadas (GSEC).

∑ i ∈ S ∑ j ∈ S x i j ≤ | S | − r ( s ) {\displaystyle \sum _{i\in S}\sum _{j\in S}x_{ij}\leq |S|-r(s)}

lo que impone que al menos r ( s ) {\displaystyle r(s)}

arcos dejar a cada cliente establezca S {\displaystyle S}

.

Los CCCG y los CCC tienen un número exponencial de restricciones, por lo que es prácticamente imposible resolver la relajación lineal. Una forma posible de resolver esto es considerar un subconjunto limitado de estas restricciones y agregar el resto si es necesario.

Un método diferente nuevamente es usar una familia de restricciones que tienen una cardinalidad polinómica que se conocen como restricciones MTZ, que primero fueron propuestas para el TSP y posteriormente extendidas por Christofides, Mingozzi y Toth.

u j − u i ≥ d j − C ( 1 − x i j ) ∀ i , j ∈ V ∖ { 0 } , i ≠ j s.t. d i + d j ≤ C {\displaystyle u_{j}-u_{i}\geq d_{j}-C(1-x_{ij})~~~~~~\forall (i,j\V\barra invertida \{0\},i\neq j~~~~{\text{s.t. }}d_{i}+d_{j}\leq C}

0 ≤ i ≤ C − d i ∀ i ∈ V ∖ { 0 } {\displaystyle 0\leq u_{i}\leq C-d_{i}~~~~~~\forall i\V\barra invertida \{0\}}

donde u i , i ∈ V ∖ { 0 } {\displaystyle u_{i},~i\V\barra invertida \{0\}}

es una variable continua que representa la carga de la izquierda en el vehículo después de visitar al cliente i {\displaystyle i}

y d i {\displaystyle d_{i}}

es la demanda del cliente i {\displaystyle i}

. Estos requisitos imponen tanto la conectividad como la capacidad. Cuando x i j = 0 {\displaystyle x_{ij}=0}

restricción, a continuación, i {\displaystyle i}

no es vinculante desde u i ≤ C {\displaystyle u_{i}\leq C}

y u j ≥ d j {\displaystyle u_{j}\geq d_{j}}

mientras que x i j = 1 {\displaystyle x_{ij}=1}

imponen que u j ≥ u i + d j {\displaystyle u_{j}\geq u_{i}+d_{j}}

.

Estos se han utilizado ampliamente para modelar el VRP básico (CVRP) y el VRPB. Sin embargo, su poder se limita a estos problemas simples. Solo se pueden usar cuando el costo de la solución se puede expresar como la suma de los costos de los costos de arco. Tampoco podemos saber qué vehículo atraviesa cada arco. Por lo tanto, no podemos usar esto para modelos más complejos donde el costo y / o la viabilidad dependen del pedido de los clientes o de los vehículos utilizados.

Enrutamiento óptimo manual versus automáticoeditar

Hay muchos métodos para resolver problemas de enrutamiento de vehículos manualmente. Por ejemplo, el enrutamiento óptimo es un gran problema de eficiencia para carretillas elevadoras en grandes almacenes. Algunos de los métodos manuales para decidir la ruta más eficiente son: Mayor espacio, forma de S, Pasillo por pasillo, Combinado y Combinado +. Mientras Combinado + método es el más complejo, por lo tanto el más difícil de ser utilizado por los operadores de carretilla elevadora, es el más eficiente método de enrutamiento. Sin embargo, la diferencia porcentual entre el método de enrutamiento óptimo manual y la ruta óptima real fue en promedio del 13%.