Il existe trois approches principales différentes pour modéliser les formulations de flux du véhicule VRP

1. — cela utilise des variables entières associées à chaque arc qui comptent le nombre de fois où le bord est traversé par un véhicule. Il est généralement utilisé pour les VRP de base. C’est bon pour les cas où le coût de la solution peut être exprimé comme la somme de tous les coûts associés aux arcs. Cependant, il ne peut pas être utilisé pour gérer de nombreuses applications pratiques.
2. Formulations de flux de marchandises — des variables entières supplémentaires sont associées aux arcs ou aux arêtes qui représentent le flux de marchandises le long des chemins parcourus par les véhicules. Cela n’a été utilisé que récemment pour trouver une solution exacte.
3. Définir le problème de partitionnement — Ceux-ci ont un nombre exponentiel de variables binaires qui sont chacune associées à un circuit réalisable différent. Le VRP est alors plutôt formulé comme un problème de partitionnement défini qui demande quelle est la collection de circuits à coût minimum qui satisfont aux contraintes VRP. Cela permet des coûts d’itinéraire très généraux.

formulationsEdit

La formulation du TSP par Dantzig, Fulkerson et Johnson a été étendue pour créer les deux formulations de flux de véhicules d’indice pour le 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}}

sous réserve de

∈ 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}

à j {\displaystyle j}

est considéré comme faisant partie de la solution et 0 {\displaystyle 0}

sinon, K { \displaystyle K}

est le nombre de véhicules disponibles et r(S) {\displaystyle r(S)}

correspond au nombre minimum de véhicules nécessaires pour desservir l’ensemble S {\displaystyle S}

. Nous supposons également que 0 {\displaystyle 0}

est le nœud de dépôt.

Les contraintes 1 et 2 indiquent qu’exactement un arc entre et exactement un sort de chaque sommet associé à un client, respectivement. Les contraintes 3 et 4 indiquent que le nombre de véhicules sortant du dépôt est le même que le nombre entrant. Les contraintes 5 sont les contraintes de réduction de capacité, qui imposent que les itinéraires doivent être connectés et que la demande sur chaque itinéraire ne doit pas dépasser la capacité du véhicule. Enfin, les contraintes 6 sont les contraintes d’intégralité.

Une contrainte arbitraire parmi les contraintes 2|V|{\displaystyle 2|V|}

est en fait implicite par les contraintes 2|V|−1 restantes {\displaystyle 2|V|-1}

pour qu’il puisse être supprimé. Chaque coupe définie par un ensemble client S {\displaystyle S}

est traversée par un nombre d’arcs non inférieur à r(s) {\displaystyle r(s)}

(nombre minimum de véhicules nécessaires pour desservir l’ensemble S { \displaystyle S}

).

Une formulation alternative peut être obtenue en transformant les contraintes de réduction de capacité en contraintes d’élimination généralisée des sous-ressources (GSECS).

∈ 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)}

qui impose qu’au moins r(s) {\displaystyle r(s)}

les arcs quittent chaque ensemble client S {\displaystyle S}

.

Les CCC et les CCC ont un nombre exponentiel de contraintes, il est donc pratiquement impossible de résoudre la relaxation linéaire. Un moyen possible de résoudre ce problème est de considérer un sous-ensemble limité de ces contraintes et d’ajouter le reste si nécessaire.

Une autre méthode consiste encore à utiliser une famille de contraintes qui ont une cardinalité polynomiale qui sont connues sous le nom de contraintes MTZ, elles ont d’abord été proposées pour le TSP et ensuite étendues par Christofides, Mingozzi et Toth.

u j-u i ≥ d j-C (1−x i j) ∀ {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\in V\ barre oblique inverse \ {0\}, i\neq j ~~~ ~ {\text {s.t. }}d_{i}+d_{j}\leq C}

0 ≤ u i ≤ C−d i ∈ i ∈ V { {0} {\displaystyle 0 \leq u_ {i}\leq C-d_ {i} ~~ ~ ~ ~ \ forall i \ in V \barre oblique inverse \{0\}}

où u i, i ∈ V { {0} {\displaystyle u_{i}, ~i\ dans V\barre oblique inverse\{0\}}

est une variable continue supplémentaire qui représente la charge laissée dans le véhicule après avoir visité le client i {\displaystyle i}

et d i {\displaystyle d_{i}}

est la demande du client i {\displaystyle i}

. Ceux-ci imposent à la fois les exigences de connectivité et de capacité. Lorsque x i j = 0 {\displaystyle x_{ij} = 0}

contrainte alors i {\displaystyle i}

n’est pas contraignant ‘ puisque u i ≤ C {\displaystyle u_ {i}\leq C}

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

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

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

.

Ils ont été largement utilisés pour modéliser le VRP de base (CVRP) et le VRPB. Cependant, leur pouvoir est limité à ces problèmes simples. Ils ne peuvent être utilisés que lorsque le coût de la solution peut être exprimé comme la somme des coûts des coûts de l’arc. Nous ne pouvons pas non plus savoir quel véhicule traverse chaque arc. Nous ne pouvons donc pas l’utiliser pour des modèles plus complexes où le coût et / ou la faisabilité dépendent de la commande des clients ou des véhicules utilisés.

Routing manuel ou automatique optimum

Il existe de nombreuses méthodes pour résoudre manuellement les problèmes de routage du véhicule. Par exemple, le routage optimal est un gros problème d’efficacité pour les chariots élévateurs dans les grands entrepôts. Certaines des méthodes manuelles pour décider de l’itinéraire le plus efficace sont: Le plus grand écart, la forme en S, Allée par allée, Combiné et Combiné +. Bien que la méthode combinée + soit la plus complexe, donc la plus difficile à utiliser par les opérateurs de chariots élévateurs, c’est la méthode de routage la plus efficace. Pourtant, la différence en pourcentage entre la méthode de routage optimale manuelle et la route optimale réelle était en moyenne de 13%.