GraphHopper.com | Forum | GitHub | Maps | Blog

Adding service start time to the cost


#1

Hey guys,
The problem I’m trying to solve:
I want to create a weight that allows prioritization of a service to take into account how early it is being routed. Basically, a priority 1 should have some sort of cost saving associated with it being assigned earlier in the day. My initial Though was changing the cost scorer from:

  • score = (4 - unassignedJob.getPriority()) * (Integer.MAX_VALUE - best.getInsertionCost()) + scoringFunction.score(best, unassignedJob);

to:

  • score = (4 - unassignedJob.getPriority())*[ARRIVAL TIME] * (Integer.MAX_VALUE - best.getInsertionCost()) + scoringFunction.score(best, unassignedJob);

I quickly realized that was stupid, as I couldn’t actually have an arrival time for missed services.

Does anyone have any ideas on how to pursue this? Has anyone effectively accomplished the same task?


#2

I think you can use a soft constraint and a custom objective function?


#3

Could you please give me some pointers? Sorry, I can’t find anything in the examples.


#4

Sorry dug a little deeper and found a similar post where you forwarded a person to a StackOverflow answer by Stefan which led me to this:

From what I can tell the class ThirteenImmediatelyAfterTwentyOne Assigns out a -500 cost if there’s a 21 and then a 13 and a 500 if not?

And the class RewardAndPenaltiesThroughSoftConstraints basically does the same thing?


#5

If what you want to achieve is that activities A and B are in the same route and A is before B, and if you would like to use a soft constraint to do that, yes I think the example does it. Note that you will need to tweak the value of the penalty/reward based on your problem to make it work as expected.

If A and B do not need to be in the same route, then it will be more complicated.

EDIT: oh the example is that B is immediately after A - not sure if that is what you want? There is another example that B is after A but not necessarily immediately after.


#6

I don’t really want either. I was just looking at those for an example of how to setup soft constraints and custom objective functions.

So my understanding on how I would accomplish my task (to create a weight so that jobs with higher priorities are completed earlier in the day) is to create a custom objective function that adds in a cost that is equal to priority*arrivalTime()?

Not sure how to use the soft constraint in this case though.


#7

A bit of an issue when trying to insert jobs, I don’t have access to jsprit.core.algorithm.state.StateFactory as it’s not a public class. Is this by design; is there another method I should be using?


#8

Let’s go through Stackoverflow_RelatedJobs_13_and_21_inSameRoute_13_immediatelyAfter_21:

What do we want to achieve here?
We want services 13 and 21 are in the same route and service 13 is immediately after service 21.

Ok let’s use a constraint to achieve it.
Hard constraint vs. soft constraint?
A question we need to ask ourselves here is what we would like to do if what we want to achieve contradicts other existing hard constraints? For example, what if time windows of the jobs determine that service 13 cannot be after service 21, or what if skills of routes and jobs determine that services 13 and 21 cannot be in the same route? If we are fine that service 13 is not immediately after service 21 or they are not in the same route in such cases, then we’d use a soft constraint; if we would rather one of the two jobs gets unassigned than to compromise in such cases, then we’d use a hard constraint.

Route constraint vs. activity constraint?
We are trying to manipulate the position of activities in a route (service 13 is immediately after service 21), so we’d use an activity constraint.

Thus let’s go ahead with a soft activity constraint.
Note that what the soft constraint does is that it guides the insertion of individual activity, penalizing or rewarding certain insertions, in the hope of generating “good” solutions. In the meantime, we need a custom objective function which is in line with the soft constraint. What the objective function does is that it selects the solution we want from the generated solutions. If the soft constraint and the objective function are not coordinated, then we might end up with a sub-optimal solution.

Now let’s look at the soft activity constraint in the example, and what it does is that:

  1. if the activity we are trying to insert (newAct) is service 13, then we reward the insertion if the previous activity is service 21, or we penalize the insertion otherwise;
  2. if the next activity is service 13, then we reward the insertion if the new activity is service 21, or we penalize the insertion otherwise.

And what about the objective function? It goes like this: besides the usual cost calculations,

  1. it rewards a route if services 13 and 21 are both in it and if service 21 is immediately after service 13;
  2. it penalizes a route if services 13 and 21 are both in it but the activity before service 21 is not service 13;
  3. it penalizes a route if only one of service 13 and 21 is in it.

We can see that the soft activity constraint and the objective function are not coordinated - in fact, they are opposite to each other! Then why do we still get a solution doing what we want? It probably is that the soft constraint is good enough that all the generated solutions achieve what we want. But in general, we would like that the soft constraint and the objective function are coordinated.

Hopefully this helps.

Best regards,
He


#9

Ok this code is pretty old and out of date. Nowadays we use

stateManager.createStateId("some state id")

or

InternalStates.COSTS (or some other internal state id you would like to use)