GraphHopper.com | Forum | GitHub | Maps | Blog

Beginner Tips - general flow of algorithm and some beginner questions


#1

Hi, everyone. I am really new to Graphhopper Jsprit and would like to get to know how the algorithm and its implementation works in general so that I have correct knowledge to base my problems and implement them correspondingly.

Particularly, I am interested in when StateUpdater and ActivityVisitor are called when we are running the algorithm. Currently, I am trying to understand what is going on under the hood by logging the outputs from Constraint and ActivityVisitor, but I get confused and can’t get the process flow.

I would like to ask - could someone outline the general process flow when we run the algorithm. To be more concrete, I would like to know:

  • If StateManager is always the same for the whole time algorithms runs? (I got this question, since sometimes when I try to get some specific state from StateManager, it returns null).
  • When running the algorithm, what is the order in which the Constraint checker and ActivityVisitor are called? My guess is that whenever some route Constraint checking is finished, ActivityVisitor is called.
  • How in general StateManager, StateUpdater, ActivityVisitor and Constraint are correlated? (It is very broad question, but maybe you have some tips for me to get started).

I have been looking for beginner friendly threads, but couldn’t find one.


#2

Hello there again.

I am currently investigating this library and found out why I was stuck upon constraints. Having a clear and structured question is a half-solution to the problem, so let me state my problem very clear. So, my goal was to set a constraint on vehicles (all or some of them) on its capacity (some specific dimension). In order to achieve that I tried to link some states to state manager to monitor current weights of vehicles (I did so by creating states and adding them to state manager). Then everytime constraint listener invoke, I would get those state and check if the weight of current tour activity would fit into the vehicle. I also set up a state updater with activity visitor to update the current weights of vehicles each time they visit tour activity. But this did not work because, as I think now, I was using problem state to save current weights of vehicles. Today I found out that there are different kinds of state (activity state, route state, problem state). Also, there are different state updaters and they are invoked correspondingly (activity visitor state updater is invoked whenever some specific tour activity is changed or inserted into a route, route visitor state update is invoked whenever route has been changed, etc.).

So, I am currently trying to use both activity states and route states in order to solve my problem. Everytime constraint is being invoked, I get the current weight of vehicle from route-vehicle state, and see if my constraint is fulfilled. If it is, I save the weight if current activity into the activity-vehicle state. Then, everytime activity visitor is invoked, I get the weight of current activity being visited and add it to the current weights. But this approach also fails and currently I am finding out why. If someone knows how to deal this question, I would be very glad. I generally want to understand how these state updaters and constraint invokers work in general. There are listeners for every route and activity, and I want to know more about this. I will keep post anything that I find usefull here. For anyone having problems with states, I would recommend reading the comments in StateManager.java file.


#3

If you check the state manager class, you will see how the route visitors and activity visitors work:

In those route visitors and activity visitors, you can calculate and store states that you would like to use later in constraints in order to avoid unnecessary repeated calculations and make the algo more efficient. For example, you definitely would like to avoid looping over activities in activity constraints because it will be very inefficient.