Dimensionality reduction approach for many-objective vehicle routing problem with demand responsive transport

Renan Mendes; Elizabeth Wanner; Flávio Martins; João Sarubbi

doi:10.1007/978-3-319-54157-0_30

Dimensionality reduction approach for many-objective vehicle routing problem with demand responsive transport

Renan Mendes^*, Elizabeth Wanner, Flávio Martins, João Sarubbi

^*Corresponding author for this work

College of Engineering and Physical Sciences

Research output: Chapter in Book/Published conference output › Conference publication

Abstract

Demand Responsive Transport (DRT) systems emanate as a substitute to face the problem of volatile, or even inconstant, demand, occurring in popular urban transport systems. This paper is focused in the Vehicle Routing Problem with Demand Responsive Transport (VRPDRT), a type of transport which enables passengers to be taken to their destination, as a shared service, trying to minimize the company costs and offer a quality service taking passengers on their needs. A manyobjective approach is applied in VRPDRT in which seven different objective functions are used. To solve the problem through traditional multiobjective algorithms, the work proposes the usage of cluster analysis to perform the dimensionaly reduction task. The seven functions are then aggregated resulting in a bi-objective formulation and the algorithms NSGA-II and SPEA 2 are used to solve the problem. The results show that the algorithms achieve statistically different results and NSGA-II reaches a greater number of non-dominated solutions when compared to SPEA 2. Furthermore, the results are compared to an approach proposed in literature that uses another way to reduce the dimensionality of the problem in a two-objective formulation and the cluster analysis procedure is proven to be a competitive methodology in that problem. It is possbile to say that the behavior of the algorithm is modified by the way the dimensionality reduction of the problem is made.

Original language	English
Title of host publication	Evolutionary Multi-Criterion Optimization
Subtitle of host publication	9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017, Proceedings
Editors	Heike Trautmann, Rudolph Günter, et al
Place of Publication	Cham (CH)
Publisher	Springer
Pages	438-452
Number of pages	15
ISBN (Electronic)	978-3-319-54157-0
ISBN (Print)	978-3-319-54156-3
DOIs	https://doi.org/10.1007/978-3-319-54157-0_30
Publication status	Published - 2017
Event	9th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2017 - Munster, Germany Duration: 19 Mar 2017 → 22 Mar 2017

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10173
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2017
Country/Territory	Germany
City	Munster
Period	19/03/17 → 22/03/17

Keywords

cluster analysis
demand responsive transport
dimensinality reduction
many-objective optimization
vehicle routing problem

Access to Document

10.1007/978-3-319-54157-0_30

Cite this

Mendes, R., Wanner, E., Martins, F., & Sarubbi, J. (2017). Dimensionality reduction approach for many-objective vehicle routing problem with demand responsive transport. In H. Trautmann, R. Günter, & et al (Eds.), Evolutionary Multi-Criterion Optimization: 9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017, Proceedings (pp. 438-452). (Lecture Notes in Computer Science; Vol. 10173). Springer. https://doi.org/10.1007/978-3-319-54157-0_30

Mendes, Renan ; Wanner, Elizabeth ; Martins, Flávio et al. / Dimensionality reduction approach for many-objective vehicle routing problem with demand responsive transport. Evolutionary Multi-Criterion Optimization: 9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017, Proceedings. editor / Heike Trautmann ; Rudolph Günter ; et al. Cham (CH) : Springer, 2017. pp. 438-452 (Lecture Notes in Computer Science).

@inproceedings{3df1687d6fe649d4a39fdc1191bf567c,

title = "Dimensionality reduction approach for many-objective vehicle routing problem with demand responsive transport",

abstract = "Demand Responsive Transport (DRT) systems emanate as a substitute to face the problem of volatile, or even inconstant, demand, occurring in popular urban transport systems. This paper is focused in the Vehicle Routing Problem with Demand Responsive Transport (VRPDRT), a type of transport which enables passengers to be taken to their destination, as a shared service, trying to minimize the company costs and offer a quality service taking passengers on their needs. A manyobjective approach is applied in VRPDRT in which seven different objective functions are used. To solve the problem through traditional multiobjective algorithms, the work proposes the usage of cluster analysis to perform the dimensionaly reduction task. The seven functions are then aggregated resulting in a bi-objective formulation and the algorithms NSGA-II and SPEA 2 are used to solve the problem. The results show that the algorithms achieve statistically different results and NSGA-II reaches a greater number of non-dominated solutions when compared to SPEA 2. Furthermore, the results are compared to an approach proposed in literature that uses another way to reduce the dimensionality of the problem in a two-objective formulation and the cluster analysis procedure is proven to be a competitive methodology in that problem. It is possbile to say that the behavior of the algorithm is modified by the way the dimensionality reduction of the problem is made.",

keywords = "cluster analysis, demand responsive transport, dimensinality reduction, many-objective optimization, vehicle routing problem",

author = "Renan Mendes and Elizabeth Wanner and Fl{\'a}vio Martins and Jo{\~a}o Sarubbi",

year = "2017",

doi = "10.1007/978-3-319-54157-0_30",

language = "English",

isbn = "978-3-319-54156-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "438--452",

editor = "Heike Trautmann and Rudolph G{\"u}nter and {et al}",

booktitle = "Evolutionary Multi-Criterion Optimization",

address = "Germany",

note = "9th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2017 ; Conference date: 19-03-2017 Through 22-03-2017",

}

