Commesso viaggiatore con più venditori?

Ho un problema che è stato effettivamente ridotto a un problema di venditore ambulante con più venditori. Ho un elenco di città da visitare da una posizione iniziale e devo visitare tutte le città con un numero limitato di venditori.

Sto cercando di trovare un’euristica e mi chiedevo se qualcuno potesse dare una mano. Ad esempio, se ho 20 città con 2 venditori, l’approccio che ho pensato di adottare è un approccio in 2 fasi. Per prima cosa, dividi le 20 città a caso in 10 città per 2 venditori ciascuna, e troverei il tour per ognuno come se fosse indipendente per alcune iterazioni. In seguito, mi piacerebbe scambiare o assegnare una città a un altro venditore e trovare il tour. Effettivamente, sarebbe un TSP e quindi un problema di makepan minimo. Il problema con questo è che sarebbe troppo lento e una buona generazione di quartiere per scambiare o assegnare una città è difficile.

Qualcuno può dare un consiglio su come potrei migliorare quanto sopra?

MODIFICARE:

La geo-localizzazione di ciascuna città è nota e i venditori iniziano e finiscono negli stessi luoghi. L’objective è ridurre al minimo il tempo di viaggio massimo, rendendo questo tipo di problema con il makepan minimo. Quindi, ad esempio, se il venditore1 impiega 10 ore e il venditore 2 impiega 20 ore, il tempo di percorrenza massimo sarà di 20 ore.

TSP è un problema difficile. Multi-TSP è probabilmente molto peggio. Non sono sicuro che tu possa trovare buone soluzioni con metodi ad-hoc come questo. Hai provato metodi meta-euristici? Proverò a utilizzare prima il metodo Cross Entropy: non dovrebbe essere troppo difficile da usare per il tuo problema. Altrimenti cerca Algoritmi generici, Ottimizzazione della colonia di formiche, Ricottura simulata …

Vedi “Un tutorial sul metodo di entropia incrociata” di Boer et al. Spiegano come utilizzare il metodo CE sul TSP. Un semplice adattamento per il tuo problema potrebbe essere quello di definire una matrice diversa per ogni venditore.

Si potrebbe presumere di voler solo trovare la partizione ottimale delle città tra i venditori (e debind il tour più breve per ogni venditore ad una classica implementazione TSP). In questo caso, nell’impostazione Cross Entropy, si considera una probabilità per ogni città Xi di essere nel tour del venditore A: P (Xi in A) = pi. E tu lavori, nello spazio di p = (p1, … pn). (Non sono sicuro che funzionerà molto bene, perché dovrai risolvere molti problemi di TSP.)

Quando inizi a parlare di più venditori, inizio a pensare all’ottimizzazione degli sciami di particelle. Ho trovato molto successo con questo usando un algoritmo di ricerca gravitazionale. Ecco un lungo documento che ho trovato riguardante l’argomento. http://eprints.utm.my/11060/1/AmirAtapourAbarghoueiMFSKSM2010.pdf

Perché non converti il ​​tuo TSP multiplo nel tradizionale TSP?
Questo è un problema ben noto (trasformazione di TSP di commessi multipli in TSP) e si possono trovare diversi articoli su di esso.

Per la maggior parte delle trasformazioni, in pratica copia il tuo depot (dove i venditori iniziano e finiscono) in diversi depot (nel tuo caso 2), crea i pesi dei bordi in modo da costringere un TSP a tornare due volte al depot, quindi rimuovere il due depositi e trasformarli in uno.

Ecco! ho ottenuto due tour a costo minimo che coprono i vertici esattamente una volta.

Non inizierei a scrivere un algoritmo per un problema così complicato (a meno che non sia il mio lavoro quotidiano) scrivere degli algoritmi di ottimizzazione). Perché non ti rivolgi a una soluzione generica come http://www.optaplanner.org/ ? Devi definire il tuo problema e il programma utilizza algoritmi che i migliori sviluppatori hanno impiegato anni per creare e ottimizzare.

Il mio primo pensiero sulla lettura della descrizione del problema sarebbe stato quello di utilizzare un approccio standard per il problema del venditore (googlando per uno appropriato perché non ho mai dovuto scrivere codice per questo); Quindi prendi il risultato e dividilo a metà. Il tuo algoritmo potrebbe quindi essere quello di decidere dove “metà” è – forse è la metà delle città, o forse si basa sulla distanza, o forse una combinazione. Oppure cerca il risultato per la distanza più grande tra due città e scegli quella come separazione tra l’ultima città del commesso # 1 e la prima città del venditore n. 2. Naturalmente non si limita a due venditori, si dividerà in x pezzi; Ma nel complesso l’idea è che la tua soluzione TSP di venditore standard dovrebbe avere già le città “vicine” l’una accanto all’altra nel grafico di viaggio, quindi non devi inventare un algoritmo di raggruppamento separato …

Ad ogni modo, sono sicuro che ci siano soluzioni migliori, ma questo mi sembra un buon primo approccio.

Dai un’occhiata a questa domanda (562904) – sebbene non sia identico al tuo, ci dovrebbe essere del buon cibo per i pensieri e dei riferimenti per ulteriori studi.

Come menzionato nella risposta sopra, la soluzione di clustering gerarchico funzionerà molto bene per il tuo problema. Invece di continuare a dissolvere i cluster finché non hai un singolo percorso, fermati quando hai n, dove n è il numero di venditori che hai. Probabilmente è ansible migliorarlo aggiungendo alcune fermate “finte” per migliorare la probabilità che i cluster finiscano uniformsmente distanziati dalla destinazione iniziale se i cluster iniziali sono troppo disparati. Non è ottimale, ma non otterrai una soluzione ottimale per un problema come questo. Creo un’applicazione che mostri il problema e poi provi molte varianti della soluzione per capire se la tua euristica è abbastanza ottimale.

In ogni caso non vorrei randomizzare i cluster, il che farebbe sì che la maggior parte dei cluster non sia ottimale.

appena iniziando a leggere la tua domanda usando l’algoritmo genetico mi è venuto in mente. basta usare due algoritmi genetici nello stesso tempo in cui è ansible risolvere il modo in cui assegnare le città ai venditori e l’altro in grado di risolvere il TSP per ogni venditore che si ha.