I want to use JSprit for taxi app purpose, I implemented Shipment (Pickup / Delivery) and it works correctly, for example:
Vehicle type 1;capacity 0,4 ; number of vehicle : 3 (Vehicle1/2/3)
vehicule start at depot and must return to depot after all this shipment assigned are finished
Shipment 1 => Pickup 1 person on POI1 => Deliver 1 person on POI2 ; capacity 0,1
Shipment 2 => Pickup 1 person on POI1 => Deliver 1 person on POI3 ; capacity 1,1
Shipment 3 => Pickup 1 person on POI2 => Deliver 1 person on POI3 ; capacity 0,1
Result i get now :
route | vehicle | activity | job | arrTime | endTime | costs |
---|---|---|---|---|---|---|
1 | VHL01 | start | - | undef | 0 | 0 |
1 | VHL01 | pickupShipment | 2 | 12 | 70 | 12 |
1 | VHL01 | pickupShipment | 1 | 70 | 80 | 12 |
1 | VHL01 | deliverShipment | 1 | 88 | 88 | 19 |
1 | VHL01 | pickupShipment | 3 | 88 | 100 | 19 |
1 | VHL01 | deliverShipment | 2 | 114 | 114 | 33 |
1 | VHL01 | deliverShipment | 3 | 114 | 114 | 33 |
1 | VHL01 | end | - | 123 | undef | 42 |
Result i want :
I would like for each shipment the pickup is immediately followed by related delivery before moving to the next shipment (a taxi must deliver the passenger he has taken before going to another race)
For that i implemented an HarActivtyConstraint , the result i get is better but not optimal :
I get every pickup followed directly by the corresponding delivery but now each route have only one shipment , i check the cost, time windows (i tested without time windows smae result) … everything is fine the same vehicule can make 2 shipments but i get one shipment by vehicule bellow you will find my code and result any help will be much appreciate.
route | vehicle | activity | job | arrTime | endTime | costs |
---|---|---|---|---|---|---|
1 | VHL01 | start | - | undef | 0 | 0 |
1 | VHL01 | pickupShipment | 3 | 6 | 100 | 6 |
1 | VHL01 | deliverShipment | 3 | 114 | 114 | 20 |
1 | VHL01 | end | - | 123 | undef | 28 |
------ | ------ | ------ | ------ | ------ | ------ | ------ |
2 | VHL02 | start | - | undef | 0 | 0 |
2 | VHL02 | pickupShipment | 1 | 12 | 70 | 12 |
2 | VHL02 | deliverShipment | 1 | 78 | 78 | 19 |
2 | VHL02 | end | - | 84 | undef | 25 |
The result i want will be
VHL01 : Pickup1 -> Deliver1 -> Pickup2 -> Deliver2 -> Pickup3 -> Deliver3
Or
VHL01 : Pickup1 -> Deliver1 -> Pickup3 -> Deliver3
VHL02: Pickup2 -> Deliver2
…
My CostMatrix :
FROM | TO | DISTANCE | TIME |
---|---|---|---|
DEPOT | POI1 | 11.8 | 12.0 |
DEPOT | POI2 | 5.2 | 6.0 |
DEPOT | POI3 | 8.8 | 9.0 |
POI1 | DEPOT | 11.8 | 12.0 |
POI1 | POI2 | 7.5 | 8.0 |
POI1 | POI3 | 16.9 | 17.0 |
POI2 | DEPOT | 5.6 | 6.0 |
POI2 | POI1 | 7.4 | 8.0 |
POI2 | POI3 | 13.8 | 15.0 |
POI3 | DEPOT | 8.7 | 9.0 |
POI3 | POI1 | 16.6 | 17.0 |
POI3 | POI2 | 13.9 | 14.0 |
Here is my complete code
public static void main(String[] args) {
...
init here Location (own java bean)
...
VehicleType vhlType1 = VehicleTypeImpl.Builder.newInstance("VHLTYPE1")
.addCapacityDimension(0, 4).build();
VehicleImpl vhl1 = VehicleImpl.Builder.newInstance("VHL01")
.setStartLocation(Location.newInstance(depot.getName()))
.setLatestArrival(780).setType(vhlType1)
.setReturnToDepot(true).build();
VehicleImpl vhl2 = VehicleImpl.Builder.newInstance("VHL02")
.setStartLocation(Location.newInstance(depot.getName()))
.setLatestArrival(780).setType(vhlType1)
.setReturnToDepot(true).build();
List<VehicleImpl> listVehicules = new ArrayList<VehicleImpl>();
listVehicules.add(vhl1);
listVehicules.add(vhl2);
Shipment shipment1 = Shipment.Builder.newInstance("1")
.addSizeDimension(0, 1)
.setPickupLocation(Location.newInstance(poi1.getName()))
.setDeliveryLocation(Location.newInstance(poi2.getName()))
.setPickupTimeWindow(TimeWindow.newInstance(60, 70))
.setPickupServiceTime(10).build();
Shipment shipment2 = Shipment.Builder.newInstance("2")
.addSizeDimension(0, 1)
.setPickupLocation(Location.newInstance(poi1.getName()))
.setDeliveryLocation(Location.newInstance(poi3.getName()))
.setPickupTimeWindow(TimeWindow.newInstance(60, 70))
.setPickupServiceTime(10).build();
Shipment shipment3 = Shipment.Builder.newInstance("3")
.addSizeDimension(0, 1)
.setPickupLocation(Location.newInstance(poi2.getName()))
.setDeliveryLocation(Location.newInstance(poi3.getName()))
.setPickupTimeWindow(TimeWindow.newInstance(90, 110))
.setPickupServiceTime(10).build();
VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder =
VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);
...
creating here an asymetric cost matrix from graphhopper instance with real distance and time
...
VehicleRoutingTransportCosts costMatrix = costMatrixBuilder.build();
HardActivityConstraint hac = new HardActivityConstraint() {
public ConstraintsStatus fulfilled(JobInsertionContext iFacts,
TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
if (prevAct instanceof PickupShipment && newAct instanceof PickupShipment)
return ConstraintsStatus.NOT_FULFILLED_BREAK;
if (newAct instanceof PickupShipment && nextAct instanceof PickupShipment)
return ConstraintsStatus.NOT_FULFILLED_BREAK;
if (newAct instanceof DeliverShipment && prevAct instanceof DeliverShipment)
return ConstraintsStatus.NOT_FULFILLED_BREAK;
//IF I DONT PUT THIS CONDITION IT'S NOT WORKING (algorithm.InsertionInitialSolutionFactory - create initial solution)
if (prevAct instanceof Start) {
if (newAct instanceof PickupShipment || newAct instanceof DeliverShipment) {
if (nextAct instanceof End) {
return ConstraintsStatus.FULFILLED;
}
}
}
if (newAct instanceof PickupShipment) {
if (prevAct instanceof DeliverShipment) {
if (nextAct instanceof DeliverShipment) {
PickupShipment current = (PickupShipment) newAct;
DeliverShipment previous = (DeliverShipment) prevAct;
DeliverShipment next = (DeliverShipment) nextAct;
if (current.getJob().getId() != previous.getJob().getId() && current.getJob().getId() == next.getJob().getId()) {
return ConstraintsStatus.FULFILLED;
} else {
return ConstraintsStatus.NOT_FULFILLED;
}
}
}
}
if (newAct instanceof DeliverShipment) {
if (prevAct instanceof PickupShipment) {
DeliverShipment current = (DeliverShipment) newAct;
PickupShipment previous = (PickupShipment) prevAct;
if (current.getJob().getId() != previous.getJob().getId()) {
return ConstraintsStatus.NOT_FULFILLED;
} else {
return ConstraintsStatus.FULFILLED;
}
}
}
if (prevAct instanceof Start) {
System.out.println("JE START ");
if (newAct instanceof PickupShipment) {
if (nextAct instanceof DeliverShipment) {
PickupShipment current = (PickupShipment) newAct;
DeliverShipment next = (DeliverShipment) nextAct;
if (current.getJob().getId() != next.getJob().getId()) {
return ConstraintsStatus.NOT_FULFILLED;
} else {
return ConstraintsStatus.FULFILLED;
}
}
}
return ConstraintsStatus.NOT_FULFILLED;
}
return ConstraintsStatus.NOT_FULFILLED;
}
};
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.setRoutingCost(costMatrix);
vrpBuilder.addAllVehicles(listVehicules);
vrpBuilder.addJob(shipment1).addJob(shipment2).addJob(shipment3);
vrpBuilder.setFleetSize(FleetSize.FINITE);
VehicleRoutingProblem vrp = vrpBuilder.build();
StateManager stateManager = new StateManager(vrp);
ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);
constraintManager.addConstraint(hac, ConstraintManager.Priority.CRITICAL);
//VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance(vrp).buildAlgorithm();
VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance(vrp)
.setStateAndConstraintManager(stateManager, constraintManager).buildAlgorithm();
Collection<VehicleRoutingProblemSolution> solutions = vra.searchSolutions();
SolutionPrinter.print(vrp, Solutions.bestOf(solutions), SolutionPrinter.Print.VERBOSE);
}
}
Any help will be much appreciated