Salut a tous!
S'il vous plait aidez-moi !!
Je suis un étudiant en mastère, je suis débutant en programmation, en effet je travaille sur les méthodes d'optimisation en recherche opérationnelle, plus précisément les méta-heuristiques.
Dans ce qui suit mon programme que j'ai écrits en langage C, qui vise à rechercher une solution qui va être utilisée par la suite comme une solution initiale (algorithme de greedy). Je vais essayer d'être bref pour expliquer qu'est ce que je veux faire exactement.
On a des coordonnes des points qui sont stockes dans un fichier de type TXT, j'ai calcule la distance euclidienne pour avoir une matrice, le but maintenant c'est de trouve une route pour chaque véhicule celle-ci a une capacité limite (Qmax) qui doit être respecte et une distance a parcourus limitée (Dmax) aussi. Chaque client est visité une seule fois et par une seule véhicule.
P.S. : le nombre de voiture est limitée, l'essentiel c' visite tout les clients
Chaque voiture doit débuter de l'entrepôt (vertex 0) et retourne à l'entrepôt a la fin de son trajet.
Voila mon programme il marche mais les résultats sont faux.
Voici les données:
V0 0.0000 0.0000 0.0
V1 30.0000 0.0000 10.0
V2 29.6306 40.6930 30.0
V3 28.5317 90.2705 30.0
V4 6.7302 13.6197 10.0
V5 24.2705 17.6336 10.0
V6 11.2132 1.2132 30.0
Veuillez copiez ces donnes dans un fichier de type TXT et entrez l'adresse dans la fonction « getting data from txt file »
Le problème se localise dans la fonction greedy_algorithm pour les autres se marche normalement.
Pour ces donnes le résultat doit être 4 routes :
Route [0] : 0-6-0
Route [0] : 0-4-5-1-0
Route [0] : 0-2-0
Route [0] : 0-3-0
Aidez-moi s'il vous plait !! Merci d'avance à ceux qui prendront la peine d'essayer de coder ou de lire le message.
LE PROGRAMME:
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
/************Global Variables************/
#define vertices 7 // Number of Customers
#define Qmax 30 //Vehicle Capacity
#define Dmax 100 //Maximum Distance Covered by Each Vehicle
struct data
{
char label[15];
float x;
float y;
float q;
} tab [500];
/************Getting Data from TXT_FILE************/
int get_data ()
{
FILE *input;
char s[80];
int i,n;
input = fopen("C:\\Users\\User\\Desktop\\TEST_FILE.txt","r"); // veuillez entrez l'adresse ou se localise le fichier de donnees
if((input)!= NULL)
printf("File Opened Successfully\n");
else
printf("ERROR OCCURRED...File Failed to be Opened!\n");
n=0;
while (fgets(s,80,input))
{
sscanf (s,"%s%f%f%f", tab[n].label, &tab[n].x, &tab[n].y, &tab[n].q);
n++ ;
}
for (i= 0 ; i <n ; i++)
printf ("\n%s %3.4f %3.4f %2.0f", tab[i].label, tab[i].x, tab[i].y, tab[i].q);
return (n);
}
/*****************dynamic allocation for Matrix **********/
float** allocate(int N, int M)
{
int i;
float **A = NULL;
//we allocate memory for N row, it's row pointer
A = (float**) malloc( sizeof(float*) * N );
// if allocation succeed we allocate for M column
if( A != NULL )
for( i=0; i<N; i++ )
A[i] = (float*) malloc( sizeof(float) * M );
if (A == NULL)
{
puts("\nFailure to allocate room for pointers");
exit(0);
}
return A;
}
/*************Deallocate Matrix (Free Memory)*******************/
void deallocate( float **A, int N )
{
int i;
//free each row
for( i=0; i<N; i++ )
free( A[i] );
free( A );
}
/**********display a table**********/
void display_table( float *vector, int taille )
{
int i;
for( i=0; i<taille; i++ )
printf("[%d] %f\t", i, vector[i]);
}
/******* display a matrix *******8*/
void display_matrix( float **A, int N, int M)
{
int i, j;
for(i=0; i<N; i++)
{
for(j=0; j<M; j++)
printf(" %f ", A[i][j]);
printf("\n");
}
}
/************compute the Euclidean Distance************/
float** euclidian_distance (float *row, float *column, int t)
{
int i,j;
float **matrix;
float xd=0,yd=0;
matrix = allocate(vertices, vertices);
printf("\n\nThe Matrix of Distance is:\n");
for(i=0;i<t;i++)
{
for(j=0;j<t;j++)
{
xd=tab[i].x-tab[j].x;
yd=tab[i].y-tab[j].y;
matrix[i][j]=sqrt((xd*xd)+(yd*yd));
}
}
return (matrix);
}
/**************************search value minimum in matrix*****************************/
float search_value(float **mat, int t, int indice)
{
float MIN=1000;// each time initialize TEMP to 99.9
int j;
for(j=1;j<t;j++)
{
if((mat[indice][j]<MIN)&&(mat[indice][j]!=0))
MIN=mat[indice][j]; // assign the value to TEMP
}
return (MIN);
}
/**************************search its indice in matrix*****************************/
int search_indice(float **mat, int t, int indice)
{
float MIN=1000;// initialize MIN each time
int j,y;
for(j=1;j<t;j++)
{
if((mat[indice][j]<MIN)&&(mat[indice][j]!=0))
{
MIN=mat[indice][j]; // assign the value to MIN
y=j;
}
}
return (y);
}
/************Construction of Initial Solutions Using Greedy Algorithm************/
void greedy_algo (float **mat, int t )
{
float **dist, **qte ;
float MIN;
int c,i,j,z,k,w,col,x,y;
float *D,*Q;
int *indice;
float *sequence;
//float **ptr1, *ptr2;
dist = allocate(sizeof (k) , vertices);
qte = allocate(sizeof (k) , vertices);
sequence = (float*) malloc (vertices *sizeof (float));
indice = (int*) malloc (vertices *sizeof(int));
Q = (float*) malloc(sizeof (k) * sizeof(float) );
D = (float*) malloc( sizeof (k) * sizeof(float) );
//initialize table
for(i=0;i<t;i++)
{
Q[i]=0;
D[i]=0;
}
i=0; //initialize row to 0
j=0;
for(x=0;x<t;x++)
{
for(y=1;y<t;y++)
{
while (mat[x][y]!=0)//repeat till the matrix is equal to 0 except column 1
{
MIN=search_value(mat,t,i); //printf("\n%f\n",MIN);
sequence[j]=MIN;
i=search_indice(mat,t,i); //printf("\n%d\n",i);
indice[j]=i;
for(z=0;z<t;z++)
{
mat[z][i]=0;// transform the whole column to inorder to avoid return to same point
}
j++;
}
}
}
printf("\n");
display_table(sequence,t-1);
puts("\n");
for(k=0;k<t-1;k++)
printf("[%d] %d\t",k,indice[k]);
k=0; //initialize the first route
col=0;
w=0;
for(c=0;c<t-1;c++)
{
dist[k][col]=sequence[c]; //printf(" %f\t",dist[k][col]);
qte[k][col]=tab[indice[c]].q; //printf(" %f\t",qte[k][col]);
Q[k]+=qte[k][col];
D[k]+=dist[k][col]+mat[indice[c]][0];
if((Q[k]>=Qmax)||(D[k]>=Dmax))
{
k++;//goto next road
col=-1;
if(c<t-2)
{
c++;
D[k]+=mat[indice[c]][0];//start from the depot
c--;
}
}
else
D[k]-=mat[indice[c]][0];
if (c==t-2)
D[k]+=mat[indice[c]][0];
col++;
}
printf("\n\nmatrice of distance\n");
display_matrix(dist,k, c);
printf("Total of Distance of road\n");
display_table( D, k );
printf("\n\nmatrice of quantity\n");
display_matrix(qte,k,c);
printf("Total quantity of road\n");
display_table( Q, k );
printf("\n");
display_matrix(mat,t,t);
}
/**************************Principal Program****************************************/
void main (void)
{
int n;
FILE *fp;
float **distance_matrix;
distance_matrix = allocate(vertices, vertices);
fp=fopen("C:\\Users\\Mohamed Anis TRIGUI\\Desktop\\RESULT_FILE_TEST.txt","w");
n=get_data();
distance_matrix =euclidian_distance(&tab[100].x, &tab[100].y, vertices);
display_matrix(distance_matrix,vertices,vertices);
greedy_algo(distance_matrix, vertices);
}