[sumo-user] weight update-routing algorithms

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

[sumo-user] weight update-routing algorithms

Raheleh Zarei
Hello,

I would like to know about calculating the cost of the shortest path in 3 routing algorithms in SUMO. Is the metric, travel time? Do they take the cost of internal edges into account when they find the shortest path?
I read this page  https://sumo.dlr.de/docs/Simulation/Routing.html , but it is not very clear for me.
The reason I ask this is that I have added another routing algorithm in SUMO. I assign the cost of each edge  using the function below:

 void MyRouter::setcurrent_weight(SUMOTime msTime, const V* const vehicle)
{
current_weight.clear();
for (const E * edge : myEdges){
 if (edge->getFromJunction() != nullptr && edge->getToJunction() != nullptr) {
   current_weight.push_back(MSRoutingEngine::getEffort(edge, vehicle, STEPS2TIME(msTime)));}
}
}

and update the whole vector in the interval defined by   --device.rerouting.adaptation-interval . However, the calculated shortest path and duration, for some trips, are slightly longer. I think there should be a difference between how I assign the edge weight and the way CH and other algorithms do.


--
RAZ

_______________________________________________
sumo-user mailing list
[hidden email]
To unsubscribe from this list, visit https://www.eclipse.org/mailman/listinfo/sumo-user
Reply | Threaded
Open this post in threaded view
|

Re: [sumo-user] weight update-routing algorithms

Jakob Erdmann
The metric is travel time and internal edges are taken into account.


Am Di., 16. Juni 2020 um 21:49 Uhr schrieb Raheleh Zarei <[hidden email]>:
Hello,

I would like to know about calculating the cost of the shortest path in 3 routing algorithms in SUMO. Is the metric, travel time? Do they take the cost of internal edges into account when they find the shortest path?
I read this page  https://sumo.dlr.de/docs/Simulation/Routing.html , but it is not very clear for me.
The reason I ask this is that I have added another routing algorithm in SUMO. I assign the cost of each edge  using the function below:

 void MyRouter::setcurrent_weight(SUMOTime msTime, const V* const vehicle)
{
current_weight.clear();
for (const E * edge : myEdges){
 if (edge->getFromJunction() != nullptr && edge->getToJunction() != nullptr) {
   current_weight.push_back(MSRoutingEngine::getEffort(edge, vehicle, STEPS2TIME(msTime)));}
}
}

and update the whole vector in the interval defined by   --device.rerouting.adaptation-interval . However, the calculated shortest path and duration, for some trips, are slightly longer. I think there should be a difference between how I assign the edge weight and the way CH and other algorithms do.


--
RAZ
_______________________________________________
sumo-user mailing list
[hidden email]
To unsubscribe from this list, visit https://www.eclipse.org/mailman/listinfo/sumo-user

_______________________________________________
sumo-user mailing list
[hidden email]
To unsubscribe from this list, visit https://www.eclipse.org/mailman/listinfo/sumo-user
Reply | Threaded
Open this post in threaded view
|

Re: [sumo-user] weight update-routing algorithms

Raheleh Zarei
Hello,

I have some questions about routing algorithms in SUMO. I read the explanation in this link https://sumo.dlr.de/docs/Simulation/Routing.html but still, there are some points that are not clear to me.
1- Does CH  return the same shortest (fastest) path as astar or Dijkstra? I'm asking this because I'm not sure if Dijkstra also uses the updated edge weights after each interval or if it calculates the real weight of each edge at the time of each s-t query.
2- Does CH return the approximate shortest (fastest) path but Dijkstra and astar return the exact one at time t?
3- Is this normal that with travel time as a metric, astar returns different average travel time (duration) for a 200 trips file than Dijkstra?

Thanks



On Tue, Jun 16, 2020 at 4:11 PM Jakob Erdmann <[hidden email]> wrote:
The metric is travel time and internal edges are taken into account.


Am Di., 16. Juni 2020 um 21:49 Uhr schrieb Raheleh Zarei <[hidden email]>:
Hello,

I would like to know about calculating the cost of the shortest path in 3 routing algorithms in SUMO. Is the metric, travel time? Do they take the cost of internal edges into account when they find the shortest path?
I read this page  https://sumo.dlr.de/docs/Simulation/Routing.html , but it is not very clear for me.
The reason I ask this is that I have added another routing algorithm in SUMO. I assign the cost of each edge  using the function below:

 void MyRouter::setcurrent_weight(SUMOTime msTime, const V* const vehicle)
{
current_weight.clear();
for (const E * edge : myEdges){
 if (edge->getFromJunction() != nullptr && edge->getToJunction() != nullptr) {
   current_weight.push_back(MSRoutingEngine::getEffort(edge, vehicle, STEPS2TIME(msTime)));}
}
}

