I'm using JSPRIT to solve routing and travelsman problems. It is actually working for simple constraints (time, capacity, etc.). But I tried to implement the "Related jobs" constaints. I succeeded for the simple case like the 7th job to be served before the 1st in the list.
I want to group and optimize some services. I would like to force the 7th to be served before the 1st AND the 21st before the 13th for exemple. And maybe some more.
When I try this, the result order only the 7th before the 1st but the 21st is not before the 13th and sometimes not even in the same route.
It's a more complex case than : Related jobs in JSprit .
Would anyone has an exemple? Has someone tried this?
public final static int PERSON_DIMENSION_INDEX = 0;
public final static boolean VEHICLE_RETURNS_AT_DEPOT = false;
public final static Location TEST_VEHICLE_LOCATION = Location.newInstance(48.856614, 2.352222);
public final static int TEST_VEHICLE_LOCATION_INDEX = 0;
public final static int MAX_INCREMENT = 25;
public final static boolean USE_DISTANCE_MATRIX = true;
public final static boolean ADD_TIME_CONSTRAINTS = false;
public final static boolean USE_ONE_BEFORE_ANOTHER_CONSTRAINT = true;
private static final boolean PLOT_RESULT = false;
public static void main(String[] args) {
/*
* Date today : 8 o'clock
*/
// .getDirections(contextTest, "27 rue jacques louvel tessier", "10 rue
// de geispitzen");
Calendar c = new GregorianCalendar();
c.set(Calendar.HOUR_OF_DAY, 8); // anything 0 - 23
c.set(Calendar.MINUTE, 0);
c.set(Calendar.SECOND, 0);
Date d1 = c.getTime(); // the midnight, that's the first second of the
// day.
System.out.println("Date today 8h clock");
System.out.println(d1.toString());
System.out.println(d1.getTime() / 1000);
final long TODAY_START_TIME = d1.getTime() / 1000;
/*
* Here, get the vehicles types.
*/
List<TypeVehicle> vehicleTypes = getVehiclesTypesFromDatabase();
/*
* Built de jsprit vehicle types.
*/
Map<String, VehicleTypeImpl> jSpritvVehicleTypes = new HashMap<String, VehicleTypeImpl>();
for (TypeVehicle vehicleType : vehicleTypes) {
String vehicleTypeId = String.valueOf(vehicleType.getId());
int vehicleCapacity = vehicleType.getAvailableSeats();
VehicleTypeImpl jSpritvVehicleType = VehicleTypeImpl.Builder.newInstance(vehicleTypeId)
.addCapacityDimension(PERSON_DIMENSION_INDEX, vehicleCapacity).build();
jSpritvVehicleTypes.put(vehicleTypeId, jSpritvVehicleType);
}
/*
* Here, get the vehicles.
*/
List<Vehicle> vehicles = getVehiclesFromDatabase();
/*
* Here, build the vehicles.
*/
Map<String, VehicleImpl> jSpritVehicles = new HashMap<String, VehicleImpl>();
for (Vehicle Vehicle : vehicles) {
String vehicleId = String.valueOf(Vehicle.getId());
List<Habilitation> habilitations = Vehicle.getHabilitations();
String thisVehicleTypeId = String.valueOf(Vehicle.getType());
VehicleTypeImpl vehicleType = jSpritvVehicleTypes.get(thisVehicleTypeId);
Skills skills = null;
for (Habilitation habilitation : habilitations) {
skills = new Skills.Builder().addSkill(habilitation.getLabel()).build();
}
VehicleImpl vehicleImpl = VehicleImpl.Builder.newInstance(vehicleId).setType(vehicleType).addSkills(skills)
.setStartLocation(TEST_VEHICLE_LOCATION).setEarliestStart(TODAY_START_TIME).build();
jSpritVehicles.put(vehicleId, vehicleImpl);
}
/*
* Here, get the spots to serve (pickups and deliveries)
*/
List<Place> places = getSpots(); // This will change a lot.
List<Service> services = new ArrayList<Service>();
int increment = 0;
String[] origins = new String[MAX_INCREMENT];
String[] destinations = new String[MAX_INCREMENT];
origins[0] = TEST_VEHICLE_LOCATION.getCoordinate().getX() + "," + TEST_VEHICLE_LOCATION.getCoordinate().getY();
destinations[0] = TEST_VEHICLE_LOCATION.getCoordinate().getX() + ","
+ TEST_VEHICLE_LOCATION.getCoordinate().getY();
increment++;
for (Place place : places) {
if (increment < MAX_INCREMENT) {
String id = String.valueOf(increment);
int dimensionValue = place.getAccessibility();
double lat = place.getLat();
double lng = place.getLng();
Location location = Location.newInstance(lat, lng);
Service.Builder builder = Service.Builder.newInstance(id)
.addSizeDimension(PERSON_DIMENSION_INDEX, dimensionValue).setLocation(location);
/*
* TIME CONSTRAINTS
*/
if (ADD_TIME_CONSTRAINTS) {
int random = randomNumber(0, 43200); // 12 hours of possible
// work. 8am / 8pm
System.out.println("Time windows : " + new Date((TODAY_START_TIME + random) * 1000).toString()
+ " / " + new Date((TODAY_START_TIME + random + 1800) * 1000).toString());
builder.addTimeWindow(TODAY_START_TIME + random, TODAY_START_TIME + random + 1800);
}
Service service = builder.build();
services.add(service);
origins[increment] = lat + "," + lng;
destinations[increment] = lat + "," + lng;
increment++;
}
}
/*
* Here, get the constraints (ex : one before another)
*/
/*
* Here, get the time limits
*/
VehicleRoutingTransportCostsMatrix costsMatrix;
if (USE_DISTANCE_MATRIX) {
/*
* Distances matrix
*/
VehicleRoutingTransportCostsMatrix.Builder vrtcMatrix = VehicleRoutingTransportCostsMatrix.Builder
.newInstance(true);
GeoApiContext context = null;
costsMatrix = generateCostMatrix(origins, destinations, vrtcMatrix, context);
}
/*
* Init jsprit
*/
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.addAllVehicles(jSpritVehicles.values()).addAllJobs(services);
vrpBuilder.setFleetSize(FleetSize.INFINITE);
if (USE_DISTANCE_MATRIX) {
System.out.println("Using DISTANCE MATRIX...");
vrpBuilder = vrpBuilder.setRoutingCost(costsMatrix);
} else {
System.out.println("NOT Using DISTANCE MATRIX...");
}
VehicleRoutingProblem problem = vrpBuilder.build();
/*
* get the algorithm out-of-the-box.
*/
VehicleRoutingAlgorithm algorithm;
if (USE_ONE_BEFORE_ANOTHER_CONSTRAINT) {
/**
* Adding constraints...
*/
String before = "11";
String after = "9";
final StateManager stateManager = new StateManager(problem);
stateManager.addStateUpdater(new JobsInRouteMemorizer(stateManager));
ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);
constraintManager.addConstraint(new OneJobBeforeAnother(stateManager, before, after));
final RewardAndPenaltiesThroughSoftConstraints contrib = new RewardAndPenaltiesThroughSoftConstraints(problem, before, after);
SolutionCostCalculator costCalculator = new SolutionCostCalculator() {
@Override
public double getCosts(VehicleRoutingProblemSolution solution) {
double costs = 0.;
List<VehicleRoute> routes = (List<VehicleRoute>) solution.getRoutes();
for(VehicleRoute route : routes){
costs+=route.getVehicle().getType().getVehicleCostParams().fix;
costs+=stateManager.getRouteState(route, InternalStates.COSTS, Double.class);
costs+=contrib.getCosts(route);
}
return costs;
}
};
VehicleRoutingAlgorithmBuilder vraBuilder = new VehicleRoutingAlgorithmBuilder(problem,
"algorithmConfig.xml");
vraBuilder.addCoreConstraints();
vraBuilder.setStateAndConstraintManager(stateManager, constraintManager);
vraBuilder.setObjectiveFunction(costCalculator);
algorithm = vraBuilder.build();
} else {
algorithm = Jsprit.createAlgorithm(problem);
}
/*
* and search a solution which returns a collection of solutions (here
* only one solution is constructed)
*/
Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
/*
* use the static helper-method in the utility class Solutions to get
* the best solution (in terms of least costs)
*/
for (VehicleRoutingProblemSolution vehicleRoutingProblemSolution : solutions) {
System.out.println("Solution #"
+ ((List<VehicleRoutingProblemSolution>) solutions).indexOf(vehicleRoutingProblemSolution));
System.out.println(vehicleRoutingProblemSolution.getCost());
}
VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);
SolutionPrinter.print(problem, bestSolution, Print.VERBOSE);
new GraphStreamViewer(problem, bestSolution).labelWith(Label.ID).setRenderDelay(100).display();
if(PLOT_RESULT){
new GraphStreamViewer(problem, bestSolution).labelWith(Label.ID).setRenderDelay(100).display();
}
}
I finally found out. I just forgot to add the generated costs to the cost calculator. See below :
final List<RewardAndPenaltiesThroughSoftConstraints> contribs = new ArrayList<RewardAndPenaltiesThroughSoftConstraints>();
for (Integer id : forcedOrdersList.keySet()) {
List<String> order= forcedOrdersList.get(id);
String before = order.get(0);
String after = order.get(1);
constraintManager.addConstraint(new OneJobBeforeAnother(stateManager, before, after));
contribs.add(new RewardAndPenaltiesThroughSoftConstraints(problem, before, after));
}
SolutionCostCalculator costCalculator = new SolutionCostCalculator() {
@Override
public double getCosts(VehicleRoutingProblemSolution solution) {
double costs = 0.;
List<VehicleRoute> routes = (List<VehicleRoute>) solution.getRoutes();
for(VehicleRoute route : routes){
costs+=route.getVehicle().getType().getVehicleCostParams().fix;
costs+=stateManager.getRouteState(route, InternalStates.COSTS, Double.class);
for (RewardAndPenaltiesThroughSoftConstraints contrib : contribs) {
costs+=contrib.getCosts(route);
}
}
return costs;
}
};