O problema do transporte escolar rural: uma abordagem Column-and-cut para o problema de roteamento de veículos capacitado

Abstract

There is a situation of remoteness and difficulty of access to public services in general, in which the Brazilian rural population is submitted. One of the main, the access to education, is moving towards a horizon better by providing adequate transportation to students. This work isin line with the local governments interest in order to assist in improving the provision of a school transport service better quality at a lower cost. This paper addresses the issue of rural school transportation, classified as Capacitated Vehicle Routing Problem, proposing some Column-andcut algorithms to its resolution faster and with acceptable limits. The chosen master problem is derived from the set partitioning proposed by Balinski e Quandt (1964) which is combined withthree different subproblems. These ones are responsible for generate the columns, they are the qroutes method from Christofides, Mingozzi e Toth (1981a) and the Shortest Path Problem with Resources Constraints, non-elementar from Desrochers (1986) and the elementar from Feilletet al. (2004). Once the formulation is relaxed, two families of cuts were used to improve the obtained bounds, the first one is the Subset-row Inequalities from Jepsen et al. (2008) and the second one the Strong Degree Constraints from Contardo, Desaulniers e Lessard (2015). Themodels are evaluated using some of literature benchmarking instances.