Discussion :

[laureat]

Bonjour,

Dans le cadre de mon projet de fin d'étude, je devrais implémenter un l'algorithme d'insertion à cout minimum en langage C pour résoudre le problème de tournées de véhicules avec fenetre de temps.
Voici mes deux structures de données

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct node
{
 
    int no;
    double x;
    double y;
    int demand;
    int service_time;
    int lower;
    int upper;
    int capacity;
    int start_time;
    struct node *p_next;
    struct node *p_prev;
};
typedef struct vertex
{
    struct node *p_tail;
    struct node *p_head;
}vertex_t;
struct route
{
 
    int no;
    double cost;
    double distance;
    int max_capacity;
    int cur_capacity;
    node_t *node;
 
};
typedef struct route
{
    int length;
    struct tour *p_tail;
    struct tour *p_head;
}route_t;

Quelqu'un pourrait-il me donner les grandes étapes de cet algorithme?
Merci par avance de vos aides.

[Franck Dernoncourt]

Peut-être cet article pourra t'aider : http://www.iro.umontreal.ca/~dift6751/paper_solomon.pdf ("Algorithms for the Vehicle Routing and Scheduling Problems with Time Window", 1987 Solomon)

Sinon cet article regroupe plusieurs algo plus récents : http://neo.lcc.uma.es/radi-aeb/WebVR...les/vrptw4.pdf ("Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows", 1994).