Hi,
The problem
I am working on a problem, where the vehicles picks up one or more items from given locations and then they deliver them to the destination of each pick (in any order). The twist is, that when they deliver something to a destination, they have to pick up immediately the backhaul cargo as well and they should be transported back to the original pickup location. (The two cargos have the same dimension, so capacity is never a problem.)
For example:
Tasks to do:
1 box of banana from Ap to Ad
1 box of apple from Bp to Bd
1 box of banana from Ap to Ad
1 box of lemon from Cp to Cd
From this, I create Shipment jobs (two from each):
Shipment 1.1 cargo: banana, pick location Ap, delivery location Ad
Shipment 1.2 cargo: banana, pick location Ad, delivery location Ap
Shipment 2.1 cargo: apple, pick location Bp, delivery location Bd
Shipment 2.2 cargo: apple, pick location Bd, delivery location Bp
etc…
What I would expect something like this:
Route 1:
- R1.1: Pick banana from Ap (Shipment 1.1)
- R1.2: Pick banana from Ap (Shipment 3.1)
- R1.3: Pick apple from Bp (Shipment 2.1)
- R1.4: Deliver apple to Bd (Shipment 2.1)
- R1.5: Pick apple(backhaul) from Bd (Shipment 2.2)
- R1.6: Deliver banana to Ad (Shipment 1.1)
- R1.7: Pick banana(backhaul) from Ad (Shipment 1.2)
- R1.8: Deliver banana to Ad (Shipment 3.1)
- R1.9: Pick banana(backhaul) from Ad (Shipment 3.2)
- R1.10: Deliver banana(backhaul) to Ap (Shipment 1.2)
- R1.11: Deliver banana(backhaul) to Ap (Shipment 3.2)
- R1.12: Deliver apple(backhaul) to Bp (Shipment 2.2)
Route 2:
- R2.1: Pick lemon from Cp (Shipment 4.1)
- R2.2: Deliver lemon to Cd (Shipment 4.1)
- R2.3: Pick lemon(backhaul) from Cd (Shipment 4.2)
- R2.4: Deliver lemon(backhaul) to Cp (Shipment 4.2)
What I must force is that R1.4 and R1.5 is after each other in the right order. (Also (R1.6,R1.7), (R1.8, R1.9), and (R2.2, R2.3) should follow each other tightly.)
My first solution idea
My solution idea was to create a HardActivityConstraint:
public class PickupEmptyAfterDeliveryConstraint implements HardActivityConstraint {
@Override
public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
if (newAct instanceof PickupActivity) {
PickupActivity pa = (PickupActivity) newAct;
String newId = pa.getJob().getId();
ConstraintsStatus status;
if (!newId.startsWith(AudiJspritCalculator.BACKHAUL_SHIPMENT_PREFIX)) {
// This is not a backhaul pick -> ok
status = ConstraintsStatus.FULFILLED;
} else {
String name = newId.substring(AudiJspritCalculator.BACKHAUL_SHIPMENT_PREFIX.length());
if (prevAct instanceof DeliveryActivity) {
// Previous activity is a delivery
DeliveryActivity da = (DeliveryActivity) prevAct;
if (da.getJob().getId().equals(AudiJspritCalculator.FILLIN_SHIPMENT_PREFIX + name)) {
// Previous activity is a delivery of the fill of the backhaul, so it's ok
status = ConstraintsStatus.FULFILLED;
} else {
// Previous activity is not the delivery of the fill of the backhaul, fail
status = ConstraintsStatus.NOT_FULFILLED;
}
} else {
// Previous activity is not a delivery, so fail (a backhaul pick cannot start a route)
status = ConstraintsStatus.NOT_FULFILLED;
}
}
return status;
}
return ConstraintsStatus.FULFILLED;
}
}
This means that the constraint rejects insertation when
- The newAct is a pick of a backhaul shipment
- AND the previuos activity is
- not a delivery of a fill shipment
- OR a not the delivery of the pickup of the newAct
This works fine in theory, but life is much harder. What I’ve found out after some testing and thinking, that this constraint so much reduces the number of acceptable results from all the possible solutions, that a genetic algorithm will never run into any valid solution. In other words: with this constraints the backhaul pickups is restricted to be inserted into only a single valid positions in all routes and the algorithm will never try this.
So my conclusion that maybe I have to do this completely differently, but I am stucked how I could do it.
Any suggestions?
PS: Maybe a ShipmentWithBackhaul job would be nice one day.