Framväxten av självkörande bilar kommer att dramatiskt förändra hur vi rör oss i städer i framtiden.

Särskilt, privat bilägande förväntas gå över mot delade mobilitetstjänster, med fordonsparkoperatörer som erbjuder transport på begäran. Detta bör bidra till att minska trafiken i tätorter och minska utsläppen av växthusgaser.

För att dessa tjänster ska växa, dock, exakta och beräkningseffektiva algoritmer kommer att behövas för att effektivt matcha individer med fordon på begäran, för att klara de hundratusentals resor som rutinmässigt görs inom storstäder.

Men forskare har ännu inte löst problemet med hur man bäst kan dimensionera och driva en fordonsflotta, med tanke på en särskild nivå av efterfrågan på personlig rörlighet.

Nu, i en tidning som publicerades i dag i tidskriften Natur , ett team av forskare koordinerat av Carlo Ratti, chef för MIT:s Senseable City Lab, avslöja en beräkningseffektiv lösning på detta problem, som de kallar "minimumflottans problem".

"Vi började undersöka detta problem motiverat av de ökande trenderna mot delad rörlighet, som sannolikt kommer att bli ännu starkare med övergången till autonoma fordon, säger Ratti, som också är professor i praktiken vid MIT:s institution för stadsstudier och planering. "Om efterfrågan på mobilitet betjänas av flottor av delade fordon, en grundläggande fråga är:Hur många fordon behöver vi för att tillgodose mobilitetsbehoven hos, säga, en stad som New York? "

Forskare har tidigare försökt lösa denna fråga med hjälp av varianter av "resande säljarproblem, " som syftar till att minimera den totala sträckan som en säljare som måste besöka ett givet antal destinationer i en stad.

Dock, det har hittills visat sig vara extremt svårt att hitta en optimal lösning på problemet med resande säljare, även med dagens kraftfulla datorer. Som ett resultat, bra lösningar för flotthantering har varit kraftigt begränsade i storlek, vilket betyder att de bara kan beräknas för flottor med bara några tiotals fordon, enligt Paolo Santi, en forskare vid Senseable City Lab och en senior forskare vid det italienska nationella forskningsrådet CNR, som ledde forskargruppen.

Detta är inte tillräckligt för att möta behoven i en stor stad som New York, han säger.

"Om vi ​​skulle överväga att ersätta det nuvarande taxisystemet i New York med en optimerad fordonsflotta, vi måste hitta det bästa sättet att servera de cirka 500, 000 resor gjorda på en dag, som för närvarande betjänas av cirka 13, 500 taxibilar, säger Santi.

Istället, forskarna använde en nätverksbaserad modell som de har kallat "fordonsdelningsnätverket" för att närma sig problemet. De använde tidigare ett liknande tillvägagångssätt, kallas "delbarhetsnätverket, "i en tidning från 2014 för att hitta det bästa sättet att dela åkattraktioner i en storstad.

Algoritmen representerar taxiflottans delbarhet som en graf, en matematisk abstraktion som består av noder (eller cirklar) och kanter (linjerna mellan noder). I detta fall, noderna representerar resor, och kanterna representerar det faktum att två specifika resor kan trafikeras av ett enda fordon.

Med hjälp av denna graf, algoritmen kunde hitta den bästa lösningen för flottningsdelning.

Laget, som också inkluderade Moe Vazifeh, den första författaren till artikeln och tidigare en ledande forskare vid Senseable City Lab; Giovanni Resta, en forskare vid Institutet för informatik och telematik i CNR; och Steven Strogatz, professor i matematik vid Cornell University, testade lösningen på en datamängd på 150 miljoner taxiresor som tagits i New York under loppet av ett år.

De beräknade restider med hjälp av det faktiska vägnätet på Manhattan och GPS-baserade uppskattningar härledda från taxiresans datauppsättning.

De fann att realtidsimplementering av metoden med nästan optimala servicenivåer minskade flottans storlek med 30 procent.

Lösningen förutsätter inte att någon individ måste dela en resa. Istället, det innebär helt enkelt en omorganisation av taxiexpeditionsverksamheten, som kan utföras med en enkel smartphone -app.

Lösningen kan bli ännu mer relevant under de kommande åren, som flottor av nätverksanslutna, självkörande bilar blir vanliga, säger Ratti.

"Om vi ​​ser på Manhattan som helhet, vi skulle teoretiskt kunna tillgodose dess mobilitetskrav med cirka 140, 000 fordon – ungefär hälften av dagens antal, " säger han. "Detta visar att morgondagens urbana problem när det gäller mobilitet inte nödvändigtvis kan hanteras med mer fysisk infrastruktur utan med mer intelligens, eller med andra ord:med mer kisel och mindre asfalt. "

Forskarna planerar nu att utföra ytterligare arbete för att utforska det minsta antal parkeringsplatser som behövs i städer, tillsammans med försäkringsbolaget Allianz.