#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2013
    Posts
    2
    Rep Power
    0

    Post Programmation optimiser C++


    Bonjour,
    je suis en train de coder un problème de tournées de véhicules avec fenêtres de temps avec C++(opérations de collectes des marchandises au prés des fournisseurs et les regrouper au niveau du dépôt). Ma solution initiale consiste a déterminer l'ensemble des tournées selon les contraintes de capacités et temporelles sachant que la fonction objectif de ma problème consiste a minimiser le temps de parcours.
    j'ai déjà essayé de coder cette solution initiale ( tout en calculant le matrice de distance et le matrice des temps parcourus entre les fournisseurs eux même d'une part et les fournisseurs et le dépôt d'autre part, pour calculer la distance et le temps parcouru d'une tournée) Ainsi pour une retard ou avancement de collecte, tout en comparant avec la fenêtre de temps de chaque fournisseurs,on accordant une valeur de pénalité.
    Bon mon problème est tout ce travail doivent être formulé dans une fonction qui doit retourner les données sans faire des affichages "printf" au sein de la fonction et pour bien expliqué je veux que cette fonction retourner une expression de ce type la: "return S.eval+S.pen*pen" (avec pen=pénalité et eval et le nom de la fonction) et puisque je ne maîtrise pas les structures. Pouvez vous m'aidez pour incorporer les structures dans mon code.
    mon code est:
    void cumul(int *S)
    {
    int aux,aux1,aux2,aux3;

    perm(S,m);

    cum[0]=dem[0];
    for(i=1;i<=m;i++)
    {

    if(cum[i-1]+dem[i]<=cc)
    {
    cum[i]=cum[i-1]+dem[i];

    }
    else
    {
    aux=id[i];
    id[i]=id[i+1];
    id[i+1]=aux;
    aux1=dem[i];
    dem[i]=dem[i+1];
    dem[i+1]=aux1;
    aux2=x_tp[i];
    x_tp[i]=x_tp[i+1];
    x_tp[i+1]=aux2;
    aux3=y_tp[i];
    y_tp[i]=y_tp[i+1];
    y_tp[i+1]=aux3;
    cum[i]=cum[i-1]+dem[i];

    }
    if(cum[i]>cc)
    {
    cum[i]=dem[i];
    }
    }

    }


    void initial_tour(int *S)
    {
    int nbt=1,tw=0,val=10,pen=10,v_pen;
    tr=new int[m];
    float dis=0;
    cum[0]= dem[0];tr[0]=1;
    int j=1;
    for (i=1;i<=m;i++)
    {

    if(cum[i-1]+dem[S[i]]<=cc)
    {
    tr[i]=j;
    }
    else
    {
    tr[i]=j+1;nbt++;
    j++;
    }
    //printf("%d\t %d\t %d\t %d\t %d\t %d\t %d\n",i,id[S[i]],dem[i],cum[i],tr[i],x_tp[i],y_tp[i]);

    }
    int t=1,*dt_liv,*k=new int[nbt];
    dt_liv=new int [m];
    dt_liv[0]=320;
    int diff;
    affichage(id);
    printf("\n\n");
    printf("************************distance && temps pour chaque tour************************\n");
    printf("tour\t distance\t temps\n");
    for(i=1;i<=m+1;i++)
    {
    if(tr[i]==tr[i-1])
    {

    //printf(" %d,%d ",id[S[i-1]],id[S[i]]);
    dt_liv[i]=dt_liv[i-1]+tw_cc[id[S[i-1]]][id[S[i]]];
    //printf("-----%d\t %d\t %d \n\n",tw_cc[id[S[i-1]]][id[S[i]]],x_tp[i-1],y_tp[i-1]);printf("****%d\n",dt_liv[i]);

    dis+=dis_cc[id[S[i-1]]][id[S[i]]];
    tw+=tw_cc[id[S[i-1]]][id[S[i]]];


    }
    else
    {
    //printf("----%d\n",cum[S[i-1]]);
    tw+=cum[S[i-1]];
    tw+=val;
    dt_liv[i]=dt_liv[i-1]+tw_cc[id[S[i-1]]][id[S[0]]];
    //printf(" %d,%d ",id[S[i-1]],id[S[0]]);
    //printf("-----%d\t %d\t %d\n\n",tw_cc[id[S[i-1]]][id[S[0]]],x_tp[i-1],y_tp[i-1]);printf("****%d\n",dt_liv[i]);

    dis+=dis_cc[id[S[i-1]]][id[S[0]]];
    tw+=tw_cc[id[S[i-1]]][id[S[0]]];

    /*printf("-----------tour %d-----------",t);
    printf("%f \t %d\n",dis,tw);printf("\n");*/
    k[i]=t;printf("%d\t %f\t %d\n",k[i],dis,tw);
    t++;
    dis=0;tw=0;dt_liv[i-1]=320;
    dt_liv[i]=dt_liv[i-1]+tw_cc[id[S[0]]][id[S[i]]];
    /*printf(" %d,%d ",id[S[0]],id[S[i]]);
    printf("-----%d\t %d\t %d\n\n",tw_cc[id[S[0]]][id[S[i]]],x_tp[0],y_tp[0]);printf("****%d\n",dt_liv[i]);*/

    dis+=dis_cc[id[S[0]]][id[S[i]]];
    tw+=tw_cc[id[S[0]]][id[S[i]]];

    }
    if(dt_liv[i]>y_tp[i])
    {
    diff=dt_liv[i]-y_tp[i];
    //printf("^^^^^%d\n",diff);
    v_pen=pen*diff;
    //printf("_____%d\n",v_pen);
    tw+=v_pen;
    }
    else
    {
    diff=0;
    }


    }

    }

    int eval(int *S)
    {int nbt=1;

    cumul(S);
    initial_tour(S);
    for(i=1;i<=m;i++)if(tr[i]!=tr[i-1]){nbt++;}

    return nbt;
    }
    s'il vous paît j'ai besoin d'aide
    merci.
  2. #2
  3. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,117
    Rep Power
    1803
    It is hard to suggest and answer since the code is incomplete - there are no declarations for any of the array variables you use for example - structures are about data, and you have omitted nearly all the useful information about the data.

    Moreover, all your variable names are tersely names and probably abbreviations of french, so it is difficult for an English speaker (or even a French speaker too perhaps?) to perhaps follow your code.

    However I notice that you have many separate arrays all indexed in the same way. I suggest at least that you collate these data represented in these separate arrays in a single structure and then have a single array of that structure. For example:

    Il est difficile de proposer et de répondre puisque le code est incomplet - il n'y a pas de déclarations pour l'une des variables de tableau que vous utilisez, par exemple - sont sur ​​les structures de données, et que vous avez omis de près toutes les informations utiles sur les données.

    En outre, tous les noms des variables sont laconiquement noms et probablement abréviations de français, de sorte qu'il est difficile pour un anglophone (ou même un haut-parleur français trop peut-être?) À suivre peut-être de votre code.

    Cependant, je constate que vous avez beaucoup de tableaux distincts tous indexés de la même manière. Je suggère au moins que vous rassembler ces données représentées dans ces tableaux distincts en une structure unique et avoir un seul réseau de cette structure. Par exemple:

    C++ Code:
     
    struct myStruct
    {
        int a ;
        int b ;
        int c ;
    } ;
     
     
    myStruct data = new myStruct[m] ;
     
    int x = data[i].a + data[i].b + data[i].c


    All that said, this is C++ - you'd do better to use classes and an OOP design rather than simple structures.

    Tout cela étant dit, il s'agit de C++ - vous feriez mieux d'utiliser des classes et une conception de la programmation orientée objet, plutôt que des structures simples.
    Last edited by clifford; December 25th, 2013 at 09:55 AM.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2013
    Posts
    2
    Rep Power
    0

    Post


    Effectivement, mon problème est d'introduire les structures et puisque je ne les maîtrise pas, ceci m’apparaît un peu difficile. Bon concernant mon code voici le code complet:


    #include <stdlib.h>
    #include "stdafx.h"
    #include <string.h>
    #include <stdio.h>
    #include<math.h>
    #include<time.h>


    /***************Déclaration******************/

    float **dis_cc,*dis_dc;
    int **tw_cc,*tw_dc;
    int m,cc,st_t,ed_t,vt,f,g,j,i,*S;
    int *id,*dem,*x_td,*y_td,*x_tp,*y_tp,*cum,*xd,*yd,*xp,*yp;
    float pen=10,dis=0;
    int *tr,t,*dt_liv,tw=0;

    /*******************************************************/

    float distance1(float x1,float y1,float x2,float y2)
    {
    float dis;
    dis=(float)pow(pow((double)x1-x2,2)+pow((double)y1-y2,2),0.5);
    return dis;
    }
    int distance2(float x1,float y1,float x2,float y2)
    {
    int dis;
    dis=(int)pow(pow((double)x1-x2,2)+pow((double)y1-y2,2),0.5);
    return dis;
    }
    void tri(int *S,int m)
    {
    int aux,aux2,aux3,aux1,aux6,aux4,aux5;


    for (i=1;i<m;i++)
    {
    for(j=i+1;j<=m;j++)
    {
    if((x_tp[S[i]]>=x_tp[S[j]])||(tw_cc[id[S[i-1]]][id[S[i]]]>=tw_cc[id[S[i-1]]][id[S[j]]]))//&&(y_tp[S[i]]>=y_tp[S[j]]))
    {

    aux2=id[S[i]];
    id[S[i]]=id[S[j]];
    id[S[j]]=aux2;

    aux=x_tp[S[i]];
    x_tp[S[i]]=x_tp[S[j]];
    x_tp[S[j]]=aux;

    aux1=y_tp[S[i]];
    y_tp[S[i]]=y_tp[S[j]];
    y_tp[S[j]]=aux1;

    aux3=dem[S[i]];
    dem[S[i]]=dem[S[j]];
    dem[S[j]]=aux3;

    aux4=xp[S[i]];
    xp[S[i]]=xp[S[j]];
    xp[S[j]]=aux4;

    aux5=yp[S[i]];
    yp[S[i]]=yp[S[j]];
    yp[S[j]]=aux5;
    }
    }
    }
    }



    void affichage(int *id)
    {
    printf("FRS\t");
    for(i=1;i<=m;i++)
    {
    printf("%d\t",id[i]);
    }printf("\n");
    printf("Tourne\t");
    for(i=1;i<=m;i++)
    {
    printf("%d\t",tr[i]);
    }printf("\n");
    }
    void cumul(int *S)
    {
    int aux,aux1,aux2,aux3;

    tri(S,m);

    cum[0]=dem[0];
    for(i=1;i<=m;i++)
    {
    if(cum[i-1]+dem[i]<=cc)
    {
    cum[i]=cum[i-1]+dem[i];

    }
    else
    {
    aux=id[i];
    id[i]=id[i+1];
    id[i+1]=aux;
    aux1=dem[i];
    dem[i]=dem[i+1];
    dem[i+1]=aux1;
    aux2=x_tp[i];
    x_tp[i]=x_tp[i+1];
    x_tp[i+1]=aux2;
    aux3=y_tp[i];
    y_tp[i]=y_tp[i+1];
    y_tp[i+1]=aux3;
    cum[i]=cum[i-1]+dem[i];

    }
    if(cum[i]>cc)
    {
    cum[i]=dem[i];
    }
    }

    }


    void initial_tour(int *S)
    {
    int nbt=1,tw=0,val=10,pen=10,v_pen;
    tr=new int[m];
    float dis=0;
    cum[0]= dem[0];tr[0]=1;
    int j=1;
    for (i=1;i<=m;i++)
    {

    if(cum[i-1]+dem[S[i]]<=cc)
    {

    tr[i]=j;
    }
    else
    {
    tr[i]=j+1;nbt++;
    j++;
    }
    printf("%d\t %d\t %d\t %d\t %d\t %d\t %d\n",i,id[S[i]],dem[i],cum[i],tr[i],x_tp[i],y_tp[i]);


    }//printf("%d\t%d\t%d\t%d\t%d\n",tw_cc[id[S[3]]][id[S[4]]],tw_cc[id[S[3]]][id[S[14]]],id[S[3]],id[S[4]],id[S[14]]);

    int t=1,*dt_liv,*k=new int[nbt];
    dt_liv=new int [m];
    dt_liv[0]=320;
    int diff;
    affichage(id);
    printf("\n\n");
    printf("************************distance && temps pour chaque tour************************\n");
    printf("tour\t distance\t temps\n");
    for(i=1;i<=m+1;i++)
    {
    if(tr[i]==tr[i-1])
    {

    printf(" %d,%d ",id[S[i-1]],id[S[i]]);
    dt_liv[i]=dt_liv[i-1]+tw_cc[id[S[i-1]]][id[S[i]]];
    printf("-----%d\t %d\t %d \n\n",tw_cc[id[S[i-1]]][id[S[i]]],x_tp[i-1],y_tp[i-1]);printf("****%d\n",dt_liv[i]);

    dis+=dis_cc[id[S[i-1]]][id[S[i]]];
    tw+=tw_cc[id[S[i-1]]][id[S[i]]];


    }
    else
    {
    tw+=cum[S[i-1]];
    tw+=val;
    dt_liv[i]=dt_liv[i-1]+tw_cc[id[S[i-1]]][id[S[0]]];
    printf(" %d,%d ",id[S[i-1]],id[S[0]]);
    printf("-----%d\t %d\t %d\n\n",tw_cc[id[S[i-1]]][id[S[0]]],x_tp[i-1],y_tp[i-1]);printf("****%d\n",dt_liv[i]);

    dis+=dis_cc[id[S[i-1]]][id[S[0]]];
    tw+=tw_cc[id[S[i-1]]][id[S[0]]];

    printf("-----------tour %d-----------",t);
    printf("%f \t %d\n",dis,tw);printf("\n");
    k[i]=t;//printf("%d\t %f\t %d\n",k[i],dis,tw);
    t++;
    dis=0;tw=0;dt_liv[i-1]=320;
    dt_liv[i]=dt_liv[i-1]+tw_cc[id[S[0]]][id[S[i]]];
    printf(" %d,%d ",id[S[0]],id[S[i]]);
    printf("-----%d\t %d\t %d \n\n",tw_cc[id[S[0]]][id[S[i]]],x_tp[0],y_tp[0]);printf("****%d\n",dt_liv[i]);

    dis+=dis_cc[id[S[0]]][id[S[i]]];
    tw+=tw_cc[id[S[0]]][id[S[i]]];

    }
    if((dt_liv[i]>y_tp[i])||(dt_liv[i]<x_tp[i]))
    {
    diff=dt_liv[i]-y_tp[i];
    //printf("^^^^^%d\n",diff);
    v_pen=pen*diff;
    //printf("_____%d\n",v_pen);
    tw+=v_pen;
    }
    else
    {
    diff=0;
    }


    }

    }

    int eval(int *S)
    {int nbt=1;
    cumul(S);
    initial_tour(S);
    for(i=1;i<=m;i++)if(tr[i]!=tr[i-1]){nbt++;}

    return nbt;
    }
  6. #4
  7. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,117
    Rep Power
    1803
    Utilisez les balises de code!

IMN logo majestic logo threadwatch logo seochat tools logo