The flying sidekick traveling salesman problem with multiple drops: A simple and effective heuristic approach Article Swipe

PDF

Sarah K. Schaumann , Abhishake Kundu , Juan C. Pina-Pardo , Matthias Winkenbach , Ricardo A. Gatica , Stephan M. Wagner , Timothy I. Matis ·

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

We study the Flying Sidekick Traveling Salesman Problem with Multiple Drops (FSTSP-MD), a multi-modal last-mile delivery model where a single truck and a single drone cooperatively deliver customer packages. In the FSTSP-MD, the drone can be launched from the truck to deliver multiple packages before it returns to the truck for a new delivery operation. The objective is to find the synchronized truck and drone delivery routes that minimize the completion time of the delivery process. We develop a simple and effective heuristic to solve the FSTSP-MD based on an order-first, split-second scheme. The core component of our heuristic is a novel split algorithm that finds FSTSP-MD solutions in polynomial time for a given sequence of customers. We embed this split algorithm into a simple heuristic approach that combines standard local search and diversification techniques. The simplicity of our heuristic does not sacrifice performance: we show that it consistently outperforms state-of-the-art solution approaches developed for both the FSTSP-MD and the FSTSP (i.e., the single-drop case) through extensive numerical experiments. Based on both stylized and real-world instances, we also show that the FSTSP-MD substantially reduces completion times compared to traditional truck-only delivery systems. We provide extensive managerial insights into the impacts of drone capabilities and customer distribution on delivery efficiency. Our discussion compares the benefits of drones with greater payload capacity and those with greater speed. We highlight which service area characteristics increase savings but also require enhanced drone capabilities.

Related Topics

Travelling Salesman Problem

Concepts

Travelling salesman problem Heuristic Simple (philosophy) Mathematical optimization Computer science Traveling purchaser problem 2-opt Mathematics Epistemology Philosophy

Metadata

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

All OpenAlex metadata

Raw OpenAlex JSON

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

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

Digital Object Identifier
Title: The flying sidekick traveling salesman problem with multiple drops: A simple and effective heuristic approach

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-03-26

Full publication date if available
Authors: Sarah K. Schaumann, Abhishake Kundu, Juan C. Pina-Pardo, Matthias Winkenbach, Ricardo A. Gatica, Stephan M. Wagner, Timothy I. Matis

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

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

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/2403.18091

Direct OA link when available
Concepts: Travelling salesman problem, Heuristic, Simple (philosophy), Mathematical optimization, Computer science, Traveling purchaser problem, 2-opt, Mathematics, Epistemology, Philosophy

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