and update the whole vector in the interval defined by   --device.rerouting.adaptation-interval . However, the calculated shortest path and duration, for some trips, are slightly longer. I think there should be a difference between how I assign the edge weight and the way CH and other algorithms do.


--
RAZ
_______________________________________________
sumo-user mailing list
[hidden email]
To unsubscribe from this list, visit https://www.eclipse.org/mailman/listinfo/sumo-user
_______________________________________________
sumo-user mailing list
[hidden email]
To unsubscribe from this list, visit https://www.eclipse.org/mailman/listinfo/sumo-user


--
RAZ

_______________________________________________
sumo-user mailing list
[hidden email]
To unsubscribe from this list, visit https://www.eclipse.org/mailman/listinfo/sumo-user
Reply | Threaded
Open this post in threaded view
|

Re: [sumo-user] weight update-routing algorithms

behrisch
Administrator
Hi,
if you use routing without dynamic edge weights (not the rerouting
device but duarouter for instance) all router should behave the same
(unless you have artficial networks where you have multiple routes of
exactly the same length). If younupdate edge weights dynamically CH will
not use them but dijkstra and astar should still behave the same.

Best regards,
Michael

Am 23.06.20 um 17:01 schrieb Raheleh Zarei:

> Hello,
>
> I have some questions about routing algorithms in SUMO. I read the
> explanation in this
> link https://sumo.dlr.de/docs/Simulation/Routing.html but still, there
> are some points that are not clear to me.
> 1- Does CH  return the same shortest (fastest) path as astar or
> Dijkstra? I'm asking this because I'm not sure if Dijkstra also uses the
> updated edge weights after each interval or if it calculates the real
> weight of each edge at the time of each s-t query.
> 2- Does CH return the approximate shortest (fastest) path but Dijkstra
> and astar return the exact one at time t?
> 3- Is this normal that with travel time as a metric, astar returns
> different average travel time (duration) for a 200 trips file than Dijkstra?
>
> Thanks
>
>
>
> On Tue, Jun 16, 2020 at 4:11 PM Jakob Erdmann <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     The metric is travel time and internal edges are taken into account.
>
>
>     Am Di., 16. Juni 2020 um 21:49 Uhr schrieb Raheleh Zarei
>     <[hidden email] <mailto:[hidden email]>>:
>
>         Hello,
>
>         I would like to know about calculating the cost of the shortest
>         path in 3 routing algorithms in SUMO. Is the metric, travel
>         time? Do they take the cost of internal edges into account when
>         they find the shortest path?
>         I read this page 
>         https://sumo.dlr.de/docs/Simulation/Routing.html , but it is not
>         very clear for me.
>         The reason I ask this is that I have added another routing
>         algorithm in SUMO. I assign the cost of each edge  using the
>         function below:
>
>          void MyRouter::setcurrent_weight(SUMOTime msTime, const V*
>         const vehicle)
>         {
>         current_weight.clear();
>         for (const E * edge : myEdges){
>          if (edge->getFromJunction() != nullptr && edge->getToJunction()
>         != nullptr) {
>            current_weight.push_back(MSRoutingEngine::getEffort(edge,
>         vehicle, STEPS2TIME(msTime)));}
>         }
>         }
>
>         and update the whole vector in the interval defined by 
>          --device.rerouting.adaptation-interval . However, the
>         calculated shortest path and duration, for some trips, are
>         slightly longer. I think there should be a difference between
>         how I assign the edge weight and the way CH and other algorithms do.
>
>
>         --
>         *RAZ*
>         _______________________________________________
>         sumo-user mailing list
>         [hidden email] <mailto:[hidden email]>
>         To unsubscribe from this list, visit
>         https://www.eclipse.org/mailman/listinfo/sumo-user
>
>     _______________________________________________
>     sumo-user mailing list
>     [hidden email] <mailto:[hidden email]>
>     To unsubscribe from this list, visit
>     https://www.eclipse.org/mailman/listinfo/sumo-user
>
>
>
> --
> *RAZ*
>
> _______________________________________________
> sumo-user mailing list
> [hidden email]
> To unsubscribe from this list, visit https://www.eclipse.org/mailman/listinfo/sumo-user
>


_______________________________________________
sumo-user mailing list
[hidden email]
To unsubscribe from this list, visit https://www.eclipse.org/mailman/listinfo/sumo-user

signature.asc (201 bytes) Download Attachment