GraphHopper.com | Forum | GitHub | Maps | Blog

HardConstraint for jobs with no transport time


#1

Hi, I’m trying to add a hard constraint where if the transport time between two activities is zero, then the job cannot be assigned to the current route (at the moment). Here’s an example of time matrix:

Matrix

My matrix is not symmetric, so Start/End to A2 is zero but A2 to Start/End is 10. The route obtained is discarding activity A2, but the job can be assigned from A1 to A2 (because has no zero time):

Route

Finally, here’s my code:

public class AlternativeTimeDistanceConstraint implements HardActivityConstraint {

    //....

    @Override
    public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
        double newActArrTime = prevActDepTime + costMatrix.getTransportTime(prevAct.getLocation(), newAct.getLocation(), prevActDepTime, null, null);

        if (prevActDepTime == newActArrTime) {                
            return ConstraintsStatus.NOT_FULFILLED;
        }

        double newActDepTime = newActArrTime + newAct.getOperationTime();
        double nextActArrTime = newActDepTime + costMatrix.getTransportTime(newAct.getLocation(), nextAct.getLocation(), newActDepTime, null, null);

        if (newActDepTime == nextActArrTime) {
            return ConstraintsStatus.NOT_FULFILLED;
        }

        return ConstraintsStatus.FULFILLED;
    }    
}

Thanks in advance


#2

is your distance matrix all zeros? it seems that A2 gets unassigned in your case because the penalty for unassigned job is 0 (maxCosts in the objective function). you can try and define a positive MAX_TRANSPORT_COSTS, e.g.:

algoBuilder.setProperty(Jsprit.Parameter.MAX_TRANSPORT_COSTS, "100");

moreover, it seems this constraint could potentially be broken by the ruin process. you might want to address that.


#3

@jie31best In my matrix, the distance is zero only when the time is zero. I tried to define MAX_TRANSPORT_COSTS, but the result still the same.

If my constraint is broken by the ruin process, what can I do?


#4

hmm, but it works on my side…

    VehicleType vehicleType = VehicleTypeImpl.Builder.newInstance("type")
        .build();

    Vehicle vehicle = VehicleImpl.Builder.newInstance("veh")
        .setType(vehicleType)
        .setStartLocation(Location.newInstance(0))
        .setEndLocation(Location.newInstance(0))
        .setReturnToDepot(true)
        .build();

    Service s1 = Service.Builder.newInstance("s1")
        .setLocation(Location.newInstance(1))
        .build();
    Service s2 = Service.Builder.newInstance("s2")
        .setLocation(Location.newInstance(2))
        .build();

    final FastVehicleRoutingTransportCostsMatrix costsMatrix =
        FastVehicleRoutingTransportCostsMatrix.Builder.newInstance(3, false)
//            .addTransportTime(0, 1, 10)
//            .addTransportTime(0, 2, 0)
//            .addTransportTime(1, 0, 10)
//            .addTransportTime(1, 2, 8)
//            .addTransportTime(2, 0, 10)
//            .addTransportTime(2, 1, 8)
            .addTransportTimeAndDistance(0, 1, 10, 10)
            .addTransportTimeAndDistance(0, 2, 0, 0)
            .addTransportTimeAndDistance(1, 0, 10, 10)
            .addTransportTimeAndDistance(1, 2, 8, 8)
            .addTransportTimeAndDistance(2, 0, 10, 10)
            .addTransportTimeAndDistance(2, 1, 8, 8)
            .build();

    final VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
        .addJob(s1)
        .addJob(s2)
        .addVehicle(vehicle)
        .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
        .setRoutingCost(costsMatrix)
        .build();

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

    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) {
//            VehicleRoutingTransportCosts transportCosts = vrp.getTransportCosts();
//            double transportTimeFromPrevToNew = transportCosts.getTransportTime(
//                prevAct.getLocation(), newAct.getLocation(), prevActDepTime,
//                iFacts.getNewDriver(), iFacts.getNewVehicle()
//            );
//            if (transportTimeFromPrevToNew <= Math.ulp(0.))
//                return ConstraintsStatus.NOT_FULFILLED;
//            double newActArrTime = prevActDepTime + transportTimeFromPrevToNew;
//            double newActStartTime = Math.max(newActArrTime,
//                newAct.getTheoreticalEarliestOperationStartTime());
//            double newActDuration = vrp.getActivityCosts().getActivityDuration(
//                newAct, newActArrTime, iFacts.getNewDriver(), iFacts.getNewVehicle()
//            );
//            double newActDepTime = newActStartTime + newActDuration;
//            double transportTimeFromNewToNext = transportCosts.getTransportTime(
//                newAct.getLocation(), nextAct.getLocation(), newActDepTime,
//                iFacts.getNewDriver(), iFacts.getNewVehicle()
//            );
//            if (transportTimeFromNewToNext <= Math.ulp(0.))
//                return ConstraintsStatus.NOT_FULFILLED;
//            return ConstraintsStatus.FULFILLED;

            double newActArrTime = prevActDepTime + costsMatrix.getTransportTime(
                prevAct.getLocation(), newAct.getLocation(), prevActDepTime, null, null);

            if (prevActDepTime == newActArrTime) {
                return ConstraintsStatus.NOT_FULFILLED;
            }

            double newActDepTime = newActArrTime + newAct.getOperationTime();
            double nextActArrTime = newActDepTime + costsMatrix.getTransportTime(
                newAct.getLocation(), nextAct.getLocation(), newActDepTime, null, null);

            if (newActDepTime == nextActArrTime) {
                return ConstraintsStatus.NOT_FULFILLED;
            }

            return ConstraintsStatus.FULFILLED;
        }
    }, ConstraintManager.Priority.HIGH);
    algoBuilder.setStateAndConstraintManager(stateManager, constraintManager);

    //algoBuilder.setProperty(Jsprit.Parameter.MAX_TRANSPORT_COSTS, "100");

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

