期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 287, 期 1, 页码 76-89出版社
ELSEVIER
DOI: 10.1016/j.ejor.2020.04.047
关键词
Routing; Backhauls; Branch-cut-and-price; Integer programming
资金
- Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior - Brasil (CAPES) [001]
- Conselho Nacional de Desenvolvimento Cientifico e Tecnologico (CNPq) [303799/2018-8, 428549/2016-0, 307843/2018-1, 313601/2018-6, 308528/2018-2]
- Fundacao de Amparo aPesquisa do Estado do Rio de Janeiro (FAPERJ) [E-26/202.790/2019, E-26/202.887/2017]
- Inria
- CNRS (LABRI and IMB)
- Universitede Bordeaux
- Bordeaux INP
- Conseil Regional d'Aquitaine
In this paper, we are interested in the exact solution of the vehicle routing problem with backhauls (VRPB), a classical vehicle routing variant with two types of customers: linehaul (delivery) and backhaul (pickup) ones. We propose two branch-cut-and-price (BCP) algorithms for the VRPB. The first one follows the traditional approach with one pricing subproblem, whereas the second one exploits the linehaul/backhaul customer partitioning and defines two pricing subproblems. The methods incorporate elements of state-of-the-art BCP algorithms, such as rounded capacity cuts, limited-memory rank-1 cuts, strong branching, route enumeration, arc elimination using reduced costs and dual stabilization. Computational experiments show that the proposed algorithms are capable of obtaining optimal solutions for all existing instances with up to 200 customers, many of them for the first time. The approach involving two pricing subproblems appears to be more efficient than the traditional one. We introduce new large instances and find tight bounds for them. We finally evaluate the performance of the algorithms on benchmark instances of the heterogeneous fixed fleet VRPB and the VRPB with time windows. (C) 2020 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据