| 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 |
| TITULO |
| Articles published in other media outlets ( ): |
| More itemsLess items |
| VEICULO: TITULO (DATA) |
| VEICULO: TITULO (DATA) |