21 |
[en] VEHICLE ROUTING PROBLEMS WITH TIME WINDOWS AND EXACT SYNCHRONIZATION CONSTRAINTS / [pt] PROBLEMAS DE ROTEAMENTO DE VEÍCULOS COM JANELAS DE TEMPO E SINCRONIZAÇÃO EXATA DE OPERAÇAOFABIAN ARTURO CASTILLA PENARANDA 29 December 2014 (has links)
[pt] Uma generalização do problema de roteamento de veículos (VRP) presente em aplicações práticas em portos e operações em minas é o objeto desta dissertação. Nesta variante do VRP cada cliente pode demandar diferentes tipos de veículos para cumprir tarefas colaborativamente. Nesta atividade, os veículos podem aguardar o início da operação no local porém, devem iniciar as tarefas ao mesmo tempo. O objetivo é determinar as rotas dos veículos disponíveis de modo a maximizar a soma (ponderada) dos clientes atendidos enquanto a distância total percorrida é minimizada. O caso específico onde todos os clientes são atendidos e a distância total percorrida é minimizada determina o problema central estudado nessa dissertação. Este caso particular pode ser visto como uma generalização direta do, muito estudado e conhecido problema de roteamento, VRP com janelas de tempo (VRPTW) onde a capacidade
dos veículos é suficientemente grande. Esta escolha de um problema mais restrito é justificada por permitir uma clara comparação de sua dificuldade através da sua relação com o VRPTW. A partir da classificação
dos casos de sincronização em problemas de roteamento proposta por (DREXL, 2012), denominamos o problema aqui estudado de Problema de Roteamento de Veículos com Janelas de Tempo e Sincronização exata da Operação (VRPTWEOS). Neste trabalho damos uma definição formal ao VRPTWEOS. Modelos de programação inteira são propostos e analisados. Também apressentamos métodos de resolução baseados na decomposição Dantzig-Wolfe, dos quais são derivados algoritmos exatos e aproximados.
Com o propósito de avaliar a eficiencia desses algoritmos, foi criado um grupo de instancias de teste baseado no benchmark do Solomon para o VRPTW. O método usado para criar o conjunto de instancias de teste é descrito em detalhe. Experimentos computacionais sobre este conjunto de instancias mostraram que o método de resolução proposto é promissor para a resolução do VRPTWEOS. / [en] This dissertation addresses a generalization of the vehicle routing problem (VRP) that arises in real life applications in ports and mine operations. In this VRP variant, each customer may demand different types
of vehicles to perform a task collaboratively. Vehicles are allowed to wait at the locations but they must start operating at the same time. The objective is to route the available vehicles while maximizing the (weighted) sum of served customers and minimizing the total distance traveled. The specific case where all customers must be served while minimizing the total distance traveled is the central problem here studied. This special case can be viewed as a straightforward generalization of, a well known and more specific routing problem, the VRP with time windows (VRTPTW) where the capacity of the vehicles is sufficiently large. We support this narrower scope by stating that it allows a clear comparison of the problem
hardness by its relation to the VRPTW. Sticking to the classification of synchronization in vehicle routing proposed by (DREXL, 2012) we named this problem as the Vehicle Routing Problem with Time Windows and Exact Operation Synchronization (VRPTWEOS). In this work, a formal definition for the VRPTWEOS is provided. Integer programming models for this problem are proposed and analyzed. Furthermore, we propose a solution method based on the Dantzig-Wolfe decomposition for which exact and aproximated resolution algorithms are described. In order to test the performance of those algorithms, a group of benchmark instances for the VRPTWEOS was created on top of the Solomon benchmark for the
VRPTW. The method used to create the benchmark instances is described in detail. Computational experiments over the mentioned set of instances showed that the proposed solution approach is a promising alternative for solving the VRPTWEOS.
|
22 |
[en] AN EFFICIENT ALGORITHM FOR THE ADJACENT QUADRATIC SHORTEST PATH PROBLEM WITH APPLICATION TO SMOOTH TRANSMISSION LINE ROUTING / [pt] UM ALGORITMO EFICIENTE PARA O PROBLEMA DE CAMINHO MAIS CURTO QUADRÁTICO ADJACENTE COM APLICAÇÃO NO DESENHO DE ROTAS SUAVES DE LINHAS DE TRANSMISSÃOJOAO MARCOS DUSI VILELA 13 January 2022 (has links)
[pt] Essa dissertação explora o problema roteamento de linhas de transmissão (LT) através da solução do caminho mais curto em um grafo sem ciclos de melhoria, considerando custos quadráticos para arcos adjacentes. Esse problema é conhecido como o Problema do Caminho Mínimo Quadrático
Adjacente (CMQA). Esse trabalho apresenta uma descrição teórica do CMQA, propõe uma extensão do algoritmo Dijkstra (aqDijkstra) para solução de CMQA em tempo polinomial e discute como o algoritimo pode ser utilizado em metodologias de roteamento de LT. Em seguida, apresentamos uma melhoria estendendo o algoritmo A estrela para sua forma adjacente quadrática (aqA estrela), incluindo uma etapa de busca reversa para estimação de custos de chegada. Foram feitos experimentos computacionais contemplando a variação de custos quadráticos, geração de instâncias aleatórias, testes de estresse e comparação com abordagens já utilizadas na literatura. Os resultados sugerem que: (i) aqA estrela teve o melhor desempenho, atingindo tempos de busca 40 vezes mais rápidos que aqDijkstra e 50 vezes mais rápido que a abordagem mais rápida apresentada pela literatura; (ii) a eficiência dos algoritmos não foi afetada pela variação dos custos quadráticos; (iii) os algoritmos propostos aqA estrela e aqDijkstra também foram mais eficientes nas instancias aleatórias, reafirmando a superioridade dos mesmos. Duas aplicações
são apresentadas, uma de objetivo ilustrativo e outra para um caso real. O algoritimo aqA estrela foi usado para solução de um CMQA em um grafo de quase um bilhão de arcos quadraticos, resultado em uma rota proposta com custos adicionais três vezes menor. / [en] This dissertation explores the problem of transmission line (TL) routing through finding the shortest path on an undirected graph with no improving cycles, considering quadratic costs for adjacent arcs. This problem
is known as the Adjacent Quadratic Shortest Path Problem (AQSPP). This work provides the theoretical background for the AQSPP, proposes an extension of Dijkstra s algorithm (aqDijkstra) for solving AQSPP in
polynomial-time and discusses how AQSPP can be included in routing methodologies. Furthermore, it is presented an improvement to the algorithm: the adjacent quadratic A star (aq A star) with a backward search for cost-togo estimation, to speed up search. For computational experiments, aqDijkstra
and aqA star are benchmarked with other algorithms from the technical literature. The search behavior of the algorithms is also studied within different tests, including: quadratic cost variation, randomly generated graph instances and increasingly larger instances. The numerical results suggests that: (i) aqA star outperformed all the other algorithms, being 40 times faster than aqDijsktra and 50 times faster than the fastest benchmark algorithm; (ii) the studied algorithms do not lose efficiency as quadratic costs increase;
(iii) aqA star and aqDijkstra were faster benchmark algorithms under random graph instances, indicating their robustness. Two applications are provided, one for illustrative purposes, and another to study performance on a real application. The aqA star algorithm solved an AQSSP on a graph with almost a
billion quadratic arcs and provided a route with three times lower additional costs.
|
23 |
[en] ADAPTIVE ROUTING IN DATA COMMUNICATION NETWORKS THROUGH REINFORCEMENT LEARNING / [pt] ROTEAMENTO ADAPTATIVO EM REDES DE COMUNICAÇÃO DE DADOS POR REINFORCEMENT LEARNING / [es] RUTEAMIENTO ADAPTATIVO EN REDES DE COMUNICACIÓN DE DATOR POR REINFORCEMENT LEARNINGYVAN JESUS TUPAC VALDIVIA 13 March 2001 (has links)
[pt] Esta dissertação investiga a aplicação dos métodos de
Reinforcement Learning na descoberta de rotas ótimas em uma
rede de comunicação. Uma rede de comunicação real possui um
comportamento dinâmico, mudando seu estado com o tempo. Os
algoritmos de roteamento devem, portanto, oferecer rapidez
na resposta às mudanças do estado da rede. O objetivo do
trabalho é avaliar a aplicação de técnicas de Reinforcement
Learning (RL) como base de algoritmos adaptativos de
roteamento de pacotes. O problema de roteamento de pacotes
sob a visão de RL consiste na definição de cada nó na rede
como um agente RL, sendo que este agente deve definir ações
de forma a minimizar uma função objetivo que pode ser o
tempo de roteamento dos pacotes. Um dos objetivos do RL é
precisamente aprender a tomar as ações que minimizem uma
função. O trabalho consistiu de 4 etapas principais: um
estudo sobre a área de Reinforcement Learning (RL); um
estudo sobre a área de redes de comunicação e roteamento de
pacotes; a modelagem do problema de roteamento como um
sistema RL e implementação de diferentes métodos de RL para
obter algoritmos de roteamento; e o estudo de casos.
O estudo na área de Reinforcement Learning abrangeu desde
as definições mais fundamentais: suas características, os
elementos de um sistema RL e modelagem do ambiente como um
Processo de Decisão de Markov, até os métodos básicos de
solução: Programação Dinâmica, método de Monte Carlo, e o
método de Diferenças Temporais. Neste último método, foram
considerados dois algoritmos específicos: TD e Q-Learning.
Em seguida, foi avaliado o parâmetro Eligibility Traces
como uma alternativa para apressar o processo de
aprendizado, obtendo o TD(lambda) e o Q(lambda)
respectivamente. O estudo sobre Redes de Comunicação e
Roteamento de pacotes envolveu os conceitos básicos de
redes de comunicações, comutação por pacotes, a questão do
roteamento de pacotes e os algoritmos existentes
adaptativos e não adaptativos, que são utilizados na
atualidade. Nas redes de comunicação, definidas como um
conjunto de nós ligados através de enlaces de comunicação,
para se enviar uma mensagem de um nó a outro, geralmente, a
mensagem é quebrada em pedaços, chamados pacotes, e
enviados através de outros nós, até chegar ao destino.
Deste modo surge o problema de escolher os nós que levem o
pacote o mais rápido possível até o nó destino. Os
algoritmos analisados foram: Shortest Path Routing que
procura os caminhos com menor número de nós
intermediários, não sendo sensível às mudanças na carga nem
na topologia da rede; Weighted Shortest Path Routing, que
oferece um melhor desempenho a partir de uma visão global
do estado da rede, que nem sempre é fácil de obter em redes
reais e o algoritmo de Bellman-Ford, baseado em decisões de
roteamento locais e atualizações periódicas, com algumas
limitações para obter políticas em altas cargas. Este
último é um dos algoritmos mais utilizados na atualidade,
sendo base de muitos protocolos de roteamento existentes.
A modelagem do problema de roteamento como um sistema RL
foi inspirada por uma característica na definição de um
sistema RL: um agente que interage com o ambiente e aprende
a atingir um objetivo. Assim, a modelagem dos algoritmos
tem como objetivo aprender a descobrir as rotas que
minimizem o tempo de roteamento de pacotes desde uma origem
até um dado destino. A avaliação de uma rota escolhida não
pode ser obtida antes que o pacote alcance o seu destino
final. Este fato faz com que os processos de aprendizado
supervisionado tenham dificuldade de se aplicar a esse
problema. Por outro lado, o Reinforcement Learning não
necessita de um par entrada-resposta para fazer o
aprendizado, permitindo-lhe abordar o problema com relativa
facilidade. Na modelagem efetuada, cada nó na rede se
comporta como um agente de RL que age na própria rede, a
qual é o ambiente. A informação das rotas é armazenada nas
funções de valor existentes em todos os nós da rede para / [en] This dissertation investigates the application of
Reinforcement Learning methods to the discovery of
optimal routes in communication networks. Any current
communication network displays dynamic behavior,
changing its states over time. Therefore, the routing
algorithms must react swiftly to changes in the network
status. The objective of this work is to evaluate the
application of some Reinforcement Learning techniques to
define adaptive packet routing algorithms. The packet
routing problem under the RL vision consists in the
definition of each node on network as an RL agent. Thus,
each agent must take actions in order to minimize an
objective function such as end to end packet routing delay.
One main objective of the RL is precisely learning to
take the actions that minimize a given function.
This thesis is consists of 4 main parts: first, a study of
Reinforcement Learning (RL); a study of the
communication networks and packet routing; the routing
problem model as a RL system and the implementation
of several RL methods in order to obtain some routing
algorithms; e finally, the case study.
The study of Reinforcement Learning extends from the more
basic definitions, Reinforcement Learning
features, elements of a RL system and environment modeling
as a Markovian Decision Process, to the basic
methods of solution: Dynamic Programming, Monte Carlo
methods and Temporal Differences methods. In this
last case, two specific algorithms have been considered: TD
and Q-Learning, and, finally, the Eligibility Traces
are evaluated as a useful tool that permits us to
accelerate the learning process leading to the TD(lambda)
and the Q(lambda) routing algorithms. The study on
communication networks and packet routing
involves the foundations of communication networks, packet
switching, the packet routing problem, and adaptive and non-
adaptive routing algorithms used
at the present time. Communication networks are defined as
a set of nodes connected through communication
links. In order to send a message from a source node to a
destination node usually the message is broken into
segments called packets, and these are sent through other
nodes until arriving at the destination. In this way the
problem appears to choose the path which takes the shortest
possible time for the packet to reach the destination
node. The following algorithms have been analyzed: Shortest
Path Routing that looks for paths with minimal
hop number, not being sensible to the changes of load level
and network topology; Weighted Shortest Path
Routing that offers better performance from a global vision
of the state of the network, which is not always easy
to get in real networks; on the other hand, the Bellman-
Ford routing algorithm was studied, this is based on local
routing decisions and periodic updates, with some
limitations to obtain policies in high load conditions.
Bellman-Ford
is one of the algorithms most used at the present time,
being the basis for many existing routing protocols.
The modeling of the routing problem as a RL system was
inspired by one of the main features of the
definition of an RL system: an agent who interacts with the
environment and learns to reach an objective;
therefore, the modeling of the routing algorithms has as
its objective to learn to discover the paths that minimize
packet routing time from an origin to an destination. The
evaluation of a chosen route cannot be completed
before the package reaches its final destination. This fact
implies that supervised learning cannot be applied to
the routing problem. On the other hand, Reinforcement
Learning does not need a input-output pair for the
learning process, allowing it to approach the problem with
relative ease. In the modeling, each network node is
viewed as a RL agent that acts in the same network; the
network is the environment. The routing information is
stored in the existing value functions in all nodes in the
network, for each node and all another destination node / [es] Esta disertación investiga la aplicación de los métodos de
Reinforcement Learning en la determinación de rutas óptimas
en una red de comunicación. Una red de comunicación real
posee un comportamiento dinámico, donde su estado varia en
el tiempo. Los algoritmos de ruta óptima deben, por lo
tanto, ofrecer rapidez en la respuesta a las variaciones
del estado de la red. El objetivo de este trabajo es
evaluar la aplicación de técnicas de Reinforcement Learning
(RL) como base de algoritmos adaptativos de problemas de
ruteamiento en redes. Este problema consiste en la
definición de cada nodo de la red como un agente RL. Este
agente debe definir acciones de modo a minimizar una
función objetivo que puede ser el tiempo de ruteamiento.
El trabajo consta de 4 etapas principais: un estudio sobre
el área de Reinforcement Learning (RL); un estudio sobre
redes de comunicación y problema de ruteamiento; el modelo
de ruta óptima como un sistema RL y la implementación de
diferentes métodos de RL para obtener algoritmos de ruta
óptima; y un estudio de casos.
El estudio en el área de Reinforcement Learning va desde
las definiciones fundamentales: características, elementos
de un sistema RL y modelaje del ambiente como un Proceso de
Decisión de Markov, hasta los métodos básicos de solución:
Programación Dinámica, método de Monte Carlo, y método de
Diferencias Temporales. En este último método, fueron
considerados dos algoritmos específicos: TD e Q-Learning.
A seguir, fue evaluado el parámetro Eligibility Traces como
una alternativa para agilizar el proceso de aprendizaje,
obteniendo el TD(lambda) y el Q(lambda) respectivamente.
El estudio sobre Redes de Comunicación y Problema de
Transporte incluye los conceptos básicos de redes de
comunicaciones, la cuestión de la ruta óptima y los
algoritmos adaptativos y no adaptativos existentes, que se
utilizan actualmente. Los algoritmos analizados fueron:
Shortest Path Routing, que busca los caminos con menor
número de nodos intermedios, no siendo sensible a
variaciones en la carga ni en la topología de la red;
Weighted Shortest Path Routing, que ofrece un mejor
desempeño a partir de una visión global del estado de la
red, que no siempre es fácil de obtener en redes reales; y
el algoritmo de Bellman-Ford, que tiene como base
decisiones de rutas locales y actualizaciones periódicas,
con algunas limitaciones para obtener políticas en altas
cargas. Este último es uno de los algoritmos más utilizados
en la actualidad, siendo base de muchos protocolos de
trazado de ruta existentes. La solución para modelar el
problema de ruteamiento como un
sistema RL fue inspirada por una característica en la
definición de un sistema RL: un agente que interactúa con
el ambiente y aprende a alcanzar un objetivo. Así, el
modelo tiene como objetivo aprender a determinar las rutas
que minimizen el timpo desde el origen hasta un destino
dado. La evaluación de uma ruta seleccionada no puede ser
obtenida antes que el paquete alcance su destino final.
Esto hace que los procesos de aprendizaje supervisionado
tengan dificultades para ser aplicados a este problema. Por
otro lado, Reinforcement Learning no necesita de un par
entrada-salida para el aprendizaje, permitiendo así,
abordar el problema con relativa facilidad. En el modelo
establecido, cada nodo en la red se comporta como un agente
de RL que actúa en la propria red.
La información de las rutas se almacena en las funciones de
valor existentes en todos los nodos de la red para cada
nodo destino diferente. Esta información contiene un valor
estimado del tiempo requerido para un paquete para llegar
hasta el nodo destino. La actualización de esos valores se
realiza durante la transición del paquete hasta el vecino
seleccionado. En este trabajo se implementaron varios
algoritmos de ruta óptima. Cada uno de los algoritmos
aplica características de las técnicas en Reinforcement
Learning: o Q(lambda)-Routing, y el TD-Routing. En el
estudio d
|
24 |
[pt] O PROBLEMA DE ROTEAMENTO EM ARCOS CAPACITADOS COM DEPENDÊNCIA DE TEMPO E VEICULOS ELÉTRICOS / [en] THE ELECTRIC TIME-DEPENDENT CAPACITATED ARC ROUTING PROBLEMJAHIR DESAILY LLAGAS ORTEGA 24 November 2022 (has links)
[pt] Com o aumento das questões energéticas e ambientais, os veículos elétricos (EVs) se tornarão um modo de transporte essencial na distribuição logística. Um cenário vital a ser considerado é a dependência do congestionamento
do tráfego nos tempos de viagem dos veículos, como é comum nas áreas urbanas hoje. Esse recurso significa que a velocidade de um EV em cada rota
pode ser distinta durante diferentes períodos. Como os EVs possuem autonomia limitada, vários trabalhos na literatura propuseram modelos de consumo
de energia em função da velocidade e fatores aerodinâmicos. No entanto, sua
aplicação permanece limitada e simplificada devido à sua dependência da velocidade e dos tempos de viagem. No caso da velocidade, os modelos da literatura
trabalham sob uma velocidade média durante um determinado arco ou introduzem aproximações com métodos de linearização por partes. Em relação aos
tempos de viagem, os atuais algoritmos de roteamento de veículos muitas vezes
reformulam a rede viária em um gráfico completo onde cada arco representa o
caminho mais rápido entre dois locais. Os resultados obtidos por esses métodos
divergem da realidade, principalmente para problemas de roteamento de arco
envolvendo serviços nos arcos de uma rede rodoviária. Por essas razões, definimos o Problema de Roteamento de Arco Capacitado Elétrico com tempos de
viagem dependentes do tempo e taxa de consumo de energia dependente da velocidade. Ao longo de um horizonte de planejamento, cada arco está associado
a uma função de velocidade passo a passo. O objetivo é atender um conjunto
de arcos que demandam serviços por meio de uma frota de EVs com carga e
capacidade de bateria limitadas, minimizando o tempo total de viagem. Além
disso, a taxa de consumo de energia por unidade de tempo percorrido é considerada uma função não linear baseada na velocidade. Propomos um algoritmo
de pré-processamento de consumo de energia de forma fechada sem aproximações. Nós o incorporamos em uma metaheurística Iterate Local Search e
comparamos o impacto no projeto de rotas com os veículos convencionais. / [en] With energy and environmental issues rising, electric vehicles (EVs)
will become an essential mode of transportation in logistics distribution. A
vital scenario to consider is the dependence of traffic congestion on vehicle
travel times, as it is common in urban areas today. This feature means that
the speed of an EV on each route may be distinct during different periods.
Because EVs have a limited driving range, various works in the literature have
proposed energy consumption models as a function of speed and aerodynamic
factors. However, their application remains limited and oversimplified due
to their dependence on speed and travel times. In the case of speed, the
models in the literature work under an average speed during a given arc or
introduce approximations with piece-wise linearization methods. Regarding
travel times, current vehicle routing algorithms often reformulate the road
network into a complete graph where each arc represents the quickest path
between two locations. The results obtained by these methods differ from
reality, particularly for Arc Routing Problems involving services on the arcs
of a road network. For these reasons, we define the Electric Capacitated Arc
Routing Problem with Time-dependent Travel times, and Speed-dependent
Energy Consumption Rate (E-TDCARP). Over a planning horizon, each arc
is associated with a step-wise speed function. Based on this function, a vehicle s
speed can change while traveling on a given arc. The objective is to serve a
set of arcs that require services through a fleet of electric vehicles with limited
load and battery capacity, minimizing the total travel time. Furthermore, the
energy consumption rate per unit of time traveled (ECR) is considered a nonlinear function based on speed. We propose a closed-form energy consumption
preprocessing algorithm without approximations. We embed it into an Iterate
Local Search metaheuristic (ILS) for E-TDCARP and compare the impact on
the design of routes between these alternative vehicles and conventional ones.
|
25 |
[pt] PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM MOTORISTAS OCASIONAIS PARA ENTREGAS DE LAST-MILE: UMA ABORDAGEM META-HEURÍSTICA / [en] VEHICLE ROUTING PROBLEM WITH OCCASIONAL DRIVERS FOR E-COMMERCE LAST-MILE DELIVERY: A METAHEURISTIC APPROACHMATHEUS OLIVEIRA MEIRIM 25 September 2023 (has links)
[pt] Nos últimos anos o comércio eletrônico tem se difundido na sociedade e a logística de entrega dos produtos é um dos pilares para que este mercado mantenha o nível de serviço alto e continue sendo vantajoso para o consumidor decidir por realizar a compra pela internet. O presente trabalho se destina a estudar sobre o problema de roteamento de veículos de entrega last-mile para e-commerce e aplicar a metaheurística Iterated Local Search (ILS) visando otimizar o roteamento do trecho last-mile de encomendas realizadas em uma empresa de comércio eletrônico brasileira. Com o objetivo de encontrar rotas de menor custo para as entregas a serem realizadas, este trabalho propõe uma extensão para o Vehcile Routing Problem With Occasional Drivers (VRPOD),considerando frota heterogênea e motoristas ocasionais realizando o transporte de mais de uma entrega. Para a aplicação do método foram utilizados dados fornecidos por uma empresa de e-commerce que foram devidamente anonimizados de forma a não ser possível identificar a empresa e nem os clientes, respeitando os princípios éticos. Foram utilizadas 121 instâncias, sendo a menor com um vértice e a maior com 344. Os resultados do modelo proposto são apresentados em dois cenários, primeiramente considerando que o roteamento é realizado sem a utilização de motoristas ocasionais. O segundo cenário considera a disponibilização de motoristas ocasionais para serem utilizados em algumas rotas. Ambos os cenários foram comparados com as rotas geradas pelo roteador existente hoje na companhia e os resultados preliminares indicam que o sem a utilização de motoristas ocasionais o ILS proposto obtém melhores soluções em 53.72 por cento das instâncias e quando os motoristas ocasionais são incorporados a rota ocorre melhoria em 76.03 por cento das instâncias utilizadas. A utilização de motoristas ocasionais também proporciona uma redução de 10.30 por cento no custo médio de roteamento. / [en] In recent years, e-commerce has become widespread in society, and the
logistics of product delivery is a crucial pillar for this market to maintain
a high level of service and remain advantageous for consumers choosing to
make purchases online. The present work aims to study the problem of last-mile vehicle routing for e-commerce deliveries and apply an Iterated Local
Search (ILS) metaheuristic to optimize the routing of parcels in a Brazilian e-commerce company. With the objective of finding routes with the lowest cost
for the deliveries, this study proposes an extension to the Vehicle Routing
Problem with Occasional Drivers (VRPOD), considering a heterogeneous
fleet and occasional drivers handling multiple deliveries. For the methodology
application, data provided by an e-commerce company are used, and they
are properly anonymized to prevent the identification of the company and
its clients, respecting ethical principles. A total of 121 instances are used,
ranging from the smallest with one vertex to the largest with 344. The results of
the proposed model are presented in two scenarios: firstly, considering routing
without the use of occasional drivers, and secondly, considering the availability
of occasional drivers for some routes. Both scenarios are compared with the
routes generated by the current router used in the company, and preliminary
results indicate that without the use of occasional drivers, the proposed ILS
obtains better solutions in 53.72 percent of the instances, and when occasional drivers
are incorporated into the route, improvements occur in 76.03 percent of the instances.
The utilization of occasional drivers also provides a 10.30 percent reduction in the
average routing cost.
|
Page generated in 0.0254 seconds