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

• Grant number: 14/00939-8
• Support Opportunities: Regular Research Grants
• Start date: April 01, 2014
• End date: March 31, 2016
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Pedro Augusto Munari Junior
• Grantee: Pedro Augusto Munari Junior
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil
• Associated researchers: Douglas José Alem Junior
• Associated research grant(s): 14/50228-0 - Formulations and solution methods for vehicle routing problems with data uncertainty, AP.R

Abstract

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)

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, JUL 2017. (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, 2017-10-09. (14/00939-8, 14/22542-2)

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, 2016-06-14. (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, MAR 2016. (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, JUL 2017. (14/00939-8)

MUNARI, PEDRO; MORABITO, REINALDO. A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen. Top, v. 26, n. 3, p. 437-464, OCT 2018. (16/01860-1, 14/00939-8)