Deep Learning for Data-Driven Districting-and-Routing Article Swipe

PDF

ARTHUR MONTEIRO FERRAZ , Quentin Cappart , Thibaut Vidal ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2402.06040

Districting-and-routing is a strategic problem aiming to aggregate basic geographical units (e.g., zip codes) into delivery districts. Its goal is to minimize the expected long-term routing cost of performing deliveries in each district separately. Solving this stochastic problem poses critical challenges since repeatedly evaluating routing costs on a set of scenarios while searching for optimal districts takes considerable time. Consequently, solution approaches usually replace the true cost estimation with continuous cost approximation formulas extending Beardwood-Halton-Hammersley and Daganzo's work. These formulas commit errors that can be magnified during the optimization step. To reconcile speed and solution quality, we introduce a supervised learning and optimization methodology leveraging a graph neural network for delivery-cost estimation. This network is trained to imitate known costs generated on a limited subset of training districts. It is used within an iterated local search procedure to produce high-quality districting plans. Our computational experiments, conducted on five metropolitan areas in the United Kingdom, demonstrate that the graph neural network predicts long-term district cost operations more accurately, and that optimizing over this oracle permits large economic gains (10.12% on average) over baseline methods that use continuous approximation formulas or shallow neural networks. Finally, we observe that having compact districts alone does not guarantee high-quality solutions and that other learnable geometrical features of the districts play an essential role.

Related Topics

Computer Science

Artificial Intelligence

Machine Learning

Data Science

Concepts

Computer science Routing (electronic design automation) Artificial intelligence Machine learning Data science Computer network

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2402.06040
PDF: https://arxiv.org/pdf/2402.06040
OA Status: green
Cited By: 2
Related Works: 10
OpenAlex ID: https://openalex.org/W4391766394

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4391766394

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2402.06040

Digital Object Identifier
Title: Deep Learning for Data-Driven Districting-and-Routing

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-02-08

Full publication date if available
Authors: ARTHUR MONTEIRO FERRAZ, Quentin Cappart, Thibaut Vidal

List of authors in order
Landing page: https://arxiv.org/abs/2402.06040

Publisher landing page
PDF URL: https://arxiv.org/pdf/2402.06040

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2402.06040

Direct OA link when available
Concepts: Computer science, Routing (electronic design automation), Artificial intelligence, Machine learning, Data science, Computer network

Top concepts (fields/topics) attached by OpenAlex
Cited by: 2

Total citation count in OpenAlex
Citations by year (recent): 2025: 1, 2024: 1

