7
$\begingroup$

I am implementing a solution for packages consolidation (basing on Nurse Problem solution) with OR-Tools CP Solver.

There is a factory that manufactures some small Packages that need to be transported by post to the customers. It would be optimal to consolidate some mini_Packages into bigger Packages (for example if we respect total weight limit, we can merge 3 light mini_Packages into one Package and pay transport costs once not 3 times).

Mini_Packages have some important attributes in data source (fixed destination, weight, acceptable delivery date range).

My main 0-1 integer variable looks like:

x[mini_package_number, optimal_shipment_date, package_number]

It == 1 if mini_Package should be send on a certain day, consolidated to a certain Package_number.

Conflicting products

A mini_Package represents a single product item. Name of the product is an attribute of mini_Package, given in a certain list (position on the list = mini_Package_number).

products = [34, 12, 12, 456 ...]
meaning that:
mini_Package 0 contains product 34
mini_Package 1 contains product 12
mini_Package 2 also contains product 12

There are some products that cannot be merged together. If a mini_Packages represent a certain product it cannot be merged (to the same Package) with another mini_Package that represents conflicting product.

The format of conflict matrix can be adjusted for the model.

At the moment I plan following format:

conflict_list = [(1,3), (3,6), (5,19)] saying that:
product 1 and 3 cannot go together
product 3 and 6 cannot go together
product 5 and 19 cannot go together

Conflict list represents mutually exclusive pairs, however it is important that final Package may merge more products (for example four mini_Packages with non-conflicting products 1, 1, 2, 6).

Do you have any ideas how such a logic could be implemented?

Improve this question
$\endgroup$
1
  • $\begingroup$ Would a simple $x_1 + x_2 \le 1$ for each entry in conflict list do the trick? $\endgroup$
    – CMichael
    Oct 14, 2019 at 7:07

1 Answer 1

Reset to default
1
$\begingroup$

You can use the linear constraint function to add additional constraints which prohibit mutually exclusive pairs. I'd imagine that each mini package has to be scheduled on one date so this leads to the following code:

for (product_a, product_b) in conflict_list:
    mps_with_productb = [mp for mp, p in enumerate(products) where p == product_b]
    for mp1 in [mp for mp, p in enumerate(products) where p == product_a]:
        model.AddLinearConstraint(sum(x[mp1,i,k] for i in shipping_dates for k in package_numbers) + sum(x[mp2,i,k] for mp2 in mps_with_productb for i in shipping_dates for k in package_numbers), 1, 1)

This will force only one of the variables to be 1, thus, for a given mini package mp1 which has product_a no other mini package which has product_b can be scheduled in the same package. If you do not have to ship all mini packages then change the first 1 to a 0.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think it can be close, however mini_Package (first dimension of x variable) is just a row number of the record, not a product code. Product codes for mini_Packages are available on another list. I edited my post to add short example. Could you have a look? $\endgroup$
    – Tomasz Kot
    Oct 14, 2019 at 10:50
  • $\begingroup$ ok, so as I understand it the mini package corresponds to a certain product and the conflict list talks about products (not mini packages)... I'll try to incorporate it in the code. $\endgroup$
    – JakobS
    Oct 14, 2019 at 14:15
  • $\begingroup$ Thank you for the update. I adjusted it a little bit to deal with project specifics, but the general idea worked well! :) Thx! $\endgroup$
    – Tomasz Kot
    Oct 21, 2019 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.