Já estás num bom caminho! Realmente a melhor forma de pensares no problema é dividi-lo como fizeste : primeiro tratar de fazer com que o camião faça a distribuição eficientemente pelos pontos do grafo e só depois tratar de ver a questão de diferentes pontos de partida e a partir desses criar os melhores circuitos.
Quanto a agrupar clientes, tenta achar a árvore de expansão mínima a partir de um supermercado (Prim), podes parar quando achares N pontos e a partir daí trabalhas com os pontos que achares como TSP. Outra abordagem, pode ser achar os pontos de entrega mais próximos (shortest path) e criar um circuito com esses pontos.
Não te esqueças de usar mapas do OSM, é sempre valorizado se o trabalho tiver aplicações reais.
Boa Tarde!
Já estás num bom caminho! Realmente a melhor forma de pensares no problema é dividi-lo como fizeste : primeiro tratar de fazer com que o camião faça a distribuição eficientemente pelos pontos do grafo e só depois tratar de ver a questão de diferentes pontos de partida e a partir desses criar os melhores circuitos.
Quanto a dividir o grafo num sub-grafo : é uma boa ideia! Arranjar um grafo que só possui pontos de interesse acaba por tornar um problema TSP(https://en.wikipedia.org/wiki/Travelling_salesman_problem) mais fácil de resolver.
Quanto a agrupar clientes, tenta achar a árvore de expansão mínima a partir de um supermercado (Prim), podes parar quando achares N pontos e a partir daí trabalhas com os pontos que achares como TSP. Outra abordagem, pode ser achar os pontos de entrega mais próximos (shortest path) e criar um circuito com esses pontos.
Não te esqueças de usar mapas do OSM, é sempre valorizado se o trabalho tiver aplicações reais.
Cumprimentos, Pedro Castro.