GraphHopper.com | Forum | GitHub | Maps | Blog

Problem with priority handling


#1

Hi

Let me first explain what I am doing then I’ll talk about the possible bug.
I am writing a hard activity constraint for priority management.
In my scenario there are three priorities. 1st, 2nd and Any which I equate to 1, 2, 3 respectively.
These values also apply to time windows.

The rules are:
In the 1st window, P3 jobs must not be handled before P1 jobs.
In the 2nd window, P3 jobs must not be handled before P2 jobs.
Because of the windows, P2 jobs will never appear in the 1st window and P1 jobs will never appear in the 2nd window.

Below is a snippet of the code.

public ConstraintsStatus fulfilled(JobInsertionContext iFacts,TourActivity prevAct, TourActivity newAct,TourActivity nextAct, double prevActDepTime){

		if(newAct instanceof DeliverShipment || newAct instanceof PickupShipment){
			if( (((JobActivity) newAct).getJob().getPriority() == 3) ){
				int newJobPriority = ((JobActivity) newAct).getJob().getPriority();
				int prevJobPriority = ((JobActivity) prevAct).getJob().getPriority();
				if(newJobPriority < prevJobPriority  )
				{
					return ConstraintsStatus.NOT_FULFILLED;
				}   				
			}
		}
		return ConstraintsStatus.FULFILLED;
	}

}

The problem is that all Pickup jobs are given Priority 2 irrespective of the delivery job priority.

I can’t ignore pickups because we don’t want low priority pickups to happen before high priority deliveries.

Shipments cannot set the priority separately for the pickups and deliveries.

So the possible bug proposition is that for a pickupShipment a call to ((JobActivity) act).getJob().getPriority() always returns 2.
My view is that it should always return the priority of the delivery job.

kind regards
Grant


#2

Hi Grant,

Are you saying that, in the constraint, when the newAct is PickupShipment, and if you call ((TourActivity.JobActivity) newAct).getJob().getPriority(), it is always returning 2, regardless what the job priority is, while when the newAct is DeliverShipment, it is always returning the correct job priority?

But when I try to reproduce this by running the following snippet, I always get the correct job priority, whether the newAct is PickupShipment or DeliverShipment.

Please let me know if I overlooked anything.

Best regards,
He

    VehicleType vehicleType = VehicleTypeImpl.Builder.newInstance("car").build();
    Vehicle vehicle = VehicleImpl.Builder.newInstance("car1")
        .setType(vehicleType)
        .setStartLocation(Location.newInstance(0, 0))
        .build();
    Shipment shipment = Shipment.Builder.newInstance("shipment")
        .setPickupLocation(Location.newInstance(0, 0))
        .setDeliveryLocation(Location.newInstance(0, 0))
        .setPriority(10)
        .build();

    VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
    vrpBuilder.addVehicle(vehicle);
    vrpBuilder.setFleetSize(VehicleRoutingProblem.FleetSize.FINITE);
    vrpBuilder.addJob(shipment);
    VehicleRoutingProblem vrp = vrpBuilder.build();

    Jsprit.Builder algoBuilder = Jsprit.Builder.newInstance(vrp);

    StateManager stateManager = new StateManager(vrp);
    ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);
    constraintManager.addConstraint(new HardActivityConstraint() {
        @Override
        public ConstraintsStatus fulfilled(JobInsertionContext iFacts,
                                           TourActivity prevAct,
                                           TourActivity newAct,
                                           TourActivity nextAct,
                                           double prevActDepTime) {
            if (newAct instanceof PickupShipment) {
                System.out.println("PickupShipment: " +
                    ((TourActivity.JobActivity) newAct).getJob().getPriority());
            }
            else if (newAct instanceof DeliverShipment) {
                System.out.println("DeliverShipment: " +
                    ((TourActivity.JobActivity) newAct).getJob().getPriority());
            }
            else {
                throw new IllegalStateException("incorrect act type");
            }
            return ConstraintsStatus.FULFILLED;
        }
    }, ConstraintManager.Priority.HIGH);
    algoBuilder.setStateAndConstraintManager(stateManager, constraintManager);

    VehicleRoutingAlgorithm algo = algoBuilder.buildAlgorithm();
    VehicleRoutingProblemSolution solution = Solutions.bestOf(algo.searchSolutions());
    SolutionPrinter.print(vrp, solution, SolutionPrinter.Print.VERBOSE);

#3

Hi He (@jie31best)

well you hit the nail on the head. I was being fed bad data - all jobs at P2. Sorry to have wasted your time on that.
However - perhaps you could consider the problem. I am frequently getting P3 jobs scheduled in front of P1 even with the hard constraint in place.

Its hair pulling stuff.

regards
Grant


#4

Maybe something like this?

    constraintManager.addConstraint(new HardActivityConstraint() {
        @Override
        public ConstraintsStatus fulfilled(JobInsertionContext iFacts,
                                           TourActivity prevAct,
                                           TourActivity newAct,
                                           TourActivity nextAct,
                                           double prevActDepTime) {
            int newActPriority = ((TourActivity.JobActivity) newAct).getJob().getPriority();
            int prevActPriority = Integer.MIN_VALUE;
            if (!(prevAct instanceof Start))
                prevActPriority = ((TourActivity.JobActivity) prevAct).getJob().getPriority();
            int nextActPriority = Integer.MAX_VALUE;
            if (!(nextAct instanceof End))
                nextActPriority = ((TourActivity.JobActivity) nextAct).getJob().getPriority();
            if (newActPriority < prevActPriority)
                return ConstraintsStatus.NOT_FULFILLED_BREAK;
            if (newActPriority > nextActPriority)
                return ConstraintsStatus.NOT_FULFILLED;
            return ConstraintsStatus.FULFILLED;
        }
    }, ConstraintManager.Priority.HIGH);

#5

Hi He

Interesting. I have not seen NOT_FULFILLED_BREAK. What is the difference between that and NOT_FULLFILLED?

regards
Grant


#6

NOT_FULFILLED_BREAK means it will reject the insertion of newAct at the current position and will not try to insert newAct in any downstream position in the route.


#7

cool. that would prevent wasting time on something that will not be allowed downstream due to issues upstream.
Thanks He thats very helpful.

regards
Grant