Qual è il nome di questa variante logistica di TSP?

Question

Ho un problema logistico che può essere visto come una variante di $ \ text {} TSP $. E 'così naturale, sono sicuro che è stato studiato in ricerca operativa o qualcosa di simile. Ecco un modo di guardare al problema.

Ho $ P $ magazzini sul piano cartesiano. C'è un percorso da un magazzino ad ogni altro magazzino e la metrica distanza utilizzata è la distanza euclidea. In aggiunta, ci sono $ n $ diversi elementi. Ogni elemento $ 1 \ leq i \ leq n $ possono essere presenti in un qualsiasi numero di magazzini. Abbiamo un collezionista e ci viene dato un punto di partenza $ s $ per esso, dire l'origine $ (0,0) $. Il collettore viene dato un ordine, quindi un elenco di elementi. Qui, si può supporre che l'elenco contiene solo gli elementi distinti e solo uno di ciascuno. Dobbiamo stabilire il giro più breve a partire da $ s $ visitando alcune serie di magazzini in modo che la prendiamo ogni voce del ordine.

Ecco una visualizzazione di un'istanza generata casualmente con $ P = 35 $. Magazzini sono rappresentati con cerchi. quelli rossi contengono oggetto $ 1 $, quelli blu oggetto $ 2 $ e verde voce quelle $ 3 $. Dato un certo punto di partenza di $ s $ e l'ordine ($ 1,2,3 $), dobbiamo scegliere uno rosso, uno blu e uno verde del magazzino in modo da l'ordine può essere completata. Per caso, non ci sono magazzini multi-colored in questo esempio in modo che tutti contengono esattamente un elemento. Questo particolare esempio è un caso di set-TSP .

I grado di dimostrare che il problema è effettivamente $ \ {mathcal NP} $ - hard. Consideriamo un caso in cui ogni elemento $ I $ si trova in una diversa magazzino $ p_i $. L'ordine è tale che contiene ogni elemento. Ora dobbiamo visitare ogni magazzino $ p_i $ e trovare il giro più breve farlo. Ciò equivale di risolvere un caso di $ \ text {} TSP $.

Essendo così ovviamente utile, almeno nel contesto della logistica, il routing e la pianificazione, sono sicuro che questo è stato studiato prima. Ho due domande:

1. Qual è il nome del problema?
2. Come ben si può sperare di approssimare il problema (ammesso $ \ mathcal {P} \ neq \ mathcal {NP} $)?

Sono abbastanza contento con il nome e / o di riferimento (s) al problema. Forse la risposta al secondo punto segue facilmente o posso scoprire che me stesso.

Answer 1

Tra l'altro, questo problema può essere visto come un'istanza del Travelling dell'Acquirente problema. $ \ Text {} TPP $ è una generalizzazione di $ \ text {} TSP $ ed è stato proposto da T. Ramesh, Viaggi problema acquirente, 1981. Il problema è il seguente:

viene fornita una serie $ M = \ {1, ..., m \} $ dei mercati e una serie di $ N = \ {1, ..., n \} $ di prodotti. Inoltre c'è dato $ c_ {ij} $, il costo del viaggio dalla città di $ i $ alla città di $ j $, e non negativo $ d_ {ij} $, il costo di un prodotto $ i $ al mercato di $ j $ . L'acquirente ha inizio dalla sua città natale (ad esempio città $ 1 $), e viaggia a un sottoinsieme dei $ M $ città ed acquisti ciascuno dei $ n $ prodotti delle città che visita, e tornare di nuovo alla sua città natale. L'obiettivo è quello di trovare un tour per l'acquirente che in modo tale che la somma delle spese di viaggio e di acquisto sono minimizzate.

Quindi, mettere nei termini della domanda iniziale, i magazzini sono mercati. Ogni elemento disponibile ad un mercato ha pari prezzo. Se l'oggetto $ I $ non è disponibile a un mercato $ j $, il suo prezzo di $ d_ {ij} $ è impostato su un valore elevato.

