UMA PROPOSTA MULTIOBJETIVO PARA O PROBLEMA DE ROTEAMENTO
DE VEÍCULOS CAPACITADOS ACUMULATIVO
Bruno Salezze Vieira
Universidade Federal do Rio de Janeiro
Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia – COPPE
Programa de Engenharia de Transportes – PET
RESUMO
O Problema de Roteamento de Veículos Capacitados Acumulativo, conhecido na literatura como Cumulative
Capacitated Vehicle Routing Problem é um problema difícil de ser resolvido, com muitas aplicações do mundo
real em transporte e logística de distribuição. Seu principal objetivo é encontrar o menor somatório dos tempos
de chegadas para entregar as mercadorias, utilizando uma frota de veículos idênticos com capacidade restrita,
para os clientes com demandas próprias. No entanto, existem outros objetivos, e tendo uma gama de soluções
que representam os conflitos entre objetivos é crucial para muitas aplicações. Embora pesquisas anteriores
tenham usado métodos heurísticos e exatos para resolver este problema, tem raramente concentrada na
otimização de mais de um objetivo, e quase nunca considerou explicitamente a diversidade de soluções. Este
artigo é um estudo do PRVCA e de problemas de roteamento multiobjetivo para a proposta de uma formulação
matemática para o problema em um caso multiobjetivo.
ABSTRACT
The Cumulative Capacitated Vehicle Routing Problem (CCVRP) is a difficult problem to be solved, with many
real-world applications in transportation and distribution logistics. Its main objective is to find the lowest sum of
arrivals from time to deliver the goods, using a fleet of identical vehicles with restricted capacity for customers
with their own demands. However, there are other objectives, and having a range of solutions that represent the
conflicts between goals is crucial for many applications. Although previous research has used heuristic and exact
methods to solve this problem, it rarely concentrated on optimizing more than one goal, and almost never
explicitly considered the diversity of solutions. This article is a study of CCVPR and multiobjective routing
problems for the proposal of a mathematical formulation of the problem in a multi-objective case.
1. INTRODUÇÃO
O Problema de Roteamento de Veículos (Vehicle Routing Problem (VRP)) é um dos
problemas de otimização combinatória mais importantes e amplamente estudado, com muitas
aplicações do mundo real em logística de distribuição e transporte (Toth e Vigo, 2001).
Seu objetivo é obter o conjunto de rotas de menor custo atendendo demanda dos clientes.
Desde que o problema foi proposto por Dantzig e Ramser (1959) como uma generalização do
problema do caixeiro viajante, o custo tem sido associado principalmente com a distância
percorrida. Entretanto existem vários outros tipos de custos envolvidos, tais como aqueles
associados aos veículos utilizados e à carga de trabalho das equipes (Jozefowiez et al., 2008).
O Problema de Roteamento de Veículos Capacitados Acumulativo (PRVCA) é uma variação
do clássico PVR em que o objetivo é a minimização da soma dos tempos de chegada aos
clientes, em vez da distância total percorrida. Também é uma extensão do Delivery Man
Problem (DMP) para o caso de vários veículos. Sendo assim, todos os métodos de solução
conhecidos do DMP se estendem naturalmente ao PRVCA.
O PRVCA ocorre em várias situações. É relevante em sistemas de distribuição em que é
desejável fornecer o serviço o mais cedo possível a todos os clientes. No roteamento de
ônibus escolar, por exemplo, minimizando o tempo médio de chegada em cada aluno é uma
medida mais justa que minimizar o tempo total percorrido pelo ônibus (Bowerman et al.,
1995). Além disso, quando as catástrofes naturais acontecem, é essencial que a ajuda chegue
rapidamente a cada vítima, a fim de salvar vidas e fornecer suprimentos de emergência, de
modo que o objetivo tradicional de minimização da distância percorrida não é adequado.
Várias medidas de desempenho podem ser utilizadas no processo de roteamento, sendo assim
minimizando o tempo de atendimento do último cliente ou o tempo médio de chegada aos
clientes estão entre os comumente utilizados. Quando se analisa tais objetivos conflitantes
simultaneamente, tal efeito foi investigado por Campbell et al. (2008).
Ao analisar a literatura, verificou-se que o PRVCA não foi abordado ainda de maneira
multiobjetivo que permita contemplar situações de objetivos conflitantes, como os citados
anteriormente de minimizar o custo da frota, ou distribuição da carga de trabalho.
Assim, este trabalho se propõe a estudar o PRVCA e problemas de roteamento multiobjetivo
afim de propor uma formulação multiobjetivo para o PRVCA com o intuito de contribuir com
pesquisas e desenvolvimento de métodos de solução que se aproximem mais de problemas do
mundo real.
O restante deste artigo está assim estruturado. A Seção 2 apresenta uma revisão bibliográfica
do PRVCA, mostrando os estudos mais recentes da área e de problemas relacionados. Na
Seção 3 é discutido problemas de roteamento multiobjetivos, os seus tipos de problemas, de
objetivos e os métodos de solução conhecidos. Na seção 4 é proposta a formulação
matemática do PRVCA multiobjetivo. Finalmente na Seção 5 são discutidas as conclusões
desta pesquisa.
2. REVISÃO BIBLIOGRÁFICA DO PRVCA
O PRVCA foi inicialmente proposto por Ngueveu et al. (2010). Os autores apresentaram o
problema, e então propuseram uma meta-heurísticas para solução. Um algoritmo memético
que consiste em cruzamentos populacionais de soluções, tomadores de decisão probabilísticos
e buscas locais para refino de solução.
Em seguida, foi estudado do ponto de vista heurístico primeiramente com uma metaheurística
Adaptive Large Neighborhood Search (Ribeiro and Laporte, 2012), onde todos os resultados
foram melhores ou iguais a Ngueveu et al. (2010). Em Ke e Feng (2013), o desempenho dos
três algoritmos foi comparado. Com base nessa comparação, a meta heurística de duas fases e
a Adaptive Large Neighborhood Search, cada uma forneceu as melhores soluções conhecidas
para cerca de metade dos casos de teste famosos na literatura.
E finalmente, Vidal et al. (2014) apresentaram algoritmo genético híbrido unificado para
problemas de roteamento de veículos em geral. Esta meta-heurística foi chamada de Unified
Hybrid Genetic Search (UHGS). Testado em 29 problemas variantes de roteamento de
veículos e 42 conjuntos de instâncias bem conhecidas na literatura, totalizando 1099
experimentos computacionais. Em 1045 dos 1099 casos testados, foram encontradas ou
melhoradas as melhores soluções conhecidas até então. Nas 7 instâncias do PRVCA testadas,
o UHGS igualou os 6 melhores resultados encontrados por Ke e Feng (2013) e melhoraram o
último, possuindo atualmente os melhores resultados do estado da arte de quase todos os
problemas de roteamento atuais.
Do ponto de vista exato, foi estudado por Lysgaard e Wøhlk (2014), que propuseram um
algoritmo baseado em branch-and-cut-and-price onde foram encontradas várias soluções
ótimas em problemas de até 150 clientes.
Kara et al. (2008) consideraram uma variação do PRVC, onde a função objetivo a ser
minimizada não é a soma dos tempos de chegada, mas sim a soma dos tempos de chegada
multiplicado pela demanda do nó. Eles mostraram que problema, é extensão da PRVCA,
denominado CumVRP e relacionam com outros problemas.
A versão não capacitada do PRVCA é conhecido como k-traveling repairman problem, onde
k é o número de veículos disponíveis. Para este problema, Fakcharoenphol et al. (2007)
apresentam um algoritmo 8.497-aproximativo, que é parcialmente baseado no resultado
devido a Chaudhuri et al. (2003). Jothi e Raghavachari (2007) estudaram uma extensão do
problema k-traveling repairman problem em que há um tempo de reparo, além do tempo de
viagem. Apresentam um algoritmo de ((3β+1)/2)-aproximação para este problema, onde β é o
fator de aproximação que pode ser obtido para o k-traveling repairman problem.
Um caso particular do PRVCA para um único veículo é chamado problema de latência
mínima (Minimum Latency Problem), que tem atraído muitos trabalhos. É bem estudado tanto
do com métodos exatos ou aproximativos. Várias abordagens exatas têm sido propostas para o
MLP, a maioria das quais são baseadas em programação dinâmica, branch-and-bound, ou
uma combinação dos dois (Wu et al., 2004). O melhor algoritmo de aproximação atual para o
MLP é devido a Chaudhuri et al. (2003) e alcança um fator de aproximativo de 3,59.
3. PROBLEMAS DE ROTEAMENTO DE VEÍCULOS MULTIOBJETIVO
Problemas de roteamento, como o problema de roteamento de veículos e o problema do
caixeiro viajante, são amplamente estudados tanto por causa de seu apelo acadêmico clássico
e quanto por suas inúmeras aplicações na vida real. Da mesma forma, o campo da otimização
multiobjetivo está atraindo mais e mais atenção, pois oferece novas oportunidades para a
definição de problemas. Um problema de roteamento pode ser definido em termos dos
seguintes componentes: rede, pedido, frota, custo e objetivo, tais elementos serão detalhados a
seguir (Jozefowiez et al., 2008):
 Rede pode ser simétrica, assimétrica ou mista. Ela é representada como um grafo no
qual os nós representam cidades, clientes e/ou depósitos, enquanto arcos representam
as ligações de estradas, ferrovias, túneis ou conexões simbólicas. Em grafos com
pesos, o valor de cada arco representa geralmente o custo de o atravessar. Janelas de




tempo associadas com os nós ou arcos também pode ser definida em alguns
problemas. Uma janela de tempo indica um intervalo de tempo no qual, por exemplo,
um cliente deve ser atendido.
Pedidos podem ser fixos ou estocásticos, representam demandas associadas a nós ou
arcos, e podem ser de um ou mais produtos. Geralmente, aparecem em problemas de
distribuição, em que uma certa quantidade de um dado produto deve ser entregue a
clientes ou precisam se deslocar ao longo de um determinado arco. Existem também
problemas de coleta e entrega, os quais requisitam que um produto deve primeiro ser
coletado em um local e, em seguida, ser entregue em outro lugar. Um problema
associado a demanda de arcos é uma rede de coleta de lixo, todo o caminhão da
empresa de coleta tem que passar em todas as ruas (arcos) desejadas.
Frota gera restrições que afetam as rotas. Uma frota pode ser heterogênea ou
homogênea. Ela pode ser composta por um único veículo ou vários veículos, cuja
utilização pode, ou não, ser limitada pela capacidade, o tempo ou a distância. Além
disso, pode haver relações entre veículos, produtos e clientes.
Custos são normalmente fixos ou variáveis para os veículos. Leva-se em conta custo
fixo de utilização e outro, variável que depende de sua utilização, em termos de
distância percorrida ou de tempo utilizados. Os custos também podem incluir as
penalidades de serviços efetuados quando um cliente recebe uma entrega tardia ou
incompleta.
Objetivos podem ser múltiplos e diversos. Os objetivos mais comuns incluem
minimizar a distância total percorrida, o tempo total necessário, o custo total da
viagem, e/ou o tamanho da frota, e maximizar a qualidade do serviço e/ou o lucro
obtido. No entanto, quando múltiplos objetivos são identificados, frequentemente eles
são conflitantes.
Com isso, um problema multiobjetivo (PMO) pode ser definido como:
Onde:
n ≥ 2 é o número de funções objetivo;
, é a variável vetor de decisão; D é o
espaço de soluções viável; e F(x), o vetor objetivo. O conjunto S = F(D) corresponde às
soluções viáveis no espaço do objetivo, e
, em que
, é uma solução
do espaço objetivo. A solução para um problema multiobjetivo (PMO) é na verdade um
conjunto de soluções não-dominadas chamado conjunto de Pareto (PS), onde o domínio é
definido como:
Definição: A solução
domina a solução
.
se e somente se
Uma solução y encontrada por um algoritmo A é dito ser potencialmente Pareto ótima
(potentially Pareto optimal), em relação a A, se A não consegue encontrar uma solução z, tal
que z domine y. No entanto, a dominância de Pareto não estabelece uma ordem completa das
soluções de um problema.
Há três abordagens para resolver um problema multiobjetivo: abordagens prioritárias,
abordagens entre atividades, e posteriores. Em abordagens prioritárias, um tomador de
decisão utiliza preferências para os diferentes objetivos. Em abordagens interativas, as
escolhas do tomador de decisão são feitas durante o processo de resolução do problema. Em
abordagens a posterior, um conjunto de soluções potencialmente não dominadas é gerado em
primeiro lugar, e, em seguida, o tomador de decisão escolhe entre essas soluções.
Problemas multiobjetivo de roteamento são usados principalmente de três formas: para
estender problemas acadêmicos clássicos, a fim de melhorar a sua aplicação prática (sem
nunca perder de vista o objetivo inicial), especificar problemas clássicos, e estudar os casos da
vida real em que os objetivos foram claramente identificados pelo tomador de decisão e são
dedicados a um problema da vida real ou aplicação específica. Este trabalho se encaixa na
categoria de extensão de um problema acadêmico clássico, a fim de melhorar a sua aplicação
prática.
3.1. Objetivos recorrentes na literatura
Nesta seção, os diferentes objetivos estudados na literatura são apresentados e classificados de
acordo com a componente do problema com a qual eles estão associados.
3.1.1. Custo
Minimizar o custo das soluções geradas é o objetivo mais comum. O custo pode ser expresso
de várias formas, tais como distância percorrida, tempo total necessário, ou o número de
clientes visitados. De modo geral, redução do custo está ligado a um critério econômico. No
problema multiobjetivo do caixeiro viajante, os diferentes objetivos correspondem aos
diferentes custos de arco. No entanto, são possíveis outros motivos. Por exemplo, em estudos
de Park e Koelling (1986), a distância percorrida deve ser minimizada para evitar danificar o
produto sendo transportado.
3.1.2. Espalhamento
Apesar da minimização do custo ser o objetivo mais comum, este objetivo é, por vezes,
ignorado, como é o caso dos estudos de Corberán et al. (2002) e Pacheco e Martí (2006).
Estes autores escolheram minimizar o espalhamento (isto é, minimizar o comprimento do
passeio mais longo). Esta escolha foi motivada pelo ambiente, uma área rural na Espanha,
onde, devido às grandes distâncias entre postos locais, as rotas de ônibus tendem a ser longas
e o ônibus é totalmente preenchido enche. Minimizar o espalhamento garante alguma
qualidade em termos de tempo gasto no ônibus pelo primeiro aluno que pegou em
comparação com o tempo gasto pelo último aluno.
3.1.3. Equilíbrio
Alguns objetivos são projetados para nivelar as disparidades entre as rotas. Tais objetivos são
frequentemente introduzidos a fim de trazer um elemento de igualdade. Para definir um
objetivo de equilíbrio, é necessário definir um volume de trabalho da rota, o que pode ser
expressa como o número de clientes visitado, a quantidade dos produtos entregues, o tempo
necessário ou o comprimento da rota, por exemplo.
3.1.4. Relacionados a nós ou arcos
A maioria dos estudos que tratam de objetivo relacionados com nó ou arcos envolvem janelas
de tempo (Hong e Park, 1999). Nesses estudos, as janelas de tempo são substituídas por um
objetivo que minimiza tanto o número de restrições violadas (Rahoual e Djoukhdjoukh,
2003), o total de clientes e/ou tempo de espera do motorista devido ao atraso (Hong e Park,
1999), ou ambos objetivos ao mesmo tempo (Geiger, 2008).
3.1.5. Relacionados a recursos
Os principais recursos encontrados na literatura são veículos e bens. Um objetivo que muitas
vezes aparece é a minimização do número de veículos, o que pode ser interpretado em termos
econômicos, na medida em que um menor número de veículos utilizados significa menor
investimento monetário (por exemplo, para a compra de veículos, combustível e salários dos
motoristas) (Corberán et al., 2002; Tan et al., 2006).
Outros objetivos relativos ao veículo podem ser usados para maximizar o custo-benefício do
veículo em termos de tempo ou capacidade, ao passo que os objetivos relativos às
mercadorias podem ser introduzidos para atender a natureza dos bens em conta. Por exemplo,
o fato da mercadoria ser perecível pode ser levado em consideração com o objetivo de evitar
sua deterioração (Jozefowiez et al., 2008).
3.2. Algoritmos de Otimização Multiobjectivo
Ao longo dos anos, várias técnicas têm sido propostas para resolver problemas multiobjetivos.
Estas estratégias podem ser divididas em três categorias gerais: métodos escalares, métodos
de Pareto, e todos os outros (técnicas não escalares e algoritmos não Pareto). Métodos
escalares utilizam transformações matemáticas, como agregação linear ponderada. Métodos
de Pareto, que se aplicam a noção de posição dominante Pareto para avaliara qualidade de
uma solução ou para comparar soluções, são usados principalmente com algoritmos
evolutivos e estão se tornando mais e mais populares (Coello et al., 2002). Métodos de Pareto
inclui as técnicas que levam em consideração os diferentes objetivos separadamente.
3.2.1. Técnicas escalares
O método de escalar mais popular é, como mencionado acima, a agregação linear ponderada,
que realiza o produto interno de um vetor de pesos de mesma dimensão do vetor de funções
objetivos. No entanto, este método possui alguns inconvenientes. Em primeiro lugar, os pesos
devem ser ajustados de acordo com a importância dos objetivos, o que pode ser uma tarefa
difícil. Além disso, este método não é capaz de encontrar todas as soluções Pareto Ótima, ou
seja, ele só encontra as soluções no casco convexo do conjunto Pareto Ótimo, que depende de
várias execuções com pesos diferentes (Geoffrion, 1968).
Ainda assim, esta técnica é relativamente simples de implementar e pode ser usado com
qualquer das heurísticas de um único objetivo ou meta-heurísticas descritas na literatura para
o mesmo problema em questão.
3.2.2. Métodos de Pareto
Métodos de Pareto abordam a noção de posição dominante Pareto diretamente. Esta
abordagem foi introduzida principalmente por Golberg (1989) para algoritmos evolucionários.
Embora tais permita que um objetivo a ser favorecido em detrimento de outro, pode ser uma
ajuda útil para os tomadores de decisão. Em problemas multiobjetivos de roteamento de
veículos, o conceito de Pareto é frequentemente utilizado num quadro evolutivo. Segundo
Jozefowiez et al. (2008), mais de 20 publicações usaram algoritmos evolutivos com métodos
de Pareto para resolver problemas de roteamento multiobjetivos. Dentre eles, 11 propuseram
híbridos baseados em algoritmos evolutivos e pesquisas locais, heurística, e/ou métodos
exatos para o problema considerado.
3.2.3. Não escalares e algoritmos não-Pareto
Alguns estudos empregam nem escalar, nem métodos de Pareto para resolver problemas
multiobjetivos de roteamento. Neste caso, estes métodos não-escalares e não-Pareto são
baseados em algoritmos genéticos, estratégias lexicográficas, mecanismos de colônias de
formigas, ou heurísticas específicas. Um estudo mais detalhado destes métodos foi realizado
em Jozefowiez et al. (2008).
4. MODELO MATEMÁTICO
O PRVCA é definido como um grafo não direcionado G = (V,E) onde V = {0,1...,n,n+1} é
um conjunto de vértices, com os vértices 0 e n+1 sendo o depósito, e
éo
conjunto dos clientes. O conjunto
é o conjunto de arestas. O tempo de
viagem cij está associado a cada aresta (i,j) ∈ E. Assume-se que os tempos deviagem são
simétricos e satisfazem a desigualdade triangular. Cada cliente i ∈ V’ possui uma demanda qi
e considere R sendo o conjunto de veículos com capacidade idêntica Q. Seja o tempo de
chegada do veículo k no cliente i e seja
uma variável binária que assume o valor 1 caso o
veículo k visita o cliente j logo após ao cliente i sendo que a aresta
recebe 0
caso contrário. O PRVCA consiste em encontrar um conjunto de rotas tal que todo veículo
inicie sua rota no depósito (0) e, após atender um conjunto de clientes, retorne ao ponto inicial
(n+1), não excedendo a capacidade Q de cada veículo.
O objetivo clássico do PRVCA é a minimização da soma dos tempos de chegada, que pode
ser escrita como
. Neste artigo propõe-se incorporar um segundo objetivo que está
associado ao custo de utilização da frota, pois existe um custo de um veículo ser empregado
ck. Seja ck o custo de utilizar o veículo k ∈ R em alguma rota. Sendo assim, o custo de
utilização da frota por ser representado por:
Então, a formulação proposta para o PRVCA para o objetivo clássico e o objetivo 1 neste
artigo é:
Sujeito a:
As restrições 4 são conhecidas como restrições de conservação de fluxo. As restrições 5
garantem que cada cliente seja atendido por um único veículo. As restrições 6 determinam
que a demanda total coletada por cada veículo k não exceda a capacidade Q do mesmo. As
restrições 7 e 8 induzem que cada rota comece saindo do depósito e termine retornando ao
mesmo. As restrições 9 garantem que para todo cliente j atendido após o cliente i pelo veículo
k, então deve ser maior ou igual a , somado do tempo de viajem cij, e M é uma constante
maior que qualquer + cij . As restrições 10 impõe não negatividade do tempo de
atendimento para cada cliente e veículo. Finalmente, a equação 11 determina as variáveis de
decisão
como binárias.
Entretanto, como discutido na subsecção 3.2.1, não existem muitos métodos que abordam
problemas multiobjetivo como são. Então, para se aplicar os métodos de solução conhecidos
como heurísticas, meta-heurísticas, ou algoritmos exatos já desenvolvidos para o PRVCA é
necessária a aplicação de uma técnica escalar. O método mais comum para representação de
uma função de múltiplos objetivos como uma de único objetivo é a atribuição de pesos γi para
cada i objetivo. Em outras palavras, a representação mono objetiva desta função biobjetiva é
dada pelo produto interno de um vetor de pesos Γ=(γ1 ,γ2), que pode ser escrita como Γ·(z1 ,z2)
=
. Finalmente, pode-se representar a formulação proposta do
PRVCA para este caso biobjetivo, utilizando uma técnica escalar como:
Sujeito a:
(4) − (11)
5. CONCLUSÕES
O Problema de Roteamento de Veículos Capacitados Acumulativo, é um problema difícil de
ser resolvido, com muitas aplicações do mundo real em transporte e logística de distribuição.
Seu principal objetivo é encontrar o menor conjunto de distância de rotas para entregar as
mercadorias, utilizando uma frota de veículos idênticos com capacidade restrita, para os
clientes com janelas de tempo de serviço. No entanto, existem outros objetivos, e tendo uma
gama de soluções que representam os conflitos entre objetivos é crucial para muitas
aplicações.
Neste artigo, apresentamos o Problema de Roteamento de Veículos Capacitados Acumulativo
como foi proposto, as motivações para relevante contribuição desta pesquisa, os trabalhos
relacionados recentes. Também uma visão geral de múltiplos objetivos aplicados a problemas
de roteamento de veículos, seguido, finalmente, da formulação proposta.
Originalmente se pretendia testar a formulação proposta. Logo, em trabalhos futuros, se
deseja aplicar os métodos de solução eficientes para o PRVCA Multiobjetivo como foi
proposto neste trabalho. E também algoritmos evolucionários que gerem um espaço de
soluções Pareto-ótimo para efeito de comparação com a técnica escalar proposta até então.
Utilizando das instâncias mais conhecidas da literatura que são as mesmas de PRVC e PRV
clássicos, logo há uma grande base para comparação.
6. REFERÊNCIAS BIBLIOGRÁFICAS
Bowerman, R., Hall, B., e Calamai, P. (1995). A multi-objective optimization approach to
urban school bus routing: Formulation and solution method. Transportation Research Part A:
Policy and Practice, 29(2):107–123.
Campbell, A. M., Vandenbussche, D., e Hermann, W. (2008). Routing for relief efforts.
Transportation Science, 42(2):127–145.
Chaudhuri, K., Godfrey, B., Rao, S., e Talwar, K. (2003). Paths, trees, and minimum latency
tours. In Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE
Symposium on, pages 36–45. IEEE.
Coello, C. A. C., Van Veldhuizen, D. A., e Lamont, G. B. (2002). Evolutionary algorithms for
solving multi-objective problems, volume 242. Springer.
Corberán, A., Fernández, E., Laguna, M., Martí, R., et al. (2002). Heuristic solutions to the
problem of routing school buses with multiple objectives. Journal of the operational research
society, 53(4):427–435.
Dantzig, G. B. e Ramser, J. H. (1959). The truck dispatching problem. Management science,
6(1):80–91.
Fakcharoenphol, J., Harrelson, C., e Rao, S. (2007). The k-traveling repairmen problem. ACM
Transactions on Algorithms (TALG), 3(4):40.
Geiger, M. J. (2008). Genetic algorithms for multiple objective vehicle routing. arXiv preprint
arXiv:0809.0416.
Geoffrion, A. M. (1968). Proper efficiency and the theory of vector maximization. Journal of
Mathematical Analysis and Applications, 22(3):618–630.
Golberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning.
Addion wesley, 1989.
Hong, S.-C. e Park, Y.-B. (1999). A heuristic for bi-objective vehicle routing with time
window constraints. International Journal of Production Economics, 62(3):249–258.
Jothi, R. e Raghavachari, B. (2007). Approximating the k-traveling repairman problem with
repairtimes. Journal of Discrete Algorithms, 5(2):293–303.
Jozefowiez, N., Semet, F., e Talbi, E.-G. (2008). Multi-objective vehicle routing problems.
European Journal of Operational Research, 189(2):293–309.
Kara, İ., Kara, B. Y., e Yetis, M. K. (2008). Cumulative vehicle routing problems. Vehicle
Routing Problem, pages 85–98.
Ke, L. e Feng, Z. (2013). A two-phase metaheuristic for the cumulative capacitated vehicle
routing problem. Computers & Operations Research, 40(2):633–638.
Lysgaard, J. e Wøhlk, S. (2014). A branch-and-cut-and-price algorithm for the cumulative
capacitated vehicle routing problem. European Journal of Operational Research, 236(3):800–
810.
Ngueveu, S. U., Prins, C., e Calvo, R. W. (2010). An effective memetic algorithm for the
cumulative capacitated vehicle routing problem. Computers & Operations Research,
37(11):1877–1885.
Pacheco, J. e Martí, R. (2006). Tabu search for a multi-objective routing problem. Journal of
the Operational Research Society, 57(1):29–37.
Park, Y. B. e Koelling, C. P. (1986). A solution of vehicle routing problems in a multiple
objective environment. Engineering Costs and Production Economics, 10(2):121–132.
Rahoual, M. e Djoukhdjoukh, W. (2003). Métaheuristique hybride pareto pour le probleme de
tournées de véhicules avec fenêtres horaires. In Evolution Artificielle, volume 2003, pages
380–395.
Ribeiro, G. M. e Laporte, G. (2012). An adaptive large neighborhood search heuristic for the
cumulative capacitated vehicle routing problem. Computers & Operations Research,
39(3):728–735.
Tan, K., Chew, Y., e Lee, L. (2006). A hybrid multiobjective evolutionary algorithm for
solving vehicle routing problem with time windows. Computational Optimization and
Applications, 34(1):115–151.
Toth, P. e Vigo, D. (2001). The vehicle routing problem. Society for Industrial and Applied
Mathematics.
Vidal, T., Crainic, T. G., Gendreau, M., e Prins, C. (2014). A unified solution framework for
multi-attribute vehicle routing problems. European Journal of Operational Research,
234(3):658–673.
Wu, B. Y., Huang, Z.-N., e Zhan, F.-J. (2004). Exact algorithms for the minimum latency
problem. Information Processing Letters, 92(6):303–309.