Not complete cost matrix

Hi guys!

I just started working with jsprit library. Examples are going well.
But I have specific request from my boss, and to tell you the truth I’m kinda stuck :confused:

I have to plan route on 236 stops, and I have cost matrix including time and distance for that. Problem is that this matrix is not complete. cause for each stop I get data only for 8 nearest stops. it gives me error like below:

Caused by: java.lang.NullPointerException
at jsprit.core.util.EuclideanDistanceCalculator.calculateDistance(EuclideanDistanceCalculator.java:23) [jsprit-core-1.6.2.jar:]

and this is my code:

//based on stop list create list of services
List serviceList = stopList.stream()
.map(s → Service.Builder.newInstance(s.getInvoiceId())
.addSizeDimension(0, s.getQty() > 0 ? s.getQty() : (s.getQty() * -1))
.setLocation(Location.newInstance(s.getInvoiceId()))
.build())
.collect(Collectors.toList());

    //based on cost matrix from DB create cost matrix for algorithm
    VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(false);
    matrix.stream().forEach(m -> {
         costMatrixBuilder.addTransportTime(m.getIdFrom(), m.getIdTo(), m.getTime());
        costMatrixBuilder.addTransportDistance(m.getIdFrom(), m.getIdTo(), m.getDistance());
    });
    VehicleRoutingTransportCosts costMatrix = costMatrixBuilder.build();
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
            .setFleetSize(VehicleRoutingProblem.FleetSize.INFINITE)
            .setRoutingCost(costMatrix)
            .addVehicle(vehicle)
            .addAllJobs(serviceList)
            .build();
    VehicleRoutingAlgorithm vra = Jsprit.createAlgorithm(vrp);
    VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(vra.searchSolutions());

I checked - it tries to calculate distance based on location coordinates, but I don’t supply that - I want to use my incomplete matrix for that.

Can someone help me with this one? Does anybody used that before?
thanks in advance

EDIT

After carefully reading thru jsprit code, I found places where this error is generated, and I wrote my own VehicleRoutingTransportCostsMatrix extending AbstractForwardVehicleRoutingTransportCosts.
and when it is in situation that there is no data about distance or time, it’s not crashes, but returns insanely big value, so that this route would not be considered as a good one.

If anyone has better solution I will be very thankful.

You should provide costs for each pair of locations. If you do not have time and distance information from your matrix then just add a proxi, e.g. a huge number or so …

Thank you Stefan.

I did that : here is my class code:

