Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2007-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 MSDispatch_RouteExtension.cpp
15 : /// @author Michael Behrisch
16 : /// @date 06.08.2020
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_RouteExtension.h"
28 :
29 : //#define DEBUG_DISPATCH
30 : //#define DEBUG_COND2(obj) (obj->getID() == "p0")
31 : #define DEBUG_COND2(obj) (true)
32 :
33 :
34 : // ===========================================================================
35 : // method definitions
36 : // ===========================================================================
37 : void
38 809 : MSDispatch_RouteExtension::findInsertionPoint(std::vector<const Reservation*>::iterator& resIt, EdgePosVector::iterator& edgeIt,
39 : const EdgePosVector::iterator& edgeEnd, ConstMSEdgeVector& route,
40 : const MSEdge* newEdge, const double newPos) const {
41 3648 : for (const MSEdge* edge : route) {
42 10076 : while (edgeIt != edgeEnd && edge == edgeIt->first) {
43 6434 : if (edge == newEdge && edgeIt->second > newPos) {
44 : break;
45 : }
46 : resIt++;
47 : edgeIt++;
48 : }
49 3648 : if (edge == newEdge) {
50 : break;
51 : }
52 : }
53 809 : }
54 :
55 :
56 : int
57 131 : MSDispatch_RouteExtension::dispatch(MSDevice_Taxi* taxi, std::vector<Reservation*>::iterator& resIt, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router, std::vector<Reservation*>& reservations) {
58 131 : const Reservation* const res = *resIt;
59 : #ifdef DEBUG_DISPATCH
60 : if (DEBUG_COND2(person)) {
61 : std::cout << SIMTIME << " dispatch taxi=" << taxi->getHolder().getID() << " person=" << toString(res->persons) << "\n";
62 : }
63 : #endif
64 131 : const SUMOTime now = MSNet::getInstance()->getCurrentTimeStep();
65 131 : const bool isPerson = (*res->persons.begin())->isPerson();
66 131 : int capacityLeft = remainingCapacity(taxi, res);
67 131 : std::vector<const Reservation*> sequence{ res, res };
68 131 : std::vector<const Reservation*> toRemove{ res };
69 131 : EdgePosVector posSequence({ std::make_pair(res->from, res->fromPos), std::make_pair(res->to, res->toPos) });
70 131 : const Reservation* first = sequence.front();
71 131 : const Reservation* last = sequence.back();
72 : ConstMSEdgeVector route;
73 131 : router.compute(first->from, first->fromPos, last->to, last->toPos, &taxi->getHolder(), MAX2(now, first->pickupTime), route);
74 : // check whether the ride can be shared
75 663 : for (auto it2 = resIt + 1; it2 != reservations.end();) {
76 547 : Reservation* const res2 = *it2;
77 547 : const bool isPerson2 = (*res2->persons.begin())->isPerson();
78 547 : if (capacityLeft < (int)res2->persons.size() || isPerson != isPerson2 || !taxi->compatibleLine(res2)) {
79 : it2++;
80 0 : continue;
81 : }
82 : // check whether res2 picks up or gets picked up on the way
83 : ConstMSEdgeVector route2;
84 : // TODO It may be more efficient to check first whether from and to are already in the route
85 547 : router.compute(res2->from, res2->fromPos, res2->to, res2->toPos, &taxi->getHolder(), MAX2(now, res2->pickupTime), route2);
86 547 : const bool pickup = std::find(route.begin(), route.end(), res2->from) != route.end();
87 547 : const bool dropoff = std::find(route.begin(), route.end(), res2->to) != route.end();
88 547 : const bool pickup2 = std::find(route2.begin(), route2.end(), first->from) != route2.end();
89 547 : const bool dropoff2 = std::find(route2.begin(), route2.end(), last->to) != route2.end();
90 : #ifdef DEBUG_DISPATCH
91 : if (DEBUG_COND2(person)) std::cout << " consider sharing ride with " << toString(res2->persons)
92 : << " from=" << res2->from->getID() << ":" << res2->fromPos << " to=" << res2->to->getID() << ":" << res2->toPos
93 : << " pickup=" << pickup << " startFirst=" << pickup2
94 : << " dropoff=" << dropoff << " endLast=" << dropoff2
95 : << "\n";
96 : #endif
97 547 : if ((pickup || pickup2) && (dropoff || dropoff2)) {
98 427 : std::vector<const Reservation*>::iterator resSeqIt = sequence.begin();
99 427 : EdgePosVector::iterator edgeIt = posSequence.begin();
100 427 : if (pickup) {
101 : // new reservation gets picked up
102 392 : findInsertionPoint(resSeqIt, edgeIt, posSequence.end(), route, res2->from, res2->fromPos);
103 : }
104 427 : resSeqIt = sequence.insert(resSeqIt, res2) + 1;
105 427 : edgeIt = posSequence.insert(edgeIt, std::make_pair(res2->from, res2->fromPos)) + 1;
106 427 : if (dropoff) {
107 : // new reservation drops off and route continues
108 417 : findInsertionPoint(resSeqIt, edgeIt, posSequence.end(), route, res2->to, res2->toPos);
109 417 : sequence.insert(resSeqIt, res2);
110 417 : posSequence.insert(edgeIt, std::make_pair(res2->to, res2->toPos));
111 : } else {
112 : // new reservation ends last
113 10 : sequence.push_back(res2);
114 10 : posSequence.push_back(std::make_pair(res2->to, res2->toPos));
115 : }
116 427 : toRemove.push_back(res2);
117 : it2 = reservations.erase(it2); // (resIt before it2) stays valid
118 : // TODO we have more capacity if some pickup is after an earlier dropoff
119 427 : capacityLeft -= (int)res2->persons.size();
120 427 : if (capacityLeft == 0) {
121 : break;
122 : }
123 : route.clear();
124 412 : first = sequence.front();
125 412 : last = sequence.back();
126 : // TODO this is wrong for non linear networks! should be reusing the route snippets from above
127 412 : router.compute(first->from, first->fromPos, last->to, last->toPos, &taxi->getHolder(), MAX2(now, first->pickupTime), route);
128 412 : } else {
129 : it2++;
130 : }
131 547 : }
132 131 : if (sequence.size() > 2) {
133 83 : taxi->dispatchShared(sequence);
134 83 : if (myOutput != nullptr) {
135 120 : myOutput->writeXMLHeader("DispatchInfo_RouteExtension", "");
136 60 : myOutput->openTag("dispatchShared");
137 120 : myOutput->writeAttr("time", time2string(now));
138 60 : myOutput->writeAttr("id", taxi->getHolder().getID());
139 120 : myOutput->writeAttr("persons", toString(res->persons));
140 120 : myOutput->writeAttr("sharingPersons", toString(sequence));
141 60 : myOutput->writeAttr("type", "routeExtension");
142 120 : myOutput->closeTag();
143 : }
144 : #ifdef DEBUG_DISPATCH
145 : if (DEBUG_COND2(person)) std::cout << " sharing ride with " << toString(sequence)
146 : << "\n";
147 : #endif
148 : } else {
149 48 : taxi->dispatch(*res);
150 : }
151 689 : for (const Reservation* r : toRemove) {
152 558 : servedReservation(r, taxi); // deleting r
153 : }
154 131 : resIt = reservations.erase(resIt);
155 131 : return (int)toRemove.size();
156 131 : }
157 :
158 :
159 : /****************************************************************************/
|
