HOW TO consider incompatible products in tour planning

[Bernd Welter]

Hello there,

today a customer asked me whether it is possible to consider the following constraint in a tour optimization:

• His orders are dealing with some products (ProductId = 1, 2, ...)
• The server has to ensure that some of the products are not on a truck at the same time (1=Sheep, 2=Wolves).
• Sometimes the products are not allowed to be picked on the same tour (do not pick 2=milk after delivering 1=oil)

We can take care of such constrains by using the ProductIncompatibility.
I created a little scenario that shows what the effects of this feature are.

The global setup of the scenario:
Depot is in Stuttgart, the arrows show the relations (pickup=freen, delivery=red)

inco.gif (24.25 KiB) Viewed 8484 times

Imagine that we have two AB orders:

• the Depot is located int Stuttgart
• ORDER 1 : a single item of product 1 is brought from Karlsruhe to Berlin
• ORDER 2 : a single item of product 2 is brought from Hamburg to Munich (=München)

Here are the results - the total distances of the tours and chains are mentioned in brackets.

Without enforcing the separation of the products the potential of optimization is the highest one. The two orders are picked up in a row and delivered afterwards.

Incompatible-NO.PNG (7.74 KiB) Viewed 8484 times

Without restrictions - just a single tour with shortest distance

inco.NO.gif (25.53 KiB) Viewed 8484 times

By applying the new ProductIncompatibility() {
incompatibilityType = ProductIncompatibilityType.NOT_AT_SAME_TIME,
productId1 = 1,
productId2 = 2
}
the server ensures that both products are not on the truck at the same time but he doesn't have to get back to the depot between the orders.

Incompatible-NOT_AT_SAME_TIME.PNG (7.83 KiB) Viewed 8484 times

Single tour but not AT SAME TIME

inco.NOT_AT_SAME_TIME.gif (24.7 KiB) Viewed 8484 times

With
new ProductIncompatibility() {
incompatibilityType = ProductIncompatibilityType.NOT_ON_SAME_TOUR,
productId1 = 1,
productId2 = 2
}
the server has to get back to the depot before taking care of the other order. So in the end there have to be TWO tours instead of one.

Incompatible-NOT_ON_SAME_TOUR.PNG (9.1 KiB) Viewed 8484 times

Not even at same tour - worst distance

inco.NOT_ON_SAME_TOUR.gif (25.49 KiB) Viewed 8484 times

I hope this shows that you can solve the customers usecase.

Best regards Bernd

[columbs]

Hello Bernd,
thank you for your explanation. We want to implement this solution in order to solve a usecase, and I have made some experiments on the rawrequestrunner.

In the request I have 4 orders with product 1 and 3 orders with product 2.
When I set productincompatibility "NOT_AT_SAME_TIME", xTour plans only the orders for 1 product but not the other ones.

The strange thing is: if I give an input plan, I get no errors. Any Idea what's wrong here?

Thank you very much for your help!
Sebastiano

[Bernd Welter]

Hello Sebastiano,

I tested your requests with xTour 1.24. Both scenarios return 100% scheduled orders.
I assume this is related to the latest version of xTour but I raised an internal JIRA to get a statement from DEV department.

Best regards
Bernd

[Bernd Welter]

Quick feedback from DEV:
From 1.24.0.0. to 1.24.0.1 we improved/fixed this:

1.24.0.1
Improvement: Shorter reaction time in case of cancelling an area tour planning (e.g. by limiting the available machine time).
Bugfix: If there are no priorities at all orders present, this is now correctly considered in the planning algorithm.

According to Haba this (#2) is probably the reason why the latest version returns the desired results.

Best regards Bernd