Eclipse SUMO - Simulation of Urban MObility
MSDispatch_GreedyShared.cpp
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2007-2020 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 /****************************************************************************/
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>
26 #include "MSRoutingEngine.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 MSDispatch_GreedyShared::dispatch(MSDevice_Taxi* taxi, std::vector<Reservation*>::iterator& resIt, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router, std::vector<Reservation*>& reservations) {
40  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  const int capacityLeft = taxi->getHolder().getVehicleType().getPersonCapacity() - (int)res->persons.size();
48  // check whether the ride can be shared
49  int shareCase = 0;
50  Reservation* res2 = nullptr;
51  double absLoss = 0;
52  double relLoss = 0;
53  double absLoss2 = 0;
54  double relLoss2 = 0;
55  double directTime = -1; // only computed once for res
56  double directTime2 = -1;
57  for (auto it2 = resIt + 1; it2 != reservations.end(); it2++) {
58  res2 = *it2;
59  if (capacityLeft < (int)res2->persons.size()) {
60  continue;
61  }
62  // res picks up res2 on the way
63  directTime2 = -1; // reset for new candidate
64  const SUMOTime startPickup = MAX2(now, res->pickupTime);
65  const double detourTime = computeDetourTime(startPickup, res2->pickupTime, taxi,
66  res->from, res->fromPos, res2->from, res2->fromPos, res->to, res->toPos, router, directTime);
67  const double absLossPickup = detourTime - directTime;
68  const double relLossPickup = absLossPickup / directTime;
69 
70 #ifdef DEBUG_DISPATCH
71  if (DEBUG_COND2(person)) std::cout << " consider sharing ride with " << toString(res2->persons)
72  << " absLossPickup=" << absLossPickup
73  << " relLossPickup=" << relLossPickup
74  << "\n";
75 #endif
76  if (absLossPickup < myAbsoluteLossThreshold && relLossPickup < myRelativeLossThreshold) {
77  const SUMOTime startDropOff = MAX2(now, res2->pickupTime);
78  double directTimeTmp = -1; // direct time from picking up res2 to dropping of res
79  // case 1: res2 is dropped off before res (more detour for res)
80  double detourTime2 = computeDetourTime(startDropOff, startDropOff, taxi,
81  res2->from, res2->fromPos, res2->to, res2->toPos, res->to, res->toPos, router, directTimeTmp);
82  const double absLoss_c1 = absLossPickup + (detourTime2 - directTimeTmp);
83  const double relLoss_c1 = absLoss_c1 / directTime;
84 
85  // case 2: res2 is dropped off after res (detour for res2)
86  double detourTime3 = computeDetourTime(startDropOff, startDropOff, taxi,
87  res2->from, res2->fromPos, res->to, res->toPos, res2->to, res2->toPos, router, directTime2);
88  const double absLoss_c2 = detourTime3 - directTime2;
89  const double relLoss_c2 = absLoss_c2 / directTime2;
90 
91  if (absLoss_c2 <= absLoss_c1 && absLoss_c2 < myAbsoluteLossThreshold && relLoss_c2 < myRelativeLossThreshold) {
92  shareCase = 2;
93  taxi->dispatchShared({res, res2, res, res2});
94  absLoss = absLossPickup;
95  relLoss = relLossPickup;
96  absLoss2 = absLoss_c2;
97  relLoss2 = relLoss_c2;
98  } else if (absLoss_c1 < myAbsoluteLossThreshold && relLoss_c1 < myRelativeLossThreshold) {
99  shareCase = 1;
100  taxi->dispatchShared({res, res2, res2, res});
101  absLoss = absLoss_c1;
102  relLoss = relLoss_c1;
103  absLoss2 = 0;
104  relLoss2 = 0;
105  }
106  if (shareCase != 0) {
107  reservations.erase(it2); // (it before it2) stays valid
108  break;
109  } else {
110 #ifdef DEBUG_DISPATCH
111  if (DEBUG_COND2(person)) std::cout << " rejected:"
112  << " absLoss_c1=" << absLoss_c1
113  << " relLoss_c1=" << relLoss_c1
114  << " absLoss_c2=" << absLoss_c2
115  << " relLoss_c2=" << relLoss_c2
116  << "\n";
117 #endif
118  }
119  }
120  }
121  if (shareCase != 0) {
122  if (myOutput != nullptr) {
123  myOutput->writeXMLHeader("DispatchInfo_GreedyShared", "");
124  myOutput->openTag("dispatchShared");
125  myOutput->writeAttr("time", time2string(now));
126  myOutput->writeAttr("id", taxi->getHolder().getID());
127  myOutput->writeAttr("persons", toString(res->persons));
128  myOutput->writeAttr("sharingPersons", toString(res2->persons));
129  myOutput->writeAttr("type", shareCase);
130  myOutput->writeAttr("absLoss", absLoss);
131  myOutput->writeAttr("relLoss", relLoss);
132  myOutput->writeAttr("absLoss2", absLoss2);
133  myOutput->writeAttr("relLoss2", relLoss2);
134  myOutput->closeTag();
135  }
136 #ifdef DEBUG_DISPATCH
137  if (DEBUG_COND2(person)) std::cout << " sharing ride with " << toString(res2->persons)
138  << " type=" << shareCase
139  << " absLoss=" << absLoss << " relLoss=" << relLoss
140  << " absLoss2=" << absLoss2 << " relLoss2=" << relLoss2
141  << "\n";
142 #endif
143  servedReservation(res2); // deleting res2
144  } else {
145  taxi->dispatch(*res);
146  }
147  servedReservation(res); // deleting res
148  resIt = reservations.erase(resIt);
149  return shareCase == 0 ? 1 : 2;
150 }
151 
152 
153 /****************************************************************************/
#define DEBUG_COND2(obj)
std::string time2string(SUMOTime t)
convert SUMOTime to string
Definition: SUMOTime.cpp:68
#define SIMTIME
Definition: SUMOTime.h:60
long long int SUMOTime
Definition: SUMOTime.h:31
T MAX2(T a, T b)
Definition: StdDefs.h:79
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:44
A device which collects info on the vehicle trip (mainly on departure and arrival)
Definition: MSDevice_Taxi.h:48
void dispatch(const Reservation &res)
service the given reservation
void dispatchShared(const std::vector< const Reservation * > &reservations)
service the given reservations
const double myRelativeLossThreshold
relative time threshold for declining shared ride
const double myAbsoluteLossThreshold
absolute time threshold for declining shared ride in s
virtual int dispatch(MSDevice_Taxi *taxi, std::vector< Reservation * >::iterator &resIt, SUMOAbstractRouter< MSEdge, SUMOVehicle > &router, std::vector< Reservation * > &reservations)
trigger taxi dispatch.
OutputDevice * myOutput
optional file output for dispatch information
Definition: MSDispatch.h:145
static double computeDetourTime(SUMOTime t, SUMOTime viaTime, const MSDevice_Taxi *taxi, const MSEdge *from, double fromPos, const MSEdge *via, double viaPos, const MSEdge *to, double toPos, SUMOAbstractRouter< MSEdge, SUMOVehicle > &router, double &timeDirect)
compute directTime and detourTime
Definition: MSDispatch.cpp:148
void servedReservation(const Reservation *res)
Definition: MSDispatch.cpp:121
static MSNet * getInstance()
Returns the pointer to the unique instance of MSNet (singleton).
Definition: MSNet.cpp:171
SUMOTime getCurrentTimeStep() const
Returns the current simulation step.
Definition: MSNet.h:313
SUMOVehicle & getHolder() const
Returns the vehicle that holds this device.
int getPersonCapacity() const
Get this vehicle type's person capacity.
const std::string & getID() const
Returns the id.
Definition: Named.h:73
bool writeXMLHeader(const std::string &rootElement, const std::string &schemaFile, std::map< SumoXMLAttr, std::string > attrs=std::map< SumoXMLAttr, std::string >())
Writes an XML header with optional configuration.
OutputDevice & openTag(const std::string &xmlElement)
Opens an XML tag.
OutputDevice & writeAttr(const SumoXMLAttr attr, const T &val)
writes a named attribute
Definition: OutputDevice.h:239
bool closeTag(const std::string &comment="")
Closes the most recently opened tag and optionally adds a comment.
virtual const MSVehicleType & getVehicleType() const =0
Returns the object's "vehicle" type.
SUMOTime pickupTime
Definition: MSDispatch.h:58
const MSEdge * to
Definition: MSDispatch.h:61
double fromPos
Definition: MSDispatch.h:60
const MSEdge * from
Definition: MSDispatch.h:59
std::set< MSTransportable * > persons
Definition: MSDispatch.h:56
double toPos
Definition: MSDispatch.h:62