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 MSStopOptimizer.cpp
15 : /// @author Jakob Erdmann
16 : /// @date Nov 2025
17 : ///
18 : // Optimizes prioritized stops
19 : /****************************************************************************/
20 : #include <config.h>
21 : #include <queue>
22 : #include "MSLane.h"
23 : #include "MSEdge.h"
24 : #include "MSStoppingPlace.h"
25 : #include "MSStopOptimizer.h"
26 :
27 : //#define DEBUG_OPTIMIZE_SKIPPED
28 :
29 : // ===========================================================================
30 : // method definitions
31 : // ===========================================================================
32 :
33 : ConstMSEdgeVector
34 45 : MSStopOptimizer::optimizeSkipped(const MSEdge* source, double sourcePos, std::vector<StopEdgeInfo>& stops, ConstMSEdgeVector edges) const {
35 : // intial solution is an upper bound on the acceptle total skipped priority
36 : double minSkipped = 0;
37 : double totalPrio = 0;
38 45 : std::vector<StopEdgeInfo> bestStops = stops;
39 : std::shared_ptr<StopPathNode> bestNode = nullptr;
40 45 : double bestCost = myRouter.recomputeCostsPos(edges, myVehicle, sourcePos, 0, myT);
41 : std::vector<int> skipped;
42 :
43 : // each upcoming stop is part of a graph where we can start to search for a
44 : // better solution. We evaluate followers lazily and prune based on the best
45 : // solution already found
46 : std::priority_queue<std::shared_ptr<StopPathNode>, std::vector<std::shared_ptr<StopPathNode> >, spnCompare> queue;
47 :
48 90 : auto prev = std::make_shared<StopPathNode>(*this, StopEdgeInfo(source, -1, SIMSTEP, sourcePos));
49 45 : prev->stopIndex = -1;
50 45 : prev->routeIndex = 0;
51 45 : prev->cost = bestCost;
52 45 : prev->checked = true;
53 : //std::cout << " i=-1 e=" << prev->edge->getID() << " sp=" << prev->skippedPrio << " rp=" << prev->reachedPrio << "\n";
54 45 : queue.push(prev);
55 :
56 240 : for (int i = 0; i < (int)stops.size(); i++) {
57 195 : const StopEdgeInfo& stop = stops[i];
58 195 : if (stop.skipped) {
59 52 : skipped.push_back(i);
60 52 : minSkipped += stops[i].priority;
61 : } else {
62 : auto ptr = std::make_shared<StopPathNode>(*this, stop);
63 143 : ptr->skippedPrio = minSkipped;
64 143 : ptr->reachedPrio = prev->reachedPrio;
65 143 : ptr->reachedMandatory = prev->reachedMandatory;
66 143 : if (stop.priority >= 0) {
67 122 : ptr->reachedPrio += stop.priority;
68 : } else {
69 21 : ptr->reachedMandatory += 1;
70 : }
71 143 : ptr->checked = true;
72 : ptr->prev = prev;
73 143 : ptr->stopIndex = i;
74 143 : ConstMSEdgeVector subEdges(edges.begin(), edges.begin() + stop.routeIndex);
75 143 : ptr->cost = myRouter.recomputeCostsPos(subEdges, myVehicle, sourcePos, 0, myT);
76 143 : ptr->edges.insert(ptr->edges.begin(), edges.begin() + prev->routeIndex, edges.begin() + stop.routeIndex + 1);
77 : prev = ptr;
78 : bestNode = ptr;
79 143 : queue.push(ptr);
80 143 : }
81 369 : totalPrio += MAX2(0.0, stop.priority);
82 : //std::cout << " i=" << i << " e=" << ptr->edge->getID() << " sp=" << ptr->skippedPrio << " rp=" << ptr->reachedPrio << "\n";
83 : }
84 : #ifdef DEBUG_OPTIMIZE_SKIPPED
85 : std::cout << SIMTIME << " optimizeSkipped veh=" << myVehicle->getID()
86 : << " source=" << source->getID() << " sourcePos=" << sourcePos
87 : << " nStops=" << stops.size() << " skipped=" << toString(skipped) << " qSize=" << queue.size()
88 : << " minSkipped=" << minSkipped << " totalPrio=" << totalPrio << "\n";
89 : for (const StopEdgeInfo& stop : stops) {
90 : std::cout << " edge=" << stop.edge->getID() << " name=" << stop.nameTag.first << " wasSkipped=" << stop.skipped << " prio=" << stop.priority << "\n";
91 : }
92 : std::cout << " bestNode edge=" << bestNode->edge->getID() << " rPrio=" << bestNode->reachedPrio << " cost=" << bestNode->cost << "\n";
93 : #endif
94 :
95 : std::map<const MSEdge*, std::shared_ptr<StopPathNode> > bestIntermediate;
96 2527 : while (!queue.empty()) {
97 : auto ptr = queue.top();
98 2482 : queue.pop();
99 : #ifdef DEBUG_OPTIMIZE_SKIPPED
100 : std::cout << " qSize=" << queue.size() << " topNode edge=" << ptr->edge->getID()
101 : << " name='" << ptr->nameTag.first << "' skippedPrio=" << ptr->skippedPrio
102 : << " trackChanges=" << ptr->trackChanges
103 : << " cost=" << ptr->cost
104 : << " reachedPrio=" << ptr->reachedPrio
105 : << " mandatory=" << ptr->reachedMandatory
106 : << " stopIndex=" << ptr->stopIndex << "\n";
107 : #endif
108 2482 : auto succ = ptr->getSuccessor(stops, minSkipped);
109 : #ifdef DEBUG_OPTIMIZE_SKIPPED
110 : std::cout << " cost2=" << ptr->cost << " reachedPrio2=" << ptr->reachedPrio << " mandatory2=" << ptr->reachedMandatory << " succ=" << (succ == nullptr ? "NULL" : succ->edge->getID()) << "\n";
111 : #endif
112 2482 : if (*bestNode < *ptr) {
113 37 : minSkipped = MIN2(minSkipped, totalPrio - ptr->reachedPrio);
114 : #ifdef DEBUG_OPTIMIZE_SKIPPED
115 : std::cout << " newBestNode edge=" << bestNode->edge->getID() << " minSkipped=" << minSkipped
116 : << " orm=" << bestNode->reachedMandatory << " rm=" << ptr->reachedMandatory
117 : << " orp=" << bestNode->reachedPrio << " rp=" << ptr->reachedPrio
118 : << " otc=" << bestNode->trackChanges << " tc=" << ptr->trackChanges
119 : << " oc=" << bestNode->cost << " c=" << ptr->cost
120 : << "\n";
121 : #endif
122 : bestNode = ptr;
123 : }
124 2482 : if (succ != nullptr) {
125 2035 : if (minSkipped == 0 && ptr->trackChanges > bestNode->trackChanges) {
126 : #ifdef DEBUG_OPTIMIZE_SKIPPED
127 : std::cout << "pruned by minTC=" << bestNode->trackChanges << "\n";
128 : #endif
129 728 : continue;
130 : }
131 : auto it = bestIntermediate.find(ptr->edge);
132 1307 : if (it == bestIntermediate.end()) {
133 246 : bestIntermediate[ptr->edge] = ptr;
134 : #ifdef DEBUG_OPTIMIZE_SKIPPED
135 : std::cout << "firstBest " << ptr->edge->getID() << "\n";
136 : #endif
137 : } else {
138 : auto best = it->second;
139 : assert(best->checked);
140 : assert(ptr->checked);
141 1061 : if (best == ptr) {
142 : #ifdef DEBUG_OPTIMIZE_SKIPPED
143 : std::cout << "alreadyBest " << ptr->edge->getID() << " rp=" << ptr->reachedPrio << " tc=" << ptr->trackChanges << " c=" << ptr->cost << "\n";
144 : #endif
145 209 : } else if (!(*best < *ptr)) {
146 : #ifdef DEBUG_OPTIMIZE_SKIPPED
147 : std::cout << "skip " << ptr->edge->getID()
148 : << " orp=" << best->reachedPrio << " rp=" << ptr->reachedPrio
149 : << " otc=" << best->trackChanges << " tc=" << ptr->trackChanges
150 : << " oc=" << best->cost << " c=" << ptr->cost
151 : << "\n";
152 : #endif
153 : continue;
154 : } else {
155 49 : bestIntermediate[ptr->edge] = ptr;
156 : #ifdef DEBUG_OPTIMIZE_SKIPPED
157 : std::cout << "newBest " << ptr->edge->getID()
158 : << " orp=" << best->reachedPrio << " rp=" << ptr->reachedPrio
159 : << " otc=" << best->trackChanges << " tc=" << ptr->trackChanges
160 : << " oc=" << best->cost << " c=" << ptr->cost
161 : << "\n";
162 : #endif
163 : }
164 : }
165 1147 : queue.push(ptr);
166 1147 : queue.push(succ);
167 : }
168 : }
169 240 : for (auto& stop : stops) {
170 : // init true and later set false for all used stops
171 195 : if (!stop.skipped) {
172 143 : stop.backtracked = true;
173 143 : stop.skipped = true;
174 : }
175 : }
176 : ConstMSEdgeVector bestEdges;
177 222 : while (bestNode != nullptr && bestNode->stopIndex >= 0) {
178 : #ifdef DEBUG_OPTIMIZE_SKIPPED
179 : std::cout << " revBestNode index=" << bestNode->stopIndex << " edge=" << bestNode->edge->getID() << " name=" << bestNode->nameTag.first << " tc=" << bestNode->trackChanges << " c=" << bestNode->cost << "\n";
180 : #endif
181 177 : stops[bestNode->stopIndex].skipped = false;
182 177 : stops[bestNode->stopIndex].backtracked = false;
183 177 : stops[bestNode->stopIndex].origEdge = bestNode->origEdge;
184 177 : if (!bestEdges.empty() && !bestNode->edges.empty()) {
185 : bestNode->edges.pop_back();
186 : }
187 177 : bestEdges.insert(bestEdges.begin(), bestNode->edges.begin(), bestNode->edges.end());
188 : bestNode = bestNode->prev;
189 : }
190 : #ifdef DEBUG_OPTIMIZE_SKIPPED
191 : std::cout << "oldEdges=" << toString(edges) << "\nnewEdges=" << toString(bestEdges) << "\n";
192 : #endif
193 45 : return bestEdges;
194 90 : }
195 :
196 :
197 : std::shared_ptr<MSStopOptimizer::StopPathNode>
198 2482 : MSStopOptimizer::StopPathNode::getSuccessor(const std::vector<StopEdgeInfo>& stops, double minSkipped) {
199 2482 : if (!checked) {
200 1147 : checked = true;
201 : // @todo caching, bulk-routing
202 1147 : double newCost = 0;
203 1147 : if (!so.reachableInTime(prev->edge, prev->pos, edge, pos, arrival, edges, newCost)) {
204 : #ifdef DEBUG_OPTIMIZE_SKIPPED
205 : std::cout << " prevIndex=" << prev->stopIndex << " prevEdge=" << prev->edge->getID() << " i=" << stopIndex << " edge=" << edge->getID() << " unreachable\n";
206 : #endif
207 : // indicate failure
208 76 : reachedMandatory = -1;
209 76 : return nullptr;
210 : } else {
211 : #ifdef DEBUG_OPTIMIZE_SKIPPED
212 : std::cout << " prevIndex=" << prev->stopIndex << " prevEdge=" << prev->edge->getID() << " i=" << stopIndex << " edge=" << edge->getID() << " reached with edges=" << toString(edges) << " cost=" << cost << " newCost=" << newCost << "\n";
213 : #endif
214 : }
215 1071 : reachedPrio += MAX2(0.0, priority);
216 1071 : cost += newCost;
217 1071 : if (priority < 0) {
218 28 : reachedMandatory++;
219 : }
220 : }
221 2406 : int nextIndex = stopIndex + numSkipped + 1;
222 2412 : while (nextIndex < (int)stops.size()) {
223 2336 : const StopEdgeInfo& next = stops[nextIndex];
224 : #ifdef DEBUG_OPTIMIZE_SKIPPED
225 : std::cout << " i=" << stopIndex << " next=" << nextIndex << " numSkipped=" << numSkipped << " altIndex=" << altIndex << "\n";
226 : #endif
227 : // always try the default track first
228 2336 : if (altIndex == -1) {
229 1189 : altIndex++;
230 1189 : auto succ = std::make_shared<StopPathNode>(so, next);
231 1189 : succ->skippedPrio = skippedPrio;
232 1189 : succ->reachedPrio = reachedPrio;
233 1189 : succ->reachedMandatory = reachedMandatory;
234 1189 : succ->trackChanges = trackChanges;
235 1189 : succ->cost = cost;
236 0 : succ->prev = shared_from_this();
237 1189 : succ->stopIndex = nextIndex;
238 : return succ;
239 : }
240 1147 : const std::vector<MSStoppingPlace*>& alternatives = MSNet::getInstance()->getStoppingPlaceAlternatives(next.nameTag.first, next.nameTag.second);
241 1147 : if (next.priority < 0) {
242 : // next stop can neither be skipped nor changed
243 : #ifdef DEBUG_OPTIMIZE_SKIPPED
244 : std::cout << " i=" << stopIndex << " next=" << nextIndex << " isMandatory\n";
245 : #endif
246 : return nullptr;
247 : }
248 1446 : while (altIndex < (int)alternatives.size()) {
249 1173 : MSStoppingPlace* alt = alternatives[altIndex];
250 1173 : const MSEdge* altEdge = &alt->getLane().getEdge();
251 1173 : altIndex++;
252 1173 : if (altEdge == next.edge || !alt->getLane().allowsVehicleClass(so.myVehicle->getVClass())) {
253 327 : continue;
254 : }
255 846 : auto succ = std::make_shared<StopPathNode>(so, next);
256 846 : succ->trackChanges = trackChanges;
257 846 : succ->pos = alt->getEndLanePosition();
258 846 : succ->skippedPrio = skippedPrio;
259 846 : succ->reachedPrio = reachedPrio;
260 846 : succ->reachedMandatory = reachedMandatory;
261 846 : succ->cost = cost;
262 0 : succ->prev = shared_from_this();
263 846 : succ->stopIndex = nextIndex;
264 846 : succ->origEdge = succ->edge;
265 846 : succ->edge = altEdge;
266 846 : succ->trackChanges += 1;
267 : return succ;
268 : }
269 273 : skippedPrio =+ next.priority;
270 273 : if (skippedPrio >= minSkipped) {
271 : // cannot improve on current best solution
272 : #ifdef DEBUG_OPTIMIZE_SKIPPED
273 : std::cout << " i=" << stopIndex << " next=" << nextIndex << " skippedPrio=" << skippedPrio << " minSkipped=" << minSkipped << " pruned\n";
274 : #endif
275 : return nullptr;
276 : }
277 6 : nextIndex++;
278 6 : altIndex = -1;
279 6 : numSkipped++;
280 : }
281 : #ifdef DEBUG_OPTIMIZE_SKIPPED
282 : std::cout << " i=" << stopIndex << " noSuccessors\n";
283 : #endif
284 : return nullptr;
285 : }
286 :
287 :
288 : bool
289 1147 : MSStopOptimizer::reachableInTime(const MSEdge* from, double fromPos,
290 : const MSEdge* to, double toPos,
291 : SUMOTime arrival,
292 : ConstMSEdgeVector& into, double &cost) const {
293 1147 : myRouter.compute(from, fromPos, to, toPos, myVehicle, myT, into, true);
294 1147 : if (into.size() > 0) {
295 1080 : cost = myRouter.recomputeCostsPos(into, myVehicle, fromPos, toPos, myT);
296 : //std::cout << " from=" << from->getID() << " fromPos=" << fromPos << " to=" << to->getID() << " toPos=" << toPos << " t=" << myT << " cost=" << cost << " arrival=" << arrival << " maxDelay=" << myMaxDelay << "\n";
297 1080 : if (myT + TIME2STEPS(cost) <= arrival + myMaxDelay) {
298 : return true;
299 : }
300 : }
301 : return false;
302 : }
303 :
304 :
305 : /****************************************************************************/
|
