Advanced search
Start date

Interior point Branch-price-and-cut methods for variants of the vehicle routing problem


The purpose of this research project is to develop branch-price-and-cut (BPC) methods for solving two real-life variants of the vehicle routing problem. The first variant allows multiple deliverymen in each route and, thus, it seeks to determine the number of crew members that should be allocated at each vehicle, in addition to the usual routing decisions. The number of deliverymen affects directly the service time at each customer and, as a consequence, it affects the number of customers that are visited per day. The second variant considers requests of pickup and delivery of products, so it models urban situations such as the delivery of goods and dial-a-ride transportation services. BPC methods are currently the state-of-the-art approaches for solving vehicle routing problems to optimality. However, these methods still may take a long time in practice and, hence, the research of techniques to improve the performance of BPC methods is very active nowadays. Therefore, we intend to propose an interior point BPC for each problem variant, which uses the primal-dual interior point algorithm with the aim of improving the efficiency of generating columns and valid inequalities. In addition, we will exploit the strong branching and early branching techniques within the proposed interior point BPC. To the best of our knowledge, these strategies have never been used to solve the addressed problems. Furthermore, we intend to deal with the data uncertainties, a feature which is typically observed in real-life situations, although it has gained little attention on formulations and solution methods available in the vehicle routing literature.Benchmark instances available in the literature as well as real-life data instances will be used to verify the performance of the methods in extensive computational experiments. (AU)

Articles published in Agência FAPESP Newsletter about the research grant:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications (6)
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
FURTADO, MARIA GABRIELA S.; MUNARI, PEDRO; MORABITO, REINALDO. Pickup and delivery problem with time windows: A new compact two-index formulation. OPERATIONS RESEARCH LETTERS, v. 45, n. 4, p. 334-341, . (10/10133-0, 14/22542-2, 14/00939-8)
MARIA GABRIELA S. FURTADO; PEDRO MUNARI; REINALDO MORABITO. O problema de coleta e entrega com janelas de tempo na indústria petrolífera: modelos e métodos branch-and-cut. Gestão & Produção, v. 24, n. 3, p. 501-513, . (14/22542-2, 14/00939-8)
ALDAIR ÁLVAREZ; PEDRO MUNARI. Abordagens metaheurísticas para o problema de roteamento de veículos com janelas de tempo e múltiplos entregadores. Gestão & Produção, v. 23, n. 2, p. 279-293, . (14/00939-8)
GONDZIO, JACEK; GONZALEZ-BREVIS, PABLO; MUNARI, PEDRO. Large-scale optimization with the primal-dual column generation method. MATHEMATICAL PROGRAMMING COMPUTATION, v. 8, n. 1, p. 47-82, . (14/50228-0, 14/00939-8)
ALVAREZ, ALDAIR; MUNARI, PEDRO. An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen. Computers & Operations Research, v. 83, p. 1-12, . (14/00939-8)

Please report errors in scientific publications list using this form.