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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationEvolutionary Multi-Criterion Optimization
Subtitle of host publication9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017, Proceedings
EditorsHeike Trautmann, Rudolph Günter, et al
Place of PublicationCham (CH)
PublisherSpringer
Pages438-452
Number of pages15
ISBN (Electronic)978-3-319-54157-0
ISBN (Print)978-3-319-54156-3
DOIs
Publication statusPublished - 2017
Event9th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2017 - Munster, Germany
Duration: 19 Mar 201722 Mar 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10173
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2017
CountryGermany
CityMunster
Period19/03/1722/03/17

Fingerprint

Vehicle routing
Vehicle Routing Problem
Dimensionality Reduction
Cluster analysis
NSGA-II
Cluster Analysis
Nondominated Solutions
Formulation
Service Quality
Volatiles
Substitute
Dimensionality
Demand
Objective function
Minimise
Costs
Industry
Methodology

Keywords

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

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). Cham (CH): Springer. https://doi.org/10.1007/978-3-319-54157-0_30
Mendes, Renan ; Wanner, Elizabeth ; Martins, Flávio ; Sarubbi, João. / 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",

}

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; Sarubbi, João.

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/Report/Conference proceedingConference contribution

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 contribution

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)

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). https://doi.org/10.1007/978-3-319-54157-0_30