Total citation count in OpenAlex
Citations by year (recent): 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/W4393299865
doi	https://doi.org/10.48550/arxiv.2403.18091
ids.doi	https://doi.org/10.48550/arxiv.2403.18091
ids.openalex	https://openalex.org/W4393299865
fwci	0.0
type	preprint
title	The flying sidekick traveling salesman problem with multiple drops: A simple and effective heuristic approach
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10586
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9416999816894531
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1707
topics[0].subfield.display_name	Computer Vision and Pattern Recognition
topics[0].display_name	Robotic Path Planning Algorithms
topics[1].id	https://openalex.org/T10100
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9404000043869019
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1702
topics[1].subfield.display_name	Artificial Intelligence
topics[1].display_name	Metaheuristic Optimization Algorithms Research
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C175859090
concepts[0].level	2
concepts[0].score	0.8486326932907104
concepts[0].wikidata	https://www.wikidata.org/wiki/Q322212
concepts[0].display_name	Travelling salesman problem
concepts[1].id	https://openalex.org/C173801870
concepts[1].level	2
concepts[1].score	0.6986082196235657
concepts[1].wikidata	https://www.wikidata.org/wiki/Q201413
concepts[1].display_name	Heuristic
concepts[2].id	https://openalex.org/C2780586882
concepts[2].level	2
concepts[2].score	0.6203442811965942
concepts[2].wikidata	https://www.wikidata.org/wiki/Q7520643
concepts[2].display_name	Simple (philosophy)
concepts[3].id	https://openalex.org/C126255220
concepts[3].level	1
concepts[3].score	0.5032998919487
concepts[3].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[3].display_name	Mathematical optimization
concepts[4].id	https://openalex.org/C41008148
concepts[4].level	0
concepts[4].score	0.49133387207984924
concepts[4].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[4].display_name	Computer science
concepts[5].id	https://openalex.org/C4331618
concepts[5].level	4
concepts[5].score	0.4646095335483551
concepts[5].wikidata	https://www.wikidata.org/wiki/Q7836034
concepts[5].display_name	Traveling purchaser problem
concepts[6].id	https://openalex.org/C106472803
concepts[6].level	3
concepts[6].score	0.4095516800880432
concepts[6].wikidata	https://www.wikidata.org/wiki/Q291440
concepts[6].display_name	2-opt
concepts[7].id	https://openalex.org/C33923547
concepts[7].level	0
concepts[7].score	0.3095778822898865
concepts[7].wikidata	https://www.wikidata.org/wiki/Q395
concepts[7].display_name	Mathematics
concepts[8].id	https://openalex.org/C111472728
concepts[8].level	1
concepts[8].score	0.0
concepts[8].wikidata	https://www.wikidata.org/wiki/Q9471
concepts[8].display_name	Epistemology
concepts[9].id	https://openalex.org/C138885662
concepts[9].level	0
concepts[9].score	0.0
concepts[9].wikidata	https://www.wikidata.org/wiki/Q5891
concepts[9].display_name	Philosophy
keywords[0].id	https://openalex.org/keywords/travelling-salesman-problem
keywords[0].score	0.8486326932907104
keywords[0].display_name	Travelling salesman problem
keywords[1].id	https://openalex.org/keywords/heuristic
keywords[1].score	0.6986082196235657
keywords[1].display_name	Heuristic
keywords[2].id	https://openalex.org/keywords/simple
keywords[2].score	0.6203442811965942
keywords[2].display_name	Simple (philosophy)
keywords[3].id	https://openalex.org/keywords/mathematical-optimization
keywords[3].score	0.5032998919487
keywords[3].display_name	Mathematical optimization
keywords[4].id	https://openalex.org/keywords/computer-science
keywords[4].score	0.49133387207984924
keywords[4].display_name	Computer science
keywords[5].id	https://openalex.org/keywords/traveling-purchaser-problem
keywords[5].score	0.4646095335483551
keywords[5].display_name	Traveling purchaser problem
keywords[6].id	https://openalex.org/keywords/2-opt
keywords[6].score	0.4095516800880432
keywords[6].display_name	2-opt
keywords[7].id	https://openalex.org/keywords/mathematics
keywords[7].score	0.3095778822898865
keywords[7].display_name	Mathematics
language	en
locations[0].id	pmh:oai:arXiv.org:2403.18091
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/2403.18091
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/2403.18091
locations[1].id	doi:10.48550/arxiv.2403.18091
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	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
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.2403.18091
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5023200768
authorships[0].author.orcid	https://orcid.org/0000-0002-2595-1991
authorships[0].author.display_name	Sarah K. Schaumann
authorships[0].author_position	first
authorships[0].raw_author_name	Schaumann, Sarah K.
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5072283160
authorships[1].author.orcid	https://orcid.org/0000-0002-1086-481X
authorships[1].author.display_name	Abhishake Kundu
authorships[1].author_position	middle
authorships[1].raw_author_name	Kundu, Abhishake
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5062328206
authorships[2].author.orcid	https://orcid.org/0000-0001-9928-4434
authorships[2].author.display_name	Juan C. Pina-Pardo
authorships[2].author_position	middle
authorships[2].raw_author_name	Pina-Pardo, Juan C.
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5072799821
authorships[3].author.orcid	https://orcid.org/0000-0002-8237-625X
authorships[3].author.display_name	Matthias Winkenbach
authorships[3].author_position	middle
authorships[3].raw_author_name	Winkenbach, Matthias
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5001529384
authorships[4].author.orcid
authorships[4].author.display_name	Ricardo A. Gatica
authorships[4].author_position	middle
authorships[4].raw_author_name	Gatica, Ricardo A.
authorships[4].is_corresponding	False
authorships[5].author.id	https://openalex.org/A5068668597
authorships[5].author.orcid	https://orcid.org/0000-0003-0471-5663
authorships[5].author.display_name	Stephan M. Wagner
authorships[5].author_position	middle
authorships[5].raw_author_name	Wagner, Stephan M.
authorships[5].is_corresponding	False
authorships[6].author.id	https://openalex.org/A5046924389
authorships[6].author.orcid
authorships[6].author.display_name	Timothy I. Matis
authorships[6].author_position	last
authorships[6].raw_author_name	Matis, Timothy I.
authorships[6].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/2403.18091
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	The flying sidekick traveling salesman problem with multiple drops: A simple and effective heuristic approach
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10586
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9416999816894531
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1707
primary_topic.subfield.display_name	Computer Vision and Pattern Recognition
primary_topic.display_name	Robotic Path Planning Algorithms
related_works	https://openalex.org/W4389782626, https://openalex.org/W2359992618, https://openalex.org/W4376138746, https://openalex.org/W2362402143, https://openalex.org/W2361554335, https://openalex.org/W4220987199, https://openalex.org/W2308371765, https://openalex.org/W2171568915, https://openalex.org/W2265604726, https://openalex.org/W2170228269
cited_by_count	1
counts_by_year[0].year	2024
counts_by_year[0].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2403.18091
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/2403.18091
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/2403.18091
primary_location.id	pmh:oai:arXiv.org:2403.18091
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/2403.18091
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/2403.18091
publication_date	2024-03-26
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	12, 18, 22, 51, 78, 100, 112, 123
abstract_inverted_index.In	29
abstract_inverted_index.We	0, 76, 117, 192, 225
abstract_inverted_index.an	89
abstract_inverted_index.be	35
abstract_inverted_index.in	108
abstract_inverted_index.is	57, 99
abstract_inverted_index.it	45, 147
abstract_inverted_index.of	72, 96, 115, 137, 200, 214
abstract_inverted_index.on	88, 170, 206
abstract_inverted_index.to	40, 47, 58, 83, 187
abstract_inverted_index.we	144, 176
abstract_inverted_index.Our	209
abstract_inverted_index.The	55, 93, 135
abstract_inverted_index.and	21, 63, 80, 132, 158, 173, 203, 220
abstract_inverted_index.but	233
abstract_inverted_index.can	34
abstract_inverted_index.for	50, 111, 154
abstract_inverted_index.new	52
abstract_inverted_index.not	141
abstract_inverted_index.our	97, 138
abstract_inverted_index.the	2, 30, 32, 38, 48, 60, 69, 73, 85, 156, 159, 162, 180, 198, 212
abstract_inverted_index.also	177, 234
abstract_inverted_index.area	229
abstract_inverted_index.both	155, 171
abstract_inverted_index.core	94
abstract_inverted_index.does	140
abstract_inverted_index.find	59
abstract_inverted_index.from	37
abstract_inverted_index.into	122, 197
abstract_inverted_index.show	145, 178
abstract_inverted_index.that	67, 104, 127, 146, 179
abstract_inverted_index.this	119
abstract_inverted_index.time	71, 110
abstract_inverted_index.with	8, 216, 222
abstract_inverted_index.Based	169
abstract_inverted_index.Drops	10
abstract_inverted_index.FSTSP	160
abstract_inverted_index.based	87
abstract_inverted_index.case)	164
abstract_inverted_index.drone	24, 33, 64, 201, 237
abstract_inverted_index.embed	118
abstract_inverted_index.finds	105
abstract_inverted_index.given	113
abstract_inverted_index.local	130
abstract_inverted_index.model	16
abstract_inverted_index.novel	101
abstract_inverted_index.solve	84
abstract_inverted_index.split	102, 120
abstract_inverted_index.study	1
abstract_inverted_index.those	221
abstract_inverted_index.times	185
abstract_inverted_index.truck	20, 39, 49, 62
abstract_inverted_index.where	17
abstract_inverted_index.which	227
abstract_inverted_index.(i.e.,	161
abstract_inverted_index.Flying	3
abstract_inverted_index.before	44
abstract_inverted_index.drones	215
abstract_inverted_index.routes	66
abstract_inverted_index.search	131
abstract_inverted_index.simple	79, 124
abstract_inverted_index.single	19, 23
abstract_inverted_index.speed.	224
abstract_inverted_index.Problem	7
abstract_inverted_index.deliver	26, 41
abstract_inverted_index.develop	77
abstract_inverted_index.greater	217, 223
abstract_inverted_index.impacts	199
abstract_inverted_index.payload	218
abstract_inverted_index.provide	193
abstract_inverted_index.reduces	183
abstract_inverted_index.require	235
abstract_inverted_index.returns	46
abstract_inverted_index.savings	232
abstract_inverted_index.scheme.	92
abstract_inverted_index.service	228
abstract_inverted_index.through	165
abstract_inverted_index.FSTSP-MD	86, 106, 157, 181
abstract_inverted_index.Multiple	9
abstract_inverted_index.Salesman	6
abstract_inverted_index.Sidekick	4
abstract_inverted_index.approach	126
abstract_inverted_index.benefits	213
abstract_inverted_index.capacity	219
abstract_inverted_index.combines	128
abstract_inverted_index.compared	186
abstract_inverted_index.compares	211
abstract_inverted_index.customer	27, 204
abstract_inverted_index.delivery	15, 53, 65, 74, 190, 207
abstract_inverted_index.enhanced	236
abstract_inverted_index.increase	231
abstract_inverted_index.insights	196
abstract_inverted_index.launched	36
abstract_inverted_index.minimize	68
abstract_inverted_index.multiple	42
abstract_inverted_index.packages	43
abstract_inverted_index.process.	75
abstract_inverted_index.sequence	114
abstract_inverted_index.solution	151
abstract_inverted_index.standard	129
abstract_inverted_index.stylized	172
abstract_inverted_index.systems.	191
abstract_inverted_index.FSTSP-MD,	31
abstract_inverted_index.Traveling	5
abstract_inverted_index.algorithm	103, 121
abstract_inverted_index.component	95
abstract_inverted_index.developed	153
abstract_inverted_index.effective	81
abstract_inverted_index.extensive	166, 194
abstract_inverted_index.heuristic	82, 98, 125, 139
abstract_inverted_index.highlight	226
abstract_inverted_index.last-mile	14
abstract_inverted_index.numerical	167
abstract_inverted_index.objective	56
abstract_inverted_index.packages.	28
abstract_inverted_index.sacrifice	142
abstract_inverted_index.solutions	107
abstract_inverted_index.approaches	152
abstract_inverted_index.completion	70, 184
abstract_inverted_index.customers.	116
abstract_inverted_index.discussion	210
abstract_inverted_index.instances,	175
abstract_inverted_index.managerial	195
abstract_inverted_index.operation.	54
abstract_inverted_index.polynomial	109
abstract_inverted_index.real-world	174
abstract_inverted_index.simplicity	136
abstract_inverted_index.truck-only	189
abstract_inverted_index.(FSTSP-MD),	11
abstract_inverted_index.efficiency.	208
abstract_inverted_index.multi-modal	13
abstract_inverted_index.outperforms	149
abstract_inverted_index.single-drop	163
abstract_inverted_index.techniques.	134
abstract_inverted_index.traditional	188
abstract_inverted_index.capabilities	202
abstract_inverted_index.consistently	148
abstract_inverted_index.distribution	205
abstract_inverted_index.experiments.	168
abstract_inverted_index.order-first,	90
abstract_inverted_index.performance:	143
abstract_inverted_index.split-second	91
abstract_inverted_index.synchronized	61
abstract_inverted_index.capabilities.	238
abstract_inverted_index.cooperatively	25
abstract_inverted_index.substantially	182
abstract_inverted_index.characteristics	230
abstract_inverted_index.diversification	133
abstract_inverted_index.state-of-the-art	150
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	7
citation_normalized_percentile