A Population-Based Local Search for Solving a Bi-objective Vehicle Routing Problem

J.M. Pasia; Karl Dörner; Richard Hartl; Marc Reimann

doi:10.1007/978-3-540-71615-0_15

A Population-Based Local Search for Solving a Bi-objective Vehicle Routing Problem

J.M. Pasia, Karl Dörner, Richard Hartl, Marc Reimann

Department of Accounting, Innovation and Strategy

Publications: Contribution to book › Contribution to proceedings

Abstract

In this paper we present a population-based local search for solving a bi-objective vehicle routing problem. The objectives of the problem are minimization of the tour length and balancing the routes. The algorithm repeatedly generates a pool of good initial solutions by using a randomized savings algorithm followed by local search. The local search uses three neighborhood structures and evaluates the fitness of candidate solutions using dominance relation. Several test instances are used to assess the performance of the new approach. Computational results show that the population-based local search outperforms the best known algorithm for this problem.

Original language	English
Title of host publication	Evolutionary computation in combinatorial optimization
Subtitle of host publication	7th European conference ; proceedings / EvoCOP 2007, Valencia, Spain, April 11 - 13, 2007
Editors	Carlos Cotta
Place of Publication	Berlin [u.a.]
Publisher	Springer-Verlag Berlin
Pages	166-175
Number of pages	9
ISBN (Print)	978-3-540-71614-3
DOIs	https://doi.org/10.1007/978-3-540-71615-0_15
Publication status	Published - 2007

Publication series

Series	Lecture Notes in Computer Science
Volume	4446
ISSN	0302-9743

Austrian Fields of Science 2012

502052 Business administration

Access to Document

10.1007/978-3-540-71615-0_15

Cite this

Pasia, J. M., Dörner, K., Hartl, R., & Reimann, M. (2007). A Population-Based Local Search for Solving a Bi-objective Vehicle Routing Problem. In C. Cotta (Ed.), Evolutionary computation in combinatorial optimization: 7th European conference ; proceedings / EvoCOP 2007, Valencia, Spain, April 11 - 13, 2007 (pp. 166-175). Springer-Verlag Berlin. https://doi.org/10.1007/978-3-540-71615-0_15

Pasia, J.M. ; Dörner, Karl ; Hartl, Richard et al. / A Population-Based Local Search for Solving a Bi-objective Vehicle Routing Problem. Evolutionary computation in combinatorial optimization: 7th European conference ; proceedings / EvoCOP 2007, Valencia, Spain, April 11 - 13, 2007. editor / Carlos Cotta. Berlin [u.a.] : Springer-Verlag Berlin, 2007. pp. 166-175 (Lecture Notes in Computer Science, Vol. 4446).

@inproceedings{15cc8ca914dd48d8a8f5adf9d51d40e2,

title = "A Population-Based Local Search for Solving a Bi-objective Vehicle Routing Problem",

abstract = "In this paper we present a population-based local search for solving a bi-objective vehicle routing problem. The objectives of the problem are minimization of the tour length and balancing the routes. The algorithm repeatedly generates a pool of good initial solutions by using a randomized savings algorithm followed by local search. The local search uses three neighborhood structures and evaluates the fitness of candidate solutions using dominance relation. Several test instances are used to assess the performance of the new approach. Computational results show that the population-based local search outperforms the best known algorithm for this problem.",

author = "J.M. Pasia and Karl D{\"o}rner and Richard Hartl and Marc Reimann",

year = "2007",

doi = "10.1007/978-3-540-71615-0_15",

language = "English",

isbn = "978-3-540-71614-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer-Verlag Berlin",

pages = "166--175",

editor = "Carlos Cotta",

booktitle = "Evolutionary computation in combinatorial optimization",

}

Pasia, JM, Dörner, K , Hartl, R & Reimann, M 2007, A Population-Based Local Search for Solving a Bi-objective Vehicle Routing Problem. in C Cotta (ed.), Evolutionary computation in combinatorial optimization: 7th European conference ; proceedings / EvoCOP 2007, Valencia, Spain, April 11 - 13, 2007. Springer-Verlag Berlin, Berlin [u.a.], Lecture Notes in Computer Science, vol. 4446, pp. 166-175. https://doi.org/10.1007/978-3-540-71615-0_15

A Population-Based Local Search for Solving a Bi-objective Vehicle Routing Problem. / Pasia, J.M.; Dörner, Karl ; Hartl, Richard et al.
Evolutionary computation in combinatorial optimization: 7th European conference ; proceedings / EvoCOP 2007, Valencia, Spain, April 11 - 13, 2007. ed. / Carlos Cotta. Berlin [u.a.]: Springer-Verlag Berlin, 2007. p. 166-175 (Lecture Notes in Computer Science, Vol. 4446).

Publications: Contribution to book › Contribution to proceedings

TY - GEN

T1 - A Population-Based Local Search for Solving a Bi-objective Vehicle Routing Problem

AU - Pasia, J.M.

AU - Dörner, Karl

AU - Hartl, Richard

AU - Reimann, Marc

PY - 2007

Y1 - 2007

N2 - In this paper we present a population-based local search for solving a bi-objective vehicle routing problem. The objectives of the problem are minimization of the tour length and balancing the routes. The algorithm repeatedly generates a pool of good initial solutions by using a randomized savings algorithm followed by local search. The local search uses three neighborhood structures and evaluates the fitness of candidate solutions using dominance relation. Several test instances are used to assess the performance of the new approach. Computational results show that the population-based local search outperforms the best known algorithm for this problem.

AB - In this paper we present a population-based local search for solving a bi-objective vehicle routing problem. The objectives of the problem are minimization of the tour length and balancing the routes. The algorithm repeatedly generates a pool of good initial solutions by using a randomized savings algorithm followed by local search. The local search uses three neighborhood structures and evaluates the fitness of candidate solutions using dominance relation. Several test instances are used to assess the performance of the new approach. Computational results show that the population-based local search outperforms the best known algorithm for this problem.

U2 - 10.1007/978-3-540-71615-0_15

DO - 10.1007/978-3-540-71615-0_15

M3 - Contribution to proceedings

SN - 978-3-540-71614-3

T3 - Lecture Notes in Computer Science

SP - 166

EP - 175

BT - Evolutionary computation in combinatorial optimization

A2 - Cotta, Carlos

PB - Springer-Verlag Berlin

CY - Berlin [u.a.]

ER -

Pasia JM, Dörner K , Hartl R, Reimann M. A Population-Based Local Search for Solving a Bi-objective Vehicle Routing Problem. In Cotta C, editor, Evolutionary computation in combinatorial optimization: 7th European conference ; proceedings / EvoCOP 2007, Valencia, Spain, April 11 - 13, 2007. Berlin [u.a.]: Springer-Verlag Berlin. 2007. p. 166-175. (Lecture Notes in Computer Science, Vol. 4446). doi: 10.1007/978-3-540-71615-0_15

A Population-Based Local Search for Solving a Bi-objective Vehicle Routing Problem

Abstract

Publication series

Austrian Fields of Science 2012

Access to Document

Fingerprint

Cite this