---
_id: '48841'
abstract:
- lang: eng
text: We tackle a bi-objective dynamic orienteering problem where customer requests
arise as time passes by. The goal is to minimize the tour length traveled by a
single delivery vehicle while simultaneously keeping the number of dismissed dynamic
customers to a minimum. We propose a dynamic Evolutionary Multi-Objective Algorithm
which is grounded on insights gained from a previous series of work on an a-posteriori
version of the problem, where all request times are known in advance. In our experiments,
we simulate different decision maker strategies and evaluate the development of
the Pareto-front approximations on exemplary problem instances. It turns out,
that despite severely reduced computational budget and no oracle-knowledge of
request times the dynamic EMOA is capable of producing approximations which partially
dominate the results of the a-posteriori EMOA and dynamic integer linear programming
strategies.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Christian
full_name: Grimme, Christian
last_name: Grimme
- first_name: Stephan
full_name: Meisel, Stephan
last_name: Meisel
- first_name: Günter
full_name: Rudolph, Günter
last_name: Rudolph
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: 'Bossek J, Grimme C, Meisel S, Rudolph G, Trautmann H. Bi-Objective Orienteering:
Towards a Dynamic Multi-objective Evolutionary Algorithm. In: Deb K, Goodman E,
Coello Coello CA, et al., eds. Evolutionary Multi-Criterion Optimization (EMO).
Lecture Notes in Computer Science. Springer International Publishing; 2019:516–528.
doi:10.1007/978-3-030-12598-1_41'
apa: 'Bossek, J., Grimme, C., Meisel, S., Rudolph, G., & Trautmann, H. (2019).
Bi-Objective Orienteering: Towards a Dynamic Multi-objective Evolutionary Algorithm.
In K. Deb, E. Goodman, C. A. Coello Coello, K. Klamroth, K. Miettinen, S. Mostaghim,
& P. Reed (Eds.), Evolutionary Multi-Criterion Optimization (EMO) (pp.
516–528). Springer International Publishing. https://doi.org/10.1007/978-3-030-12598-1_41'
bibtex: '@inproceedings{Bossek_Grimme_Meisel_Rudolph_Trautmann_2019, place={Cham},
series={Lecture Notes in Computer Science}, title={Bi-Objective Orienteering:
Towards a Dynamic Multi-objective Evolutionary Algorithm}, DOI={10.1007/978-3-030-12598-1_41},
booktitle={Evolutionary Multi-Criterion Optimization (EMO)}, publisher={Springer
International Publishing}, author={Bossek, Jakob and Grimme, Christian and Meisel,
Stephan and Rudolph, Günter and Trautmann, Heike}, editor={Deb, Kalyanmoy and
Goodman, Erik and Coello Coello, Carlos A. and Klamroth, Kathrin and Miettinen,
Kaisa and Mostaghim, Sanaz and Reed, Patrick}, year={2019}, pages={516–528}, collection={Lecture
Notes in Computer Science} }'
chicago: 'Bossek, Jakob, Christian Grimme, Stephan Meisel, Günter Rudolph, and Heike
Trautmann. “Bi-Objective Orienteering: Towards a Dynamic Multi-Objective Evolutionary
Algorithm.” In Evolutionary Multi-Criterion Optimization (EMO), edited
by Kalyanmoy Deb, Erik Goodman, Carlos A. Coello Coello, Kathrin Klamroth, Kaisa
Miettinen, Sanaz Mostaghim, and Patrick Reed, 516–528. Lecture Notes in Computer
Science. Cham: Springer International Publishing, 2019. https://doi.org/10.1007/978-3-030-12598-1_41.'
ieee: 'J. Bossek, C. Grimme, S. Meisel, G. Rudolph, and H. Trautmann, “Bi-Objective
Orienteering: Towards a Dynamic Multi-objective Evolutionary Algorithm,” in Evolutionary
Multi-Criterion Optimization (EMO), 2019, pp. 516–528, doi: 10.1007/978-3-030-12598-1_41.'
mla: 'Bossek, Jakob, et al. “Bi-Objective Orienteering: Towards a Dynamic Multi-Objective
Evolutionary Algorithm.” Evolutionary Multi-Criterion Optimization (EMO),
edited by Kalyanmoy Deb et al., Springer International Publishing, 2019, pp. 516–528,
doi:10.1007/978-3-030-12598-1_41.'
short: 'J. Bossek, C. Grimme, S. Meisel, G. Rudolph, H. Trautmann, in: K. Deb, E.
Goodman, C.A. Coello Coello, K. Klamroth, K. Miettinen, S. Mostaghim, P. Reed
(Eds.), Evolutionary Multi-Criterion Optimization (EMO), Springer International
Publishing, Cham, 2019, pp. 516–528.'
date_created: 2023-11-14T15:58:52Z
date_updated: 2023-12-13T10:43:07Z
department:
- _id: '819'
doi: 10.1007/978-3-030-12598-1_41
editor:
- first_name: Kalyanmoy
full_name: Deb, Kalyanmoy
last_name: Deb
- first_name: Erik
full_name: Goodman, Erik
last_name: Goodman
- first_name: Carlos A.
full_name: Coello Coello, Carlos A.
last_name: Coello Coello
- first_name: Kathrin
full_name: Klamroth, Kathrin
last_name: Klamroth
- first_name: Kaisa
full_name: Miettinen, Kaisa
last_name: Miettinen
- first_name: Sanaz
full_name: Mostaghim, Sanaz
last_name: Mostaghim
- first_name: Patrick
full_name: Reed, Patrick
last_name: Reed
extern: '1'
keyword:
- Combinatorial optimization
- Dynamic optimization
- Metaheuristics
- Multi-objective optimization
- Vehicle routing
language:
- iso: eng
page: 516–528
place: Cham
publication: Evolutionary Multi-Criterion Optimization (EMO)
publication_identifier:
isbn:
- 978-3-030-12598-1
publication_status: published
publisher: Springer International Publishing
series_title: Lecture Notes in Computer Science
status: public
title: 'Bi-Objective Orienteering: Towards a Dynamic Multi-objective Evolutionary
Algorithm'
type: conference
user_id: '102979'
year: '2019'
...
---
_id: '48839'
abstract:
- lang: eng
text: We analyze the effects of including local search techniques into a multi-objective
evolutionary algorithm for solving a bi-objective orienteering problem with a
single vehicle while the two conflicting objectives are minimization of travel
time and maximization of the number of visited customer locations. Experiments
are based on a large set of specifically designed problem instances with different
characteristics and it is shown that local search techniques focusing on one of
the objectives only improve the performance of the evolutionary algorithm in terms
of both objectives. The analysis also shows that local search techniques are capable
of sending locally optimal solutions to foremost fronts of the multi-objective
optimization process, and that these solutions then become the leading factors
of the evolutionary process.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Christian
full_name: Grimme, Christian
last_name: Grimme
- first_name: Stephan
full_name: Meisel, Stephan
last_name: Meisel
- first_name: Günter
full_name: Rudolph, Günter
last_name: Rudolph
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: 'Bossek J, Grimme C, Meisel S, Rudolph G, Trautmann H. Local Search Effects
in Bi-Objective Orienteering. In: Proceedings of the Genetic and Evolutionary
Computation Conference. GECCO ’18. Association for Computing Machinery; 2018:585–592.
doi:10.1145/3205455.3205548'
apa: Bossek, J., Grimme, C., Meisel, S., Rudolph, G., & Trautmann, H. (2018).
Local Search Effects in Bi-Objective Orienteering. Proceedings of the Genetic
and Evolutionary Computation Conference, 585–592. https://doi.org/10.1145/3205455.3205548
bibtex: '@inproceedings{Bossek_Grimme_Meisel_Rudolph_Trautmann_2018, place={New
York, NY, USA}, series={GECCO ’18}, title={Local Search Effects in Bi-Objective
Orienteering}, DOI={10.1145/3205455.3205548},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Grimme,
Christian and Meisel, Stephan and Rudolph, Günter and Trautmann, Heike}, year={2018},
pages={585–592}, collection={GECCO ’18} }'
chicago: 'Bossek, Jakob, Christian Grimme, Stephan Meisel, Günter Rudolph, and Heike
Trautmann. “Local Search Effects in Bi-Objective Orienteering.” In Proceedings
of the Genetic and Evolutionary Computation Conference, 585–592. GECCO ’18.
New York, NY, USA: Association for Computing Machinery, 2018. https://doi.org/10.1145/3205455.3205548.'
ieee: 'J. Bossek, C. Grimme, S. Meisel, G. Rudolph, and H. Trautmann, “Local Search
Effects in Bi-Objective Orienteering,” in Proceedings of the Genetic and Evolutionary
Computation Conference, 2018, pp. 585–592, doi: 10.1145/3205455.3205548.'
mla: Bossek, Jakob, et al. “Local Search Effects in Bi-Objective Orienteering.”
Proceedings of the Genetic and Evolutionary Computation Conference, Association
for Computing Machinery, 2018, pp. 585–592, doi:10.1145/3205455.3205548.
short: 'J. Bossek, C. Grimme, S. Meisel, G. Rudolph, H. Trautmann, in: Proceedings
of the Genetic and Evolutionary Computation Conference, Association for Computing
Machinery, New York, NY, USA, 2018, pp. 585–592.'
date_created: 2023-11-14T15:58:51Z
date_updated: 2023-12-13T10:42:14Z
department:
- _id: '819'
doi: 10.1145/3205455.3205548
extern: '1'
keyword:
- combinatorial optimization
- metaheuristics
- multi-objective optimization
- orienteering
- transportation
language:
- iso: eng
page: 585–592
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-5618-3
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’18
status: public
title: Local Search Effects in Bi-Objective Orienteering
type: conference
user_id: '102979'
year: '2018'
...
---
_id: '48874'
abstract:
- lang: eng
text: State of the Art inexact solvers of the NP-hard Traveling Salesperson Problem
TSP are known to mostly yield high-quality solutions in reasonable computation
times. With the purpose of understanding different levels of instance difficulties,
instances for the current State of the Art heuristic TSP solvers LKH+restart and
EAX+restart are presented which are evolved using a sophisticated evolutionary
algorithm. More specifically, the performance differences of the respective solvers
are maximized resulting in instances which are easier to solve for one solver
and much more difficult for the other. Focusing on both optimization directions,
instance features are identified which characterize both types of instances and
increase the understanding of solver performance differences.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: 'Bossek J, Trautmann H. Understanding Characteristics of Evolved Instances
for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.
In: Proceedings of the XV International Conference of the Italian Association
for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037.
AI*IA 2016. Springer-Verlag; 2016:3–12. doi:10.1007/978-3-319-49130-1_1'
apa: Bossek, J., & Trautmann, H. (2016). Understanding Characteristics of Evolved
Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.
Proceedings of the XV International Conference of the Italian Association for
Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037,
3–12. https://doi.org/10.1007/978-3-319-49130-1_1
bibtex: '@inproceedings{Bossek_Trautmann_2016, place={Berlin, Heidelberg}, series={AI*IA
2016}, title={Understanding Characteristics of Evolved Instances for State-of-the-Art
Inexact TSP Solvers with Maximum Performance Difference}, DOI={10.1007/978-3-319-49130-1_1},
booktitle={Proceedings of the XV International Conference of the Italian Association
for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037},
publisher={Springer-Verlag}, author={Bossek, Jakob and Trautmann, Heike}, year={2016},
pages={3–12}, collection={AI*IA 2016} }'
chicago: 'Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of
Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance
Difference.” In Proceedings of the XV International Conference of the Italian
Association for Artificial Intelligence on Advances in Artificial Intelligence
- Volume 10037, 3–12. AI*IA 2016. Berlin, Heidelberg: Springer-Verlag, 2016.
https://doi.org/10.1007/978-3-319-49130-1_1.'
ieee: 'J. Bossek and H. Trautmann, “Understanding Characteristics of Evolved Instances
for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference,”
in Proceedings of the XV International Conference of the Italian Association
for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037,
2016, pp. 3–12, doi: 10.1007/978-3-319-49130-1_1.'
mla: Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of Evolved
Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.”
Proceedings of the XV International Conference of the Italian Association for
Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037,
Springer-Verlag, 2016, pp. 3–12, doi:10.1007/978-3-319-49130-1_1.
short: 'J. Bossek, H. Trautmann, in: Proceedings of the XV International Conference
of the Italian Association for Artificial Intelligence on Advances in Artificial
Intelligence - Volume 10037, Springer-Verlag, Berlin, Heidelberg, 2016, pp. 3–12.'
date_created: 2023-11-14T15:58:57Z
date_updated: 2023-12-13T10:47:11Z
doi: 10.1007/978-3-319-49130-1_1
extern: '1'
keyword:
- Combinatorial optimization
- Instance hardness
- Metaheuristics
- Transportation
- TSP
language:
- iso: eng
page: 3–12
place: Berlin, Heidelberg
publication: Proceedings of the XV International Conference of the Italian Association
for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037
publication_identifier:
isbn:
- 978-3-319-49129-5
publication_status: published
publisher: Springer-Verlag
series_title: AI*IA 2016
status: public
title: Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact
TSP Solvers with Maximum Performance Difference
type: conference
user_id: '102979'
year: '2016'
...
---
_id: '48887'
abstract:
- lang: eng
text: 'We evaluate the performance of a multi-objective evolutionary algorithm on
a class of dynamic routing problems with a single vehicle. In particular we focus
on relating algorithmic performance to the most prominent characteristics of problem
instances. The routing problem considers two types of customers: mandatory customers
must be visited whereas optional customers do not necessarily have to be visited.
Moreover, mandatory customers are known prior to the start of the tour whereas
optional customers request for service at later points in time with the vehicle
already being on its way. The multi-objective optimization problem then results
as maximizing the number of visited customers while simultaneously minimizing
total travel time. As an a-posteriori evaluation tool, the evolutionary algorithm
aims at approximating the related Pareto set for specifically designed benchmarking
instances differing in terms of number of customers, geographical layout, fraction
of mandatory customers, and request times of optional customers. Conceptional
and experimental comparisons to online heuristic procedures are provided.'
author:
- first_name: Stephan
full_name: Meisel, Stephan
last_name: Meisel
- first_name: Christian
full_name: Grimme, Christian
last_name: Grimme
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Martin
full_name: Wölck, Martin
last_name: Wölck
- first_name: Günter
full_name: Rudolph, Günter
last_name: Rudolph
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: 'Meisel S, Grimme C, Bossek J, Wölck M, Rudolph G, Trautmann H. Evaluation
of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle.
In: Proceedings of the Genetic and Evolutionary Computation Conference .
GECCO’15. Association for Computing Machinery; 2015:425–432. doi:10.1145/2739480.2754705'
apa: Meisel, S., Grimme, C., Bossek, J., Wölck, M., Rudolph, G., & Trautmann,
H. (2015). Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic
Routing of a Vehicle. Proceedings of the Genetic and Evolutionary Computation
Conference , 425–432. https://doi.org/10.1145/2739480.2754705
bibtex: '@inproceedings{Meisel_Grimme_Bossek_Wölck_Rudolph_Trautmann_2015, place={New
York, NY, USA}, series={GECCO’15}, title={Evaluation of a Multi-Objective EA on
Benchmark Instances for Dynamic Routing of a Vehicle}, DOI={10.1145/2739480.2754705},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference
}, publisher={Association for Computing Machinery}, author={Meisel, Stephan and
Grimme, Christian and Bossek, Jakob and Wölck, Martin and Rudolph, Günter and
Trautmann, Heike}, year={2015}, pages={425–432}, collection={GECCO’15} }'
chicago: 'Meisel, Stephan, Christian Grimme, Jakob Bossek, Martin Wölck, Günter
Rudolph, and Heike Trautmann. “Evaluation of a Multi-Objective EA on Benchmark
Instances for Dynamic Routing of a Vehicle.” In Proceedings of the Genetic
and Evolutionary Computation Conference , 425–432. GECCO’15. New York, NY,
USA: Association for Computing Machinery, 2015. https://doi.org/10.1145/2739480.2754705.'
ieee: 'S. Meisel, C. Grimme, J. Bossek, M. Wölck, G. Rudolph, and H. Trautmann,
“Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing
of a Vehicle,” in Proceedings of the Genetic and Evolutionary Computation Conference
, 2015, pp. 425–432, doi: 10.1145/2739480.2754705.'
mla: Meisel, Stephan, et al. “Evaluation of a Multi-Objective EA on Benchmark Instances
for Dynamic Routing of a Vehicle.” Proceedings of the Genetic and Evolutionary
Computation Conference , Association for Computing Machinery, 2015, pp. 425–432,
doi:10.1145/2739480.2754705.
short: 'S. Meisel, C. Grimme, J. Bossek, M. Wölck, G. Rudolph, H. Trautmann, in:
Proceedings of the Genetic and Evolutionary Computation Conference , Association
for Computing Machinery, New York, NY, USA, 2015, pp. 425–432.'
date_created: 2023-11-14T15:58:59Z
date_updated: 2023-12-13T10:49:06Z
department:
- _id: '819'
doi: 10.1145/2739480.2754705
extern: '1'
keyword:
- combinatorial optimization
- metaheuristics
- multi-objective optimization
- online algorithms
- transportation
language:
- iso: eng
page: 425–432
place: New York, NY, USA
publication: 'Proceedings of the Genetic and Evolutionary Computation Conference '
publication_identifier:
isbn:
- 978-1-4503-3472-3
publisher: Association for Computing Machinery
series_title: GECCO’15
status: public
title: Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing
of a Vehicle
type: conference
user_id: '102979'
year: '2015'
...