The Dial-a-Ride Problem with Split Requests and Profits

Sophie N. Parragh (), Jorge Pinho de Sousa () and Bernardo Almada-Lobo ()
Additional contact information
Sophie N. Parragh: Department of Business Administration, University of Vienna, 1090 Vienna, Austria; and INESC Porto/IBM CAS Portugal, 4200-465 Porto, Portugal
Jorge Pinho de Sousa: INESC TEC/Faculdade de Engenharia da Universidade do Porto, 4200-465 Porto, Portugal
Bernardo Almada-Lobo: INESC TEC/Faculdade de Engenharia da Universidade do Porto, 4200-465 Porto, Portugal

Transportation Science, 2015, vol. 49, issue 2, 311-334

Abstract: 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 algorithm is developed. We investigate the impact of request splitting under different geographical settings, assuming favorable settings for request splitting in terms of the number of people per request. The largest benefits from request splitting are obtained for problem settings exhibiting clustered customer locations.

Keywords: pickup and delivery; split requests; branch-and-price; variable neighborhood search (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0520 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:49:y:2015:i:2:p:311-334

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().