Vid problem med dial-a-ride måste föremål transporteras från en källa till en destination. Egenskaperna hos de berörda servrarna och de särskilda kraven för färderna kan variera. Problem definieras på ett visst metriska utrymme, och målet är att hitta en genomförbar lösning som minimerar en viss objektiv funktion. Strukturen på dessa problem möjliggör en not som liknar standardnotationen för schemaläggning och köproblem. Vi introducerar en sådan notation och visar hur en klass av 7,930 dial-a-ride problemtyper uppstår från detta tillvägagångssätt. När vi undersöker deras computational komplexitet, definierar vi en partiell beställning på problemklassen och införlivar den i datorprogrammet DaRClass. Som indata använder DARClass listor över problem vars komplexitet är känd. Utgången är en klassificering av alla problem i en av tre komplexitetsklasser: lösbar i polynom tid, NP-hård, eller öppen. För ett urval av de problem som utgör indata för DaRClass, visar vi ett bevis på polynom-tid solvability eller NP-hårdhet. (Vehicle Routing; Dial-a-Ride; Computational Complexity)
De REF tillhandahåller en klassificering av problem med Dial-a-Ride med hjälp av en not som liknar den för schemaläggning och köproblem: Företräde är en aspekt av denna klassificering.
Computer-Aided Complexity Classification of Dial-a-Ride Problems
{'venue': 'INFORMS Journal on Computing', 'journal': 'INFORMS Journal on Computing', 'mag_field_of_study': ['Mathematics', 'Computer Science']}