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 48 : 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 48 : std::vector<StopEdgeInfo> bestStops = stops;
39 48 : 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 96 : auto prev = std::make_shared<StopPathNode>(*this, StopEdgeInfo(source, -1, SIMSTEP, sourcePos));
48 : std::shared_ptr<StopPathNode> bestNode = prev;
49 48 : prev->stopIndex = -1;
50 48 : prev->routeIndex = 0;
51 48 : prev->cost = bestCost;
52 48 : prev->checked = true;
53 : //std::cout << " i=-1 e=" << prev->edge->getID() << " sp=" << prev->skippedPrio << " rp=" << prev->reachedPrio << "\n";
54 48 : queue.push(prev);
55 :
56 246 : for (int i = 0; i < (int)stops.size(); i++) {
57 198 : const StopEdgeInfo& stop = stops[i];
58 198 : if (stop.skipped) {
59 55 : skipped.push_back(i);
60 55 : 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 375 : 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 2539 : while (!queue.empty()) {
97 : auto ptr = queue.top();
98 2491 : 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 2491 : 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 2491 : 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 2491 : if (succ != nullptr) {
125 2038 : 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 1310 : if (it == bestIntermediate.end()) {
133 249 : 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 1150 : queue.push(ptr);
166 1150 : queue.push(succ);
167 : }
168 : }
169 246 : for (auto& stop : stops) {
170 : // init true and later set false for all used stops
171 198 : if (!stop.skipped) {
172 143 : stop.backtracked = true;
173 143 : stop.skipped = true;
174 : }
175 : }
176 : ConstMSEdgeVector bestEdges;
177 48 : if (bestNode->stopIndex < 0) {
178 : // all stops were skipped. End route on current edge
179 3 : bestEdges.push_back(source);
180 : }
181 225 : 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 177 : stops[bestNode->stopIndex].skipped = false;
186 177 : stops[bestNode->stopIndex].backtracked = false;
187 177 : stops[bestNode->stopIndex].origEdge = bestNode->origEdge;
188 177 : if (!bestEdges.empty() && !bestNode->edges.empty()) {
189 : bestNode->edges.pop_back();
190 : }
191 177 : 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 48 : return bestEdges;
198 48 : }
199 :
200 :
201 : std::shared_ptr<MSStopOptimizer::StopPathNode>
202 2491 : MSStopOptimizer::StopPathNode::getSuccessor(const std::vector<StopEdgeInfo>& stops, double minSkipped) {
203 2491 : if (!checked) {
204 1150 : checked = true;
205 : // @todo caching, bulk-routing
206 1150 : double newCost = 0;
207 1150 : 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 79 : reachedMandatory = -1;
213 79 : 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 1071 : reachedPrio += MAX2(0.0, priority);
220 1071 : cost += newCost;
221 1071 : if (priority < 0) {
222 28 : reachedMandatory++;
223 : }
224 : }
225 2412 : int nextIndex = stopIndex + numSkipped + 1;
226 2418 : while (nextIndex < (int)stops.size()) {
227 2342 : 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 2342 : if (altIndex == -1) {
233 1192 : altIndex++;
234 1192 : auto succ = std::make_shared<StopPathNode>(so, next);
235 1192 : succ->skippedPrio = skippedPrio;
236 1192 : succ->reachedPrio = reachedPrio;
237 1192 : succ->reachedMandatory = reachedMandatory;
238 1192 : succ->trackChanges = trackChanges;
239 1192 : succ->cost = cost;
240 0 : succ->prev = shared_from_this();
241 1192 : succ->stopIndex = nextIndex;
242 : return succ;
243 : }
244 1150 : const std::vector<MSStoppingPlace*>& alternatives = MSNet::getInstance()->getStoppingPlaceAlternatives(next.nameTag.first, next.nameTag.second);
245 1150 : 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 1449 : while (altIndex < (int)alternatives.size()) {
253 1173 : MSStoppingPlace* alt = alternatives[altIndex];
254 1173 : const MSEdge* altEdge = &alt->getLane().getEdge();
255 1173 : altIndex++;
256 1173 : if (altEdge == next.edge || !alt->getLane().allowsVehicleClass(so.myVehicle->getVClass())) {
257 327 : continue;
258 : }
259 846 : auto succ = std::make_shared<StopPathNode>(so, next);
260 846 : succ->trackChanges = trackChanges;
261 846 : succ->pos = alt->getEndLanePosition();
262 846 : succ->skippedPrio = skippedPrio;
263 846 : succ->reachedPrio = reachedPrio;
264 846 : succ->reachedMandatory = reachedMandatory;
265 846 : succ->cost = cost;
266 0 : succ->prev = shared_from_this();
267 846 : succ->stopIndex = nextIndex;
268 846 : succ->origEdge = succ->edge;
269 846 : succ->edge = altEdge;
270 846 : succ->trackChanges += 1;
271 : return succ;
272 : }
273 276 : skippedPrio += next.priority;
274 276 : 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 1150 : MSStopOptimizer::reachableInTime(const MSEdge* from, double fromPos,
294 : const MSEdge* to, double toPos,
295 : SUMOTime arrival,
296 : ConstMSEdgeVector& into, double &cost) const {
297 1150 : myRouter.compute(from, fromPos, to, toPos, myVehicle, myT, into, true);
298 1150 : if (into.size() > 0) {
299 1080 : 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 1080 : if (myT + TIME2STEPS(cost) <= arrival + myMaxDelay) {
302 : return true;
303 : }
304 : }
305 : return false;
306 : }
307 :
308 :
309 : /****************************************************************************/
|
