Dynamic bi-objective routing of multiple vehicles

Jakob Bossek; Christian Grimme; Heike Trautmann

doi:10.1145/3377930.3390146

Dynamic bi-objective routing of multiple vehicles

Jakob Bossek, Christian Grimme, Heike Trautmann

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

3 Downloads (Pure)

Abstract

In practice, e.g. in delivery and service scenarios, Vehicle-Routing-Problems (VRPs) often imply repeated decision making on dynamic customer requests. As in classical VRPs, tours have to be planned short while the number of serviced customers has to be maximized at the same time resulting in a multi-objective problem. Beyond that, however, dynamic requests lead to the need for re-planning of not yet realized tour parts, while already realized tour parts are irreversible. In this paper we study this type of bi-objective dynamic VRP including sequential decision making and concurrent realization of decisions. We adopt a recently proposed Dynamic Evolutionary Multi-Objective Algorithm (DEMOA) for a related VRP problem and extend it to the more realistic (here considered) scenario of multiple vehicles. We empirically show that our DEMOA is competitive with a multi-vehicle offline and clairvoyant variant of the proposed DEMOA as well as with the dynamic single-vehicle approach proposed earlier.

Original language	English
Title of host publication	GECCO 2020
Subtitle of host publication	Proceedings of the 2020 Genetic and Evolutionary Computation Conference
Place of Publication	New York, NY
Publisher	Association for Computing Machinery
Pages	166-174
Number of pages	9
ISBN (Electronic)	978-1-4503-7128-5
DOIs	https://doi.org/10.1145/3377930.3390146
Publication status	Published - 25 Jun 2020
Externally published	Yes
Event	Genetic and Evolutionary Computation Conference, GECCO 2020 - Online Event, Cancun, Mexico Duration: 8 Jul 2020 → 12 Jul 2020

Conference

Conference	Genetic and Evolutionary Computation Conference, GECCO 2020
Abbreviated title	GECCO 2020
Country/Territory	Mexico
City	Cancun
Period	8/07/20 → 12/07/20

Keywords

Decision making
Dynamic optimization
Evolutionary algorithms
Multi-objective optimization
Vehicle routing
n/a OA procedure

Access to Document

10.1145/3377930.3390146

ArticleSubmitted version, 557 KB

Cite this

@inproceedings{b1bf8edac4cd448cb528730743556ca1,

title = "Dynamic bi-objective routing of multiple vehicles",

abstract = "In practice, e.g. in delivery and service scenarios, Vehicle-Routing-Problems (VRPs) often imply repeated decision making on dynamic customer requests. As in classical VRPs, tours have to be planned short while the number of serviced customers has to be maximized at the same time resulting in a multi-objective problem. Beyond that, however, dynamic requests lead to the need for re-planning of not yet realized tour parts, while already realized tour parts are irreversible. In this paper we study this type of bi-objective dynamic VRP including sequential decision making and concurrent realization of decisions. We adopt a recently proposed Dynamic Evolutionary Multi-Objective Algorithm (DEMOA) for a related VRP problem and extend it to the more realistic (here considered) scenario of multiple vehicles. We empirically show that our DEMOA is competitive with a multi-vehicle offline and clairvoyant variant of the proposed DEMOA as well as with the dynamic single-vehicle approach proposed earlier.",

keywords = "Decision making, Dynamic optimization, Evolutionary algorithms, Multi-objective optimization, Vehicle routing, n/a OA procedure",

author = "Jakob Bossek and Christian Grimme and Heike Trautmann",

note = "Publisher Copyright: {\textcopyright} 2020 ACM.; Genetic and Evolutionary Computation Conference, GECCO 2020, GECCO 2020 ; Conference date: 08-07-2020 Through 12-07-2020",

year = "2020",

month = jun,

day = "25",

doi = "10.1145/3377930.3390146",

language = "English",

pages = "166--174",

booktitle = "GECCO 2020",

publisher = "Association for Computing Machinery",

address = "United States",

}

Bossek, J, Grimme, C & Trautmann, H 2020, Dynamic bi-objective routing of multiple vehicles. in GECCO 2020: Proceedings of the 2020 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, New York, NY, pp. 166-174, Genetic and Evolutionary Computation Conference, GECCO 2020, Cancun, Mexico, 8/07/20. https://doi.org/10.1145/3377930.3390146

Dynamic bi-objective routing of multiple vehicles. / Bossek, Jakob; Grimme, Christian; Trautmann, Heike.
GECCO 2020: Proceedings of the 2020 Genetic and Evolutionary Computation Conference. New York, NY: Association for Computing Machinery, 2020. p. 166-174.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Dynamic bi-objective routing of multiple vehicles

AU - Bossek, Jakob

AU - Grimme, Christian

AU - Trautmann, Heike

PY - 2020/6/25

Y1 - 2020/6/25

N2 - In practice, e.g. in delivery and service scenarios, Vehicle-Routing-Problems (VRPs) often imply repeated decision making on dynamic customer requests. As in classical VRPs, tours have to be planned short while the number of serviced customers has to be maximized at the same time resulting in a multi-objective problem. Beyond that, however, dynamic requests lead to the need for re-planning of not yet realized tour parts, while already realized tour parts are irreversible. In this paper we study this type of bi-objective dynamic VRP including sequential decision making and concurrent realization of decisions. We adopt a recently proposed Dynamic Evolutionary Multi-Objective Algorithm (DEMOA) for a related VRP problem and extend it to the more realistic (here considered) scenario of multiple vehicles. We empirically show that our DEMOA is competitive with a multi-vehicle offline and clairvoyant variant of the proposed DEMOA as well as with the dynamic single-vehicle approach proposed earlier.

AB - In practice, e.g. in delivery and service scenarios, Vehicle-Routing-Problems (VRPs) often imply repeated decision making on dynamic customer requests. As in classical VRPs, tours have to be planned short while the number of serviced customers has to be maximized at the same time resulting in a multi-objective problem. Beyond that, however, dynamic requests lead to the need for re-planning of not yet realized tour parts, while already realized tour parts are irreversible. In this paper we study this type of bi-objective dynamic VRP including sequential decision making and concurrent realization of decisions. We adopt a recently proposed Dynamic Evolutionary Multi-Objective Algorithm (DEMOA) for a related VRP problem and extend it to the more realistic (here considered) scenario of multiple vehicles. We empirically show that our DEMOA is competitive with a multi-vehicle offline and clairvoyant variant of the proposed DEMOA as well as with the dynamic single-vehicle approach proposed earlier.

KW - Decision making

KW - Dynamic optimization

KW - Evolutionary algorithms

KW - Multi-objective optimization

KW - Vehicle routing

KW - n/a OA procedure

UR - https://www.scopus.com/pages/publications/85091779543

U2 - 10.1145/3377930.3390146

DO - 10.1145/3377930.3390146

M3 - Conference contribution

SP - 166

EP - 174

BT - GECCO 2020

PB - Association for Computing Machinery

CY - New York, NY

T2 - Genetic and Evolutionary Computation Conference, GECCO 2020

Y2 - 8 July 2020 through 12 July 2020

ER -

Dynamic bi-objective routing of multiple vehicles

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this