Per-year citation counts (last 5 years)
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4391766394
doi	https://doi.org/10.48550/arxiv.2402.06040
ids.doi	https://doi.org/10.48550/arxiv.2402.06040
ids.openalex	https://openalex.org/W4391766394
fwci
type	preprint
title	Deep Learning for Data-Driven Districting-and-Routing
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11598
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9718000292778015
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Internet Traffic Analysis and Secure E-voting
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.5773838758468628
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C74172769
concepts[1].level	2
concepts[1].score	0.5349932909011841
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1446839
concepts[1].display_name	Routing (electronic design automation)
concepts[2].id	https://openalex.org/C154945302
concepts[2].level	1
concepts[2].score	0.44777345657348633
concepts[2].wikidata	https://www.wikidata.org/wiki/Q11660
concepts[2].display_name	Artificial intelligence
concepts[3].id	https://openalex.org/C119857082
concepts[3].level	1
concepts[3].score	0.36806604266166687
concepts[3].wikidata	https://www.wikidata.org/wiki/Q2539
concepts[3].display_name	Machine learning
concepts[4].id	https://openalex.org/C2522767166
concepts[4].level	1
concepts[4].score	0.3372837007045746
concepts[4].wikidata	https://www.wikidata.org/wiki/Q2374463
concepts[4].display_name	Data science
concepts[5].id	https://openalex.org/C31258907
concepts[5].level	1
concepts[5].score	0.25398388504981995
concepts[5].wikidata	https://www.wikidata.org/wiki/Q1301371
concepts[5].display_name	Computer network
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.5773838758468628
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/routing
keywords[1].score	0.5349932909011841
keywords[1].display_name	Routing (electronic design automation)
keywords[2].id	https://openalex.org/keywords/artificial-intelligence
keywords[2].score	0.44777345657348633
keywords[2].display_name	Artificial intelligence
keywords[3].id	https://openalex.org/keywords/machine-learning
keywords[3].score	0.36806604266166687
keywords[3].display_name	Machine learning
keywords[4].id	https://openalex.org/keywords/data-science
keywords[4].score	0.3372837007045746
keywords[4].display_name	Data science
keywords[5].id	https://openalex.org/keywords/computer-network
keywords[5].score	0.25398388504981995
keywords[5].display_name	Computer network
language	en
locations[0].id	pmh:oai:arXiv.org:2402.06040
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2402.06040
locations[0].version	submittedVersion
locations[0].raw_type
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2402.06040
locations[1].id	doi:10.48550/arxiv.2402.06040
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2402.06040
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5027305288
authorships[0].author.orcid
authorships[0].author.display_name	ARTHUR MONTEIRO FERRAZ
authorships[0].author_position	first
authorships[0].raw_author_name	Ferraz, Arthur
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5065781444
authorships[1].author.orcid	https://orcid.org/0000-0002-8742-0774
authorships[1].author.display_name	Quentin Cappart
authorships[1].author_position	middle
authorships[1].raw_author_name	Cappart, Quentin
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5009386864
authorships[2].author.orcid	https://orcid.org/0000-0001-5183-8485
authorships[2].author.display_name	Thibaut Vidal
authorships[2].author_position	last
authorships[2].raw_author_name	Vidal, Thibaut
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2402.06040
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Deep Learning for Data-Driven Districting-and-Routing
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11598
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9718000292778015
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Internet Traffic Analysis and Secure E-voting
related_works	https://openalex.org/W2961085424, https://openalex.org/W4306674287, https://openalex.org/W3046775127, https://openalex.org/W3107602296, https://openalex.org/W3170094116, https://openalex.org/W4386462264, https://openalex.org/W3209574120, https://openalex.org/W4364306694, https://openalex.org/W4312192474, https://openalex.org/W4283697347
cited_by_count	2
counts_by_year[0].year	2025
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2024
counts_by_year[1].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2402.06040
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2402.06040
best_oa_location.version	submittedVersion
best_oa_location.raw_type
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2402.06040
primary_location.id	pmh:oai:arXiv.org:2402.06040
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2402.06040
primary_location.version	submittedVersion
primary_location.raw_type
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2402.06040
publication_date	2024-02-08
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	2, 47, 98, 105, 122
abstract_inverted_index.It	128
abstract_inverted_index.To	90
abstract_inverted_index.an	132, 215
abstract_inverted_index.be	84
abstract_inverted_index.in	30, 150
abstract_inverted_index.is	1, 19, 114, 129
abstract_inverted_index.of	27, 49, 125, 211
abstract_inverted_index.on	46, 121, 146, 178
abstract_inverted_index.or	188
abstract_inverted_index.to	6, 20, 116, 137
abstract_inverted_index.we	96, 193
abstract_inverted_index.Its	17
abstract_inverted_index.Our	142
abstract_inverted_index.and	75, 93, 101, 167, 205
abstract_inverted_index.can	83
abstract_inverted_index.for	53, 109
abstract_inverted_index.not	201
abstract_inverted_index.set	48
abstract_inverted_index.the	22, 64, 87, 151, 156, 212
abstract_inverted_index.use	184
abstract_inverted_index.zip	12
abstract_inverted_index.This	112
abstract_inverted_index.cost	26, 66, 70, 163
abstract_inverted_index.does	200
abstract_inverted_index.each	31
abstract_inverted_index.five	147
abstract_inverted_index.goal	18
abstract_inverted_index.into	14
abstract_inverted_index.more	165
abstract_inverted_index.over	170, 180
abstract_inverted_index.play	214
abstract_inverted_index.that	82, 155, 168, 183, 195, 206
abstract_inverted_index.this	35, 171
abstract_inverted_index.true	65
abstract_inverted_index.used	130
abstract_inverted_index.with	68
abstract_inverted_index.These	78
abstract_inverted_index.alone	199
abstract_inverted_index.areas	149
abstract_inverted_index.basic	8
abstract_inverted_index.costs	45, 119
abstract_inverted_index.gains	176
abstract_inverted_index.graph	106, 157
abstract_inverted_index.known	118
abstract_inverted_index.large	174
abstract_inverted_index.local	134
abstract_inverted_index.other	207
abstract_inverted_index.poses	38
abstract_inverted_index.role.	217
abstract_inverted_index.since	41
abstract_inverted_index.speed	92
abstract_inverted_index.step.	89
abstract_inverted_index.takes	56
abstract_inverted_index.time.	58
abstract_inverted_index.units	10
abstract_inverted_index.while	51
abstract_inverted_index.work.	77
abstract_inverted_index.(e.g.,	11
abstract_inverted_index.United	152
abstract_inverted_index.aiming	5
abstract_inverted_index.codes)	13
abstract_inverted_index.commit	80
abstract_inverted_index.during	86
abstract_inverted_index.errors	81
abstract_inverted_index.having	196
abstract_inverted_index.neural	107, 158, 190
abstract_inverted_index.oracle	172
abstract_inverted_index.plans.	141
abstract_inverted_index.search	135
abstract_inverted_index.subset	124
abstract_inverted_index.within	131
abstract_inverted_index.(10.12%	177
abstract_inverted_index.Solving	34
abstract_inverted_index.compact	197
abstract_inverted_index.imitate	117
abstract_inverted_index.limited	123
abstract_inverted_index.methods	182
abstract_inverted_index.network	108, 113, 159
abstract_inverted_index.observe	194
abstract_inverted_index.optimal	54
abstract_inverted_index.permits	173
abstract_inverted_index.problem	4, 37
abstract_inverted_index.produce	138
abstract_inverted_index.replace	63
abstract_inverted_index.routing	25, 44
abstract_inverted_index.shallow	189
abstract_inverted_index.trained	115
abstract_inverted_index.usually	62
abstract_inverted_index.Finally,	192
abstract_inverted_index.Kingdom,	153
abstract_inverted_index.average)	179
abstract_inverted_index.baseline	181
abstract_inverted_index.critical	39
abstract_inverted_index.delivery	15
abstract_inverted_index.district	32, 162
abstract_inverted_index.economic	175
abstract_inverted_index.expected	23
abstract_inverted_index.features	210
abstract_inverted_index.formulas	72, 79, 187
abstract_inverted_index.iterated	133
abstract_inverted_index.learning	100
abstract_inverted_index.minimize	21
abstract_inverted_index.predicts	160
abstract_inverted_index.quality,	95
abstract_inverted_index.solution	60, 94
abstract_inverted_index.training	126
abstract_inverted_index.Daganzo's	76
abstract_inverted_index.aggregate	7
abstract_inverted_index.conducted	145
abstract_inverted_index.districts	55, 198, 213
abstract_inverted_index.essential	216
abstract_inverted_index.extending	73
abstract_inverted_index.generated	120
abstract_inverted_index.guarantee	202
abstract_inverted_index.introduce	97
abstract_inverted_index.learnable	208
abstract_inverted_index.long-term	24, 161
abstract_inverted_index.magnified	85
abstract_inverted_index.networks.	191
abstract_inverted_index.procedure	136
abstract_inverted_index.reconcile	91
abstract_inverted_index.scenarios	50
abstract_inverted_index.searching	52
abstract_inverted_index.solutions	204
abstract_inverted_index.strategic	3
abstract_inverted_index.approaches	61
abstract_inverted_index.challenges	40
abstract_inverted_index.continuous	69, 185
abstract_inverted_index.deliveries	29
abstract_inverted_index.districts.	16, 127
abstract_inverted_index.estimation	67
abstract_inverted_index.evaluating	43
abstract_inverted_index.leveraging	104
abstract_inverted_index.operations	164
abstract_inverted_index.optimizing	169
abstract_inverted_index.performing	28
abstract_inverted_index.repeatedly	42
abstract_inverted_index.stochastic	36
abstract_inverted_index.supervised	99
abstract_inverted_index.accurately,	166
abstract_inverted_index.demonstrate	154
abstract_inverted_index.districting	140
abstract_inverted_index.estimation.	111
abstract_inverted_index.geometrical	209
abstract_inverted_index.methodology	103
abstract_inverted_index.separately.	33
abstract_inverted_index.considerable	57
abstract_inverted_index.experiments,	144
abstract_inverted_index.geographical	9
abstract_inverted_index.high-quality	139, 203
abstract_inverted_index.metropolitan	148
abstract_inverted_index.optimization	88, 102
abstract_inverted_index.Consequently,	59
abstract_inverted_index.approximation	71, 186
abstract_inverted_index.computational	143
abstract_inverted_index.delivery-cost	110
abstract_inverted_index.Districting-and-routing	0
abstract_inverted_index.Beardwood-Halton-Hammersley	74
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile