CODEWITHSUNDEEP
calgorithmmatrix2dcluster-analysis
Sazzad Hissain Khan
Sazzad Hissain Khan

Reputation: 40166

Searching for efficient clustering algorithm

In a 2D NxN matrix each point represents a area of a map. There are M numbers of customers in random areas whose service need to be served by K numbers of customer service centers in random areas. Each customer service center can serve up to X number of jobs. Number of all customers must be less than or equals to total capability of customer service centres. All customers must to be assigned in any of the service centre and hamiltonian distance is the cost (customer can move up,left,down and right only towards service centre). How to assign customers to minimise the total cost? I was looking for a direction if its a well known problem or at least pseudocode.

Upvotes: 1

Views: 71

Answers (2)

lcastillov
lcastillov

Reputation: 2153

I think you can handle this problem using MinCost/MaxFlow algorithm. Create the graph as follow:

  • Create M + K + 2 nodes; M customer-nodes, K customer-service-center-nodes (csc-nodes), a source and a sink.
  • Create K edges from the source to the K csc-nodes with cost 0 and capacity equal to the number of customers that each CSC can serve.
  • Create M edges from the M customer-nodes to the sink, each edge will have capacity 1 and cost 0.
  • Create K * M edges from the K csc-nodes to the M customer-nodes each one with a capacity equal to 1 and cost equal to the distance between the CSC and the customer.

Run MinCost/MaxFlow algorithm on the network (V = M + K + 2, E = M + K + M*K). If the max-flow value is equal to M, then you can serve all the customers with the resulting (minimum) cost.

gg1

The solution for this case is 23.

gg2

Upvotes: 1

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77454

The way the problem is formulated, you have a constrained optimization problem, and not a clustering problem. It likely is convex, integer and linear.

Clustering algorithms won't satisfy the capacity constraint.

There is plenty of research on such optimization. There are various highly optimized solvers available.

Upvotes: 1

Related Questions