[en] DISTRICTING AND VEHICLE ROUTING: LEARNING THE DELIVERY COSTS

[pt] DISTRICTING E ROTEAMENTO DE VEÍCULOS: APRENDENDO A ESTIMAR CUSTOS DE ENTREGA

[pt] ARTHUR MONTEIRO FERRAZ

[pt] METAHEURISTICAS

[pt] APRENDIZADO EM GRAFOS

[pt] APRENDIZADO PROFUNDO

[pt] ROTEAMENTO DE VEICULOS

[en] METAHEURISTICS

[en] GRAPH NEURAL NETWORKS

[en] DEEP LEARNING

[en] VEHICLE ROUTING

[pt] O problema de Districting-and-routing é um problema estratégico no qual porções geográficas devem ser agregadas em regiões de entrega, e cada região de entrega possui um custo de roteamento estimado. Seu objetivo é de minimizar esses custos, além de garantir a divisão da região em distritos. A simulação para obter uma boa aproximação é muito custosa computacionalmente, enquanto mecanismos como buscas locais exigem que esse cálculo seja feito de forma muito eficiente, tornando essa estratégia de aproximação inviável para uma solução metaheurística. Grande parte das soluções existentes para esse problema utilizam de formulas de aproximação contínua para mensurar os custos de roteamento, funções essas que são rápidas de serem calculadas porém cometem erros significativos. Em contraste, propomos uma Rede Neural em Grafo (Graph Neural Network - GNN) que é usada como oráculo por um algoritmo de otimização. Nossos experimentos computacionais executados com dados de cidades do Reino Unido mostram que a GNN é capaz de produzir previsões de custos mais precisas em tempo computacional aceitável. O uso desse estimator na busca local impacta positivamente a qualidade das soluções, levando a uma economia de 10,35 por cento no custo de entrega estimado em relação a função Beardwood, que é comumente usada nesse cenários, e ganhos similares em comparação com outros métodos de aproximação.

[en] The districting-and-routing problem is a strategic problem in which basic geographical units (e.g., zip codes) should be aggregated into delivery regions, and each delivery region is characterized by a routing cost estimated over an extended planning horizon. The objective is to minimize the expected routing costs while ensuring regional separability through the definition of the districts. Repeatedly simulating routing costs on a set of scenarios while searching for good districts can be computationally intensive, so existing solution approaches for this problem rely on approximation functions. In contrast, we propose to rely on a graph neural network (GNN) trained on a set of demand scenarios, which is then used within an optimization approach to infer routing costs while solving the districting problem. Our computational experiments on various metropolitan areas show that the GNN produces accurate cost predictions. Moreover, using this better estimator during the search positively impacts the quality of the districting solutions and leads to 10.35 percent delivery-cost savings over the commonly-used Beardwood estimator and similar gains compared to other approximation methods.

THIBAUT VICTOR GASTON VIDAL

QUENTIN CAPPART

MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO

THIBAUT VICTOR GASTON VIDAL

QUENTIN CAPPART

ALBERTO MARIA SANTINI

2023-01-12

2022-09-19

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=61766@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=61766@2

https://doi.org/10.17771/PUCRio.acad.61766