Hi,
The problem in hand contains two identical vehicles (V1 and V2), three non-identical shipments (S1, S2, and S3), and five locations (L1 - L5). You can assume the locations are at a straight line, in order. I have set the optimizer to be run again when the solution contains unassigned jobs, however only twice in row. To do this, I have two lists, one containing new shipments and one containing unassigned jobs from the first optimization run. The optimizer is also run every few days and when a vehicle only has 2 destinations left or less. New shipments are out double of the amount of days than the optimization is run.
Shipments S1 and S2 originate from L1, whereas S3 originates from L2. Destinations for the shipments are L3, L4, and L5 respectively. V1 start is located at L1 and V2 start is located in between L2 and L3.
Basically:
- Gather information from model (assigned shipments from the vehicle model, newShipments list, unassignedShipments list).
- Run optimization.
- Get solution.
- Add assigned jobs to vehicles in model and mark the jobs to be later removed from newShipments list
- If unassigned found, remove such shipments from unassignedShipments list, copy such shipments from newShipments list to unassignedShipments list and mark to be removed from newShipments list.
- If number 5 was run, remove both assigned and unassigned/marked jobs from newShipments list and jump to number 1.
- Done.
This is where it gets interesting.
The program is started and the optimization gives an immediate optimum: V1 picks up S1 and S2 from L1 and then picks up S3 from L2, after which it delivers the shipments to their destinations. No further optimization is needed. The optmiziations at the two final destinations for V1 is as expected. After shipping, there is still a few days to wait.
The second batch of same shipments is out and the optimization is run. The first optimum gives only S3 as an assigned job. The optimization is run again with S3 as assigned to a V2, and S1 and S2 unassigned jobs. The second optimization gives as optimum, where only S1 is assigned (to V2), S3 is nowhere to be seen, and S2 remains as unassigned (and then deleted because of it was the second time it was unassigned in row).
It continues.
The optimizer is run after V2 picks up the shipments from L1, somehow assigning S1 to be delivered by V1, which is still waiting at L5. At that moment V2 carries S1, but does not know it has something to deliver, and V1 thinks it has something to deliver, even though it does not.
I have searched through the documentation and the forum, and have found nothing of the like. Does anybody know how services can just disappear, or even switch vehicle?
Here is the code I have used:
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.setRoutingCost(costMatrix);
for (int i = 0; i < capacities.size(); i++) {
VehicleType vehicleType = VehicleTypeImpl.Builder.newInstance("vehicleType" + i)
.setMaxVelocity(speeds.get(i))
.addCapacityDimension(0, capacities.get(i))
.addCapacityDimension(1, boxMaxWeight * capacities.get(i))
.setFixedCost(fixedCosts.get(i) / minutesPerDay)
.setCostPerServiceTime(idlingCosts.get(i) / minutesPerDay)
.setCostPerWaitingTime(idlingCosts.get(i) / minutesPerDay)
.setCostPerTransportTime(drivingCosts.get(i) / minutesPerDay)
.setCostPerDistance(1)
.build();
VehicleImpl vehicle = VehicleImpl.Builder.newInstance("vehicle" + i)
.setStartLocation(Location.newInstance(Arrays.binarySearch(names, locations.get(i))))
.setReturnToDepot(false)
.setEarliestStart(now)
.setLatestArrival(latestArrival)
.setType(vehicleType)
.addSkill(vehicleSkills.get(i))
.build();
vrpBuilder.addVehicle(vehicle);
List<String> thisDestinations = currentDestinations.get(i);
List<String> thisChains = currentChains.get(i);
List<Double> thisDeadlines = currentDeadlines.get(i);
List<Integer> thisIds = deliveryIds.get(i);
VehicleRoute.Builder initialRoute = VehicleRoute.Builder.newInstance(vehicle);
for (int j = 0; j < thisDestinations.size(); j++) {
Delivery service = Delivery.Builder.newInstance("" + thisIds.get(j))
.addSizeDimension(0, 1)
.addSizeDimension(1, 100)
.setLocation(Location.newInstance(Arrays.binarySearch(names, thisDestinations.get(j))))
.setTimeWindow(new TimeWindow(now, thisDeadlines.get(j)))
.setServiceTime(minutesPerBox)
.setName(thisChains.get(j))
//.setPriority(1) // Setting priority to 1 did not help
.build();
vrpBuilder.addJob(service);
initialRoute.addService(service);
}
initialRoute.build();
vrpBuilder.addInitialVehicleRoute(initialRoute.build());
}
for (int i = 0; i < unassignedOrigins.size(); i++) {
Shipment shipment = Shipment.Builder.newInstance(unassignedIds.get(i) + " " + 1) // 1 means unassigned shipment
.addSizeDimension(0, 1)
.addSizeDimension(1, unassignedAmount.get(i))
.setPickupLocation(Location.newInstance(Arrays.binarySearch(names, unassignedOrigins.get(i))))
.setPickupServiceTime(minutesPerBox)
.setDeliveryLocation(Location.newInstance(Arrays.binarySearch(names, unassignedDestinations.get(i))))
.setDeliveryTimeWindow(new TimeWindow(now, unassignedDeadlines.get(i) + 1440.0*3)) // added 1440.0*3 according to a forum post telling the time window was too narrow, no change to results
.setDeliveryServiceTime(minutesPerBox)
.setName(unassignedOrigins.get(i)+""+unassignedDestinations.get(i)+""+unassignedChains.get(i))
.build();
vrpBuilder.addJob(shipment);
}
for (int i = 0; i < pickups.size(); i++) {
Shipment shipment = Shipment.Builder.newInstance(indices.get(i) + " " + 0) // 0 means new shipment
.addSizeDimension(0, 1)
.addSizeDimension(1, amount.get(i))
.setPickupLocation(Location.newInstance(Arrays.binarySearch(names, pickups.get(i))))
.setPickupServiceTime(minutesPerBox)
.setDeliveryLocation(Location.newInstance(Arrays.binarySearch(names, deliveries.get(i))))
.setDeliveryTimeWindow(new TimeWindow(now, deadline.get(i)))
.setDeliveryServiceTime(minutesPerBox)
.setName(pickups.get(i)+""+deliveries.get(i)+""+chains.get(i))
.build();
vrpBuilder.addJob(shipment);
}
vrpBuilder.setFleetSize(VehicleRoutingProblem.FleetSize.FINITE);
VehicleRoutingProblem vrp = vrpBuilder.build();
Jsprit.Builder builder = Jsprit.Builder.newInstance(vrp);
stateManager = new StateManager(vrp);
ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);
builder.setStateAndConstraintManager(stateManager, constraintManager);
builder.addCoreStateAndConstraintStuff(true);
int cores = Runtime.getRuntime().availableProcessors();
builder.setProperty(Jsprit.Parameter.THREADS, "" + cores);
builder.setProperty(Jsprit.Parameter.THRESHOLD_ALPHA, "0.1");
builder.setProperty(Jsprit.Parameter.VEHICLE_SWITCH, "false");
builder.setProperty(Jsprit.Parameter.FIXED_COST_PARAM, "1.");
builder.setProperty(Jsprit.Parameter.FAST_REGRET, "true");
builder.setProperty(Jsprit.Parameter.MAX_TRANSPORT_COSTS, Double.toString(1.0E8)); // Used by recommendations found in the forum, no change to results
VehicleRoutingAlgorithm vra = builder.buildAlgorithm();
vra.setMaxIterations(5);
Collection<VehicleRoutingProblemSolution> solutions = vra.searchSolutions();
VehicleRoutingProblemSolution best = Solutions.bestOf(solutions);
Thank you!
PHillner