GraphHopper.com | Forum | GitHub | Maps | Blog

Skills with priorities does not work?


#1

In that case we override the transport cost function it’s always |x1-x2| + |y1-12|, just to simplify the problem…
I have 2 services with priority 1 and one shipment with priority 10 and requires skill “C”. I have 2 drivers, one with skill “C” which is near to the services, the second driver is near the shipment, but does not have required skills… so the solution is:
±-------------------------+
| problem |
±--------------±---------+
| indicator | value |
±--------------±---------+
| noJobs | 3 |
| noServices | 2 |
| noShipments | 1 |
| noBreaks | 0 |
| fleetsize | FINITE |
±-------------------------+
±---------------------------------------------------------+
| solution |
±--------------±-----------------------------------------+
| indicator | value |
±--------------±-----------------------------------------+
| costs | 39.0 |
| noVehicles | 1 |
| unassgndJobs | 1 |
±---------------------------------------------------------+
±-------------------------------------------------------------------------------------------------------------------------------+
| detailed solution |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| route | vehicle | activity | job | arrTime | endTime | costs |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 1 | v1 | start | - | undef | 0 | 0 |
| 1 | v1 | delivery | service_b2d3e | 5 | 6 | 5 |
| 1 | v1 | delivery | service_b4b17 | 7 | 8 | 6 |
| 1 | v1 | end | - | 8 | undef | 6 |
±-------------------------------------------------------------------------------------------------------------------------------+
±---------------+
| unassignedJobs |
±---------------+
| shipment_5bca3 |
±---------------+

if I change the shipment priority to 1, all tasks assigned:
±-------------------------+
| problem |
±--------------±---------+
| indicator | value |
±--------------±---------+
| noJobs | 3 |
| noServices | 2 |
| noShipments | 1 |
| noBreaks | 0 |
| fleetsize | FINITE |
±-------------------------+
±---------------------------------------------------------+
| solution |
±--------------±-----------------------------------------+
| indicator | value |
±--------------±-----------------------------------------+
| costs | 33.0 |
| noVehicles | 2 |
| unassgndJobs | 0 |
±---------------------------------------------------------+
±-------------------------------------------------------------------------------------------------------------------------------+
| detailed solution |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| route | vehicle | activity | job | arrTime | endTime | costs |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 1 | v1 | start | - | undef | 0 | 0 |
| 1 | v1 | pickupShipment | shipment_60c0d | 20 | 21 | 20 |
| 1 | v1 | deliverShipment | shipment_60c0d | 23 | 24 | 22 |
| 1 | v1 | end | - | 24 | undef | 22 |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 2 | v2 | start | - | undef | 0 | 0 |
| 2 | v2 | delivery | service_4860b | 8 | 9 | 8 |
| 2 | v2 | delivery | service_fac84 | 10 | 11 | 9 |
| 2 | v2 | end | - | 11 | undef | 9 |
±-------------------------------------------------------------------------------------------------------------------------------+
Do i do something wrong, or it’s a bug?
Thanks,
Ira.

here’s the example:
(in package com.graphhopper.jsprit.examples)
public static void main(String[] args) {
final HashSet first = new HashSet<>(); first.add(“C”);
final HashSet second = new HashSet<>(); second.add(“A”);second.add(“B”);
final VehicleRoutingProblem.Builder builder = VehicleRoutingProblem.Builder.newInstance().setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
.addVehicle(getVehicle(“v1”, Location.newInstance(0, 0), 0, 100, 20, first, false, 1, 1))
.addVehicle(getVehicle(“v2”, Location.newInstance(0, 14), 0, 100, 20, second, false, 1, 1))
.addJob(getService(Location.newInstance(0, 5), 0, 20, new HashSet(), 1))
.addJob(getService(Location.newInstance(0, 6), 0, 20, new HashSet(), 1))
.addJob(getShipment(Location.newInstance(10, 10), Location.newInstance(10, 12), 10, 20, 10, 50, first, 10));

    builder.setRoutingCost(getTransportCosts());
    VehicleRoutingProblem problem = builder.build();

    VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);
    Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();

    VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);

    new VrpXMLWriter(problem, solutions).write("output/problem-with-solution.xml");

    SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);
    new GraphStreamViewer(problem, bestSolution).labelWith(Label.ID).setRenderDelay(200).display();
}

private static VehicleRoutingTransportCosts getTransportCosts() {
    return new VehicleRoutingTransportCosts() {
        @Override
        public double getBackwardTransportCost(Location from, Location to, double arrivalTime, Driver driver, Vehicle vehicle) { return getDistance(from, to, arrivalTime, vehicle); }

        @Override
        public double getBackwardTransportTime(Location from, Location to, double arrivalTime, Driver driver, Vehicle vehicle) { return getDistance(from, to, arrivalTime, vehicle); }

        @Override
        public double getTransportCost(Location from, Location to, double departureTime, Driver driver, Vehicle vehicle) { return getDistance(from, to, departureTime, vehicle); }

        @Override
        public double getTransportTime(Location from, Location to, double departureTime, Driver driver, Vehicle vehicle) { return getDistance(from, to, departureTime, vehicle); }

        @Override
        public double getDistance(Location from, Location to, double departureTime, Vehicle vehicle) {
            return Math.abs(from.getCoordinate().getX() - to.getCoordinate().getX()) + Math.abs(from.getCoordinate().getY() - to.getCoordinate().getY());
        }
    };
}

private static Vehicle getVehicle(String id, Location location, int start, int end, int capacity, Set<String> skills, boolean returnToDepot, int fixedCost, int costPerDistance) {
    return VehicleImpl.Builder.newInstance(id)
        .setStartLocation(location).setLatestArrival(end).setEarliestStart(start).setType(
            VehicleTypeImpl.Builder.newInstance(UUID.randomUUID().toString()).setFixedCost(fixedCost).setCostPerDistance(costPerDistance).addCapacityDimension(0, capacity).build()
        )
        .addAllSkills(skills).setReturnToDepot(returnToDepot).build();

}

private static Service getService(Location location, int start, int end, Set<String> requiredSkills, int priority) {
    return Delivery.Builder.newInstance("service_" + UUID.randomUUID().toString().substring(0,5))
        .setLocation(location)
        .setServiceTime(1)
        .addTimeWindow(new TimeWindow(start, end))
        .addSizeDimension(0, 1)
        .addAllRequiredSkills(requiredSkills)
        .setPriority(priority)
        .setName(UUID.randomUUID().toString()).build();

}

public static Shipment getShipment(Location pickupLocation, Location dropoffLocation, int pickupStart, int pickupEnd, int dropoffStart, int dropoffEnd, Set<String> skills, int priority) {
    return Shipment.Builder.newInstance("shipment_" + UUID.randomUUID().toString().substring(0,5))
        .setPickupLocation(pickupLocation).setDeliveryLocation(dropoffLocation)
        .setDeliveryServiceTime(1).setPickupServiceTime(1)
        .addSizeDimension(0, 1)
        .setPickupTimeWindow(new TimeWindow(pickupStart, pickupEnd))
        .setDeliveryTimeWindow(new TimeWindow(dropoffStart, dropoffEnd))
        .addAllRequiredSkills(skills)
        .setPriority(priority)
        .build();
}

#2

with my understanding of how JSprit works, my assumption would be that the cost of the solution in the first case ( shipment priority 10 ) is lower when having the shipment unassigned, rather than having a vehicle to pick up and deliver the shipment.
Try toying with the priority of the services and you should be seeing the cost changing as you change the priorities
BR,
Patrik.