Advanced search
Start date
Betweenand

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
City of the host institution:São Carlos
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)

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

Scientific publications (6)
(The scientific publications listed on this page originate from the Web of Science or SciELO databases. Their authors have cited FAPESP grant or fellowship project numbers awarded to Principal Investigators or Fellowship Recipients, whether or not they are among the authors. This information is collected automatically and retrieved directly from those bibliometric databases.)
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/00939-8, 14/22542-2)
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)
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)
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)
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)