I problemet med dial-a-ride formulerar användarna önskemål om transport från ett visst ursprung till en viss destination. Transporten sker med fordon som tillhandahåller en gemensam tjänst. Problemet består i att utforma en uppsättning minimikostnadsvägar för fordon som uppfyller kapacitet, varaktighet, tidsfönster, parning, företräde och körtidsbegränsningar. Detta dokument introducerar en mixed-integer programmering formulering av problemet och en gren-och-cut algoritm. Algoritmen använder nya giltiga ojämlikheter för dial-a-ride problem samt kända giltiga ojämlikheter för pickup och leverans och fordon routing problem. Beräkningsförsök som utförs på slumpmässigt genererade fall visar att den föreslagna metoden kan användas för att lösa små till medelstora fall.
Den state-of-the-art Branch-and-cut (BaC) algoritm REF formulerar flera serverversion av detta problem med hjälp av mixed-integer programing och en gren-och-cut lösning.
A Branch-and-Cut Algorithm for the Dial-a-Ride Problem
{'venue': 'Operations Research', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}