A Branch-and-Price-and-Cut Algorithm for Heterogeneous Pickup and Delivery Problems with Configurable Vehicle Capacity

Yuan Qu () and Jonathan F. Bard ()
Additional contact information
Yuan Qu: Graduate Program in Operations Research and Industrial Engineering, University of Texas, Austin, Texas 78712
Jonathan F. Bard: Graduate Program in Operations Research and Industrial Engineering, University of Texas, Austin, Texas 78712

Transportation Science, 2015, vol. 49, issue 2, 254-270

Abstract: This paper presents a mixed-integer programming model for a variant of the pickup and delivery problem with time windows. The fleet is assumed to be heterogeneous with a novel feature that allows the vehicles to be configured before service begins to handle various types of demand. The work was motivated by a daily route planning problem arising at a senior activity center. A fleet of configurable vans is available each day to transport participants to and from the center, as well as to secondary facilities for rehabilitative and medical treatment. The number of participants and support equipment that a van can accommodate depends on how it is configured. An exact method is introduced based on branch and price and cut. At each node in the search tree, the master problem is solved by column generation to find a lower bound. To improve the bound, subset-row inequalities are applied to the variables of the master problem. Columns are generated by solving the pricing subproblems with a labeling algorithm enhanced by new dominance conditions. Local search on the current set of columns is used to quickly find promising additions. Implementation details and ways to improve the performance of the overall procedure are discussed. Testing was done on a set of real instances as well as a set of randomly generated instances with up to 50 customer requests. The results show that optimal solutions are obtained in the majority of cases.

Keywords: pickup and delivery problem; heterogeneous vehicles; branch and price and cut; configurable vehicle capacity; dial-a-ride problem (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0524 (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:254-270

Access Statistics for this article

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