Aide pour mon projet C

[invite8b421ec7]

Bonjour


Je sollicite votre aide pour mon projet.



Je travaille sur le problème de tournées de véhicules qui consiste à déterminer l'ensemble de routes (la meilleur route qui minimise la distance totale parcourue)que va emprunter chaque véhicule pour livrer les produits au client.Voici un lien wikipedia sur mon problèmehttp://fr.wikipedia.org/wiki/Probl%C...v%C3%A9hicules

J'aimerais savoir comment représenter le problème en graphe sachant que j'ai les données suivantes sur:

1.Client:
-abscisse

-ordonee

-numero

-demande

-date de service au plus tot

-date de service au plus tard

2.vehicule
-capacite
Pour les clients j'ai choisi de le réprésenter sous forme d'une liste chainée qui contient les infos sur les clients ainsi qu'un pointeur sur le client suivant. Pour le véhicule, je lai représenté sous forme d'une structure ayant deux champs.
En revanche je ne sais pas du tout comment je peux représenter les résultats (ensemble de routes) sachant que je vais procéder par un algorithme d'insertion pour construire les routes .
Merci par avance de vos lumières.

struct client
{
    
    int identifiant;
    double abscisse;
    double ordonee;
    int demande;
    int temps_service;
    int borne_inf_tw;//date au plus tot de debut service
    int borne_sup_tw;//date au plus tard debut service
    struct client *suivant;
};
struct vehicule
{
    
    int max_capacite;
    int cur_capacite //capacite courante
    
};
typedef vehicule vehicule_t;

-----

[danyvio]

Pour les clients j'ai choisi de le réprésenter sous forme d'une liste chainée qui contient les infos sur les clients ainsi qu'un pointeur sur le client suivant.

Je ne vais pas entrer dans le détail du développement qui t'incombe, même si la recherche opérationnelle a été mon dada .

Juste une chose qui m'intrigue : quelle est ta logique du chaînage des clients ?

[invitee840409b]

Bonjour,

Ce problème est similaire à celui du voyageur de commerce, tu devrais trouver plus d'informations en recherchant ces termes.

ProgVal

[invite8b421ec7]

Je ne vais pas entrer dans le détail du développement qui t'incombe, même si la recherche opérationnelle a été mon dada .

Juste une chose qui m'intrigue : quelle est ta logique du chaînage des clients ?

Si j'ai bien compris ta question, je vais utiliser une liste double chainee pour stocker la liste de clients voisins à un client.

[A voir en vidéo sur Futura]