HardConstraint for Jobs with priorities

Hi, i’m trying to add a hard constraint based on the priority of a job (a client must be served first, second, third, etc, depending on a number defining the order). Note that this is different to set a fixed initial route, since i’m not assigning a particular vehicle to do the job(s) with priority.

I thought to implement this using JobInsertionContext::getRelatedActivityContext() to retrieve the insertion index of the activity, but in both HardActivityConstraint and HardRouteConstraint this method always return null.

I tried to workaround that so i’ve implemented the constraint like this:

public class JobPriorizationConstraint implements HardRouteConstraint {
private List<PriorityJob> priorityJobs;

public JobPriorizationConstraint(List<PriorityJob> priorityJobs) {
    this.priorityJobs = priorityJobs;

public boolean fulfilled(JobInsertionContext jobInsertionContext) {
    List<TourActivity> tourActivities = jobInsertionContext.getAssociatedActivities();

    for(PriorityJob priorityJob: this.priorityJobs) {
        for (int i = 0; i < tourActivities.size(); i++) {
            TourActivity job = tourActivities.get(i);
            if (job.getLocation().getId().equals(priorityJob.getId()) && i != jsonStop.getPriority()) {
                    return false;
    return true;

the routes obtained are not following this constraint, although the code gets executed, so i’m wondering if there is something wrong with the implementation or if it’s there some better approach to achieve this?

Thanks in advance

Can you give some more info about the problem you want to solve? I assume that you have a number of jobs. A subset of these jobs have high priority, i.e. they need to be served in any case. If there is still capacity then, jobs with lower priority can be served. Did I understand it correctly?

I have a quantity of jobs and a subset of them have a priority label. Those with the lower priority value on their labels must be served first, and if there is still capacity try to serve the rest.

For instance, i can have a fleet of 5 vehicles, and 12 jobs. 2 of those jobs have a priority label of 1, 3 jobs have priority 2, and the rest has no priority. What i’m trying to achieve is that in any route generated this order always follows: Priority 1 Jobs (can be 0 or more), then priority 2 jobs (also can be 0 or more), then no priority jobs.

So for any route, sequences like this are valid:

  • P1, P1, P2, NP, NP
  • P2, NP, NP
  • P1, P2, P2, P2, NP, NP
  • NP, NP, NP, NP

and like this are invalid:

  • P2, P1, NP
  • NP, P2, NP

With the code of the previous post i was trying to accomplish this for the simple scenario where the priority values are unique between them, i.e. there exists just one job with priority 1, one with P2 and so on, and there is just one vehicle.


I think you need a HardActivityConstraint rather than a HardRouteConstraint. That is, when you insert a newAct at a particular position in a route, i.e., between prevAct and nextAct, you check the priority labels of newAct, prevAct and nextAct, and disallow the insertion if newAct has a priority label larger than nextAct or smaller than prevAct.

Here is a post where Stefan explains 3 relation types between two jobs A and B that can be modelled. It might be helpful to you.

Best regards,

1 Like

Thanks for your clarification. Now I understand your problem much better.

He is right, you need a HardActivityConstraint to enforce this. Working with an ActivityConstraint is what I experienced not that easy. You need to consider all possible states when inserting a new Activity. For example, a state might be the current route state [Start, P1,P2,NP,NP,End]. Then there are actually two allowed insertion positions for an activity of priority P1, between Start and P1 AND between P1 and P2. Thus if prevAct is of type P2 and new act of type P1, your constraint can never be fulfilled anymore and you can break evaluation in this route. When I implement such a constraint, I always start developing an appropriate test suite that mocks all possible states.

Tip: Do not use a HashMap to store your priority labels, but use an appropriate array. This really makes a difference when working with activity constraints (since they are called very frequently).

BTW: If you want to make sure that all jobs with a high priority need to be served as early as possible or to put it in other words, if you want the last high priority job to be served earlier than the first job with medium priority, I doubt that you can achieve this with your approach. You can if you only have one route, but once you have several routes NP jobs might be served earlier in time than P1 jobs, e.g. if you have two valid routes: [P1,P1,P1,P1,P1,P1], [NP,NP]. Then the first NP job will probably served earlier than the last P1 job.

1 Like

thanks both for your tips, i’ll use a HardActivityConstraint then with an array to store my labels

Tip: Each Activity is assigned an index when building the vehicle
routing problem. Thus, it should be easy for you to store your activity
labels in an array :). Your array needs to be of length (noActivities +
2) (you get the number from your vrp)

Am 09/11/15 um 15:12 schrieb SYonekura:

This topic was automatically closed 8 days after the last reply. New replies are no longer allowed.