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_GreedyShared.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_GreedyShared.h"
28 :
29 : //#define DEBUG_DISPATCH
30 : //#define DEBUG_COND2(obj) (obj->getID() == "p0")
31 : #define DEBUG_COND2(obj) (true)
32 :
33 :
34 : // ===========================================================================
35 : // MSDispatch_GreedyShared methods
36 : // ===========================================================================
37 :
38 : int
39 162 : MSDispatch_GreedyShared::dispatch(MSDevice_Taxi* taxi, std::vector<Reservation*>::iterator& resIt, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router, std::vector<Reservation*>& reservations) {
40 162 : const Reservation* const res = *resIt;
41 : #ifdef DEBUG_DISPATCH
42 : if (DEBUG_COND2(person)) {
43 : std::cout << SIMTIME << " dispatch taxi=" << taxi->getHolder().getID() << " person=" << toString(res->persons) << "\n";
44 : }
45 : #endif
46 162 : const bool isPerson = (*res->persons.begin())->isPerson();
47 162 : const int capacityLeft = remainingCapacity(taxi, res);
48 162 : const SUMOTime now = MSNet::getInstance()->getCurrentTimeStep();
49 : // check whether the ride can be shared
50 162 : int shareCase = 0;
51 : Reservation* res2 = nullptr;
52 162 : double absLoss = 0;
53 162 : double relLoss = 0;
54 162 : double absLoss2 = 0;
55 162 : double relLoss2 = 0;
56 162 : double directTime = -1; // only computed once for res
57 162 : double directTime2 = -1;
58 248 : for (auto it2 = resIt + 1; it2 != reservations.end(); it2++) {
59 182 : res2 = *it2;
60 182 : const bool isPerson2 = (*res2->persons.begin())->isPerson();
61 :
62 182 : if (capacityLeft < (int)res2->persons.size() || isPerson != isPerson2 || !taxi->compatibleLine(res2)) {
63 : // do not try to mix person and container dispatch
64 0 : continue;
65 : }
66 : // res picks up res2 on the way
67 182 : directTime2 = -1; // reset for new candidate
68 182 : const SUMOTime startPickup = MAX2(now, res->pickupTime);
69 182 : const double detourTime = computeDetourTime(startPickup, res2->pickupTime, taxi,
70 182 : res->from, res->fromPos, res2->from, res2->fromPos, res->to, res->toPos, router, directTime);
71 182 : const double absLossPickup = detourTime - directTime;
72 182 : const double relLossPickup = absLossPickup / directTime;
73 :
74 : #ifdef DEBUG_DISPATCH
75 : if (DEBUG_COND2(person)) std::cout << " consider sharing ride with " << toString(res2->persons)
76 : << " absLossPickup=" << absLossPickup
77 : << " relLossPickup=" << relLossPickup
78 : << "\n";
79 : #endif
80 182 : if (absLossPickup < myAbsoluteLossThreshold && relLossPickup < myRelativeLossThreshold) {
81 108 : const SUMOTime startDropOff = MAX2(now, res2->pickupTime);
82 108 : double directTimeTmp = -1; // direct time from picking up res2 to dropping of res
83 : // case 1: res2 is dropped off before res (more detour for res)
84 108 : double detourTime2 = computeDetourTime(startDropOff, startDropOff, taxi,
85 108 : res2->from, res2->fromPos, res2->to, res2->toPos, res->to, res->toPos, router, directTimeTmp);
86 108 : const double absLoss_c1 = absLossPickup + (detourTime2 - directTimeTmp);
87 108 : const double relLoss_c1 = absLoss_c1 / directTime;
88 :
89 : // case 2: res2 is dropped off after res (detour for res2)
90 108 : double detourTime3 = computeDetourTime(startDropOff, startDropOff, taxi,
91 108 : res2->from, res2->fromPos, res->to, res->toPos, res2->to, res2->toPos, router, directTime2);
92 108 : const double absLoss_c2 = detourTime3 - directTime2;
93 108 : const double relLoss_c2 = absLoss_c2 / directTime2;
94 :
95 108 : if (absLoss_c2 <= absLoss_c1 && absLoss_c2 < myAbsoluteLossThreshold && relLoss_c2 < myRelativeLossThreshold) {
96 66 : shareCase = 2;
97 66 : taxi->dispatchShared({res, res2, res, res2});
98 66 : absLoss = absLossPickup;
99 66 : relLoss = relLossPickup;
100 66 : absLoss2 = absLoss_c2;
101 66 : relLoss2 = relLoss_c2;
102 42 : } else if (absLoss_c1 < myAbsoluteLossThreshold && relLoss_c1 < myRelativeLossThreshold) {
103 30 : shareCase = 1;
104 30 : taxi->dispatchShared({res, res2, res2, res});
105 30 : absLoss = absLoss_c1;
106 30 : relLoss = relLoss_c1;
107 30 : absLoss2 = 0;
108 30 : relLoss2 = 0;
109 : }
110 108 : if (shareCase != 0) {
111 : reservations.erase(it2); // (it before it2) stays valid
112 96 : break;
113 : } else {
114 : #ifdef DEBUG_DISPATCH
115 : if (DEBUG_COND2(person)) std::cout << " rejected:"
116 : << " absLoss_c1=" << absLoss_c1
117 : << " relLoss_c1=" << relLoss_c1
118 : << " absLoss_c2=" << absLoss_c2
119 : << " relLoss_c2=" << relLoss_c2
120 : << "\n";
121 : #endif
122 : }
123 : }
124 : }
125 162 : if (shareCase != 0) {
126 96 : if (myOutput != nullptr) {
127 84 : myOutput->openTag("dispatchShared");
128 168 : myOutput->writeAttr("time", time2string(now));
129 84 : myOutput->writeAttr("id", taxi->getHolder().getID());
130 168 : myOutput->writeAttr("persons", toString(res->persons));
131 168 : myOutput->writeAttr("sharingPersons", toString(res2->persons));
132 84 : myOutput->writeAttr("type", shareCase);
133 84 : myOutput->writeAttr("absLoss", absLoss);
134 84 : myOutput->writeAttr("relLoss", relLoss);
135 84 : myOutput->writeAttr("absLoss2", absLoss2);
136 84 : myOutput->writeAttr("relLoss2", relLoss2);
137 168 : myOutput->closeTag();
138 : }
139 : #ifdef DEBUG_DISPATCH
140 : if (DEBUG_COND2(person)) std::cout << " sharing ride with " << toString(res2->persons)
141 : << " type=" << shareCase
142 : << " absLoss=" << absLoss << " relLoss=" << relLoss
143 : << " absLoss2=" << absLoss2 << " relLoss2=" << relLoss2
144 : << "\n";
145 : #endif
146 96 : servedReservation(res2); // deleting res2
147 : } else {
148 66 : taxi->dispatch(*res);
149 : }
150 162 : servedReservation(res); // deleting res
151 162 : resIt = reservations.erase(resIt);
152 258 : return shareCase == 0 ? 1 : 2;
153 : }
154 :
155 :
156 : /****************************************************************************/
|
