Course Grained Moves with Chain Variables
Julianne Bowles
I have a modified version of the vehicle routing problem. Rather than only dropping off packages, vehicles are picking up packages from various locations and then dropping them off. I implemented this like the vehicle routing problem with a package being duplicated for the pickup and dropoff. I used a hard constraint to guarantee the package pickup and dropoff are in the same vehicle. So, if there are 10 packages, there ends up being 20 customers in the system. (PlanningEntity = Customer, PlanningVariable = previousStandStill)
It is working fine for most of my sample problems, but some of them get caught in a score trap. The chained move helps little because it separates the dropoff from the pickup. So, I need a course-grained moved other than a chain move. I tried pillar moves, but it appears that move type does not work for chained variables. Ideally, I’d like a move that will move the pickup standstill and the dropoff standstill to a different vehicle together. I considered a Cartesian move of 2 change moves using mimic, but I do not think mimic can be applied to a problem fact. Do I need to build a custom move, or is there a way to build a pillar-type of move using a union or cartesianProduct Selector? Or any other ideas to prevent score traps in this modified VRP?
Geoffrey De Smet
Just thinking aloud:
A) Using a custom move is a good idea on your current model, but
it's indeed complex.
Users have done it before (see SO archive) but we could use an
example of VRPPD to make it easier.
B) But there's also the idea of using a radically different domain model:
@PlanningEntity class PickUp {
DropOff dropOff;
@PlanningVariable previous; // just like in normal VRP
}
@PlanningEntity class DropOff {
PickUp pickUp;
@PlanningVariable int hopCount; // between 0 and 100
@CustomShadowVariable(source = pickup & hopCount) ??; //
hmmm, this might not work, let's try C)
}
C) Another idea of using a radically different domain model:
@PlanningEntity class Customer {
@PlanningVariable previousPickup; // just like in normal VRP,
determines pickup
@PlanningVariable int hopCountDropOff; // between 0 and 100,
determines dropoff
@CustomShadowVariable(source = previousPickup &
hopCountDropOff) indexInVehicle; // or previousGeneral and
nextGeneral?
}
so it's always the same vehicle and after the pickup. The hopCount determines how many pickups/dropoffs to skip before doing it.
The shadow variable calculates the effect of the hopCount on the route so it the actual route is easily available for the score rules etc.
I haven't tried or seen B) or C) yet, but it would make an
interesting idea to research.
With kind regards,
Geoffrey De Smet
I have a modified version of the vehicle routing problem. Rather than only dropping off packages, vehicles are picking up packages from various locations and then dropping them off. I implemented this like the vehicle routing problem with a package being duplicated for the pickup and dropoff. I used a hard constraint to guarantee the package pickup and dropoff are in the same vehicle. So, if there are 10 packages, there ends up being 20 customers in the system. (PlanningEntity = Customer, PlanningVariable = previousStandStill)
It is working fine for most of my sample problems, but some of them get caught in a score trap. The chained move helps little because it separates the dropoff from the pickup. So, I need a course-grained moved other than a chain move. I tried pillar moves, but it appears that move type does not work for chained variables. Ideally, I’d like a move that will move the pickup standstill and the dropoff standstill to a different vehicle together. I considered a Cartesian move of 2 change moves using mimic, but I do not think mimic can be applied to a problem fact. Do I need to build a custom move, or is there a way to build a pillar-type of move using a union or cartesianProduct Selector? Or any other ideas to prevent score traps in this modified VRP?
--
You received this message because you are subscribed to the Google Groups "OptaPlanner development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to optaplanner-d...@googlegroups.com.
To post to this group, send email to optapla...@googlegroups.com.
Visit this group at https://groups.google.com/group/optaplanner-dev.
For more options, visit https://groups.google.com/d/optout.
