Search code examples
pythonschedulingknapsack-problemcpor-tools

Packages shipment (packages consolidation) with OR-Tools CP Solver in Python (multi-knapsack)


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_source_number, destination, optimal_shipment_date, package_number]

It == 1 if mini_package should go to a certain destination, on a certain day, consolidated to a certain Package_number.

I have managed to build most of the model, except:

1. Main challenge
How to make a constraint to ensure that when an optimal package number is assigned by the solver it cannot be used with any other destination or shipment_date? (it is meant to be physically one consolidated package going to a certain place)

Potential code:

for package_number in range(Packages):
  model.Add(sum(x[mini_package_source_number, destination, optimal_shipment_date, package_number] for ...) <= 1)

would be wrong, beacuse assigned Package_number can exist many times, consolidating several mini_Packages. It can exist several times, but has to be always assigned to the same destination and date.

Potential solver solution:

x[1, Place67, 2019-01-01, 8] = 1
x[2, Place124, 2019-01-04, 119] = 1
x[3, Place124, 2019-01-04, 119] = 1

is yet ok, mini_Packages 2 and 3 were consolidated into Package 119 to the same destination (and date).

x[4, Place55, 2019-01-05, 119] = 1

would be wrong, because mini_Package 4 was also consolidated into Package 119, that was previously decided by solver to go to another destination (and on another date).

How could it be coded? I would really appreciate any suggestion of solution.

2. Addition

@Stradivari feeling (answer below) is accurate. It is highly probable that I am using excess variables.

3. Conflicting products challenge

Points 2-3 moved to:
https://or.stackexchange.com/questions/2786/shipments-consolidation-with-or-tools-cp-solver-in-python-multi-knapsack


Solution

  • Create a boolvar for each [pkg, destination] pair.

    for package_number in range(Packages):
        for destination in destinations:
            model.AddBoolOr(v for k, v in x.items() if k[1] == destination and k[3] == package_number).OnlyEnforceIf(pkg_dest[package_number, destination])
            model.AddBoolAnd(v.Not() for k, v in x.items() if k[1] == destination and k[3] == package_number).OnlyEnforceIf(pkg_dest[package_number, destination].Not())
        model.Add(sum(pkg_dest[package_number, destination] for destination in destinations) == 1)
    

    Same logic for dates.

    BTW I feel like you may be creating a lot of useless variables with this formulation, can you actually decide a minipackage destination and/or date? Or just its package and then, for each package, its destination and date?