Optimization of the vehicle routing problem with demand responsive transport using the nsga-II algorithm

Renan S. Mendes, Elizabeth F. Wanner, Jõao F.M. Sarubbi, Flávio V.C. Martins

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

Abstract

Demand Responsive Transport (DRT) systems emerge as an alternative to deal with the problem of variable demand, or even unpredictable, occurring in conventional urban transport systems. It can be seen in some practical situations such as public transport in rural areas, wherein in some situations, there is no way to predict demand. This paper addresses the Vehicle Routing Problem with Demand Responsive Transport (VRPDRT), a type of transport which enables customers to be taken to their destination like a taxi or minibus in order to reduce operating costs and to meet customer needs. A multiobjective approach is proposed to VRPDRT in which five different objective functions are used. These functions are aggregated in three new functions resulting in a three-objective formulation for VRPDRT. When using a three objective approach, that formulation allows a better understanding of the company and human perspectives while permitting to solve the resulting problem in an efficient way. The proposed three-objective optimization problem is solved using a random method of generating solutions and an algorithm considered state of the art, the Non-dominated Sorting Genetic Algorithm II (NSGA-II). The sets of solutions are compared using the Set Coverage Metric. The results show that the NSGA-II algorithm could obtain sets of solutions with better values for all objective functions used also called the non-dominated solutions set.

Original languageEnglish
Title of host publication2016 IEEE 19th International Conference on Intelligent Transportation Systems, ITSC 2016
PublisherIEEE
Pages2657-2662
Number of pages6
ISBN (Electronic)978-1-5090-1889-5
DOIs
Publication statusPublished - 22 Dec 2016
Event19th IEEE International Conference on Intelligent Transportation Systems - Rio de Janeiro, Brazil
Duration: 1 Nov 20164 Nov 2016

Publication series

Name
PublisherIEEE
ISSN (Electronic)2153-0017

Conference

Conference19th IEEE International Conference on Intelligent Transportation Systems
Abbreviated titleITSC 2016
CountryBrazil
CityRio de Janeiro
Period1/11/164/11/16

Fingerprint

Vehicle routing
Sorting
Genetic algorithms
Operating costs
Industry

Cite this

Mendes, R. S., Wanner, E. F., Sarubbi, J. F. M., & Martins, F. V. C. (2016). Optimization of the vehicle routing problem with demand responsive transport using the nsga-II algorithm. In 2016 IEEE 19th International Conference on Intelligent Transportation Systems, ITSC 2016 (pp. 2657-2662). IEEE. https://doi.org/10.1109/ITSC.2016.7795983
Mendes, Renan S. ; Wanner, Elizabeth F. ; Sarubbi, Jõao F.M. ; Martins, Flávio V.C. / Optimization of the vehicle routing problem with demand responsive transport using the nsga-II algorithm. 2016 IEEE 19th International Conference on Intelligent Transportation Systems, ITSC 2016. IEEE, 2016. pp. 2657-2662
@inproceedings{8e35b7934f144c25ba38838e30c6471d,
title = "Optimization of the vehicle routing problem with demand responsive transport using the nsga-II algorithm",
abstract = "Demand Responsive Transport (DRT) systems emerge as an alternative to deal with the problem of variable demand, or even unpredictable, occurring in conventional urban transport systems. It can be seen in some practical situations such as public transport in rural areas, wherein in some situations, there is no way to predict demand. This paper addresses the Vehicle Routing Problem with Demand Responsive Transport (VRPDRT), a type of transport which enables customers to be taken to their destination like a taxi or minibus in order to reduce operating costs and to meet customer needs. A multiobjective approach is proposed to VRPDRT in which five different objective functions are used. These functions are aggregated in three new functions resulting in a three-objective formulation for VRPDRT. When using a three objective approach, that formulation allows a better understanding of the company and human perspectives while permitting to solve the resulting problem in an efficient way. The proposed three-objective optimization problem is solved using a random method of generating solutions and an algorithm considered state of the art, the Non-dominated Sorting Genetic Algorithm II (NSGA-II). The sets of solutions are compared using the Set Coverage Metric. The results show that the NSGA-II algorithm could obtain sets of solutions with better values for all objective functions used also called the non-dominated solutions set.",
author = "Mendes, {Renan S.} and Wanner, {Elizabeth F.} and Sarubbi, {J{\~o}ao F.M.} and Martins, {Fl{\'a}vio V.C.}",
year = "2016",
month = "12",
day = "22",
doi = "10.1109/ITSC.2016.7795983",
language = "English",
publisher = "IEEE",
pages = "2657--2662",
booktitle = "2016 IEEE 19th International Conference on Intelligent Transportation Systems, ITSC 2016",
address = "United States",

}

