Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2025 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file MSStoppingPlaceRerouter.h
15 : /// @author Mirko Barthauer
16 : /// @date Mon, 17 June 2024
17 : ///
18 : // The MSStoppingPlaceRerouter provides an interface to structure the rerouting
19 : // to the best StoppingPlace according to the evaluation components and
20 : // associated weights.
21 : /****************************************************************************/
22 : #pragma once
23 : #include <config.h>
24 : #include <map>
25 : #include <functional>
26 : #include <utils/common/MsgHandler.h>
27 : #include <utils/common/Named.h>
28 : #include <utils/common/SUMOTime.h>
29 : #include <utils/router/SUMOAbstractRouter.h>
30 : #include <utils/xml/SUMOXMLDefinitions.h>
31 : #include <microsim/MSNet.h>
32 : #include <microsim/MSStop.h>
33 : #include <microsim/MSStoppingPlace.h>
34 :
35 : class MSEdge;
36 :
37 : /// @brief store information for a single stopping place
38 14613 : struct StoppingPlaceMemoryEntry {
39 14613 : StoppingPlaceMemoryEntry() : blockedAtTime(-1), blockedAtTimeLocal(-1), score("") {}
40 :
41 : SUMOTime blockedAtTime;
42 : SUMOTime blockedAtTimeLocal;
43 : std::string score;
44 : };
45 :
46 :
47 : class StoppingPlaceMemory {
48 : public:
49 : /// @brief Definition of the map containing all visited stopping places
50 : typedef std::map<const MSStoppingPlace*, StoppingPlaceMemoryEntry, ComparatorIdLess> StoppingPlaceMap;
51 :
52 : ///@brief Constructor
53 2306 : StoppingPlaceMemory() {}
54 :
55 : // Destructor
56 2306 : virtual ~StoppingPlaceMemory() {}
57 :
58 : /** @brief Removes an item
59 : * @param[in] id The id of the item to remove
60 : * @return If the item could be removed (an item with the id was within the container before)
61 : */
62 : bool remove(MSStoppingPlace* id) {
63 : auto it = myMap.find(id);
64 : if (it == myMap.end()) {
65 : return false;
66 : } else {
67 : myMap.erase(it);
68 : return true;
69 : }
70 : }
71 :
72 : /// @brief Removes all data about evaluated StoppingPlace items
73 : void clear() {
74 : myMap.clear();
75 : }
76 :
77 : /// @brief Returns the number of stored items within the container
78 : int size() const {
79 : return (int)myMap.size();
80 : }
81 :
82 : /// @brief Store the time the StoppingPlace was confirmed to be blocked
83 54344 : void rememberBlockedStoppingPlace(const MSStoppingPlace* stoppingPlace, bool local) {
84 54344 : myMap[stoppingPlace].blockedAtTime = SIMSTEP;
85 54344 : if (local) {
86 50719 : myMap[stoppingPlace].blockedAtTimeLocal = SIMSTEP;
87 : }
88 54344 : }
89 :
90 : /// @brief Get the time the StoppingPlace was confirmed to be blocked
91 : SUMOTime sawBlockedStoppingPlace(const MSStoppingPlace* stoppingPlace, bool local) const {
92 : auto it = myMap.find(stoppingPlace);
93 51912 : if (it == myMap.end()) {
94 : return -1;
95 : } else {
96 45008 : return local ? it->second.blockedAtTimeLocal : it->second.blockedAtTime;
97 : }
98 : }
99 :
100 : /// @brief score only needed when running with gui
101 : void rememberStoppingPlaceScore(const MSStoppingPlace* stoppingPlace, const std::string& score) {
102 86699 : myMap[stoppingPlace].score = score;
103 : }
104 :
105 17369 : void resetStoppingPlaceScores() {
106 113262 : for (auto& item : myMap) {
107 95893 : item.second.score = "";
108 : }
109 17369 : }
110 :
111 : /// @brief Returns a reference to the begin iterator for the internal map
112 : typename StoppingPlaceMap::const_iterator begin() const {
113 : return myMap.begin();
114 : }
115 :
116 : /// @brief Returns a reference to the end iterator for the internal map
117 : typename StoppingPlaceMap::const_iterator end() const {
118 : return myMap.end();
119 : }
120 :
121 : private:
122 : /// @brief The map from StoppingPlace to single evaluation
123 : StoppingPlaceMap myMap;
124 :
125 : };
126 :
127 :
128 : class MSStoppingPlaceRerouter {
129 : public:
130 : typedef std::map<std::string, double> StoppingPlaceParamMap_t;
131 : typedef std::map<std::string, bool> StoppingPlaceParamSwitchMap_t;
132 : typedef std::map<MSStoppingPlace*, StoppingPlaceParamMap_t, ComparatorIdLess> StoppingPlaceMap_t;
133 : typedef std::pair<MSStoppingPlace*, bool> StoppingPlaceVisible;
134 : typedef std::map<const MSEdge*, double> Prohibitions;
135 :
136 : ///@brief Constructor
137 : MSStoppingPlaceRerouter(std::string paramPrefix = "", bool checkValidity = false, StoppingPlaceParamMap_t addEvalParams = {}, StoppingPlaceParamSwitchMap_t addInvertParams = {});
138 :
139 : // Destructor
140 8206 : virtual ~MSStoppingPlaceRerouter() {}
141 :
142 : /** @brief main method to trigger the rerouting to the "best" StoppingPlace according to the custom evaluation function
143 : *
144 : * @param[in] veh the concerned vehicle
145 : * @param[in] stoppingPlaceCandidates stopping places to choose from and whether they are visible for the vehicle
146 : * @param[in] probs probabilities of all candidate stopping places
147 : * @param[in] newDestination whether the destination changed
148 : * @param[out] newRoute the route to/from the chosen stopping place is stored here
149 : * @param[in,out] scores input score values from external source and get scores of all components of the "best" StoppingPlace
150 : * @param[in] closedEdges edges to avoid during routing
151 : * @param[in] insertStopIndex the stop index where the new StoppingPlace should be inserted
152 : * @param[in] keepCurrentStop whether the current stop at the given stopp index should still be served after the new one
153 : * @return the best stopping place according to the target function or nullptr
154 : */
155 : MSStoppingPlace* rerouteStoppingPlace(MSStoppingPlace* destStoppingPlace, const std::vector<StoppingPlaceVisible>& stoppingPlaceCandidates, const std::vector<double>& probs, SUMOVehicle& veh,
156 : bool& newDestination, ConstMSEdgeVector& newRoute, StoppingPlaceParamMap_t& scores, const Prohibitions& closedEdges = {},
157 : const int insertStopIndex = 0, const bool keepCurrentStop = true);
158 : /** @brief compute the target function for a single alternative
159 : *
160 : * @param[in] veh the concerned vehicle
161 : * @param[in] brakeGap the distance before which the vehicle cannot stop
162 : * @param[in] newDestination whether the destination changed
163 : * @param[in] alternative the stopping place to evaluate
164 : * @param[in] occupancy occupancy of the stopping place
165 : * @param[in] prob the predefined probability of this stopping place
166 : * @param[in] router the router to use for evaluation if needed
167 : * @param[in,out] stoppingPlaces the data structure to write the evaluation values to
168 : * @param[in,out] newRoutes the data structure to write the chosen route to/from the stopping place to
169 : * @param[in,out] stoppingPlaceApproaches the data structure to write the chosen route to the stopping place to
170 : * @param[in,out] maxValues maximum values for all evaluation components
171 : * @param[in] addInput external input data
172 : * @param[in] insertStopIndex the stop index where the new StoppingPlace should be inserted
173 : * @param[in] keepCurrentStop whether the current stop at the given stopp index should still be served after the new one
174 : * @return false if the stopping place cannot be used
175 : */
176 : virtual bool evaluateDestination(SUMOVehicle& veh, double brakeGap, bool newDestination,
177 : MSStoppingPlace* alternative, double occupancy, double prob,
178 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router, StoppingPlaceMap_t& stoppingPlaces,
179 : std::map<MSStoppingPlace*, ConstMSEdgeVector>& newRoutes,
180 : std::map<MSStoppingPlace*, ConstMSEdgeVector>& stoppingPlaceApproaches,
181 : StoppingPlaceParamMap_t& maxValues,
182 : StoppingPlaceParamMap_t& addInput,
183 : const int insertStopIndex = 0,
184 : const bool keepCurrentStop = true);
185 :
186 : /** @brief Compute some custom target function components
187 : *
188 : * @param[in] veh the concerned vehicle
189 : * @param[in] brakeGap the distance before which the vehicle cannot stop
190 : * @param[in] newDestination whether the destination changed
191 : * @param[in] alternative the stopping place to evaluate
192 : * @param[in] occupancy occupancy of the stopping place
193 : * @param[in] router the router to use for evaluation if needed
194 : * @param[in,out] stoppingPlaceValues the data structure to write the evaluation values to
195 : * @param[in] newRoute the complete route to the destination passing by the stopping place
196 : * @param[in] stoppingPlaceApproach the route to the stopping place
197 : * @param[in] maxValues the maximum values of the components
198 : * @param[in] addInput external input data
199 : * @return false if the stopping place cannot be used according to the custom evaluation components
200 : */
201 : virtual bool evaluateCustomComponents(SUMOVehicle& veh, double brakeGap, bool newDestination,
202 : MSStoppingPlace* alternative, double occupancy, double prob,
203 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router, StoppingPlaceParamMap_t& stoppingPlaceValues,
204 : ConstMSEdgeVector& newRoute,
205 : ConstMSEdgeVector& stoppingPlaceApproach,
206 : StoppingPlaceParamMap_t& maxValues,
207 : StoppingPlaceParamMap_t& addInput);
208 :
209 : /// @brief Whether the stopping place should be discarded due to its results from the component evaluation (allows to check for min/max thresholds and other non-linear relations)
210 : virtual bool validComponentValues(StoppingPlaceParamMap_t& stoppingPlaceValues);
211 :
212 : /// @brief Whether the stopping place should be included in the search (can be used to add an additional filter)
213 : virtual bool useStoppingPlace(MSStoppingPlace* stoppingPlace);
214 :
215 : /// @brief Provide the router to use (MSNet::getRouterTT or MSRoutingEngine)
216 : virtual SUMOAbstractRouter<MSEdge, SUMOVehicle>& getRouter(SUMOVehicle& veh, const Prohibitions& prohibited = {});
217 :
218 : /// @brief Return the number of occupied places of the StoppingPlace
219 : virtual double getStoppingPlaceOccupancy(MSStoppingPlace* stoppingPlace) = 0;
220 :
221 : /// @brief Return the number of occupied places of the StoppingPlace from the previous time step
222 : virtual double getLastStepStoppingPlaceOccupancy(MSStoppingPlace* stoppingPlace) = 0;
223 :
224 : /// @brief Return the number of places the StoppingPlace provides
225 : virtual double getStoppingPlaceCapacity(MSStoppingPlace* stoppingPlace) = 0;
226 :
227 : /// @brief store the blocked stopping place in the vehicle
228 : virtual void rememberBlockedStoppingPlace(SUMOVehicle& veh, const MSStoppingPlace* stoppingPlace, bool blocked) = 0;
229 :
230 : /// @brief store the stopping place score in the vehicle
231 : virtual void rememberStoppingPlaceScore(SUMOVehicle& veh, MSStoppingPlace* place, const std::string& score) = 0;
232 :
233 : /// @brief forget all stopping place score for this vehicle
234 : virtual void resetStoppingPlaceScores(SUMOVehicle& veh) = 0;
235 :
236 : /// @brief ask the vehicle when it has seen the stopping place
237 : virtual SUMOTime sawBlockedStoppingPlace(SUMOVehicle& veh, MSStoppingPlace* place, bool local) = 0;
238 :
239 : /// @brief ask how many times already the vehicle has been rerouted to another stopping place
240 : virtual int getNumberStoppingPlaceReroutes(SUMOVehicle& veh) = 0;
241 :
242 : /// @brief update the number of reroutes for the vehicle
243 : virtual void setNumberStoppingPlaceReroutes(SUMOVehicle& veh, int value) = 0;
244 :
245 : /// @brief read target function weights for this vehicle
246 : virtual StoppingPlaceParamMap_t collectWeights(SUMOVehicle& veh);
247 :
248 : /** @brief read the value of a stopping place search param, e.g. a component weight factor
249 : *
250 : * @param[in] veh the concerned vehicle
251 : * @param[in] param the name of the stopping place search param, excluding the param prefix (e.g. "parking.")
252 : * @param[in] defaultWeight value to return in case the param hasn't been defined for the vehicle
253 : * @param[in] warn whether a warning message shall be issued if the param is not defined for the vehicle
254 : * @return param value
255 : */
256 : double getWeight(SUMOVehicle& veh, const std::string param, const double defaultWeight, const bool warn = false);
257 :
258 : /** @brief keep track of the maximum values of each component
259 : *
260 : * @param[in] stoppingPlaceValues the target function component values of a vehicle
261 : * @param[in,out] maxValues stores the maximum values of the given stoppingPlaceValues and previously given maxValues
262 : */
263 : static void updateMaxValues(StoppingPlaceParamMap_t& stoppingPlaceValues, StoppingPlaceParamMap_t& maxValues);
264 :
265 : /** @brief compute the scalar target function value by means of a linear combination of all components/weights after normalising and optionally inverting the values
266 : *
267 : * @param[in] absValues the component values
268 : * @param[in] maxValues max values for all components
269 : * @param[in] weights weight factors for all components
270 : * @param[in] norm which component should be normalised
271 : * @param[in] invert which component should be inverted
272 : * @return target function value for a single stopping place and vehicle
273 : */
274 : static double getTargetValue(const StoppingPlaceParamMap_t& absValues, const StoppingPlaceParamMap_t& maxValues, const StoppingPlaceParamMap_t& weights, const StoppingPlaceParamSwitchMap_t& norm, const StoppingPlaceParamSwitchMap_t& invert);
275 :
276 : protected:
277 : /// @brief Ask the vehicle about the relevant rerouting parameters and initiate the maximum value data structure
278 : void readEvaluationWeights(SUMOVehicle& veh, StoppingPlaceParamMap_t& stoppingPlaceParams, StoppingPlaceParamMap_t& stoppingPlaceDefaults, StoppingPlaceParamMap_t& maxValues) {
279 : for (auto& it : stoppingPlaceParams) {
280 : const double value = getWeight(veh, it.first, stoppingPlaceDefaults[it.first]);
281 : it.second = value;
282 : if (value > maxValues[it.first]) {
283 : maxValues[it.first] = value;
284 : }
285 : }
286 : }
287 :
288 : /// @brief Determine the rerouting origin edge (not necessarily the current edge of the vehicle!)
289 32538 : const MSRouteIterator determineRerouteOrigin(SUMOVehicle& veh, int insertStopIndex) {
290 32538 : const int stopCount = (int)veh.getStops().size();
291 32538 : if (insertStopIndex == 0 || stopCount == 0) {
292 32538 : return veh.getRerouteOrigin();
293 : }
294 : // if the stop index is too high cap to route end
295 0 : const int stopIndex = MIN2(insertStopIndex, stopCount - 1);
296 0 : std::list<MSStop>::const_iterator it = veh.getStops().begin();
297 : std::advance(it, stopIndex);
298 0 : MSStop relevantStop = *it;
299 0 : return relevantStop.edge;
300 : }
301 :
302 : private:
303 :
304 : ///@brief Constructor
305 : MSStoppingPlaceRerouter() = delete;
306 :
307 : protected:
308 : const std::string myParamPrefix;
309 : bool myCheckValidity;
310 : StoppingPlaceParamMap_t myEvalParams;
311 : StoppingPlaceParamSwitchMap_t myNormParams;
312 : StoppingPlaceParamSwitchMap_t myInvertParams;
313 : };
|
