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_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 1204 : 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 6124 : for (const MSEdge* edge : route) {
42 12750 : while (edgeIt != edgeEnd && edge == edgeIt->first) {
43 7024 : if (edge == newEdge && edgeIt->second > newPos) {
44 : break;
45 : }
46 : resIt++;
47 : edgeIt++;
48 : }
49 6124 : if (edge == newEdge) {
50 : break;
51 : }
52 : }
53 1204 : }
54 :
55 :
56 : int
57 92 : MSDispatch_RouteExtension::dispatch(MSDevice_Taxi* taxi, std::vector<Reservation*>::iterator& resIt, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router, std::vector<Reservation*>& reservations) {
58 92 : 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 92 : const SUMOTime now = MSNet::getInstance()->getCurrentTimeStep();
65 92 : const bool isPerson = (*res->persons.begin())->isPerson();
66 92 : int capacityLeft = remainingCapacity(taxi, res);
67 92 : std::vector<const Reservation*> sequence{ res, res };
68 92 : std::vector<const Reservation*> toRemove{ res };
69 92 : EdgePosVector posSequence({ std::make_pair(res->from, res->fromPos), std::make_pair(res->to, res->toPos) });
70 92 : const Reservation* first = sequence.front();
71 92 : const Reservation* last = sequence.back();
72 : ConstMSEdgeVector route;
73 184 : 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 828 : for (auto it2 = resIt + 1; it2 != reservations.end();) {
76 766 : Reservation* const res2 = *it2;
77 766 : const bool isPerson2 = (*res2->persons.begin())->isPerson();
78 766 : 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 766 : router.compute(res2->from, res2->fromPos, res2->to, res2->toPos, &taxi->getHolder(), MAX2(now, res2->pickupTime), route2);
86 766 : const bool pickup = std::find(route.begin(), route.end(), res2->from) != route.end();
87 766 : const bool dropoff = std::find(route.begin(), route.end(), res2->to) != route.end();
88 : #ifdef DEBUG_DISPATCH
89 : if (DEBUG_COND2(person)) std::cout << " consider sharing ride with " << toString(res2->persons)
90 : << " pickup=" << pickup << " startFirst=" << (std::find(route2.begin(), route2.end(), first->from) != route2.end())
91 : << " dropoff=" << dropoff << " endLast=" << (std::find(route2.begin(), route2.end(), last->to) != route2.end())
92 : << "\n";
93 : #endif
94 766 : if ((pickup || std::find(route2.begin(), route2.end(), first->from) != route2.end()) &&
95 766 : (dropoff || std::find(route2.begin(), route2.end(), last->to) != route2.end())) {
96 626 : std::vector<const Reservation*>::iterator resSeqIt = sequence.begin();
97 626 : EdgePosVector::iterator edgeIt = posSequence.begin();
98 626 : if (pickup) {
99 : // new reservation gets picked up
100 578 : findInsertionPoint(resSeqIt, edgeIt, posSequence.end(), route, res2->from, res2->fromPos);
101 : }
102 626 : resSeqIt = sequence.insert(resSeqIt, res2) + 1;
103 626 : edgeIt = posSequence.insert(edgeIt, std::make_pair(res2->from, res2->fromPos)) + 1;
104 626 : if (dropoff) {
105 : // new reservation drops off and route continues
106 626 : findInsertionPoint(resSeqIt, edgeIt, posSequence.end(), route, res2->to, res2->toPos);
107 626 : sequence.insert(resSeqIt, res2);
108 626 : posSequence.insert(edgeIt, std::make_pair(res2->from, res2->fromPos));
109 : } else {
110 : // new reservation ends last
111 0 : sequence.push_back(res2);
112 0 : posSequence.push_back(std::make_pair(res2->to, res2->toPos));
113 : }
114 626 : toRemove.push_back(res2);
115 : it2 = reservations.erase(it2); // (resIt before it2) stays valid
116 : // TODO we have more capacity if some pickup is after an earlier dropoff
117 626 : capacityLeft -= (int)res2->persons.size();
118 626 : if (capacityLeft == 0) {
119 : break;
120 : }
121 : route.clear();
122 596 : first = sequence.front();
123 596 : last = sequence.back();
124 : // TODO this is wrong for non linear networks! should be reusing the route snippets from above
125 596 : router.compute(first->from, first->fromPos, last->to, last->toPos, &taxi->getHolder(), MAX2(now, first->pickupTime), route);
126 : } else {
127 : it2++;
128 : }
129 : }
130 92 : if (sequence.size() > 2) {
131 48 : taxi->dispatchShared(sequence);
132 48 : if (myOutput != nullptr) {
133 16 : myOutput->writeXMLHeader("DispatchInfo_RouteExtension", "");
134 8 : myOutput->openTag("dispatchShared");
135 16 : myOutput->writeAttr("time", time2string(now));
136 8 : myOutput->writeAttr("id", taxi->getHolder().getID());
137 16 : myOutput->writeAttr("persons", toString(res->persons));
138 16 : myOutput->writeAttr("sharingPersons", toString(sequence));
139 8 : myOutput->writeAttr("type", "routeExtension");
140 16 : myOutput->closeTag();
141 : }
142 : #ifdef DEBUG_DISPATCH
143 : if (DEBUG_COND2(person)) std::cout << " sharing ride with " << toString(sequence)
144 : << "\n";
145 : #endif
146 : } else {
147 44 : taxi->dispatch(*res);
148 : }
149 810 : for (const Reservation* r : toRemove) {
150 718 : servedReservation(r); // deleting r
151 : }
152 92 : resIt = reservations.erase(resIt);
153 184 : return (int)toRemove.size();
154 : }
155 :
156 :
157 : /****************************************************************************/
|