public class VehicleRoutingTransportCostsMatrixCustom extends AbstractForwardVehicleRoutingTransportCosts {

private Map<RelationKey, Double> distances;
private Map<RelationKey, Double> times;
private boolean isSymmetric;
private boolean timesSet;
private boolean distancesSet;
private final Double MAX_VALUE = 9999999999.0D;
private VehicleRoutingTransportCostsMatrixCustom(Builder builder) {
    this.distances = new HashMap<>();
    this.times = new HashMap<>();
    this.isSymmetric = builder.isSymmetric;
    this.distances.putAll(builder.distances);
    this.times.putAll(builder.times);
    this.timesSet = builder.timesSet;
    this.distancesSet = builder.distancesSet;
    LOGGER.info("TIME SET " + this.timesSet);
    LOGGER.info("DISTANCE SET " + this.distancesSet);
}
public double getTransportTime(Location from, Location to, double departureTime, Driver driver, Vehicle vehicle) {
    return getTime(from.getId(), to.getId());
}
private double getTime(String fromId, String toId) {
    if(fromId.equals(toId)) {
        return 0.0D;
    } else if(!timesSet) {
        return 0.0D;
    } else {
        RelationKey key = RelationKey.newKey(fromId, toId);
        if(!this.isSymmetric) {
            if(this.times.containsKey(key)) {
                return this.times.get(key);
            } else {
                return MAX_VALUE;
            }
        } else {
            Double time = this.times.get(key);
            if(time == null) {
                time = this.times.get(RelationKey.newKey(toId, fromId));
            }
            if(time != null) {
                return time;
            } else {
                return MAX_VALUE;
            }
        }
    }
}
public double getDistance(String fromId, String toId) {
    if(fromId.equals(toId)) {
        return 0.0D;
    } else if(!distancesSet) {
        return 0.0D;
    } else {
        RelationKey key = RelationKey.newKey(fromId, toId);
        if(!isSymmetric) {
            if(distances.containsKey(key)) {
                return distances.get(key);
            } else {
                return MAX_VALUE;
            }
        } else {
            Double time = distances.get(key);
            if(time == null) {
                time = distances.get(RelationKey.newKey(toId, fromId));
            }
            if(time != null) {
                return time;
            } else {
                return MAX_VALUE;
            }
        }
    }
}
public double getTransportCost(Location from, Location to, double departureTime, Driver driver, Vehicle vehicle) {
    if(vehicle == null) {
        return this.getDistance(from.getId(), to.getId());
    } else {
        VehicleTypeImpl.VehicleCostParams costParams = vehicle.getType().getVehicleCostParams();
        return costParams.perDistanceUnit * getDistance(from.getId(), to.getId()) + costParams.perTransportTimeUnit * getTime(from.getId(), to.getId());
    }
}
public static class Builder {
    private static Logger log = LogManager.getLogger(Builder.class);
    private boolean isSymmetric;
    private Map<RelationKey, Double> distances = new HashMap<>();
    private Map<RelationKey, Double> times = new HashMap<>();
    private boolean distancesSet = false;
    private boolean timesSet = false;
    public static Builder newInstance(boolean isSymmetric) {
        return new Builder(isSymmetric);
    }
    private Builder(boolean isSymmetric) {
        this.isSymmetric = isSymmetric;
    }
    public Builder addTransportDistance(String from, String to, double distance) {
        RelationKey key = RelationKey.newKey(from, to);
        if(!distancesSet) {
            distancesSet = true;
        }
        if(distances.containsKey(key)) {
            log.warn("distance from " + from + " to " + to + " already exists. This overrides distance.");
        }
        distances.put(key, distance);
        if(isSymmetric) {
            RelationKey revKey = RelationKey.newKey(to, from);
            if(distances.containsKey(revKey)) {
                distances.put(revKey, distance);
            }
        }
        return this;
    }
    public Builder addTransportTime(String from, String to, double time) {
        RelationKey key = RelationKey.newKey(from, to);
        if(!timesSet) {
            timesSet = true;
        }
        if(this.times.containsKey(key)) {
            log.warn("transport-time from " + from + " to " + to + " already exists. This overrides times.");
        }
        this.times.put(key, time);
        if(this.isSymmetric) {
            RelationKey revKey = RelationKey.newKey(to, from);
            if(times.containsKey(revKey)) {
                times.put(revKey, time);
            }
        }
        return this;
    }
    public VehicleRoutingTransportCostsMatrixCustom build() {
        return new VehicleRoutingTransportCostsMatrixCustom(this);
    }
}
static class RelationKey {
    final String from;
    final String to;
    static RelationKey newKey(String from, String to) {
        return new RelationKey(from, to);
    }
    public RelationKey(String from, String to) {
        this.from = from;
        this.to = to;
    }
    public int hashCode() {
        boolean prime = true;
        byte result = 1;
        int result1 = 31 * result + (this.from == null?0:this.from.hashCode());
        result1 = 31 * result1 + (this.to == null?0:this.to.hashCode());
        return result1;
    }
    public boolean equals(Object obj) {
        if(this == obj) {
            return true;
        } else if(obj == null) {
            return false;
        } else if(this.getClass() != obj.getClass()) {
            return false;
        } else {
            RelationKey other = (RelationKey)obj;
            if(this.from == null) {
                if(other.from != null) {
                    return false;
                }
            } else if(!this.from.equals(other.from)) {
                return false;
            }
            if(this.to == null) {
                if(other.to != null) {
                    return false;
                }
            } else if(!this.to.equals(other.to)) {
                return false;
            }
            return true;
        }
    }
}

but even I return 9999999999.0 the result looks like this:

when I created full cost matrix (results from google maps api) it generates routes right. You ever had issue like this? or maybe my code is wrong?

thanks again for help

oh does not look like an optimized solution ;). probably jsprit cannot create a reasonable neighborhood. I d do the following: Since you obviously have the coordinates, just calculate a proxi time and distance value base on great circle costs (using Haversine for example) for all pairs of locations you do not have “real” information.

solution is just from decompile JSPRIT class :slight_smile:
I’m gonna try your solution - IDK if I have coordinates - I might need to ask database team to add that to response. Will keep you posted
thank you for your help")

I’m getting there thanks to your pointers - thanks for that:)

BTW - do you know if there is a way to limit route time? cause I get routes for 12 hours - it’s bit much.
Can I limit one route to 6 hours?

1 Like

You can specify earliest start and latest arrival for your vehicles. This way you can limit the operation time of your drivers to 6 hours.

I’m on it!

will give it a try - have good feelings :grinning:
thanks!

is there a documentation of any sort to JSPRIT or only code examples?

I tried using breaks - but it’s not what I need…

Breaks are not what you need to limit working time. A break is time off in the middle of a route e.g. for eating food at lunch.

VehicleImpl vehicle = VehicleImpl.Builder.newInstance(dName).setEarliestStart(dStartTime)
	.setLatestArrival(dEndTime).setStartLocation(Location.newInstance(startLoc)).setReturnToDepot(false).build();

Whatever time unit you work with, you need to specify the start and end times in that unit.

As for documentation; I’m terrible in Java and all I needed to get going with this library with no experience was in here. This is also helpful for starting out.