Assigning a job to a specific vehicle only by applying hard constraint

I am working on a real-life VRP problem. suppose after building an initial solution, we have to add a new service to a specific solution without disturbing the initial solution. What I want that only one route that is related to that specific vehicle must be affected and other routes should remain as it is.

There is an easy or a harder solution for this, depending on whether you know on which vehicle do you want to ad the job to. This solution doesn’t involve constraints.

If you know it:
Simply, create a new problem containing only the single vehicle and the subset of jobs it has in the primary solution and run it again. If you wish, you can feed in the previous route of the vehicle to the problem as an initial route for the vehicle. It will be prety fast compared to the optimalization of the initial solution.

If you don’t know it:
Do the same as in the previous case for each vehicles one by one and pick the one which is the best (the meaning of best depends on your problem space, for example the one with the least cost increase). This looks line a lot of time, but runing the optimalization on one vehicle multiple times is faster than running the original, multi vehicle problem at once. Also it gives you the opportunity to pre filter the possible vehicles (like by utilization level) or to run the per-vehicle optimalization parallel if there are spare cores.

It has no time to do it.
The 3rd job has the time window of (6,7), and the service time of 10.
The distance between the 3rd and 2nd jobs is 1.5 (Manhattan distance). So, if the 3rd job starts the eariliest possible time, it ends at 16, which is out of the time window for the 2nd job.
Even if you reduce sevice time to 0, it can’t be inserted between the two original ones, because the travel time is 1.5.
If I reduce the service time of 3rd job to 1 and alter the time window of the 2nd from (7,8) to (8,9) it assignes all 3 jobs.

Yeah, Thanks for mathematics there that I forgot to make. But Why job 3 has not been assigned to Vehicle 1 (id =“1”)?

I’ve checked it and there is really have some kind of bug in the code with initial solution.
When I removed the algorithm1.addInitialSolution(bestSolution); line, it solved the problem and assigned all 3 jobs.
Even more interesting, that when the above statement is in the code, the solution is inconsistent. Have a look at the printout:

+--------------------------+
| problem                  |
+---------------+----------+
| indicator     | value    |
+---------------+----------+
| noJobs        | 3        | 
| noServices    | 3        | 
| noShipments   | 0        | 
| noBreaks      | 0        | 
| fleetsize     | FINITE   | 
+--------------------------+
+----------------------------------------------------------+
| solution                                                 |
+---------------+------------------------------------------+
| indicator     | value                                    |
+---------------+------------------------------------------+
| costs         | 7.0                                      | 
| noVehicles    | 1                                        | 
| unassgndJobs  | 0                                        | 
+----------------------------------------------------------+
+--------------------------------------------------------------------------------------------------------------------------------+
| detailed solution                                                                                                              |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| route   | vehicle              | activity              | job             | arrTime         | endTime         | costs           |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| 1       | 2                    | start                 | -               | undef           | 0               | 0               |
| 1       | 2                    | service               | 1               | 1               | 1               | 1               |
| 1       | 2                    | service               | 2               | 2               | 8               | 7               |
| 1       | 2                    | end                   | -               | 8               | undef           | 7               |
+--------------------------------------------------------------------------------------------------------------------------------+

As you can see, the problem contains 3 jobs, which is correct. On the other hand, the solution contains only one route with only two jobs in it. In spite this, the unassigned job count is 0.

I even have some suspicion where the bug is, but have to check. I’ll be back soon. :wink:

(I’ve opened an issue on it: https://github.com/graphhopper/jsprit/issues/354)

My goal is that only one vehicle must provide services to the added services and other routes must be unchanged.

For your original goal, see my first answer. You can do it by testing the new jobs on vehicles one by one and choose the one with most preferable solution.

For this bug, I opened an issue. Meantime, there is a workaround that works:
If you remove the line setting the initial solution:

algorithm1.addInitialSolution(bestSolution);

and instead of this, you add the routes as initial vehicle routes to the problem:

tspBuilder.addInitialVehicleRoutes(bestSolution.getRoutes());

you will get the correct answer with the third job assigned to the other vehicle.

1 Like

I have already tried i but I am getting some errors.
Exception in thread “main” java.lang.NullPointerException
at com.graphhopper.jsprit.analysis.toolbox.GraphStreamViewer.renderRoute(GraphStreamViewer.java:579)
at com.graphhopper.jsprit.analysis.toolbox.GraphStreamViewer.render(GraphStreamViewer.java:399)
at com.graphhopper.jsprit.analysis.toolbox.GraphStreamViewer.display(GraphStreamViewer.java:329)
at com.graphhopper.jsprit.examples.MultipleTimeWindowExample.main(MultipleTimeWindowExample.java:262)

Hi @nirmal786,

In order to use initial solution, instead of

    algorithm1.addInitialSolution(bestSolution);

you should use the following:

    VehicleRoutingProblemSolution initialSolution =
            new VehicleRoutingProblemSolution(bestSolution.getRoutes(), Arrays.asList(service3), Double.MAX_VALUE);
    algorithm1.addInitialSolution(initialSolution);

you need to add the new jobs to the collection of unassigned jobs, and set a large cost for the initial solution.

Best regards,
He

1 Like

You are right, but it is better if these are done by the API under the hood. I made the changes in #354.

1 Like

When I add two more jobs and apply the constraint (that Only route 1 must service these two added jobs), routes (beside 1st route) are also getting affected. I want that routes except 1 in initial solutions must not change.

This is my Hard Route constraint:

    public boolean fulfilled(JobInsertionContext iContext) {

       if(iContext.getNewVehicle().getId()=="2")
            if((iContext.getJob().getId()=="3" || iContext.getJob().getId()=="4")) {
                System.out.println("Constrainted " + iContext.getJob().getId() + "/" + iContext.getNewVehicle().getId());
                return false;
            }

        return true;
    }

Hi @nirmal786,

  1. if you want that certain routes must not change (i.e., the sequence of activities in those routes do not change, no new jobs are added to those routes, no jobs in those routes are removed, etc.), then you’d better not add those routes and associated jobs to the new vrp at all.

  2. if you want that, for certain routes, the sequence of existing activities must not change and no jobs in those routes can be removed, but new jobs can be added (at any position in those routes), then you’d better use initial routes.

  3. if you want that, for certain routes, the existing jobs should not be removed, but new jobs can be added and the sequence of existing activities can change, then you use hard route constraints to control the job-route relationship.

  4. when you use such hard route constraints, for example, like the one you implemented, job X should not be assigned to route of vehicle Y, besides what you have there (if new vehicle is Y and if new job is X, then return false), you should also check whether the current route contains job X, i.e., if new vehicle is Y and if the current route contains job X, then return false, just like the example in the walkthrough of constraints.

Hopefully this helps.

Best regards,
He

As per 1st options, you said, But I have to show all routes to the client. I have to change one of the existing routes so the second option is also not feasible. 3rd option seems good and I have applied it. It worked for me. thanks for the suggestion