#5

@jie31best, using your example, I notice that the problem is with my custom matrix. Using FastVehicleRoutingTransportCostsMatrix or VehicleRoutingTransportCostsMatrix works fine.

I have a custom matrix with multi time/distance for each from/to pairs and the information is returned considering the current time so, Start/End to A2 could be 0 or 10. I will try to find the problem with my matrix. Thank you for your help.

My matrix:

public class MultiTimeDistanceCostsMatrix extends AbstractForwardVehicleRoutingTransportCosts {

    static class RelationKey {

        static RelationKey newKey(String from, String to) {
            return new RelationKey(from, to);
        }

        final String from;
        final String to;

        public RelationKey(String from, String to) {
            super();
            this.from = from;
            this.to = to;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((from == null) ? 0 : from.hashCode());
            result = prime * result + ((to == null) ? 0 : to.hashCode());
            return result;
        }
    
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            RelationKey other = (RelationKey) obj;
            if (from == null) {
                if (other.from != null)
                    return false;
            } else if (!from.equals(other.from))
                return false;
            if (to == null) {
                if (other.to != null)
                    return false;
            } else if (!to.equals(other.to))
                return false;
            return true;
        }
    }
    
    public static class Builder {
        private static Logger log = LoggerFactory.getLogger(Builder.class);

        private Map<RelationKey, List<TimeDistance>> timesDistances = new HashMap<>();

        private boolean timesDistancesSet = false;

        private Map<String, BlockArea> blockAreas = new HashMap<>();
        
        public static Builder newInstance() {
            return new Builder();
        }

        private Builder() {
        }

        public Builder addTimesDistances(String from, String to, List<TimeDistance> timesDistances) {
            RelationKey key = RelationKey.newKey(from, to);
            if (!timesDistancesSet) timesDistancesSet = true;
            if (this.timesDistances.containsKey(key)) {
                log.warn("times/distances from " + from + " to " + to + " already exists. This overrides times/distances.");
            }
            this.timesDistances.put(key, timesDistances);
            return this;
        }

        public Builder addBlockAreas(List<BlockArea> blockAreas) {
            for (BlockArea blockArea : blockAreas) {
                if (!this.blockAreas.containsKey(blockArea.id)) this.blockAreas.put(blockArea.id, blockArea);
            }
            return this;
        }
        
        public MultiTimeDistanceCostsMatrix build() {
            return new MultiTimeDistanceCostsMatrix(this);
        }


    }

    private Map<RelationKey, List<TimeDistance>> timesDistances = new HashMap<>();

    private boolean timesDistancesSet;

    private List<BlockArea> blockAreas;

    private MultiTimeDistanceCostsMatrix(Builder builder) {
        timesDistances.putAll(builder.timesDistances);
        timesDistancesSet = builder.timesDistancesSet;
        blockAreas = new ArrayList<>(builder.blockAreas.values());
    }

    @Override
    public double getTransportTime(Location from, Location to, double departureTime, Driver driver, Vehicle vehicle) {
        String fromId = from.getId();
        String toId = to.getId();
        return getTime(fromId, toId, getIdsValidBlockAreas(fromId, toId, departureTime));
    }

    public List<String> getIdsValidBlockAreas(String fromId, String toId, double departureTime) {
        List<String> validBlockAreas = new ArrayList<>();

        double arrivalTime = departureTime + getTimeWithoutBlockAreas(fromId, toId);
        fillValidBlockAreas(fromId, toId, departureTime, arrivalTime, validBlockAreas);

        return validBlockAreas;
    }

    private void fillValidBlockAreas(String fromId, String toId, double departureTime, double arrivalTime, List<String> valid) {
        for (BlockArea blockArea : blockAreas) {
            for (BlockInterval interval : blockArea.blockIntervals) {
                if (interval.startTime <= departureTime && interval.endTime >= departureTime || interval.startTime >= departureTime && interval.startTime <= arrivalTime) {
                    if (!valid.contains(blockArea.id)) {
                        valid.add(blockArea.id);
                        double newArrivalTime = departureTime + getTime(fromId, toId, valid);
                        fillValidBlockAreas(fromId, toId, departureTime, newArrivalTime, valid);
                    }
                }
            }
        }
    }

    private double getTimeWithoutBlockAreas(String fromId, String toId) {
        return getTime(fromId, toId, Collections.emptyList());
    }

    private double getTime(String fromId, String toId, List<String> blockAreas) {
        Optional<TimeDistance> possibleTimeDistance = getTimeDistance(fromId, toId, blockAreas);

        if (possibleTimeDistance.isPresent()) {
            return possibleTimeDistance.get().getTime();
        } else return 0.0;
    }

    private Optional<TimeDistance> getTimeDistance(String fromId, String toId, List<String> blockAreas) {
        if (fromId.equals(toId)) return Optional.empty();
        if (!timesDistancesSet) return Optional.empty();
        RelationKey key = RelationKey.newKey(fromId, toId);

        if (timesDistances.containsKey(key)) {
            List<TimeDistance> distances = timesDistances.get(key);
            for (TimeDistance distance : distances) {
                List<String> ids = distance.getBlockAreas().stream().map(b -> b.getId()).collect(Collectors.toList());
                if (ids.size() == blockAreas.size() && ids.containsAll(blockAreas)) return Optional.of(distance);
            }
        }

        throw new IllegalStateException("time/distance value for relation from " + fromId + " to " + toId + " does not exist");
    }
    
    public double getDistance(String fromId, String toId, List<String> blockAreas) {
        Optional<TimeDistance> possibleTimeDistance = getTimeDistance(fromId, toId, blockAreas);

        if (possibleTimeDistance.isPresent()) {
            return possibleTimeDistance.get().getDistance();
        } else return 0.0;

    }

    @Override
    public double getTransportCost(Location from, Location to, double departureTime, Driver driver, Vehicle vehicle) {
        String fromId = from.getId();
        String toId = to.getId();
        List<String> blockAreas = getIdsValidBlockAreas(fromId, toId, departureTime);
        if (vehicle == null) return getDistance(fromId, toId, blockAreas);

        VehicleTypeImpl.VehicleCostParams costParams = vehicle.getType().getVehicleCostParams();
        return costParams.perDistanceUnit * getDistance(fromId, toId, blockAreas) + costParams.perTransportTimeUnit * getTime(fromId, toId, blockAreas);
    }

    public double getDistance(Location from, Location to, double departureTime) {
        String fromId = from.getId();
        String toId = to.getId();
        return getDistance(from.getId(), to.getId(), getIdsValidBlockAreas(fromId, toId, departureTime));
    }
}

#6

I found what is the problem. When:

  • prevAct = Start
  • newAct = A2
  • nextAct = End

Using FastVehicleRoutingTransportCostsMatrix the result is NOT_FULFILLED, because the transport time is always the same for each from/to pairs.

Using my matrix (MultiTimeDistanceCostsMatrix) the result is FULFILLED, because based on time of prevActDepTime parameter, time/distance is not zero.

  • prevAct = A1
  • newAct = A2
  • nextAct = End

In this case, with any matrix, the result of the constraint is NOT_FULFILLED.

Does anyone have any idea how to archive this?