4.2 Formulation du
problème :
Le problème du « car-sequencing »
peut être formulé à l'aide de la programmation
linéaire en nombre entier PLNE.
La notation suivante sera utilisée pour
présenter cette formulation :
Paramètre :
n:nombre total des voitures.
p : La position d'une voiture peut
être changée au maximum p positions
avant sa position initiale jusqu'à p positions après sa position
initiale .Supposons que la position initiale d'une voiture est i alors cette
voiture peut place dans les position [i-p,i+p]
Fi : une
fonction qui nous informe sur la couleur de la
voiture numéro i.
Indice :
k: indice de la position de la voiture dans
la séquence. k=1...n
i, j : indice du numéro de la voiture.
i=1...n , j=1...n
Variables de décision :
xik: variable binaire qui prend la
valeur 1si seulement si la position k dans la séquence est
occupée par la voiture numéro i et 0 si autrement :
Xik 1 si la position k est
occupée par la voiture n° i .
0 autrement.
Cij : une variable binaire
qui prend la valeur 1 si deux voitures adjacentes i et j ont une couleur
différente.
0 si non
Cij 1 si la couleur de la voiture i est
différente de la couleur de la
voiture j et  .
0 autrement .
Avec l: la position de la voiture
numéro i.
k : la position de la
voiture numéro j.
En utilisant cette notation le problème peut être
formulé comme suit :
Min z = (1)
S /c   k=1 ....n (2)
  i= 1....n (3)
 =1  i=1....n (4)
Cii = 0
 i=1 ...n (5)
xil +xjk -cij= 1
 i? j / Fi? Fj et |l-k| =1  i, j, l, k = 1...n (6)
Cij  {0,1}  i=1...n , j=1...n (7)
Xik  {0,1}  k=1 ...n (8)
Dans cette formulation, l'objectif (1) est la minimisation
du changement du couleur des voitures.
La contrainte (2) impose qu'une seule voiture i doit
être placée dans une seule position k.
La contrainte (3) impose qu'une seule position k doit
être occupée par une seule voiture i.
La contrainte (4) impose que chaque voiture peut être
placée p positions avant sa position initiale jusqu'à p positions
après sa position initiale.
La contrainte (5) affirme que chaque même voiture a la
même couleur.
La contrainte(6) indique que les deux voitures adjacentes ne
doivent pas avoir la même couleur.
| 
