I detta dokument behandlas ett problem med ett enda fordon Dial-a-Ride där kunderna kan uppleva stokastiska förseningar vid sina pickup platser. Om en kund är frånvarande när fordonet betjänar upphämtningsplatsen uppfylls begäran av en alternativ tjänst (t.ex. en taxi) vars kostnad läggs till den totala kostnaden för turen. I detta fall hoppar fordonet över motsvarande leveransplats, vilket ger en minskning av den totala färdkostnaden. Syftet med problemet är att bestämma en priori Hamiltonian turné minimera den förväntade kostnaden för lösningen. Detta problem löses med hjälp av ett heltal L-formad algoritm. Beräkningsförsök visar att algoritmen ger optimala lösningar för små och medelstora fall inom rimliga processortider. Det visas också att den faktiska kostnaden för en optimal lösning som erhålls med denna algoritm kan vara betydligt mindre än för en optimal lösning som erhålls med en deterministisk formulering.
REF införde problemet Dial-a-Ride (DARP) med stokastiska kundförseningar.
An integer L-shaped algorithm for the Dial-a-Ride Problem with stochastic customer delays
{'venue': 'Discret. Appl. Math.', 'journal': 'Discret. Appl. Math.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}