Constraint for assuring driver arrival time is after timewindow start (avoiding waiting time)

jsprit
1

Hi,

I’m trying to find a way to implement a HardActivityConstraint that prohibits drivers from arriving at an activity before it’s timewindow start, and therefore avoiding waiting time. I have currently come up with this implementation:

public ConstraintsStatus fulfilled(JobInsertionContext iFacts,       TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
if (prevAct instanceof Start && nextAct instanceof End) {
    return ConstraintsStatus.FULFILLED;
}
Vehicle vehicle = getVehicle(iFacts);
Driver driver = iFacts.getRoute().getDriver();
if (isArrivalTimeBeforeTimeSlotStart(prevAct) || isArrivalTimeBeforeTimeSlotStart(nextAct)) {
    return ConstraintsStatus.NOT_FULFILLED_BREAK;
}
double newActArrTime = prevActDepTime + transportCosts.getTransportTime(prevAct.getLocation(), newAct.getLocation(), prevActDepTime, driver, vehicle);
if (newActArrTime < newAct.getTheoreticalEarliestOperationStartTime()) {
    return ConstraintsStatus.NOT_FULFILLED;
}
return ConstraintsStatus.FULFILLED;
}

private boolean isArrivalTimeBeforeTimeSlotStart(TourActivity activity) {
    return activity.getArrTime() < activity.getTheoreticalEarliestOperationStartTime();
}

private Vehicle getVehicle(JobInsertionContext iFacts) {
    if (iFacts.getRoute().getActivities().isEmpty()) {
        return iFacts.getNewVehicle();
    }
    return iFacts.getRoute().getVehicle();
}

Although i am not convinced that this is the very correct way to implement this functionality. Is there any better method i can use to achieve my objective?

2

Well it is not wrong implementation, but it will not work at the end. Because if initial solution will contain route where your constraint is broken and this route did not enter to ruin phase, it will remain in solution and thus you will got bad solution. I did something similar with “delivery only until not empty” constraint and it did weird things. In your case if you can, I’d try soft route constraint approach with waiting time penalization and give it enough time to look up for good solution. You should consider the conflict between your constraint and penalization for unassigned jobs, which is pretty high.

1 Like
3

Thanks for the help! I tried implementing this soft constraint as shown below, but it failed miserably.

public class WaitingTimeConstraint implements SoftActivityConstraint {

    private final VehicleRoutingTransportCosts transportCosts;

    public WaitingTimeConstraint(VehicleRoutingTransportCosts transportCosts) {
        this.transportCosts = transportCosts;
    }

    @Override
    public double getCosts(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
        Driver driver = iFacts.getRoute().getDriver();
        if(isArrivalTimeBeforeTimeSlotStart(prevAct) || isArrivalTimeBeforeTimeSlotStart(nextAct)){
            return 1e10;
        }
        double newActArrivalTime = prevActDepTime + transportCosts.getTransportTime(prevAct.getLocation(), newAct.getLocation(), prevActDepTime, driver, getVehicle(iFacts));
        return (newAct.getTheoreticalEarliestOperationStartTime() - newActArrivalTime) * 1e10;
    }

    private boolean isArrivalTimeBeforeTimeSlotStart(TourActivity activity) {
        return activity.getArrTime() < activity.getTheoreticalEarliestOperationStartTime();
    }

    private Vehicle getVehicle(JobInsertionContext iFacts) {
        if (iFacts.getRoute().getActivities().isEmpty()) {
            return iFacts.getNewVehicle();
        }
        return iFacts.getRoute().getVehicle();
    }
}

Could you provide me with a correct implementation or maybe point out why this soft constraint is not working as expected? thanks for the help.

4

What does it mean “failed miserably”? Bad score? Bad solution? How bad solution? How long it run? How much iterations it did? How many jobs do you have? How many vehicles do you have? Do you have “vehicle switch” enabled?

5

I created four services, two services close to the pickup location with a timewindow of (0, 60), and two far orders with a timewindow of (300, 360). Vehicle configurations were set such that i was expecting to get one route only, as the waiting time for delivering the two far orders would have been too large, but still all four services fell into one route in the final solution. The algorithm runs for a maximum of 2000 iterations and execution time is not a problem, but it is as if waiting time penalty is not being considered at all.

6

Im afraid that this colides with main objective to do all jobs. So when there are 4 shipments, jsprit will try to deliver all of them and then lower the cost. But he never try not deliver a shipment to lower the cost. This is probably a reason why you cannot achieve your goal in such small problem.