faq 45121594

How to implement an A* router with time-dependent feature?

by Zidong on 2016-02-15 20:44:12

---

Hi,

I am currently using Matsim for my Master thesis research. I would like to implement a time-dependent A* router in Matsim. I have read the tutorial "Adding your own Routing algorithm to MATSim" from 2015: Matsim Class at TU Berlin. The example code is given at https://github.com/matsim-org/matsim/blob/0.7.x/matsim/src/main/java/tutorial/programming/example21tutorialClasses/routing/MatsimClassDijkstra.java. 

 

I extend the MatsimClassDijkstra class to implement a simple Euclidean A* router. In my research, I want to include the traffic density component. The idea is every time a route is planned, the around-the-corner traffic density along the path will increase a bit. What I am thinking is there will be a global density HashMap, with link id and timestamp as the key and density as the value, stored somewhere. The HashMap will be updated every time a path is calculated and used by subsequent planning agents.

 

The problem is I am not familiar with the complex parallel planning mechanism of Matsim. Could anyone tell me where I could store this HashMap? Or is there any better design solutions? (My initial design is to add a static member variable with my class MyAStarClass. But it seems this is not correct because a route might be replanned thus the density should not be added to the HashMap.)

 

Thanks:)

 

 

 

---

Comments: 1

---

Re: How to implement an A* router with time-dependent feature?

by Kai Nagel on 2016-02-18 15:38:39

Dear Zidong,

(1) I assume that by "extending" you don't mean the Java sense, but copy the whole class and go from there.  This is certainly what I would strongly recommend; the tutorial class should in fact be final.  In fact, best copy the whole package; there is nothing to be gained by code re-use at this level.  

(2) Why can't you store your variables in parallel to costToNode or previousNodes or queue?  As long as you use the same calling syntax as in the example (best copy the whole package), the factory will make sure that for each thread a separate instance will be created, taking care of parallelism by itself.  Just do NOT use static variables, since they will be shared between threads.

(3) If you are using git, have a look at https://github.com/matsim-org/matsim-example-project .

Best, Kai