Dagens ride sharing services imiterar fortfarande en bättre affischtavla. De listar erbjudanden och gör det möjligt att söka efter källan och målstaden, ibland berikad med radial sökning. Det är därför ganska lätt att hitta en förbindelse mellan storstäderna. Dessa platser finns på en förteckning över angivna ursprungs- och bestämmelseorter. Men när du vill gå från en liten stad till en annan liten stad, även när de är bredvid en motorväg, du stöter på problem. Du kan inte hitta erbjudanden som skulle eller kunde passera genom staden lätt med liten eller ingen omväg. Vi löser detta intressanta problem genom att presentera en snabb algoritm som beräknar erbjudanden med de minsta omvägar w.r.t. en begäran. Våra experiment visar att problemet effektivt kan lösas i tider som lämpar sig för implementering av en webbtjänst. För realistisk databasstorlek uppnår vi uppslagstider på ca 5 ms och en matchningsgrad på 90% istället för bara 70% för de enkla matchande algoritmer som används idag.
För att lösa detta intressanta problem, Geisberger et al. REF utformade en snabb algoritm som beräknar omvägar för att matcha ridesharing-erbjudanden och -förfrågningar.
Fast Detour Computation for Ride Sharing
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}