2
Ich benutze JSPRIT, um Routing- und Travelmans-Probleme zu lösen. Es arbeitet tatsächlich für einfache Einschränkungen (Zeit, Kapazität usw.). Aber ich habe versucht, die "Related Jobs" Constaints zu implementieren. Ich schaffte es für den einfachen Fall wie den 7. Job, der vor dem 1. in der Liste gedient wird.Jsprit: Kann mehrere zusammenhängende Jobs nicht hinzufügen
Ich möchte einige Dienste gruppieren und optimieren. Ich möchte den 7. vor dem 1. UND 21. vor dem 13. zum Beispiel erzwingen. Und vielleicht noch mehr.
Wenn ich das versuche, ist die Ergebnisreihenfolge nur die 7. vor der 1. aber die 21. ist nicht vor der 13. und manchmal nicht einmal auf der gleichen Route.
Es ist ein komplexerer Fall als: Related jobs in JSprit.
Hätte jemand ein Exemplar? Hat jemand das versucht?
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();
}
}