-
Notifications
You must be signed in to change notification settings - Fork 1
/
reseau.cpp
165 lines (148 loc) · 6.27 KB
/
reseau.cpp
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/*
* TP5 - Été 2022 - Planification d'une flotte de véhicules électriques
* UQAM / Département d'informatique
* INF3105 - Structures de données et algorithmes
* @author Besma Jabri
* Code permanent : JABB71560008
* @author Othmane Azzouzi
* Code permanent : AZZO27129703
*/
#include <cassert>
#include <iostream>
#include <queue>
#include <list>
#include "reseau.h"
#include <cmath>
using namespace std;
// Retourne l'index (dans le tableau bornes) du nom de la borne (ID string).
int Reseau::getBorneIndex(const std::string& sid) const{
auto i = indexbornes.find(sid);
if(i==indexbornes.end())
return -1;
return i->second;
}
PlanFlotte Reseau::calculerN1(const Requete& r) const{
PlanFlotte plan;
for(const Vehicule& v : r)
plan.push_back(calculer(v));
return plan;
}
PlanVehicule Reseau::calculer(const Vehicule& v) const{
//À compléter: c'est ici, dans calculer, que vous devez implémenter l'algorithme de Dijkstra.
int id_borne_depart = indexbornes.at(v.sdepart);
int id_borne_arrivee = indexbornes.at(v.sarrivee);
int d; // la duree pour se rendre a la borne suivante plus la duree de charge
int tempsDeplacement; // temps pour se rendre a la borne suivante
int tempsDeChargement; // temps pour se rendre a la borne suivante
double BatterieUtilisee;
map<int , int> durees;
map<int , int> parents;
/* structure des elements dans le monceau Q contient l'id de borne et la distance pour y rendre */
struct BornePrioritaire {
int id;
int duree;
BornePrioritaire(int _id, int _duree): id(_id),duree(_duree) {}
bool operator <(const BornePrioritaire borne) const {
return duree < borne.duree;
}
};
for (int i = 0; i <= bornes.size(); ++i) {
if (bornes[id_borne_depart].bornesAtteignables.count(bornes[i].id) > 0) {
durees[bornes[i].id] = std::numeric_limits<int>::max();
parents[bornes[i].id] = -1;
}
}
// distances[s] ← 0
durees[id_borne_depart] = 0;
BornePrioritaire borneDepart = BornePrioritaire(id_borne_depart,0 );
// Q ← créer FilePrioritaire(V )
priority_queue<BornePrioritaire, vector<BornePrioritaire> > Q;
Q.push(borneDepart);
while( !Q.empty() ){
BornePrioritaire V = Q.top();
Q.pop();
if ( durees[V.id] == std::numeric_limits<int>::max() ) {
break;
}
for( int i = bornes[V.id].bornesAtteignables.begin()->first; i <= bornes[V.id].bornesAtteignables.size(); ++ i) {
// les aretes qui dépasse l'autonomie de vehicule
if ( bornes[V.id].bornesAtteignables.count(i) <= 0 || bornes[V.id].bornesAtteignables.find(i)->second > v.autonomie) {
continue;
}
tempsDeplacement = std::ceil(bornes[V.id].bornesAtteignables.find(i)->second/vitesse); // correcte
BatterieUtilisee = (bornes[V.id].bornesAtteignables.find(i)->second) * (v.consommation);
tempsDeChargement = std::ceil((BatterieUtilisee*3600)/bornes[bornes[V.id].bornesAtteignables.find(i)->first].puissance);//correcte
d = durees[V.id] + tempsDeplacement + tempsDeChargement;
if (d < durees[bornes[V.id].bornesAtteignables.find(i)->first]) {
parents[bornes[V.id].bornesAtteignables.find(i)->first] = bornes[V.id].id;
durees[bornes[V.id].bornesAtteignables.find(i)->first] = d;
BornePrioritaire w = BornePrioritaire(bornes[V.id].bornesAtteignables.find(i)->first, (-1) * d);
Q.push(w);
}
}
}
// trouver le chemin minimum entre le point de depart et lien de depart
int courant;
int parent;
//-> point d'arrivé
std::map<int,int>::iterator it_parent=parents.find(id_borne_arrivee);
courant = it_parent->first;
vector<int> chemin;
chemin.push_back(id_borne_depart);
while(courant != id_borne_depart) {
parent = it_parent->second;
courant = parent;
it_parent = parents.find(courant);
if (parent != id_borne_depart) {
chemin.push_back(bornes[parent].id);
}
}
chemin.push_back(id_borne_arrivee);
PlanVehicule pv;
std::list<Etape>::iterator etape = pv.begin();
if(id_borne_depart==id_borne_arrivee) { // depart
Etape e = Etape(v.sdepart,id_borne_depart,v.datedepart,v.datedepart,v.datedepart);
pv.push_back(e);
} else {
for (int i: chemin) {
if (i == id_borne_depart ) {
Etape e = Etape(bornes[i].sid, i, v.datedepart, v.datedepart, v.datedepart);
pv.push_back(e);
} else {
Etape etap_precedente = pv.back(); // extraire les informations sur l'étape précédente
int id_precedent = etap_precedente.id_borne; // borne précédente
DateHeure fin_precedent = etap_precedente.fin; // fin du chargement et départ de la borne précédente
tempsDeplacement = std::ceil(bornes[id_precedent].bornesAtteignables.find(i)->second / vitesse);
BatterieUtilisee = (bornes[id_precedent].bornesAtteignables.find(i)->second) * (v.consommation);
tempsDeChargement = std::ceil((BatterieUtilisee*3600) /
bornes[bornes[id_precedent].bornesAtteignables.find(i)->first].puissance);
DateHeure arrivee_courant = fin_precedent + tempsDeplacement;
DateHeure fin_courant = arrivee_courant + tempsDeChargement;
Etape e = Etape(bornes[i].sid, i, arrivee_courant, arrivee_courant ,fin_courant);
pv.push_back(e);
}
}
}
return pv;
}
PlanFlotte Reseau::calculerN2(const Requete& r) const{
PlanFlotte plan;
for(const Vehicule& v : r){
PlanVehicule pv = calculer(v);
plan.push_back(pv);
//À compléter: réserver les bornes pour pv
}
//À compléter: il faut annuler les réservations
return plan;
}
PlanFlotte Reseau::calculerN3(const Requete& r) const{
std::cerr << "Niveau 3 pas encore implémenté. Utilisation de Niveau 2 («fallback»)." << std::endl;
return calculerN2(r);
}
DateHeure PlanFlotte::max() const{
DateHeure max;
for(PlanVehicule pv : *this)
if(!pv.empty() && pv.back().fin > max)
max = pv.back().fin;
return max;
}