Stai provando a risolvere un problema di ottimizzazione. La realizzazione di questo è importante per due motivi:
-
Non devi necessariamente trovare la soluzione assolutamente migliore (che richiederebbe troppo tempo per essere calcolata), ma puoi accontentarti di una soluzione abbastanza buona. Puoi perfezionare il tuo algoritmo in seguito.
-
Devi dichiarare in modo molto preciso a cosa stai ottimizzando. Presumo che tu voglia ridurre al minimo le spese dei passeggeri. Tuttavia, la combinazione di più viaggi di solito li rende più lunghi. Risparmiare un centesimo non vale la pena quando il mio viaggio dura più di mezz'ora a causa di una deviazione. Quindi c'è un'ottimizzazione secondaria per mantenere il tempo per ogni viaggio ragionevolmente minimo.
Se ottimizziamo per tempo e costi in modo indipendente, ci ritroviamo con un ampio spazio di soluzione con risposte ugualmente ottimali. Questo è indesiderabile; dobbiamo invece combinare costi e tempi in un'unica variabile di ottimizzazione. Questa connessione potrebbe essere qualcosa come " ogni 10 minuti di deviazione, voglio risparmiare almeno £ 2 ". Ha anche senso imporre ulteriori vincoli come " La condivisione del giro non può prolungare il mio viaggio di oltre il 20% " o " Voglio salvare almeno £ 2 condividendo il viaggio, altrimenti non "Non preoccuparmi di combinare il mio viaggio ".
Una volta che abbiamo impostato un tale sistema di regole, potremmo risolvere il problema semplicemente con la forza bruta - iterare attraverso tutti i gruppi di viaggi con un massimo di 4 passeggeri, e capire se dovrebbero essere combinati. Questo non è un approccio pratico.
Al contrario, abbiamo bisogno di euristica e filtri.
Dobbiamo mantenere lo spazio di ricerca il più piccolo possibile. Pertanto, possiamo escludere accoppiamenti ovviamente incompatibili contemporaneamente. Ad esempio, possiamo vedere se le durate dei viaggi si sovrappongono entro quel margine del 20%. Ciò implica che non abbiamo solo bisogno della posizione di partenza e di arrivo per ogni viaggio, ma anche del tempo di viaggio previsto senza condivisione del viaggio. Il filtro per la prossimità temporale è garantito non genera falsi negativi, a patto che tu usi qualcosa come questo margine del 20%.
Example
Let's assume we have 6 rides numbered 1–6. For each ride, we have the columns id, start, and duration. We want to find possibly compatible pairings. With brute force, we would have to look at n(n-1)/2 = 15 pairings (because for any IDs a and b, the pairing (a, a) is not valid, and (a, b) = (b, a)).
Our table (sorted by start time) might look like this:
ID start duration (start + f*duration)
1 08:00 10min 08:12
2 08:05 15min 08:23
3 08:10 5min 08:16
4 08:20 5min 08:26
5 08:30 9min 08:41
6 08:40 5min 08:46
For each ride a, we can possibly combine it with any later ride b where a.start + f*a.duration > b.start, where f is the maximal ride elongation constraint (in my example: 20% → f = 1.2). Applying this criterion gives us the following 5 possible pairings:
(1, 2), (1, 3)
(2, 3), (2, 4)
(5, 6)
Python-like pseudocode for this algorithm:
rides = rides.sort(by: (r => r.start))
pairings = []
for i from 0 to rides.length:
max_end = rides[i].start + f * rides[i].duration
for j from i to rides.length:
if rides[j].start < max_end:
pairings.append([i, j])
else:
break
This is also a good place to introduce the passenger constraint. Instead of blindly adding a pairing, we only do this if there are enough seats left:
seats_per_ride = 4
...
if rides[j].start < max_end:
total_passengers = rides[i].passengers + rides[j].passengers
if total_passengers <= seats_per_ride:
pairings.append([i, j])
else:
break
This still ignores that we can combine more than two rides. However, this can now be done as a post-processing of the resulting rides. As long as the passenger count is suitable, we can fold (a, b) and (a, c) into (a, b, c), which should be considered in addition to the existing pairings. Remember also that (a, b) and (b, a) are equivalent, so it makes sense to view combined rides as sets of rides, not just as tuples or pairs. If we apply these thoughts to the five pairings we already found, we also get
(1, 2, 3), (1, 2, 3, 4), (2, 3, 4)
Finding all sharing opportunities becomes fairly easy if we change the above algorithm to work backwards through the rides, as this can reuse existing calculations. This makes heavy use of the ordering to maintain correctness.
rides = rides.sort(by: (r => r.start), descending)
pairings = []
last_pairings = []
for i from 0 to rides.length:
max_end = rides[i].start + f * rides[i].duration
found_pairings = [[i]]
for pairing in last_pairings:
if pairing[0].start < max_end:
new_pairing = [i, *pairing]
total_passengers = sum(new_pairing.map(id => rides[id].passengers))
if total_passengers <= seats_per_ride:
pairings.append(new_pairing)
if total_passengers < seats_per_ride:
found_pairings.append(new_pairing)
else:
break
last_pairings = found_pairings
return pairings
Tuttavia, sarà anche utile applicare filtri forse imprecisi, poiché siamo interessati solo a una soluzione "abbastanza buona". Ad esempio, possiamo ignorare gli abbinamenti se sono troppo distanti, dove "troppo lontano" è il luogo in cui entra questa parte inesatta. Vorremmo rinviare il più possibile il reperimento del percorso, perché ciò richiede davvero tempo. Mentre dovremmo davvero ottimizzare il tempo, la nostra euristica potrebbe usare la distanza sulla mappa. In breve, puoi disegnare forme geometriche come rettangoli, cerchi o ellissi attorno a ciascuna rotta e vedere quali si sovrappongono. Questo è ancora piuttosto grezzo e potresti ottenere prestazioni migliori se archivi i viaggi in un database spaziale dall'inizio e chiedi esplicitamente viaggi ravvicinati utilizzando tale metrica.
Dopo aver applicato tutti i filtri, ci ritroviamo comunque con un paio di opportunità di condivisione del ride candidate. Non c'è modo di calcolare i possibili percorsi combinati. Le rotte combinate candidate sono tutte le rotte con tutti i punti di partenza e di arrivo per ogni passeggero come waypoint, con la restrizione aggiuntiva che ogni punto di arrivo deve arrivare dopo il punto di partenza corrispondente. Puoi quindi classificare ogni rotta per ogni passeggero con la nostra metrica di ottimizzazione (e magari capire che questa rotta violerebbe i nostri vincoli aggiuntivi).
Ora siamo arrivati allo spazio della soluzione (una serie di possibili giostre per ogni passeggero) e dobbiamo scegliere una soluzione (quale passeggero sceglie quale giro). Il problema rimanente è che un passeggero può avere più opzioni per condividere le corse. Quando l'utente sceglie un'opzione, i passeggeri delle altre opzioni dovranno pagare di più. È difficile trovare la soluzione perfetta in cui tutti i passeggeri combinati pagano il meno possibile, quindi mi accontenterò di una strategia non deterministica (almeno per ora, puoi sempre perfezionare più tardi). La strategia più ovvia cerca di trovare l'optimum locale per ogni passeggero:
for each passenger:
pick the ride where that passenger has to pay the least fare.
eliminate all other sharing opportunities that included this passenger.
Altre strategie avanzate potrebbero utilizzare una coda di priorità del passeggero che le ordina in base alla quantità salvata o da una metrica esterna come il tempo di prenotazione.
