Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and multiple stacks

Marilène Cherkesly, Guy Desaulniers, Stefan Irnich and Gilbert Laporte

European Journal of Operational Research, 2016, vol. 250, issue 3, 782-793

Abstract: This paper proposes models and algorithms for the pickup and delivery vehicle routing problem with time windows and multiple stacks. Each stack is rear-loaded and is operated in a last-in-first-out (LIFO) fashion, meaning that when an item is picked up, it is positioned at the rear of a stack. An item can only be delivered if it is in that position. This problem arises in the transportation of heavy or dangerous material where unnecessary handling should be avoided, such as in the transportation of cars between car dealers and the transportation of livestock from farms to slaughterhouses. To solve this problem, we propose two different branch-price-and-cut algorithms. The first solves the shortest path pricing problem with the multi-stack policy, while the second incorporates this policy partly in the shortest path pricing problem and generates additional inequalities to the master problem when infeasible multi-stack routes are encountered. Computational results obtained on instances derived from benchmark instances for the pickup and delivery traveling salesman problem with multiple stacks are reported, and reveal the advantage of incorporating the multi-stack policy in the pricing problem. Instances with up to 75 requests and with one, two and three stacks can be solved optimally within 2 hours of computational time.

Keywords: Vehicle routing with pickups and deliveries; Loading constraints; Column generation; Branch-price-and-cut; Valid inequalities (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715009728
Full text for ScienceDirect subscribers only

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:eee:ejores:v:250:y:2016:i:3:p:782-793

DOI: 10.1016/j.ejor.2015.10.046

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().