Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2026 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 55 : 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 55 : std::vector<StopEdgeInfo> bestStops = stops;
39 55 : double bestCost = myRouter.recomputeCostsPos(edges, myVehicle, sourcePos, 0, myT);
40 : std::vector<int> skipped;
41 :
42 : // each upcoming stop is part of a graph where we can start to search for a
43 : // better solution. We evaluate followers lazily and prune based on the best
44 : // solution already found
45 : std::priority_queue<std::shared_ptr<StopPathNode>, std::vector<std::shared_ptr<StopPathNode> >, spnCompare> queue;
46 :
47 110 : auto prev = std::make_shared<StopPathNode>(*this, StopEdgeInfo(source, -1, SIMSTEP, sourcePos));
48 : std::shared_ptr<StopPathNode> bestNode = prev;
49 55 : prev->stopIndex = -1;
50 55 : prev->routeIndex = 0;
51 55 : prev->cost = bestCost;
52 55 : prev->checked = true;
53 : //std::cout << " i=-1 e=" << prev->edge->getID() << " sp=" << prev->skippedPrio << " rp=" << prev->reachedPrio << "\n";
54 55 : queue.push(prev);
55 :
56 316 : for (int i = 0; i < (int)stops.size(); i++) {
57 261 : const StopEdgeInfo& stop = stops[i];
58 261 : if (stop.skipped) {
59 62 : skipped.push_back(i);
60 62 : minSkipped += stops[i].priority;
61 : } else {
62 : auto ptr = std::make_shared<StopPathNode>(*this, stop);
63 199 : ptr->skippedPrio = minSkipped;
64 199 : ptr->reachedPrio = prev->reachedPrio;
65 199 : ptr->reachedMandatory = prev->reachedMandatory;
66 199 : if (stop.priority >= 0) {
67 171 : ptr->reachedPrio += stop.priority;
68 : } else {
69 28 : ptr->reachedMandatory += 1;
70 : }
71 199 : ptr->checked = true;
72 : ptr->prev = prev;
73 199 : ptr->stopIndex = i;
74 199 : ConstMSEdgeVector subEdges(edges.begin(), edges.begin() + stop.routeIndex);
75 199 : ptr->cost = myRouter.recomputeCostsPos(subEdges, myVehicle, sourcePos, 0, myT);
76 199 : ptr->edges.insert(ptr->edges.begin(), edges.begin() + prev->routeIndex, edges.begin() + stop.routeIndex + 1);
77 : prev = ptr;
78 : bestNode = ptr;
79 199 : queue.push(ptr);
80 199 : }
81 494 : 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 3393 : while (!queue.empty()) {
97 : auto ptr = queue.top();
98 3338 : 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 3338 : 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 3338 : if (*bestNode < *ptr) {
113 44 : 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 3338 : if (succ != nullptr) {
125 2780 : if (minSkipped == 0 && ptr->trackChanges > bestNode->trackChanges) {
126 : #ifdef DEBUG_OPTIMIZE_SKIPPED
127 : std::cout << "pruned by minTC=" << bestNode->trackChanges << "\n";
128 : #endif
129 1008 : continue;
130 : }
131 : auto it = bestIntermediate.find(ptr->edge);
132 1772 : if (it == bestIntermediate.end()) {
133 333 : 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 1439 : 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 279 : } 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 1542 : queue.push(ptr);
166 1542 : queue.push(succ);
167 : }
168 : }
169 316 : for (auto& stop : stops) {
170 : // init true and later set false for all used stops
171 261 : if (!stop.skipped) {
172 199 : stop.backtracked = true;
173 199 : stop.skipped = true;
174 : }
175 : }
176 : ConstMSEdgeVector bestEdges;
177 55 : if (bestNode->stopIndex < 0) {
178 : // all stops were skipped. End route on current edge
179 3 : bestEdges.push_back(source);
180 : }
181 295 : while (bestNode != nullptr && bestNode->stopIndex >= 0) {
182 : #ifdef DEBUG_OPTIMIZE_SKIPPED
183 : std::cout << " revBestNode index=" << bestNode->stopIndex << " edge=" << bestNode->edge->getID() << " name=" << bestNode->nameTag.first << " tc=" << bestNode->trackChanges << " c=" << bestNode->cost << "\n";
184 : #endif
185 240 : stops[bestNode->stopIndex].skipped = false;
186 240 : stops[bestNode->stopIndex].backtracked = false;
187 240 : stops[bestNode->stopIndex].origEdge = bestNode->origEdge;
188 240 : if (!bestEdges.empty() && !bestNode->edges.empty()) {
189 : bestNode->edges.pop_back();
190 : }
191 240 : bestEdges.insert(bestEdges.begin(), bestNode->edges.begin(), bestNode->edges.end());
192 : bestNode = bestNode->prev;
193 : }
194 : #ifdef DEBUG_OPTIMIZE_SKIPPED
195 : std::cout << "oldEdges=" << toString(edges) << "\nnewEdges=" << toString(bestEdges) << "\n";
196 : #endif
197 55 : return bestEdges;
198 55 : }
199 :
200 :
201 : std::shared_ptr<MSStopOptimizer::StopPathNode>
202 3338 : MSStopOptimizer::StopPathNode::getSuccessor(const std::vector<StopEdgeInfo>& stops, double minSkipped) {
203 3338 : if (!checked) {
204 1542 : checked = true;
205 : // @todo caching, bulk-routing
206 1542 : double newCost = 0;
207 1542 : if (!so.reachableInTime(prev->edge, prev->pos, edge, pos, arrival, edges, newCost)) {
208 : #ifdef DEBUG_OPTIMIZE_SKIPPED
209 : std::cout << " prevIndex=" << prev->stopIndex << " prevEdge=" << prev->edge->getID() << " i=" << stopIndex << " edge=" << edge->getID() << " unreachable\n";
210 : #endif
211 : // indicate failure
212 86 : reachedMandatory = -1;
213 86 : return nullptr;
214 : } else {
215 : #ifdef DEBUG_OPTIMIZE_SKIPPED
216 : std::cout << " prevIndex=" << prev->stopIndex << " prevEdge=" << prev->edge->getID() << " i=" << stopIndex << " edge=" << edge->getID() << " reached with edges=" << toString(edges) << " cost=" << cost << " newCost=" << newCost << "\n";
217 : #endif
218 : }
219 1456 : reachedPrio += MAX2(0.0, priority);
220 1456 : cost += newCost;
221 1456 : if (priority < 0) {
222 35 : reachedMandatory++;
223 : }
224 : }
225 3252 : int nextIndex = stopIndex + numSkipped + 1;
226 3258 : while (nextIndex < (int)stops.size()) {
227 3168 : const StopEdgeInfo& next = stops[nextIndex];
228 : #ifdef DEBUG_OPTIMIZE_SKIPPED
229 : std::cout << " i=" << stopIndex << " next=" << nextIndex << " numSkipped=" << numSkipped << " altIndex=" << altIndex << "\n";
230 : #endif
231 : // always try the default track first
232 3168 : if (altIndex == -1) {
233 1626 : altIndex++;
234 1626 : auto succ = std::make_shared<StopPathNode>(so, next);
235 1626 : succ->skippedPrio = skippedPrio;
236 1626 : succ->reachedPrio = reachedPrio;
237 1626 : succ->reachedMandatory = reachedMandatory;
238 1626 : succ->trackChanges = trackChanges;
239 1626 : succ->cost = cost;
240 0 : succ->prev = shared_from_this();
241 1626 : succ->stopIndex = nextIndex;
242 : return succ;
243 : }
244 1542 : const std::vector<MSStoppingPlace*>& alternatives = MSNet::getInstance()->getStoppingPlaceAlternatives(next.nameTag.first, next.nameTag.second);
245 1542 : if (next.priority < 0) {
246 : // next stop can neither be skipped nor changed
247 : #ifdef DEBUG_OPTIMIZE_SKIPPED
248 : std::cout << " i=" << stopIndex << " next=" << nextIndex << " isMandatory\n";
249 : #endif
250 : return nullptr;
251 : }
252 1911 : while (altIndex < (int)alternatives.size()) {
253 1558 : MSStoppingPlace* alt = alternatives[altIndex];
254 1558 : const MSEdge* altEdge = &alt->getLane().getEdge();
255 1558 : altIndex++;
256 1558 : if (altEdge == next.edge || !alt->getLane().allowsVehicleClass(so.myVehicle->getVClass())) {
257 404 : continue;
258 : }
259 1154 : auto succ = std::make_shared<StopPathNode>(so, next);
260 1154 : succ->trackChanges = trackChanges;
261 1154 : succ->pos = alt->getEndLanePosition();
262 1154 : succ->skippedPrio = skippedPrio;
263 1154 : succ->reachedPrio = reachedPrio;
264 1154 : succ->reachedMandatory = reachedMandatory;
265 1154 : succ->cost = cost;
266 0 : succ->prev = shared_from_this();
267 1154 : succ->stopIndex = nextIndex;
268 1154 : succ->origEdge = succ->edge;
269 1154 : succ->edge = altEdge;
270 1154 : succ->trackChanges += 1;
271 : return succ;
272 : }
273 353 : skippedPrio += next.priority;
274 353 : if (skippedPrio >= minSkipped) {
275 : // cannot improve on current best solution
276 : #ifdef DEBUG_OPTIMIZE_SKIPPED
277 : std::cout << " i=" << stopIndex << " next=" << nextIndex << " skippedPrio=" << skippedPrio << " minSkipped=" << minSkipped << " pruned\n";
278 : #endif
279 : return nullptr;
280 : }
281 6 : nextIndex++;
282 6 : altIndex = -1;
283 6 : numSkipped++;
284 : }
285 : #ifdef DEBUG_OPTIMIZE_SKIPPED
286 : std::cout << " i=" << stopIndex << " noSuccessors\n";
287 : #endif
288 : return nullptr;
289 : }
290 :
291 :
292 : bool
293 1542 : MSStopOptimizer::reachableInTime(const MSEdge* from, double fromPos,
294 : const MSEdge* to, double toPos,
295 : SUMOTime arrival,
296 : ConstMSEdgeVector& into, double& cost) const {
297 1542 : myRouter.compute(from, fromPos, to, toPos, myVehicle, myT, into, true);
298 1542 : if (into.size() > 0) {
299 1465 : cost = myRouter.recomputeCostsPos(into, myVehicle, fromPos, toPos, myT);
300 : //std::cout << " from=" << from->getID() << " fromPos=" << fromPos << " to=" << to->getID() << " toPos=" << toPos << " t=" << myT << " cost=" << cost << " arrival=" << arrival << " maxDelay=" << myMaxDelay << "\n";
301 1465 : if (myT + TIME2STEPS(cost) <= arrival + myMaxDelay) {
302 : return true;
303 : }
304 : }
305 : return false;
306 : }
307 :
308 :
309 : /****************************************************************************/
|
