In che modo i motori di ricerca di viaggi combinano i voli

1

Sono curioso di sapere come i motori di ricerca di voli / treni combinano i risultati di più fonti. Per esempio, diciamo che sto chiedendo di andare da Londra a Parigi, e supponiamo che non ci siano voli diretti per qualsiasi motivo. Tuttavia, c'è un volo da Londra a Lille (nord della Francia), e poi un treno da lì a Parigi. Un esempio estremo potrebbe essere quello in cui non esiste neanche una connessione diretta, ma puoi raggiungere la tua destinazione combinando aereo, treno, autobus e infine taxi o un servizio di condivisione del viaggio.

In che modo un motore di ricerca potrebbe trovare l'opzione migliore? Ha accesso a un'API di base da ciascun fornitore che gli consente di chiedere corse dal punto A al punto B in un momento specifico. Non ha un database di tutte le giostre e voli disponibili, ma può solo interrogare l'API di ciascun provider, ma quelle query sono piuttosto lente (se si devono fare centinaia di esse) e costose, quindi l'obiettivo è minimizzare la quantità di query .

Sto pensando di creare un piccolo comparatore di condivisione del percorso come un progetto collaterale (e forse includere anche autobus / treno / taxi) e non sono sicuro da dove cominciare o se è fattibile considerando i vincoli.

Credo che il mio problema non riguardi semplicemente il "collegamento dei punti": le domande suggerite presuppongono che tu conosca tutti i punti e che tu abbia solo bisogno di trovare il percorso migliore. Nel mio caso è un po 'diverso perché non solo non conosco il percorso migliore, ma non so nemmeno quali "punti" ho. Posso fare domande come "c'è un passaggio da A a B", ma non posso chiedere "dammi tutte le corse che offri", il che significa che sto cercando consigli su come posso interrogare in modo efficiente per potenziali "punti" "senza usare l'approccio bruteforce di chiedere tutte le combinazioni possibili (che farebbe il sito del fornitore).

    
posta André Borie 09.08.2016 - 07:36
fonte

1 risposta

3

Gli algoritmi di individuazione dei percorsi come A * lo fanno regolarmente utilizzando alcune funzioni di costo (ad es. Distanza, tempo, o anche tempo di attesa) ed euristica per selezionare il candidato più promettente per espandere il percorso (ad es. Se possibile partenza dalla stessa stazione / aeroporto, e distanza tra punto di arrivo e destinazione).

Lo schema di base sarebbe:

  • usa una coda ordinata
  • seleziona il primo percorso in coda o il punto di partenza. Se raggiungi il target, hai il percorso ottimale
  • espanderlo sul punto finale cercando tutte le possibilità di viaggio compatibili
  • calcola il "costo" (nel tuo caso il tempo di viaggio) di ogni nuovo percorso espanso e l'euristico per raggiungere l'obiettivo
  • metti tutti questi percorsi nella coda e ordinali
  • loop di nuovo fino a quando non sei finito

Hai varianti a seconda dell'euristica che prendi, quale costo (o insieme di costi) vuoi minimizzare), come combinare costi ed euristica, se si elimina qualche espansione irrilevante, e se ci si ferma quando viene raggiunto il target o andare avanti per raccogliere diverse alternative.

In tutti questi algoritmi, il percorso viene espanso di un passo per iterazione, senza dover conoscere tutti i punti o il percorso nel grafico. Quando si presentano i risultati, il percorso potrebbe dover essere aggregato per nascondere i segmenti ovvi ma irrilevanti (ad esempio, tutte le città lungo il percorso del treno)

Se l'API che stai interrogando non fornisce tutte le deviazioni da una determinata nota, devi introdurre nell'algoritmo strategie basate sull'euristica aggiuntive, come ad esempio:

  • memorizzazione nella cache di risposte precedenti su altre richieste, quindi per creare una mappa di potenziali segmenti esistenti (ad esempio, se ci fosse un volo tra A e B in un giorno, potrebbe esserci un altro giorno, probabilmente intorno alla stessa ora). Tuttavia, dovresti comunque controllare / confermare per il viaggio corrente.
  • identificazione dei nodi hub intermodali (es. Avviare con un numero limitato di hub noti come Londra, Parigi, Franfurt ed espandere la lista automaticamente in base alle statistiche) e se non viene trovato alcun percorso diretto, iniziare a scomporre il percorso usando questi nodi hub ( ancora facendo uso dell'euristica costo / distanza)
  • prendere le regole per evitare aereo / treno per distanze più brevi.

Ci sono molte strategie che possono essere considerate. Ma non appena entri in un approccio così sfocato (ad es. Devi avanzare nei non vedenti) le tue prestazioni faranno molto affidamento sulla tua euristica e sarà necessaria molta messa a punto. Il modo più semplice sarà comunque una partnership con i servizi che offrono un'API "elenco delle partenze"

    
risposta data 09.08.2016 - 11:59
fonte

Leggi altre domande sui tag