2
$\begingroup$

I wish to assign customers to their nearest distribution hubs. These hubs have maximum capacities however, and if these are breached I would like to assign customers to the next most appropriate hub.

Currently I am trying to use a multiple knapsack problem in or-tools (happy to use other) to code a python warehouse optimisation.

In this scenario I am treating the drivetime as my value (although I actually seek to minimise it so am using the inverse square) and the capacity as a weight.

The problem is that the value (drivetime) will vary by warehouse and therefore changes.

Is there any solutions to solve this?

I think knapsack is the correct solution, but if there is something else I should try please feel free to correct me - for example assignment feels potentially more appropriate.

Am trying to do in Python as well.

Improve this question
$\endgroup$
6
  • $\begingroup$ Could you give some details about your problem (how is the drivetime defined, what are your variables, why it is multiple knapsack problem, etc.) ? $\endgroup$
    – Kuifje
    Commented Aug 31, 2022 at 9:50
  • $\begingroup$ Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. $\endgroup$
    – Community Bot
    Commented Aug 31, 2022 at 10:28
  • $\begingroup$ What exactly are you trying to achieve ? Would you like to assign customers to warehouses at minimum cost ? $\endgroup$
    – Kuifje
    Commented Aug 31, 2022 at 11:12
  • $\begingroup$ Sounds like the capacitated facility location problem. $\endgroup$
    – RobPratt
    Commented Aug 31, 2022 at 11:49
  • 1
    $\begingroup$ @RobPratt If the warehouses are already at fixed locations, is it really a facility location problem? $\endgroup$
    – prubin ♦
    Commented Aug 31, 2022 at 15:49

1 Answer 1

Reset to default
2
$\begingroup$

This sounds like a generalized assignment problem. You can solve it with a MIP solver and any suitable Python modeling package/interface. I'm not a Python user, but Pyomo and PuLP seem to be popular choices.

Improve this answer
$\endgroup$
1

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