Warehouse allocation

Problem description

A company serves a group of geographically distributed customers, where each demands a certain amount of goods to buy. To cover all the customers efficiently, the company decides to build a network of warehouses. There are a number of locations where to open the warehouses, each location having its capacity.

The goal is to assign customers to warehouses so that the customers are served in the most efficient way.

Input:

  • $N$ warehouses, each warehouse $w$ has its capacity $cap_w$ and the set-up cost $s_w$,
  • $M$ customers, each customer $c$ demands certain amount of goods $d_c$,
  • For each pair $\langle c,w \rangle$, a cost $t_{cw}$ for delivering the goods from $w$ to $c$ is defined.

Output: Assignment of customers to warehouses such that the uniform evaluation function $f(x)=\sum_{w\in N}(I(|a_w|>0)\cdot s_w+\sum_{c\in a_w}t_{cw})$ is minimized

subject to $\sum_{c\in a_w}d_c \leq cap_w$ and $\sum_{w\in N}I(c\in a_w)=1$ for all $c\in M$,

where $a_w$ is a set of customers assigned to the warehouse $w$ and $I(.)$ is an indicator function (returns 1, if the argument is true, 0 otherwise).

Possible representations

  • Array of size $M$, where $i$-th value represents a number of the warehouse assigned to $i$-th customer.
  • Matrix A[MxN], where $A_{cw}\in \{0,1\}$; $A_{cw}= 1$, if the customer $c$ is assigned to the warehouse $w$, otherwise $A_{cw}= 0$.
courses/a0m33eoa/semestral_tasks/warehouse_layout.txt · Last modified: 2024/01/03 10:04 by xposik