Utilize este identificador para referenciar este registo: http://hdl.handle.net/10451/20144
Título: A study of flow-based models for the electric vehicle routing problem
Autor: Santos, Daniel Rebelo dos
Orientador: Gouveia, Luís, 1957-
Palavras-chave: Traveling salesman problem
Vehicle routing problem
Veículos elétricos
Modelos de fluxo
Algoritmos de planos de corte
Teses de mestrado - 2015
Data de Defesa: 2015
Resumo: Em anos recentes tem-se visto um aumento do uso de veículos eléctricos por parte de empresas que possuem frotas de veículos. Um veículo eléctrico exibe um comportamento bastante distinto de um veículo usual já que não pode funcionar durante largos períodos de tempo e necessita de recarregar a sua bateria de acordo com um processo frequente e bastante demorado. Além disso, a carga transportada por um veículo elétrico influencia a quantidade de energia gasta, algo que também ocorre com veículos usuais mas que não pode ser negligenciado no caso de um veículo elétrico pois o carregamento da bateria é, como foi referido, um processo demorado e que, portanto, quer-se que seja realizado o menor número de vezes possível. A introdução de veículos elétricos também conduz a outro tipo de aspectos a considerar relativamente à topologia da rede de estradas e clientes subjacente ao problema. Uma rua a subir implica um maior consumo de energia por parte de um veículo elétrico, enquanto que uma rua a descer pode até permitir a recuperação de energia. Além disso, temos também de considerar um conjunto novo de vértices, do grafo representativo da rede de estradas, referente às possíveis estações de recarga para os veículos elétricos. O Electric Vehicle Routing Problem (EVRP) é então uma variante dos problemas clássicos do Traveling Purchaser Problem (TSP) e do Vehicle Routing Problem (VRP) em que são considerados veículos com motor elétrico. Apesar das formulações naturais do TSP e do VRP considerarem apenas variáveis que modelam os arcos na(s) rota(s) para os veículos, no EVRP isso não é suficiente e, desta forma, é necessário considerar não só variáveis de fluxo para a carga do veículo mas também variáveis de fluxo que representem o nível de energia do veículo. Assim, os modelos matemáticos para o EVRP apresentam dois sistemas de fluxo em que o sistema de fluxo de energia depende do sistema de fluxo de carga. O foco desta dissertação é estudar modelos de fluxo, tanto agregados como desagregados, baseados em adaptações de modelos de fluxo existentes para o TSP e o VRP aos quais se adiciona, de forma provavelmente não trivial, o sistema de fluxo de energia. Pretende-se assim perceber de que forma este novo sistema de fluxo influência a complexidade do problema e se os métodos atualmente utilizados para resolver o TSP e o VRP podem ou não ser bem sucedidos quando aplicados diretamente ao EVRP. Além disso é do maior interesse estudar modelos com dois sistemas de fluxo em que um depende do outro. Note-se que apenas se pretendem métodos exatos e não heurísticos. O EVRP é definido num grafo G = (V;A) onde V = {1, … n }; é o conjunto de vértices (o vértice 1 representa o depósito) e A é o conjunto de todos os arcos existentes a conectar os vértices de V . O conjunto Vc = V \ {1} representa o conjunto dos clientes e cada cliente tem uma procura qi estritamente positiva associada. De forma a simplificar os modelos apresentados nesta dissertação, assume-se que q1 = 0 e seja Q a soma de toda a procura em V . A cada arco (i; j) ϵ A associa-se um custo de utilização cij e assume-se que os custos são simétricos, isto é, cij = cji. Até este ponto não existe grande diferença entre o EVRP e os problemas clássicos do TSP e do VRP. Contudo, no EVRP associamos também a cada arco os valores αij e βij . O primeiro indica a quantidade de energia gasta ao atravessar o arco (i; j) independentemente da carga transportada, ao passo que o segundo indica a energia consumida por cada unidade adicional de carga transportada aquando da utilização do arco (i; j). Note-se que estes valores podem ser negativos e, nesse caso, o “gasto" de energia é de facto um ganho de energia. Além disso note-se também que se pode considerar que G é completo pois, caso não seja, é possível calcular os valores em falta com base em algoritmos de caminho mais curto. Para o estudo nesta dissertação a função de consumo de energia utilizada é dada por Eij(l) = αij + l x βij , em que l é a carga do veículo. Na prática qualquer função real pode ser utilizada, contudo esta definição é não só linear como também incorpora dois aspetos práticos importantes que são o consumo base de energia e o consumo adicional conforme a carga transportada. Nesta dissertação apresentam-se modelos de fluxo para dois tipos de variante: a variante do TSP e a variante do VRP. Na variante do TSP temos apenas um veículo que deve servir toda a procura dos clientes. O objetivo é encontrar uma rota de custo mínimo para esse veículo que comece e termine no depósito, que permita que o veículo visite cada cliente uma e uma só vez e que garanta que o nível de energia do veículo elétrico se mantém dentro dos seus limites, isto é, entre 0 e B, sendo B a energia máxima na bateria. Na variante do VRP considera-se a possibilidade de utilizar vários veículos com um objetivo similar, ou seja, encontrar um conjunto de rotas de custo mínimo em que cada rota começa e acaba no depósito, cada cliente é visitado uma e uma só vez, o nível de energia dos veículos mantém-se dentro dos seus limites e cada veículo não transporta mais do que a sua carga máxima, a qual se representa por C. Também são apresentados modelos que incluem estações de recarga que são definidos num grafo especial e estendido, todavia não são apresentados resultados respeitantes a estes modelos já que se decidiu estudar primeiro as variantes do EVRP sem estações de recarga. Para a resolução dos modelos e obtenção de resultados de teste foram desenvolvidos métodos de planos de corte com base em desigualdades válidas existentes para o TSP e o VRP. Isto é possível pois os modelos incorporam a modelação do TSP ou do VRP pelo que qualquer resultado que envolva apenas a parte do modelo que não considera a energia continua a ser válido para o EVRP. Estes métodos foram implementados utilizando o software CPLEX 12.6.1 e a sua Concert Technology para C++. O programa final desenvolvido está pronto para ser utilizado por qualquer utilizador que o pretenda. Os resultados de teste foram obtidos com recurso a instâncias geradas. A principal conclusão que se retira deste estudo é a de que não é expectável que as abordagens com métodos exatos usadas para o TSP e o VRP sejam suficientes para resolver o EVRP. O que se pode verificar pelos resultados obtidos é que as desigualdades válidas utilizadas não conseguem lidar com o aumento dos gaps da relaxação linear relativamente ao valor ótimo que se verifica à medida que o valor de B diminui. Contudo, uma das abordagens de planos de corte utilizada produziu alguns resultados interessantes mas, não obstante, insuficientes. Estas conclusões levam a que, como trabalho futuro, se pretenda explorar o sistema de fluxos de energia ao invés de nos focarmos apenas no que já existe para o sistema de fluxos da carga. Isto pode ser feito, por exemplo, com recurso a uma abordagem de discretização dos modelos e consequente descoberta de desigualdades válidas para este novo sistema de fluxo de energia.
In this dissertation we study a generalization of the classical Traveling Salesman and Vehicle Routing problems in which the vehicles are electric. We assume that an electric vehicle has a maximum battery charge that may not be enough to allow the vehicle to complete the tour given by the classical problem's optimal solution therefore leading to having to consider different routes with possibly worse costs. The Electric Vehicle Routing Problem is defined on a graph with a depot and a set of clients. Each client has a strictly positive demand and, in our case, we consider a pick-up variant, i.e., the load of the vehicle increases during the route. The graph's arcs are characterized by their travel cost, the energy consumed by an empty vehicle and the additional energy consumed per load unit. The energy values can be negative if there is energy recuperation (e.g. on a downward slope). We consider an homogeneous feet with fixed maximum capacity and fixed maximum energy level. The objective of the Electric Vehicle Routing Problem is to determine a set of routes with minimal total costs such that the/every route starts and ends on the depot, each client is visited exactly once, the total demand of the clients on the/a route does not exceed the load capacity and the energy level of every vehicle stays within its limits. We present and evaluate ow-based models, with both aggregated and disaggregated versions, and experiment with branch-and-cut methods based on simple valid inequalities which exist for the Traveling Salesman or Vehicle Routing problems. We also consider models with recharging stations that allow a vehicle to fully recharge its battery mid-route. Finally we discuss some results alongside future planned work.
Descrição: Tese de mestrado em Estatística e Investigação Operacional, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2015
URI: http://hdl.handle.net/10451/20144
Designação: Mestrado em Estatística e Investigação Operacional
Aparece nas colecções:FC - Dissertações de Mestrado

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ulfc114355_tm_Daniel_Santos.pdf1,09 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.