Solving TSP problem through KNIME

Hi All
I have a project that involves with TSP problem and need insight on how to utilize KNIME nodes to optimize it.

Currently, I am starting on blank space using only raw data of stores geotag (ranging 5000-8000 points). The constraint on this is only the work hour of salesman, which is 7 hours/day. I’m expecting the constraint of 7 hours would already take into account the travelling variable from 1 point to another.

My objective is to find the optimum number of salesman in the area and routing for each salesman from store 1, store 2, etc.

My method of this solution currently is using stores headquarter(HQ) long lat and all stores in the area (HQ here is only used for calculating the distance to each stores in the area) and divide it by working days, which 10 (assuming each stores will be visited twice a month during weekday). From this, I get 10 cluster showing number of stores for each day that need to be visited by using k-means nodes.
After this, I still need to get the number of stores that need to be visited by each salesman in a day, which is why I’m using a second K-means clustering (I don’t have any other ideas on other optimization node at this point).

My current method is not achieving my objectives because each cluster of salesman does not make sense, for instance salesman A can visit more than 70 stores while salesman B visit only 20 stores. I’m assuming this is because the clustering does not take any time constraint into calculation because I didn’t put the 7 hours/day working time and because all stores will be centered toward the HQ (which is I don’t have any idea what node can execute this).

Is there any nodes in KNIME currently that could achieve my objectives with the input data above and workflow?

Copy of PM

Hi @andersenyunan
I’m not an expert in the field of TSP etc. Therefore, I cannot tell you how to solve exactly your problem. Maybe this helps you a little bit. I’m sure this problem has been studied by some scientist so I’d just see what pops up on google.

Sorry that I cannot really help you with that problem. Anyways there is no KNIME node for that particular problem.
Best
Mark

2 Likes

Hi,

as Mark already said, there is no dedicated node for TSP. But if you have questions on availability of particular steps- please do not hesitate to ask.

Best regards,
Mischa

Thanks for the response!
My questions remains on the particular step on how to put time variable constraint in k-means node, as I already put distance constraint on this.

For visualization below, as you can see the results through k-means nodes with distance constraint (1 color represents 1 sales). However, the cluster results here is still not fair to each sales, where 1 can goes up to 40+ stores in a day. I’m assuming here because I didn’t put time constraint variable and I’m not sure how to put it in k-means node.