Oltre a contenere $ \ text {TSP} $, $ \ text {TPP} $ contiene premio di raccogliere $ \ text {TSP} $, uncapacited posizione impianto problema, gruppo Steiner albero dei problemi e il problema di copertura insieme come il suo immediato casi speciali. Per la durezza, seguito dai risultati di durezza attuali per la copertura set, ne consegue che non v'è alcuna PTAS per $ \ text {TPP} $, anche con i costi di viaggio metriche il cui rapporto prestazioni è meglio di $ (1-o (1)) \ ln n $ a meno che $ \ mathcal {P} = \ {mathcal NP} $. Per ulteriori discussione e la formulazione di un IP, si veda per esempio R. Ravi e F. S. Salman, ravvicinamento Algoritmi per il viaggio Acquirente problema e le sue varianti in Network Design 1999 . Il href="http://en.wikipedia.org/wiki/Traveling_purchaser_problem" rel="noreferrer"> voce di Wikipedia per fornisce anche link ad alcuni approcci euristici.

Answer 2

Il problema è nel $ \ mathrm {P} $ se il numero di elementi è costante.

Sia $ K $ sia il numero di elementi (indipendente da $ n $). Per ogni ordine delle voci, l'uso di backtracking per provare tutti gli itinerari consentiti: per la prima volta passa attraverso qualche magazzino per la prima voce (cercando tutti i magazzini), poi uno per la seconda voce e così via

.

Ci sono $ O (K!) $ Ordinamenti degli articoli. Sia $ W_i $ sia il numero di magazzini per voce $ i $. Il numero di rotte è di $ \ prod_ {i = 1} ^ K W_i \ leq \ prod_ {i = 1} ^ K n = n ^ K $. Pertanto, il tempo di esecuzione dell'algoritmo di cui sopra è $ O (K! N ^ K) $, che è polinomiale per fisso $ K $.

Se il numero di elementi può essere lineare a $ n $, il problema è almeno altrettanto difficile da approssimare da $ TSP $: si può prendere un'istanza di $ TSP $, fare un elemento per ogni vertice come avrete notato, e quindi aggiungere i vertici in più molto lontano da tutti gli altri vertici per gonfiare $ n $ (e quindi consentire per gli elementi sufficienti che ogni vertice dell'istanza $ TSP $ ha un oggetto diverso), senza distruggere la durezza del approxability di $ TSP $. Si noti che se i punti sono nel piano euclideo, allora questo non è davvero aiutare in quanto v'è un $ PTAS $ per planare $ TSP $.

Answer 3

Quello che hai descritto suona più come un problema di pianificazione in AI. Suona come quello che potrebbe essere modellato con un linguaggio di pianificazione, come ad esempio STRIPS , ADL, PDDL, ecc . una volta modellato, il piano può essere risolto da una delle tante pianificazione algoritmi / euristica, che sono tipicamente statali algoritmi di ricerca spaziale. I collegamenti Wiki dovrebbe iniziare. Un capitolo di pianificazione in qualsiasi libro di testo AI può anche aiutare. Un esempio di PDDL planner è il GraphPlanner software .

Assegnato alcuni casi piuttosto degenerati di questo problema possono essere equivalenti a TSP, questo problema non è, in generale, la stessa di TSP, né è Set TSP. In entrambi TSP e Set TSP, l'insieme di città (magazzini) di essere visitato è predefinito. Qui, non ci importa davvero su ciò che i magazzini sono visitati, ma piuttosto ci interessa solo soddisfare un ordine nel modo più economico ed efficiente possibile. Si potrebbe avere ordini che non possono essere soddisfatte. Un pianificatore tornerà con un piano vuoto o una parziale in tal caso - un rapporto di soddisfacibilità. Il problema piano satifiability è noto in generale a essere PSPACE-complete. In TSP o Set TSP, un tour ottimale esiste sempre - non potrebbe essere però unico

.