improve variability of randomized routes

[ambuehll]

Hello again,

Following up on an old discussion: #6808 I understand that currently, the router assigns random weights between [1 weights.random-factor] for all edges individually per vehicle and per rerouting step. The goal of this is to introduce some randomness in the route choice. The current solution is from my understanding very efficient from a computational point of view. We did some analysis on the outcomes (@henrigrossmann), where setting a very high factor only yields a small difference in travel times. This might be, among other factors, because setting the factors for every edge on average does not change the shortest path so much.

From a transport point of view, it would be nice if the weight would be applied to entire routes, or at least multiple segments. That makes it computationally (much) more complex because first k-shortest routes need to be found and then apply the weighing instead of solving the shortest path with altered edges.

The objective would be to develop a probabilistic route selection mechanism enabling certain vehicles to choose longer paths than the shortest route, with the ability to specify a percentage increase in average travel time compared to when every vehicle is taking the shortest route. This feature aims to introduce variability in route choices, resembling real-world transportation behavior where some vehicles may opt for longer routes due to habitual reasons or to avoid congestion.

Unfortunately, I am not sure what to suggest that would solve this in a simple way.

SUMO-version: 1.19

[namdre]

I think, as the random factor increases, the router should favour routes with fewer edges (because they have lower probability of receiving a very high penalty).

I would guess that the route variability also depends on the size of the network: if the routes consist of few edges on average, the randomization should pick quite different routes each time.

Both biases are undesirable.

[namdre]

The "penalty method" for obtaining good route alternatives is to apply a penalty to all edges of the previous route(s) and to increase the penalty until sufficient divergence is achieved. The size of the penalty gives a bound on how much worse the traveltime is allowed to become. marouter already supports option --paths.penalty and implements this algorithm (with a fixed penalty) for each OD-pair.
Potentially, duarouter/sumo could use some precomputed routes as input to guide randomization.

[ambuehll]

Thank you for all the explanations. We also discussed some arguments internally. Here is what we came up with so far:

1. do we understand correctly that adding a path.penalty would lead to the current route being penalized and that vehicles potentially switch to the second-best route after a re-routing step and potentially to the third-best after another re-routing step, or maybe switch back to the first one. Either way, this might also lead to unrealistic behavior. Maybe a way to stabilize the path switching is decreasing penalties over time or path... (not so sure about this though...).
2. Would it make sense to give an interval for the path.penalty so that each vehicle gets assigned a penalty which it then uses in the routing? In that way each vehicle would have a different bound on how much worse the traveltime is allowed to become. That would make sure that not all vehicles switch routes. We would be very much in favor of such a re-routing.

[namdre]

1. No, since the path.penalty is employed only in the marouter context, no rerouting takes place. The alternative routes are used in an iterative assignment context.
2. yes eventually, if we figure out a good way to use path penalties in sumo and not just in marouter.

Just to make sure that we're talking about the same thing, here is my current understanding of the possible use cases:

a) You want to run the simulation multiple times with randomized/noisy routing and different seeds. There should be meaningful variability between runs b) You want vehicles to do period rerouting in the simulation. If a vehicle decides to change the route, the new route should be different in a meaningful way

(and by meaningfully different, I mean something like a low percentage of overlap)

[ambuehll]

thanks for coming back to our points.

yes, a) and b) are correct. Our interest is mostly b).   1.  As an important detail to b) we might add, that when vehicles do period rerouting in the simulation, there should be some heterogeneity in the likelihood that different vehicles decide to change route onto a "meaningfully different" route (i.e. certain vehicles are more likely to change routes than others).

That's why we suggest different path penalties should be applied to different vehicles - of course, this only in case it makes sense to include path.penalty within the simulation.     2. A second (sketch of an) idea might be to use precomputed routes (maybe using path.penalty) together with a way to assign vehicles to different routes, and then still apply period rerouting along that route. As an example: 1. a vehicle might be assigned the 3rd fastest route 2. at least in the beginning, the vehicle follows that route until the first period rerouting 3. at this point it might decide to switch to the fastest route, but possibly it is already close enough to its destination, so it stays on the predefined (3rd fastest) route.   This might require a stochastic way to assign routes to vehicles which we are not too sure about.

[namdre]

In the context of rerouting, I don't think precomputation is necessary. Instead, the penalties could be applied to the edges of last route(s) of the current vehicle. (And the penalty could be a device parameter (in the vType or vehicle).

This could be done either

• with a small adaptation to MSRoutingEngine::getEffortExtra (in this context the vehicle is known and can be queried for it's routes) - this is potentially costly
• with a temporary modification to MSRoutingEngine::myEdgeSpeeds before calling vehicle.reroute - this makes it hard to do parallel routing

[MatteoFel]

thanks a lot! (sorry, jumping in because Lukas is off)

This is probably hard to answer at this stage and might need some testing: do we run the risk that this might lead to

1. If the penalties from previous routes are kept: will vehicles change from the fastest route, to the second fastest, to the third fastest, etc at each rerouting step?

2. If the penalties from previous routes are ignored/forgotten: ⁠frequent back and forth switching, because the current route is penalised too hard?

I imagine, both will depend on the scale of the penalty.

Either way, we would be excited to test any new feature that goes in this direction :)

[namdre]

Yes. Some kind of configurable penalty decay seems required (maybe exponential decay?). Please give me a gentle reminder after the conference is over (-:

[ambuehll]

Perfect! Meanwhile, we'll have a bit of a brainstorming here. Maybe @AlessioRimoldi has a few suggestions as well 👍

[ambuehll]

Hello :) This is the "gentle reminder" asked by Jakob. Happy to continue the discussions.

Lukas