Refined priorities

jsprit
1

Proposal:

Jsprit now contains only three priorities which is now an integer. My proposal is
(1) change priority to enum (cleaner, java-like): LOW, NORMAL, HIGH
(2) add two additional types of priorities: IMPORTANT, MANDATORY.

Leaving out jobs with IMPORTANT and MANDATORY priorities from the solution should have an enourmous cost impact: HIGH now has a cost 4 times the higher travel cost, the new ones should have 1000 times or more.
What jobs with these new priorities should be unique is that the initial solution builder should try hard to add these to the initial solution. The difference could be that IMPORTANT may be left out when it can’t be (easily) added to the initial solution, while MANDATORY could throw exception.

Therefore, MANDATORY is best if these jobs has non-overlapping time windows, while the IMPORTANT is more flexible.

Why are these new priorities needed?

In real life, there could be jobs, which simply can’t be left out. At first, the cost impact looks enough to solve the problem, but I experienced in real life projects, that with high number of overlapping Jobs, it is not guaranteed that these tasks will ever be choosen into the solution – not even when I’ve increased the iteration number to an insane 100.000.

As an example, I had 3 vehicles, about 1000 jobs, 6 of them with HIGH priority (mandatory). I changed the multiplier for HIGH from 4 to 1000000 (yes, one million). I had several runs (with different random seeds). There was one solution with all jobs assigned and a total cost of 30k, proving that the problem had a solution. But all the other runs provided solutions with one or two of these HIGH jobs left out, regardless of the cost being above hundred millions. Later I realized the reason: these mandatory Jobs had a relatively short timewindow with a long activity time (10-20 times more) compared to the regular jobs. Therefore, if the initial solution didn’t contain the job, it was impossible to mutate to have them (too many other jobs would have to be thrown out “under the HIGH job” – an extremely low probability).

Compatibility impact
(1) Switching to enum may cause some incompability. The builders could be modified by duplicating the setter method to support both inputs. The getter is the problematic. If you want to keep backward compability above all: there have to be two getters (@Deprecated int getPriority() and Priority getPriorityValue()),
(2) It is an extension, so it has no impact.

1 Like
2

Here is a more detailed proposal of mandatory jobs (switching to enum is another subject). At first glance, it is much easier, than it first looked like.

There are two new priorities: important and mandatory
Both has the same unasssigned cost factor: something horrible (such as 2 times the number of activities).
Initial solution strategy is modified as follows: the jobs are inserted is several runs: in each run, the jobs with the same proirity are inserted, from highest to lowest. Look at this “pseudo” code:

@Override
public VehicleRoutingProblemSolution createSolution(final VehicleRoutingProblem vrp) {
    logger.info("create initial solution");
    List<VehicleRoute> vehicleRoutes = new ArrayList<>();
    vehicleRoutes.addAll(vrp.getInitialVehicleRoutes());
    Collection<Job> badJobs = new HashSet<>();
    for (int prio = MAX_PRIORITY; prio >= MIN_PRIORITY; prio--) {
        Collection<Job> badJobsInPriority = insertion.insertJobs(vehicleRoutes, getUnassignedJobs(vrp, prio));
        if (prio == MANDATORY && badJobsInPriority.size() != 0) {
            throw new Exception(...);
        }
        badJobs.addAll(badJobsInPriority);
    }
    VehicleRoutingProblemSolution solution = new VehicleRoutingProblemSolution(vehicleRoutes, badJobs, Double.MAX_VALUE);
    double costs = solutionCostsCalculator.getCosts(solution);
    solution.setCost(costs);
    if (solutionCostsCalculator instanceof ModularSolutionCostCalculator) {
        ModularSolutionCostCalculator modCalc = (ModularSolutionCostCalculator) solutionCostsCalculator;
        solution.setDetailedCost(modCalc.calculate(solution));
    }
    return solution;
}

private List<Job> getUnassignedJobs(VehicleRoutingProblem vrp, int prio) {
    List<Job> jobs = vrp.getJobs().values().stream().filter(j -> j.getPriority() == prio).collect(Collectors.toList());
    return jobs;
}

The only difference between MANDATORY and IMPORTANT is that MANDATORY jobs must be inserted.

Additional, optional changes:

(1) The SolutionAcceptor shouldn’t accept solutions with MANDATORY jobs unassigned, however, this would hardly happened, because the high cost for lefting them out, unless it could insert an IMPORTANT job instead.

(2) The Break could be generalized as a MANDATORY job with much higher flexibility. (I’ll give my proposal later on this.)

1 Like
3

just wondering: besides giving penalties to unassigned jobs according to their priority levels in the objective function, is there a way to guide the insertion of the jobs? currently I use a soft route constraint to give a reward accordingly, but is there a better way? or is it possible to have a “hard” way to do this (for MANDATORY jobs)?

1 Like
4

I havn’t got deep enough knowledge to know this. :frowning: Guiding the insertation/ruin strategy would have a better convergation than simply throwing away bad solutions.

But whether there is such a strategy or not, the initial solution generation alteration, the one which ensures mandatory jobs to be in, is something we can’t avoid. The reason I’ve written earlier in my example: if the mandatory job has a relatively long activity time compared to the other jobs and has a short time window, the chance to add the job to the solution later is low. (It would need all the inserted jobs within the time window of the mandatory job to be removed in ruin phase.)

My proposal to add jobs in the order of their priority has an overall benefit on the quality of the initial solution, but has no impact on insertation strategy fitness. Therefore, it may solve the problem of the mandatory jobs, but not the important ones.

1 Like
5

I’ve done the first tests.
My proposal for calling the insertation in initial solution builder by priority ensures the insertation of mandatory jobs and setting the cost for unassigned as proposed earlier (4number of activitieslongest distance) is keeping them in.

But you are right, it would be extenfed for insertation as well, or these mandatory jobs will hardly be moved in later iterations. (They have to be removed and inserted in the same iteration or the solution would be discarded.)

My first idea, although I still have to check, to use the same, priority-ordered insertation, so the high priority activities which were removed would easier find “free space” in their time windows. For higher disertification, the insertation ordering could be refined to give some noise. (Sorting the unassigned activities, then choosing some of them and relocate in the sorted list.)

6

Hallo Balage1551,
I am also looking for a solution to prioritize jobs (all priorities 1 to 2, all priorities 2 to 3, etc.) and have read your suggestions.

Did you implement the requirement properly and can you tell me how?

For me, the main problem is probably that low priorities (priority 5) are already inserted in the initial solution, although jobs with priority 3 remain unplanned.

As an attempted solution, I have sorted the unassignedJobList according to priorities, unfortunately that does not help, as the assignment of the jobs to tours takes place in a random order:

    for (final Job unassignedJob : unassignedJobList) {
        completionService.submit(new Callable<ScoredJob>() {

            @Override
            public ScoredJob call() throws Exception {
                return RegretInsertion.getScoredJob(routes, unassignedJob, insertionCostsCalculator, 
                        scoringFunction);
            }

        });
    }

I would be happy if you or others had a solution for me.

Best regards,
Raine