The problem is related to a capacitated version of the k-median problem. (Here we assume the number of facilities can be varied and there is a constant cost per facility ).... so, suppose we solve the uncapacitated problem with some value of k. If all the facilities gain no more than your limit, we are done. However if (as is very likely) some popular facility gets far too much demand we have to activate the capacity constraints. One way to do this is to convert the problem to a capacitated network flow problem, with a link to an imaginary / dummy super sink from each facility with a capacity constraint on that link -- this will prevent too much from flowing through any open facility. There is a transshipment constraint at the facilities. BUT, may require facility relocation and so the problem cycles through these pairs of problems. I can dig out some references if you need more.

Hello Al Amin bin Mohamed Sultan,

Though I am not a person who deals this kind of problem in a regular basis, but I like such thing if I get chance. First, Let me clear what I understand from the described problem --

160 companies spread all around the map. You need to cluster these companies in such a way so that the total waste of each cluster is around /less than 2000 tonnes. But at the same time the real cluster should contain those companies which are neighbours (within close distance in map) to each other. Whether your requirement allows the clusters to be overlapped or not?

Any demo data (quantity of waste of companies, and their relative distances) might help me to find a solution. As I already mentioned that I am not a person of this field, so it may take some help from your side to make things more clear.

Regards,

Arindam.

You can categorized the all 160 companies on the basis of ABC analysis.

.

this sounds like a "capacitated clustering problem" ; you may be interested in the attached paper and references therein

.

Probably North West Corner could provide some good idea about how to allocate capacity to each company considering the total waste capacity processing and other constraints.

If the 160 companies are not in the same industry, then you can cluster it based on the industrial classification (refer to std. IIC). Alternatively, you may cluster it based on the company size.

thanks Dr. Zu!

The answer depends on available data . If there are some ecomomic data as transportation costs and cost for waste processing facilities, then you can formulate some location problem and solve it by common means of mathematical programming. This way you can obtain not only clusters but also their centers.

The problem is related to a capacitated version of the k-median problem. (Here we assume the number of facilities can be varied and there is a constant cost per facility ).... so, suppose we solve the uncapacitated problem with some value of k. If all the facilities gain no more than your limit, we are done. However if (as is very likely) some popular facility gets far too much demand we have to activate the capacity constraints. One way to do this is to convert the problem to a capacitated network flow problem, with a link to an imaginary / dummy super sink from each facility with a capacity constraint on that link -- this will prevent too much from flowing through any open facility. There is a transshipment constraint at the facilities. BUT, may require facility relocation and so the problem cycles through these pairs of problems. I can dig out some references if you need more.

yes Sir Morton, thanks a lot for the explanation. I would be happy to see more references on this if you have it. thanks again.

Elaborating on Professor O'Kelly's answer: You can use a capacitated Facility Location Problem, which does not require an a priori number of clusters. Or try with different values of k. An important aspect is that when you add capacity constraints, some companies could end up assigned to a cluster that is not the closest, so you need to add what is called "closest assignment constraints". I am attaching a paper that has references addressing the Capacitated Facility Location Problem, and the closest assignment constraints. The capacity constraint should limit the capacity of each cluster to 2,000.

Good luck!

Morton's answer is absolutely right.

You can also have a look to the following paper. It is not a capacity constrained model, but it discusses the optimal number of facilities to open, taking the demand, the costs and benefits related to an additional facility into account.