Mendes, RS, Wanner, EF, Sarubbi, JFM & Martins, FVC 2016, Optimization of the vehicle routing problem with demand responsive transport using the nsga-II algorithm. in 2016 IEEE 19th International Conference on Intelligent Transportation Systems, ITSC 2016. IEEE, pp. 2657-2662, 19th IEEE International Conference on Intelligent Transportation Systems, Rio de Janeiro, Brazil, 1/11/16. https://doi.org/10.1109/ITSC.2016.7795983

Optimization of the vehicle routing problem with demand responsive transport using the nsga-II algorithm. / Mendes, Renan S.; Wanner, Elizabeth F.; Sarubbi, Jõao F.M.; Martins, Flávio V.C.

2016 IEEE 19th International Conference on Intelligent Transportation Systems, ITSC 2016. IEEE, 2016. p. 2657-2662.

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

TY - GEN

T1 - Optimization of the vehicle routing problem with demand responsive transport using the nsga-II algorithm

AU - Mendes, Renan S.

AU - Wanner, Elizabeth F.

AU - Sarubbi, Jõao F.M.

AU - Martins, Flávio V.C.

PY - 2016/12/22

Y1 - 2016/12/22

N2 - Demand Responsive Transport (DRT) systems emerge as an alternative to deal with the problem of variable demand, or even unpredictable, occurring in conventional urban transport systems. It can be seen in some practical situations such as public transport in rural areas, wherein in some situations, there is no way to predict demand. This paper addresses the Vehicle Routing Problem with Demand Responsive Transport (VRPDRT), a type of transport which enables customers to be taken to their destination like a taxi or minibus in order to reduce operating costs and to meet customer needs. A multiobjective approach is proposed to VRPDRT in which five different objective functions are used. These functions are aggregated in three new functions resulting in a three-objective formulation for VRPDRT. When using a three objective approach, that formulation allows a better understanding of the company and human perspectives while permitting to solve the resulting problem in an efficient way. The proposed three-objective optimization problem is solved using a random method of generating solutions and an algorithm considered state of the art, the Non-dominated Sorting Genetic Algorithm II (NSGA-II). The sets of solutions are compared using the Set Coverage Metric. The results show that the NSGA-II algorithm could obtain sets of solutions with better values for all objective functions used also called the non-dominated solutions set.

AB - Demand Responsive Transport (DRT) systems emerge as an alternative to deal with the problem of variable demand, or even unpredictable, occurring in conventional urban transport systems. It can be seen in some practical situations such as public transport in rural areas, wherein in some situations, there is no way to predict demand. This paper addresses the Vehicle Routing Problem with Demand Responsive Transport (VRPDRT), a type of transport which enables customers to be taken to their destination like a taxi or minibus in order to reduce operating costs and to meet customer needs. A multiobjective approach is proposed to VRPDRT in which five different objective functions are used. These functions are aggregated in three new functions resulting in a three-objective formulation for VRPDRT. When using a three objective approach, that formulation allows a better understanding of the company and human perspectives while permitting to solve the resulting problem in an efficient way. The proposed three-objective optimization problem is solved using a random method of generating solutions and an algorithm considered state of the art, the Non-dominated Sorting Genetic Algorithm II (NSGA-II). The sets of solutions are compared using the Set Coverage Metric. The results show that the NSGA-II algorithm could obtain sets of solutions with better values for all objective functions used also called the non-dominated solutions set.

UR - http://ieeexplore.ieee.org/document/7795983/

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

U2 - 10.1109/ITSC.2016.7795983

DO - 10.1109/ITSC.2016.7795983

M3 - Conference contribution

AN - SCOPUS:85010022726

SP - 2657

EP - 2662

BT - 2016 IEEE 19th International Conference on Intelligent Transportation Systems, ITSC 2016

PB - IEEE

ER -

Mendes RS, Wanner EF, Sarubbi JFM, Martins FVC. Optimization of the vehicle routing problem with demand responsive transport using the nsga-II algorithm. In 2016 IEEE 19th International Conference on Intelligent Transportation Systems, ITSC 2016. IEEE. 2016. p. 2657-2662 https://doi.org/10.1109/ITSC.2016.7795983