The Bi-objective Pollution-Routing Problem with Mixed Linehauls and Backhauls

Abstract

A quantidade de gases com efeito de estufa que um veículo emite quando viaja é principalmente uma função da sua carga e velocidade, entre vários outros factores, como o comportamento de condução, características da estrada, etc. A redução do consumo de combustível de um veículo é uma forma eficaz de reduzir as emissões de poluentes para a atmosfera. Várias abordagens têm sido propostas na literatura sobre como atingir esse objectivo. O problema Poluição-Rotas é uma variante dos problemas de roteamento verde de veículos que visa minimizar uma função objectivo de custo, compreendendo o custo com o combustível e emissões e custo com a mão-de-obra. O problema consiste em determinar a velocidade e a carga óptimas em cada arco de uma rota, sujeito a restrições de capacidade dos veículos, janelas temporais e tempos de serviço. Nesta dissertação é abordado o problema Poluição-Rotas com entregas e recolhas indiferenciadas, considerando uma rede mista de entregas e recolhas. Foram estudadas as abordagens uni- e bi-objectivo do problema. Na abordagem uni-objectivo são monetizados os impactos económicos e ambientais e é procurada a minimização do seu custo total. Na abordagem bi-objectivo considera-se a minimização das emissões de CO2 e do tempo total de condução. São calculadas soluções eficientes optimizando uma função escalar do tipo e-constraint para o problema bi-objectivo. Os compromissos entre os dois objectivos são analisados. Os modelos foram testados em instâncias de referência adaptadas da literatura e os resultados obtidos são discutidos.

The amount of greenhouse gases a vehicle emits when it travels is mainly a function of its load and speed, among several other factors, such as driving behavior, the road characteristics, etc. Reducing a vehicle’s fuel consumption is an effective way of curbing pollutant emissions to the atmosphere. Several approaches have been proposed in the literature on how to ultimately achieve this goal. The Pollution-Routing Problem is a variant of the green vehicle routing problems which aims at minimizing a cost objective function comprising the cost of fuel and emissions and labor costs. The problem consists of determining the optimal vehicle speed and load on each arc of a route, subject to vehicle capacity constraints, customers’ time windows and service times. In this dissertation, the Pollution-Routing Problem with Mixed Linehauls and Backhauls is addressed, considering a mixed pickup and delivery network. The single- and bi-objective versions of the problem were studied. In the single-objective approach, the economic and environmental impacts are monetized and the minimization of their total cost is sought. In the bi-objective approach, the minimization of the CO2 emissions and the total driving time are considered. Efficient solutions were computed using the scalarizing \varepsilon-constraint technique for bi-objective optimization. The trade-offs between the two objectives are analyzed. The models were tested in benchmark instances adapted from the literature and the results obtained are discussed.