0
$\begingroup$

I have about 300 orders, where each order consists of different products that comes from a city (in total I have about 30 cities and around 100 products from all orders).

My job is to allocate the orders to specific factories that can produce those products. There are 10 factories, each with varying distance to the demand locations. Now obviously I want to allocate the orders to the closest factory to minimize the transportation cost.

However the production capacity for each product at different factory is limited, for example, say factory 1 is the closest to city 1, but can only produce 100 product 1, whereas city 1 ordered 200 product 1, so in this case I have to look for other factories that has a higher production power because I don't want to split the orders.

Moreover, factory will accept orders that the total volume of products from those orders can fit into a full load of a truck (or integer multiples of a truckload), a factory can accept multiple orders, I am also allowed to make extra orders (with the products I choose) to make sure the volume satisfies the truckload requirement.

My goals are:

  1. meet the demands from customer without splitting the order.
  2. minimize the transportation fee while making sure the factories have enough labors to produce.
  3. making fewest extra orders to fulfill the truckload requirement

How should I start formulating this problem? I feel like this has the flavour of a bin packing problem, but it seems I have two "layers" of bins, where I want to package items into a single order and then put the orders into different trucks, how would I formulate the "no splitting" requirement for an order? Thanks!

$\endgroup$
7
  • $\begingroup$ When introducing your splitting constraint, you state that: city $1$ ordered $200$ product $1$. It sounds like you are not allowed to split the demand of a city for a certain product over factories. But you state that orders are not allowed to be split, which sounds like all products of order $i$ must be produced by a single factory $j$. Can you please clarify? $\endgroup$
    – PeterD
    Aug 24, 2023 at 15:25
  • $\begingroup$ Why do you need to fill trucks? "Truckload" (as opposed to "less than truckload") freight pricing generally means that you pay for a full truck even if you only partially fill it. It does not mean that you have to fill the truck. $\endgroup$
    – prubin
    Aug 24, 2023 at 15:43
  • $\begingroup$ @PeterD You are right, all products of order i must be produced by a single factory j. $\endgroup$
    – TTY
    Aug 24, 2023 at 23:43
  • $\begingroup$ @prubin From the perspective of the factory, less than truckload would pay more, so I want to fill trucks as much as I can. $\endgroup$
    – TTY
    Aug 24, 2023 at 23:49
  • $\begingroup$ If you penalize the number of trucks used in the objective, you will tend to fill them as much as is practical. If you require exclusively full trucks, you may drive the cost of the solution up considerably (or possibly make the model infeasible). $\endgroup$
    – prubin
    Aug 25, 2023 at 1:25

1 Answer 1

1
$\begingroup$

Try with a binary variable $ x_{c,o,p}^{f}$ where $c$ is index for set of cities $C$, $o$ is index for set of orders $\{O \}$ within a city $c$ and $p$ is the product type/category from product set $P$ & $f$ is the factory.
$ x_{cop}^f = 1$ if full volume of product in an order $o$ is assigned to factory $f$ from set $F$, $0$ otherwise

Parameters:
$v_{c,o,p} =$ volume (integer) of product $p$ in an order $o$ from a city $c$.
You can drop $c$ if order has unique identifier & use $ v_{o,p}$
$ L_f =$ truckload for factory $f$
$ C_{p,f} =$ production capacity for product $p$ at factory $f$
$ D_{c,f}, T_{c,f} = $Distance & transport cost matrix
$ D_c = \{f \in F | f_i \le f_j \ \forall i,j \in F \}$: basically fo each city $c$ a set of $f$ in ascending order of distance
Derived Set $ COP = \{(c,o,p) \} =$ combination of (city,order,product)

Constraints

$\sum_f x_{c,o,p}^f = 1$

$ \sum_c \sum_o v_{c,o,p}x_{c,o,p}^f \le C_{p,f} \quad \forall f \ \ \forall p$

$ \sum_{k \in D_c}^{f} x_{c,o,p}^k \le 1 \quad \forall f \in D_c \ \ \forall c,o,p \in COP $

$ \sum_{c,o,p} v_{c,o,p}x_{c,o,p}^f \le I \times L_f \quad \forall f$ where $I$ is the integer of truck load $L$

Objective:
$\min (\sum_f (L_f - \sum_{cop}v_{c,o,p}x_{c,o,p}^f) + \sum_{f}\sum_{c,o,p}T_{c,f}x_{c,o,p}^f )$

$\endgroup$
4
  • $\begingroup$ Thank you! what does the superscript "f" in the third constraint mean? isn't $D_c$ contains all the factory for city $c$, and has already being summed over by $k$? $\endgroup$
    – TTY
    Aug 25, 2023 at 0:18
  • $\begingroup$ In that constraint I was trying to force it to consider assigning the order to the nearer possible factory while looping through $D_c$. But if objective is anyway minimizing the transport cost you may skip this constraint. $\endgroup$ Aug 25, 2023 at 3:48
  • $\begingroup$ I see, I will give it a try. I was wondering how can I add the logic that I can make extra orders to fulfill the trackload requirement, probably I can add a slack variable $y = L_f - \sum{v_{cop} x_{cop}}$ and convert it to an order with corresponding items. $\endgroup$
    – TTY
    Aug 25, 2023 at 9:53
  • $\begingroup$ Yes you can do that. That why the constraint on truckload $L$ is $\le$ relation giving you implicit slack there & I have added that in the objective as well. $\endgroup$ Aug 25, 2023 at 11:43

Your Answer

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

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