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();
}