Please use this identifier to cite or link to this item: http://hdl.handle.net/10216/87853
Author(s): Sophie Parragh
Jorge Pinho de Sousa
Bernardo Almada Lobo
Title: The dial-a-ride problem with split requests and profits
Issue Date: 2015-05-01
Description: In this paper we introduce the dial-a-ride problem with split requests and profits (DARPSRP).Users place transportation requests, specifying a pickup location, a delivery location, and a time window for either of the two. Based on maximum user ride time considerations the second time window is generated. A given fleet of vehicles, each with a certain capacity, is available to serve these requests and maximum route duration constraints have to be respected.Each request is associated with a revenue and the objective is to maximize the total profit, that is, the total revenue minus the total costs. Transportation requests involving several persons may be split if it is beneficial to do so. We formulate the DARPSRP as a mixed integer program using position variables and in terms of a path-based formulation.For the solution of the latter, we design a branch-and-price algorithm. The largest instance solved to optimality, when applied to available instances from the literature, has 40 requests; when applied to newly generated instances, the largest instance solved to optimality consists of 24 requests. To solve larger instances a variable neighborhood search algorithmis developed. We investigate the impact of request splitting under different geographical settings, assuming favorable settings for request splitting in terms of the number of peopleper request. The largest benefits from request splitting are obtained for problem settings exhibiting clustered customer locations.
Subject: Ciências Tecnológicas, Ciências da engenharia e tecnologias
Technological sciences, Engineering and technology
URI: http://hdl.handle.net/10216/87853
Document Type: Artigo em Revista Científica Internacional
Rights: restrictedAccess
Appears in Collections:FEUP - Artigo em Revista Científica Internacional

Files in This Item:
File Description SizeFormat 
65871.pdf310.57 kBAdobe PDF    Request a copy


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.