Решить задачу коммивояжера на 4-10 "городов" это, конечно, не rocket science, но все равно приятно, что коммерческие предприятия занимаются этим.

С промежуточной кластеризацией решение все равно получается эвристическим, так что я бы лучше сразу использовал эвристику для решения множественной задачи коммивояжера. Например, для вашей задачи можно использовать алгоритм муравьиных колоний (Ant Colony Optimization). Количество муравьев на каждой итерации соответствует числу сотрудников, муравьи стартуют с места жительства сотрудников и пытаются обойти "города" в соответствии с теми ограничениями, что вы наложили. При этом помимо ограничений на граф, вы можете динамически поддерживать ограничения такие как максимальное число "городов" у каждого сотрудника, или задать набор навыков у сотрудника и набор навыков требуемого для каждого "города", тогда "муравьи"-сотрудники смогут выбирать только те, "города" которые соответствуют их навыкам.