Mendes, R, Wanner, E, Martins, F & Sarubbi, J 2017, Dimensionality reduction approach for many-objective vehicle routing problem with demand responsive transport. in H Trautmann, R Günter & et al (eds), Evolutionary Multi-Criterion Optimization: 9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017, Proceedings. Lecture Notes in Computer Science, vol. 10173, Springer, Cham (CH), pp. 438-452, 9th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2017, Munster, Germany, 19/03/17. https://doi.org/10.1007/978-3-319-54157-0_30

Dimensionality reduction approach for many-objective vehicle routing problem with demand responsive transport. / Mendes, Renan; Wanner, Elizabeth; Martins, Flávio et al.
Evolutionary Multi-Criterion Optimization: 9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017, Proceedings. ed. / Heike Trautmann; Rudolph Günter; et al. Cham (CH): Springer, 2017. p. 438-452 (Lecture Notes in Computer Science; Vol. 10173).

Research output: Chapter in Book/Published conference output › Conference publication

TY - GEN

T1 - Dimensionality reduction approach for many-objective vehicle routing problem with demand responsive transport

AU - Mendes, Renan

AU - Wanner, Elizabeth

AU - Martins, Flávio

AU - Sarubbi, João

PY - 2017

Y1 - 2017

N2 - Demand Responsive Transport (DRT) systems emanate as a substitute to face the problem of volatile, or even inconstant, demand, occurring in popular urban transport systems. This paper is focused in the Vehicle Routing Problem with Demand Responsive Transport (VRPDRT), a type of transport which enables passengers to be taken to their destination, as a shared service, trying to minimize the company costs and offer a quality service taking passengers on their needs. A manyobjective approach is applied in VRPDRT in which seven different objective functions are used. To solve the problem through traditional multiobjective algorithms, the work proposes the usage of cluster analysis to perform the dimensionaly reduction task. The seven functions are then aggregated resulting in a bi-objective formulation and the algorithms NSGA-II and SPEA 2 are used to solve the problem. The results show that the algorithms achieve statistically different results and NSGA-II reaches a greater number of non-dominated solutions when compared to SPEA 2. Furthermore, the results are compared to an approach proposed in literature that uses another way to reduce the dimensionality of the problem in a two-objective formulation and the cluster analysis procedure is proven to be a competitive methodology in that problem. It is possbile to say that the behavior of the algorithm is modified by the way the dimensionality reduction of the problem is made.

AB - Demand Responsive Transport (DRT) systems emanate as a substitute to face the problem of volatile, or even inconstant, demand, occurring in popular urban transport systems. This paper is focused in the Vehicle Routing Problem with Demand Responsive Transport (VRPDRT), a type of transport which enables passengers to be taken to their destination, as a shared service, trying to minimize the company costs and offer a quality service taking passengers on their needs. A manyobjective approach is applied in VRPDRT in which seven different objective functions are used. To solve the problem through traditional multiobjective algorithms, the work proposes the usage of cluster analysis to perform the dimensionaly reduction task. The seven functions are then aggregated resulting in a bi-objective formulation and the algorithms NSGA-II and SPEA 2 are used to solve the problem. The results show that the algorithms achieve statistically different results and NSGA-II reaches a greater number of non-dominated solutions when compared to SPEA 2. Furthermore, the results are compared to an approach proposed in literature that uses another way to reduce the dimensionality of the problem in a two-objective formulation and the cluster analysis procedure is proven to be a competitive methodology in that problem. It is possbile to say that the behavior of the algorithm is modified by the way the dimensionality reduction of the problem is made.

KW - cluster analysis

KW - demand responsive transport

KW - dimensinality reduction

KW - many-objective optimization

KW - vehicle routing problem

UR - http://link.springer.com/chapter/10.1007%2F978-3-319-54157-0_30

UR - http://www.scopus.com/inward/record.url?scp=85014222915&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-54157-0_30

DO - 10.1007/978-3-319-54157-0_30

M3 - Conference publication

AN - SCOPUS:85014222915

SN - 978-3-319-54156-3

T3 - Lecture Notes in Computer Science

SP - 438

EP - 452

BT - Evolutionary Multi-Criterion Optimization

A2 - Trautmann, Heike

A2 - Günter, Rudolph

A2 - et al,

PB - Springer

CY - Cham (CH)

T2 - 9th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2017

Y2 - 19 March 2017 through 22 March 2017

ER -

Mendes R, Wanner E, Martins F, Sarubbi J. Dimensionality reduction approach for many-objective vehicle routing problem with demand responsive transport. In Trautmann H, Günter R, et al, editors, Evolutionary Multi-Criterion Optimization: 9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017, Proceedings. Cham (CH): Springer. 2017. p. 438-452. (Lecture Notes in Computer Science). Epub 2017 Feb 19. doi: 10.1007/978-3-319-54157-0_30

Dimensionality reduction approach for many-objective vehicle routing problem with demand responsive transport

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

A multiobjective strategy to allocate roadside units in a vehicular network with guaranteed levels of service

Cite this