Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2007-2024 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/transportables/MSTransportable.h>
26 : #include "MSRoutingEngine.h"
27 : #include "MSDispatch.h"
28 :
29 : //#define DEBUG_RESERVATION
30 : //#define DEBUG_DETOUR
31 : //#define DEBUG_COND2(obj) (obj->getID() == "p0")
32 : #define DEBUG_COND2(obj) (true)
33 :
34 :
35 : // ===========================================================================
36 : // Reservation methods
37 : // ===========================================================================
38 :
39 : std::string
40 32 : Reservation::getID() const {
41 32 : return toString(persons);
42 : }
43 :
44 : // ===========================================================================
45 : // MSDispatch methods
46 : // ===========================================================================
47 :
48 606 : MSDispatch::MSDispatch(const Parameterised::Map& params) :
49 : Parameterised(params),
50 606 : myOutput(nullptr),
51 606 : myReservationCount(0) {
52 606 : const std::string opt = "device.taxi.dispatch-algorithm.output";
53 606 : if (OptionsCont::getOptions().isSet(opt)) {
54 192 : OutputDevice::createDeviceByOption(opt, "DispatchInfo");
55 96 : myOutput = &OutputDevice::getDeviceByOption(opt);
56 : }
57 606 : }
58 :
59 606 : MSDispatch::~MSDispatch() {
60 1410 : for (auto item : myGroupReservations) {
61 1489 : for (Reservation* res : item.second) {
62 685 : delete res;
63 : }
64 804 : }
65 : myGroupReservations.clear();
66 606 : }
67 :
68 :
69 : Reservation*
70 2951 : MSDispatch::addReservation(MSTransportable* person,
71 : SUMOTime reservationTime,
72 : SUMOTime pickupTime,
73 : SUMOTime earliestPickupTime,
74 : const MSEdge* from, double fromPos,
75 : const MSStoppingPlace* fromStop,
76 : const MSEdge* to, double toPos,
77 : const MSStoppingPlace* toStop,
78 : std::string group,
79 : const std::string& line,
80 : int maxCapacity,
81 : int maxContainerCapacity) {
82 : // no new reservation nedded if the person can be added to an existing group
83 2951 : if (group == "") {
84 : // the default empty group implies, no grouping is wanted (and
85 : // transportable ids are unique)
86 2765 : group = person->getID();
87 : }
88 : Reservation* result = nullptr;
89 : bool added = false;
90 : auto it = myGroupReservations.find(group);
91 2951 : if (it != myGroupReservations.end()) {
92 : // try to add to existing reservation
93 132 : for (Reservation* res : it->second) {
94 : if (res->persons.count(person) == 0
95 120 : && res->from == from
96 120 : && res->to == to
97 120 : && res->fromPos == fromPos
98 120 : && res->toPos == toPos) {
99 120 : if (res->persons.size() > 0 && (*res->persons.begin())->isPerson() != person->isPerson()) {
100 0 : WRITE_WARNINGF(TL("Mixing reservations of persons and containers with the same group is not supported for % and %"),
101 : (*res->persons.begin())->getID(), person->getID());
102 : }
103 234 : if ((person->isPerson() && (int)res->persons.size() >= maxCapacity) ||
104 126 : (!person->isPerson() && (int)res->persons.size() >= maxContainerCapacity)) {
105 : // split group to ensure that at least one taxi is capable of delivering group size.
106 12 : continue;
107 : }
108 : res->persons.insert(person);
109 : result = res;
110 : added = true;
111 108 : break;
112 : }
113 : }
114 : }
115 2951 : if (!added) {
116 5686 : Reservation* newRes = new Reservation(toString(myReservationCount++), {person}, reservationTime, pickupTime, earliestPickupTime, from, fromPos, fromStop, to, toPos, toStop, group, line);
117 2843 : myGroupReservations[group].push_back(newRes);
118 2843 : result = newRes;
119 : }
120 2951 : myHasServableReservations = true;
121 : #ifdef DEBUG_RESERVATION
122 : if (DEBUG_COND2(person)) std::cout << SIMTIME
123 : << " addReservation p=" << person->getID()
124 : << " rT=" << time2string(reservationTime)
125 : << " pT=" << time2string(pickupTime)
126 : << " from=" << from->getID() << " fromPos=" << fromPos
127 : << " to=" << to->getID() << " toPos=" << toPos
128 : << " group=" << group
129 : << " added=" << added
130 : << "\n";
131 : #endif
132 2951 : return result;
133 : }
134 :
135 :
136 : std::string
137 119 : MSDispatch::removeReservation(MSTransportable* person,
138 : const MSEdge* from, double fromPos,
139 : const MSEdge* to, double toPos,
140 : std::string group) {
141 119 : if (group == "") {
142 : // the default empty group implies, no grouping is wanted (and
143 : // transportable ids are unique)
144 119 : group = person->getID();
145 : }
146 119 : std::string removedID = "";
147 : auto it = myGroupReservations.find(group);
148 119 : if (it != myGroupReservations.end()) {
149 : // try to add to existing reservation
150 119 : for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
151 119 : Reservation* res = *itRes;
152 : if (res->persons.count(person) != 0
153 119 : && res->from == from
154 119 : && res->to == to
155 119 : && res->fromPos == fromPos
156 119 : && res->toPos == toPos) {
157 : res->persons.erase(person);
158 119 : if (res->persons.empty()) {
159 119 : removedID = res->id;
160 119 : fulfilledReservation(res);
161 119 : it->second.erase(itRes);
162 : }
163 : break;
164 : }
165 : }
166 : }
167 : #ifdef DEBUG_RESERVATION
168 : if (DEBUG_COND2(person)) std::cout << SIMTIME
169 : << " removeReservation p=" << person->getID()
170 : << " from=" << from->getID() << " fromPos=" << fromPos
171 : << " to=" << to->getID() << " toPos=" << toPos
172 : << " group=" << group
173 : << " removedID=" << removedID
174 : << "\n";
175 : #endif
176 119 : return removedID;
177 : }
178 :
179 :
180 : Reservation*
181 66 : MSDispatch::updateReservationFromPos(MSTransportable* person,
182 : const MSEdge* from, double fromPos,
183 : const MSEdge* to, double toPos,
184 : std::string group, double newFromPos) {
185 66 : if (group == "") {
186 : // the default empty group implies, no grouping is wanted (and
187 : // transportable ids are unique)
188 : group = person->getID();
189 : }
190 : Reservation* result = nullptr;
191 66 : std::string updatedID = "";
192 : auto it = myGroupReservations.find(group);
193 66 : if (it != myGroupReservations.end()) {
194 36 : for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
195 36 : Reservation* res = *itRes;
196 : // TODO: if there is already a reservation with the newFromPos, add to this reservation
197 : // TODO: if there are other persons in this reservation, create a new reservation for the updated one
198 : if (res->persons.count(person) != 0
199 36 : && res->from == from
200 36 : && res->to == to
201 36 : && res->fromPos == fromPos
202 36 : && res->toPos == toPos) {
203 : // update fromPos
204 36 : res->fromPos = newFromPos;
205 : result = res;
206 36 : updatedID = res->id;
207 : break;
208 : }
209 : }
210 : }
211 : #ifdef DEBUG_RESERVATION
212 : if (DEBUG_COND2(person)) std::cout << SIMTIME
213 : << " updateReservationFromPos p=" << person->getID()
214 : << " from=" << from->getID() << " fromPos=" << fromPos
215 : << " to=" << to->getID() << " toPos=" << toPos
216 : << " group=" << group
217 : << " newFromPos=" << newFromPos
218 : << " updatedID=" << updatedID
219 : << "\n";
220 : #endif
221 66 : return result;
222 : }
223 :
224 :
225 : std::vector<Reservation*>
226 10253 : MSDispatch::getReservations() {
227 : std::vector<Reservation*> reservations;
228 39368 : for (const auto& it : myGroupReservations) {
229 29115 : reservations.insert(reservations.end(), it.second.begin(), it.second.end());
230 : }
231 10253 : return reservations;
232 : }
233 :
234 :
235 : std::vector<const Reservation*>
236 3214 : MSDispatch::getRunningReservations() {
237 3214 : return std::vector<const Reservation*>(myRunningReservations.begin(), myRunningReservations.end());
238 : }
239 :
240 :
241 : void
242 2244 : MSDispatch::servedReservation(const Reservation* res) {
243 : if (myRunningReservations.count(res)) {
244 : return; // was redispatch
245 : }
246 2045 : auto it = myGroupReservations.find(res->group);
247 2045 : if (it == myGroupReservations.end()) {
248 0 : throw ProcessError(TL("Inconsistent group reservations."));
249 : }
250 2045 : auto it2 = std::find(it->second.begin(), it->second.end(), res);
251 2045 : if (it2 == it->second.end()) {
252 0 : throw ProcessError(TL("Inconsistent group reservations (2)."));
253 : }
254 : myRunningReservations.insert(*it2);
255 2045 : const_cast<Reservation*>(*it2)->state = Reservation::ASSIGNED;
256 2045 : it->second.erase(it2);
257 2045 : if (it->second.empty()) {
258 : myGroupReservations.erase(it);
259 : }
260 : }
261 :
262 :
263 : void
264 2136 : MSDispatch::fulfilledReservation(const Reservation* res) {
265 : myRunningReservations.erase(res);
266 2136 : delete res;
267 2136 : }
268 :
269 :
270 : SUMOTime
271 1509 : MSDispatch::computePickupTime(SUMOTime t, const MSDevice_Taxi* taxi, const Reservation& res, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router) {
272 : ConstMSEdgeVector edges;
273 1509 : router.compute(taxi->getHolder().getEdge(), taxi->getHolder().getPositionOnLane() - NUMERICAL_EPS,
274 1509 : res.from, res.fromPos, &taxi->getHolder(), t, edges, true);
275 3018 : return TIME2STEPS(router.recomputeCosts(edges, &taxi->getHolder(), t));
276 : }
277 :
278 :
279 : double
280 402 : MSDispatch::computeDetourTime(SUMOTime t, SUMOTime viaTime, const MSDevice_Taxi* taxi,
281 : const MSEdge* from, double fromPos,
282 : const MSEdge* via, double viaPos,
283 : const MSEdge* to, double toPos,
284 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router,
285 : double& timeDirect) {
286 : ConstMSEdgeVector edges;
287 402 : if (timeDirect < 0) {
288 366 : router.compute(from, fromPos, to, toPos, &taxi->getHolder(), t, edges, true);
289 366 : timeDirect = router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, toPos, t);
290 : edges.clear();
291 : }
292 :
293 402 : router.compute(from, fromPos, via, viaPos, &taxi->getHolder(), t, edges, true);
294 402 : const double start = STEPS2TIME(t);
295 402 : const double leg1 = router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, viaPos, t);
296 : #ifdef DEBUG_DETOUR
297 : std::cout << " leg1=" << toString(edges) << " startPos=" << fromPos << " toPos=" << viaPos << " time=" << leg1 << "\n";
298 : #endif
299 402 : const double wait = MAX2(0.0, STEPS2TIME(viaTime) - (start + leg1));
300 : edges.clear();
301 402 : const SUMOTime timeContinue = TIME2STEPS(start + leg1 + wait);
302 402 : router.compute(via, viaPos, to, toPos, &taxi->getHolder(), timeContinue, edges, true);
303 402 : const double leg2 = router.recomputeCostsPos(edges, &taxi->getHolder(), viaPos, toPos, timeContinue);
304 402 : const double timeDetour = leg1 + wait + leg2;
305 : #ifdef DEBUG_DETOUR
306 : std::cout << " leg2=" << toString(edges) << " startPos=" << viaPos << " toPos=" << toPos << " time=" << leg2 << "\n";
307 : std::cout << " t=" << STEPS2TIME(t) << " vt=" << STEPS2TIME(viaTime)
308 : << " from=" << from->getID() << " to=" << to->getID() << " via=" << via->getID()
309 : << " direct=" << timeDirect << " detour=" << timeDetour << " wait=" << wait << "\n";
310 : #endif
311 402 : return timeDetour;
312 : }
313 :
314 :
315 : int
316 1893 : MSDispatch::remainingCapacity(const MSDevice_Taxi* taxi, const Reservation* res) {
317 : assert(res->persons.size() > 0);
318 1893 : return ((*res->persons.begin())->isPerson()
319 1893 : ? taxi->getHolder().getVehicleType().getPersonCapacity()
320 60 : : taxi->getHolder().getVehicleType().getContainerCapacity()) - (int)res->persons.size();
321 : }
322 :
323 :
324 : /****************************************************************************/
|
