Conferência de Abertura

A Branch–Cut–and–Price Process for the Arc Routing Vehicle Scheduling Problem

Les Foulds*

INF – Universidade Federal de Goiás RG – ICMC/USP São Carlos

We describe a compact method to transform arc routing vehicle scheduling problem instances into node routing problem instances. Any node routing problem instance thus created must be solved by a branch-cut-and-price process, such as the one to be described in this presentation. The purpose is to make the number of nodes in the resulting transformed graphs greater by only one unit than the number r of required arcs (arcs having demand) in the original graph, that is, r+1 nodes. This low increase in the number of nodes represents an improvement compared to previously known methods. Using an adapted version of an existing branch–cut–and–price algorithm for a capacitated node routing problem on the transformed graph results in an effective approach for a capacitated arc routing problem. Computational experiments using this approach produced useful lower bounds in reasonable computational time for many challenging numerical instances from the literature. Additionally, some such previously open instances were solved to optimality for the first time.

* Trabalha na área de Pesquisa Operacional, com ênfase em engenharia de trânsito. Tem experiência em ensino de Ciência da Computação, Otimização, Pesquisa Operacional, Ciência da Gerência, Estatística, Ciências de Decisão, modelos de gerência quantitativos e de fabricação. Até junho 2007, foi professor titular na Universidade de Waikato, Hamilton, Nova Zelândia. Possui graduação em Matemática (1970) e mestrado com honras em Matemática (1972), ambos pela Universidade de Auckland, Nova Zelândia. Fez doutorado em Engenharia na Virginia Tech, EUA, em 1974. Sua linha de pesquisa principal consiste no desenvolvimento de modelos e de técnicas de otimização para simulação do trânsito. Publicou mais de 200 artigos de pesquisa nesses tópicos, em periódicos e anais de congressos, incluindo: Nature, Operations Research, Management Science, the European Journal of Operational Research, the Journal of the Operational Research Society, the Annals of Operations Research, the Journal of Global Optmization e the Asia-Pacific Journal of Operational Research. Desde 2010, vive permanentemente no Goiânia GO, Brasil, e continua suas pesquisas em modelagem e simulação de trânsito no Instituto de Informática da Universidade Federal de Goiás como professor visitante nacional senior.