Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2007-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 MSDispatch.cpp
15 : /// @author Jakob Erdmann
16 : /// @date 16.12.2019
17 : ///
18 : // An algorithm that performs dispatch for the taxi device
19 : /****************************************************************************/
20 : #include <config.h>
21 :
22 : #include <limits>
23 : #include <microsim/MSNet.h>
24 : #include <microsim/MSEdge.h>
25 : #include <microsim/MSGlobals.h>
26 : #include <microsim/transportables/MSTransportable.h>
27 : #include "MSRoutingEngine.h"
28 : #include "MSDispatch.h"
29 :
30 : //#define DEBUG_RESERVATION
31 : //#define DEBUG_DETOUR
32 : //#define DEBUG_COND2(obj) (obj->getID() == "p0")
33 : #define DEBUG_COND2(obj) (true)
34 :
35 :
36 : // ===========================================================================
37 : // Reservation methods
38 : // ===========================================================================
39 :
40 : // ===========================================================================
41 : // MSDispatch methods
42 : // ===========================================================================
43 :
44 812 : MSDispatch::MSDispatch(const Parameterised::Map& params) :
45 : Parameterised(params),
46 812 : myOutput(nullptr),
47 812 : myReservationCount(0),
48 1624 : myRoutingMode(StringUtils::toInt(getParameter("routingMode", "1"))) {
49 812 : const std::string opt = "device.taxi.dispatch-algorithm.output";
50 812 : if (OptionsCont::getOptions().isSet(opt)) {
51 336 : OutputDevice::createDeviceByOption(opt, "DispatchInfo");
52 168 : myOutput = &OutputDevice::getDeviceByOption(opt);
53 : }
54 1624 : myKeepUnreachableResTime = string2time(OptionsCont::getOptions().getString("device.taxi.dispatch-keep-unreachable"));
55 812 : }
56 :
57 812 : MSDispatch::~MSDispatch() {
58 1187 : for (auto item : myGroupReservations) {
59 750 : for (Reservation* res : item.second) {
60 375 : delete res;
61 : }
62 : }
63 : myGroupReservations.clear();
64 812 : }
65 :
66 :
67 : Reservation*
68 2841 : MSDispatch::addReservation(MSTransportable* person,
69 : SUMOTime reservationTime,
70 : SUMOTime pickupTime,
71 : SUMOTime earliestPickupTime,
72 : const MSEdge* from, double fromPos,
73 : const MSStoppingPlace* fromStop,
74 : const MSEdge* to, double toPos,
75 : const MSStoppingPlace* toStop,
76 : std::string group,
77 : const std::string& line,
78 : int maxCapacity,
79 : int maxContainerCapacity) {
80 : // no new reservation nedded if the person can be added to an existing group
81 2841 : if (group == "") {
82 : // the default empty group implies, no grouping is wanted (and
83 : // transportable ids are unique)
84 2577 : group = person->getID();
85 : } else {
86 : auto it2 = myRunningReservations.find(group);
87 264 : if (it2 != myRunningReservations.end()) {
88 62 : for (auto item : it2->second) {
89 : Reservation* res = const_cast<Reservation*>(item.first);
90 : if (res->persons.count(person) == 0
91 60 : && res->from == from
92 60 : && res->to == to
93 60 : && res->fromPos == fromPos
94 60 : && res->toPos == toPos) {
95 : MSDevice_Taxi* taxi = item.second;
96 : if (taxi->getState() == taxi->PICKUP
97 58 : && remainingCapacity(taxi, res) > 0
98 118 : && taxi->compatibleLine(taxi->getHolder().getParameter().line, line)) {
99 : //std::cout << SIMTIME << " addPerson=" << person->getID() << " extendRes=" << toString(res->persons) << " taxi=" << taxi->getHolder().getID() << " state=" << taxi->getState() << "\n";
100 : res->persons.insert(person);
101 58 : taxi->addCustomer(person, res);
102 : return res;
103 : }
104 : }
105 : }
106 : }
107 : }
108 : Reservation* result = nullptr;
109 : bool added = false;
110 : auto it = myGroupReservations.find(group);
111 2783 : if (it != myGroupReservations.end()) {
112 : // try to add to existing reservation
113 140 : for (Reservation* res : it->second) {
114 : if (res->persons.count(person) == 0
115 128 : && res->from == from
116 128 : && res->to == to
117 128 : && res->fromPos == fromPos
118 128 : && res->toPos == toPos) {
119 128 : if (res->persons.size() > 0 && (*res->persons.begin())->isPerson() != person->isPerson()) {
120 0 : WRITE_WARNINGF(TL("Mixing reservations of persons and containers with the same group is not supported for % and %"),
121 : (*res->persons.begin())->getID(), person->getID());
122 : }
123 250 : if ((person->isPerson() && (int)res->persons.size() >= maxCapacity) ||
124 140 : (!person->isPerson() && (int)res->persons.size() >= maxContainerCapacity)) {
125 : // split group to ensure that at least one taxi is capable of delivering group size.
126 12 : continue;
127 : }
128 : res->persons.insert(person);
129 : result = res;
130 : added = true;
131 116 : break;
132 : }
133 : }
134 : }
135 2783 : if (!added) {
136 2667 : Reservation* newRes = new Reservation(toString(myReservationCount++), {person}, reservationTime, pickupTime, earliestPickupTime, from, fromPos, fromStop, to, toPos, toStop, group, line);
137 2667 : myGroupReservations[group].push_back(newRes);
138 : result = newRes;
139 : }
140 2783 : myHasServableReservations = true;
141 : #ifdef DEBUG_RESERVATION
142 : if (DEBUG_COND2(person)) std::cout << SIMTIME
143 : << " addReservation p=" << person->getID()
144 : << " rT=" << time2string(reservationTime)
145 : << " pT=" << time2string(pickupTime)
146 : << " from=" << from->getID() << " fromPos=" << fromPos
147 : << " to=" << to->getID() << " toPos=" << toPos
148 : << " group=" << group
149 : << " added=" << added
150 : << "\n";
151 : #endif
152 2783 : return result;
153 : }
154 :
155 :
156 : std::string
157 87 : MSDispatch::removeReservation(MSTransportable* person,
158 : const MSEdge* from, double fromPos,
159 : const MSEdge* to, double toPos,
160 : std::string group) {
161 87 : if (group == "") {
162 : // the default empty group implies, no grouping is wanted (and
163 : // transportable ids are unique)
164 77 : group = person->getID();
165 : }
166 87 : std::string removedID = "";
167 : auto it = myGroupReservations.find(group);
168 87 : if (it != myGroupReservations.end()) {
169 77 : for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
170 77 : Reservation* res = *itRes;
171 : if (res->persons.count(person) != 0
172 77 : && res->from == from
173 77 : && res->to == to
174 77 : && res->fromPos == fromPos
175 77 : && res->toPos == toPos) {
176 : res->persons.erase(person);
177 77 : if (res->persons.empty()) {
178 77 : removedID = res->id;
179 77 : it->second.erase(itRes);
180 : // cleans up MSDispatch_Greedy
181 77 : fulfilledReservation(res);
182 77 : if (it->second.empty()) {
183 : myGroupReservations.erase(it);
184 : }
185 : }
186 : break;
187 : }
188 : }
189 : } else {
190 : auto it2 = myRunningReservations.find(group);
191 10 : if (it2 != myRunningReservations.end()) {
192 10 : for (auto item : it2->second) {
193 : const Reservation* const res = item.first;
194 : if (res->persons.count(person) != 0
195 10 : && res->from == from
196 10 : && res->to == to
197 10 : && res->fromPos == fromPos
198 10 : && res->toPos == toPos) {
199 10 : if (res->persons.size() == 1) {
200 10 : removedID = res->id;
201 : }
202 10 : item.second->cancelCustomer(person); // will delete res via fulfilledReservation if necessary
203 : break;
204 : }
205 : }
206 : }
207 : }
208 87 : myHasServableReservations = myGroupReservations.size() > 0;
209 : #ifdef DEBUG_RESERVATION
210 : if (DEBUG_COND2(person)) std::cout << SIMTIME
211 : << " removeReservation p=" << person->getID()
212 : << " from=" << from->getID() << " fromPos=" << fromPos
213 : << " to=" << to->getID() << " toPos=" << toPos
214 : << " group=" << group
215 : << " removedID=" << removedID
216 : << " hasServable=" << myHasServableReservations
217 : << "\n";
218 : #endif
219 87 : return removedID;
220 : }
221 :
222 :
223 : Reservation*
224 150 : MSDispatch::updateReservationFromPos(MSTransportable* person,
225 : const MSEdge* from, double fromPos,
226 : const MSEdge* to, double toPos,
227 : std::string group, double newFromPos) {
228 150 : if (group == "") {
229 : // the default empty group implies, no grouping is wanted (and
230 : // transportable ids are unique)
231 : group = person->getID();
232 : }
233 : Reservation* result = nullptr;
234 150 : std::string updatedID = "";
235 : auto it = myGroupReservations.find(group);
236 150 : if (it != myGroupReservations.end()) {
237 66 : for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
238 66 : Reservation* res = *itRes;
239 : // TODO: if there is already a reservation with the newFromPos, add to this reservation
240 : // TODO: if there are other persons in this reservation, create a new reservation for the updated one
241 : if (res->persons.count(person) != 0
242 66 : && res->from == from
243 66 : && res->to == to
244 66 : && res->fromPos == fromPos
245 66 : && res->toPos == toPos) {
246 : // update fromPos
247 66 : res->fromPos = newFromPos;
248 : result = res;
249 66 : updatedID = res->id;
250 : break;
251 : }
252 : }
253 : }
254 : #ifdef DEBUG_RESERVATION
255 : if (DEBUG_COND2(person)) std::cout << SIMTIME
256 : << " updateReservationFromPos p=" << person->getID()
257 : << " from=" << from->getID() << " fromPos=" << fromPos
258 : << " to=" << to->getID() << " toPos=" << toPos
259 : << " group=" << group
260 : << " newFromPos=" << newFromPos
261 : << " updatedID=" << updatedID
262 : << "\n";
263 : #endif
264 150 : return result;
265 : }
266 :
267 :
268 : std::vector<Reservation*>
269 19526 : MSDispatch::getReservations() {
270 : std::vector<Reservation*> reservations;
271 38876 : for (const auto& it : myGroupReservations) {
272 19350 : reservations.insert(reservations.end(), it.second.begin(), it.second.end());
273 : }
274 19526 : return reservations;
275 0 : }
276 :
277 :
278 : std::vector<const Reservation*>
279 4214 : MSDispatch::getRunningReservations() {
280 : std::vector<const Reservation*> result;
281 9551 : for (auto item : myRunningReservations) {
282 10674 : for (auto item2 : item.second) {
283 5337 : result.push_back(item2.first);
284 : }
285 : }
286 4214 : return result;
287 0 : }
288 :
289 :
290 : void
291 2344 : MSDispatch::servedReservation(const Reservation* res, MSDevice_Taxi* taxi) {
292 2344 : auto itR = myRunningReservations.find(res->group);
293 2344 : if (itR != myRunningReservations.end() && itR->second.count(res) != 0) {
294 : return; // was redispatch
295 : }
296 2220 : auto it = myGroupReservations.find(res->group);
297 2220 : if (it == myGroupReservations.end()) {
298 0 : throw ProcessError(TL("Inconsistent group reservations."));
299 : }
300 2220 : auto it2 = std::find(it->second.begin(), it->second.end(), res);
301 2220 : if (it2 == it->second.end()) {
302 0 : throw ProcessError(TL("Inconsistent group reservations (2)."));
303 : }
304 2220 : myRunningReservations[res->group][res] = taxi;
305 2220 : const_cast<Reservation*>(*it2)->state = Reservation::ASSIGNED;
306 2220 : it->second.erase(it2);
307 2220 : if (it->second.empty()) {
308 : myGroupReservations.erase(it);
309 : }
310 : }
311 :
312 :
313 : void
314 4 : MSDispatch::swappedRunning(const Reservation* res, MSDevice_Taxi* taxi) {
315 4 : myRunningReservations[res->group][res] = taxi;
316 4 : }
317 :
318 :
319 : void
320 2268 : MSDispatch::fulfilledReservation(const Reservation* res) {
321 2268 : myRunningReservations[res->group].erase(res);
322 2268 : if (myRunningReservations[res->group].empty()) {
323 : myRunningReservations.erase(res->group);
324 : }
325 2268 : delete res;
326 2268 : }
327 :
328 :
329 : SUMOAbstractRouter<MSEdge, SUMOVehicle>&
330 14313 : MSDispatch::getRouter() const {
331 28626 : return myRoutingMode == 1 ? MSRoutingEngine::getRouterTT(0, SVC_TAXI) : MSNet::getInstance()->getRouterTT(0);
332 : }
333 :
334 :
335 : SUMOTime
336 3489 : MSDispatch::computePickupTime(SUMOTime t, const MSDevice_Taxi* taxi, const Reservation& res, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router) {
337 : ConstMSEdgeVector edges;
338 3489 : double fromPos = taxi->getHolder().getPositionOnLane() - NUMERICAL_EPS;
339 3489 : const MSEdge* from = *taxi->getHolder().getRerouteOrigin();
340 3489 : const bool originDiffers = from != taxi->getHolder().getEdge();
341 6945 : router.compute(from, originDiffers ? 0 : fromPos, res.from, res.fromPos, &taxi->getHolder(), t, edges, true);
342 3489 : if (edges.empty()) {
343 : return SUMOTime_MAX;
344 : } else {
345 2581 : if (originDiffers) {
346 : assert(from == *(taxi->getHolder().getCurrentRouteEdge() + 1));
347 33 : edges.insert(edges.begin(), taxi->getHolder().getEdge());
348 : }
349 2581 : return TIME2STEPS(router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, res.fromPos, t));
350 : }
351 3489 : }
352 :
353 :
354 : bool
355 3093 : MSDispatch::isReachable(SUMOTime t, const MSDevice_Taxi* taxi, const Reservation& res, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router) {
356 : ConstMSEdgeVector edges;
357 3093 : router.compute(res.from, res.fromPos, res.to, res.toPos, &taxi->getHolder(), t, edges, true);
358 3093 : return !edges.empty();
359 3093 : }
360 :
361 :
362 : double
363 440 : MSDispatch::computeDetourTime(SUMOTime t, SUMOTime viaTime, const MSDevice_Taxi* taxi,
364 : const MSEdge* from, double fromPos,
365 : const MSEdge* via, double viaPos,
366 : const MSEdge* to, double toPos,
367 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router,
368 : double& timeDirect) {
369 : ConstMSEdgeVector edges;
370 440 : if (timeDirect < 0) {
371 384 : router.compute(from, fromPos, to, toPos, &taxi->getHolder(), t, edges, true);
372 384 : timeDirect = router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, toPos, t);
373 : edges.clear();
374 : }
375 :
376 440 : router.compute(from, fromPos, via, viaPos, &taxi->getHolder(), t, edges, true);
377 440 : const double start = STEPS2TIME(t);
378 440 : const double leg1 = router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, viaPos, t);
379 : #ifdef DEBUG_DETOUR
380 : std::cout << " leg1=" << toString(edges) << " startPos=" << fromPos << " toPos=" << viaPos << " time=" << leg1 << "\n";
381 : #endif
382 440 : const double wait = MAX2(0.0, STEPS2TIME(viaTime) - (start + leg1));
383 : edges.clear();
384 440 : const SUMOTime timeContinue = TIME2STEPS(start + leg1 + wait);
385 440 : router.compute(via, viaPos, to, toPos, &taxi->getHolder(), timeContinue, edges, true);
386 440 : const double leg2 = router.recomputeCostsPos(edges, &taxi->getHolder(), viaPos, toPos, timeContinue);
387 440 : const double timeDetour = leg1 + wait + leg2;
388 : #ifdef DEBUG_DETOUR
389 : std::cout << " leg2=" << toString(edges) << " startPos=" << viaPos << " toPos=" << toPos << " time=" << leg2 << "\n";
390 : std::cout << " t=" << STEPS2TIME(t) << " vt=" << STEPS2TIME(viaTime)
391 : << " from=" << from->getID() << " to=" << to->getID() << " via=" << via->getID()
392 : << " direct=" << timeDirect << " detour=" << timeDetour << " wait=" << wait << "\n";
393 : #endif
394 440 : return timeDetour;
395 440 : }
396 :
397 :
398 : int
399 3996 : MSDispatch::remainingCapacity(const MSDevice_Taxi* taxi, const Reservation* res) {
400 : assert(res->persons.size() > 0);
401 3996 : return ((*res->persons.begin())->isPerson()
402 3996 : ? taxi->getHolder().getVehicleType().getPersonCapacity()
403 192 : : taxi->getHolder().getVehicleType().getContainerCapacity()) - (int)res->persons.size();
404 : }
405 :
406 :
407 : /****************************************************************************/
|
