Empirical analysis of optimization methods for the real-world dial-a-ride problem

Dilek Arikan; Çetin Öztoprak; Sanem Sariel

doi:10.1007/978-3-319-55849-3_38

Empirical analysis of optimization methods for the real-world dial-a-ride problem

Dilek Arikan^*, Çetin Öztoprak, Sanem Sariel

^*Corresponding author for this work

Department of Artificial Intelligence and Data Engineering

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

Abstract

This paper deals with solving the Dial-a-Ride Problem (DARP) for an on-demand delivery start-up company which delivers products to its customers from their corresponding pick-up points within guaranteed time intervals. The primary goal of the company is to minimize its operational costs while fulfilling the orders under the constraints on time window, duration, carrier capacity and ride time. This problem is formulated as the real-world DARP, and two methods are empirically evaluated by using Mixed Integer Programming (MIP) and Genetic Algorithm (GA) frameworks. The experiments are done on the simulated data provided by the company. The results show that a heuristic approach is more suitable for the real-world problem to meet the time window limitations.

Original language	English
Title of host publication	Applications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings
Editors	J.Ignacio Hidalgo, Carlos Cotta, Ting Hu, Alberto Tonda, Paolo Burrelli, Matt Coler, Giovanni Iacca, Michael Kampouridis, Antonio M. Mora Garcia, Giovanni Squillero, Anthony Brabazon, Evert Haasdijk, Jacqueline Heinerman, Fabio D Andreagiovanni, Jaume Bacardit, Trung Thanh Nguyen, Sara Silva, Ernesto Tarantino, Anna I. Esparcia-Alcazar, Gerd Ascheid, Kyrre Glette, Stefano Cagnoni, Paul Kaufmann, Francisco Fernandez de Vega, Michalis Mavrovouniotis, Mengjie Zhang, Federico Divina, Kevin Sim, Neil Urquhart, Robert Schaefer
Publisher	Springer Verlag
Pages	589-600
Number of pages	12
ISBN (Print)	9783319558486
DOIs	https://doi.org/10.1007/978-3-319-55849-3_38
Publication status	Published - 2017
Event	20th European Conference on the Applications of Evolutionary Computation, EvoApplications 2017 - Amsterdam, Netherlands Duration: 19 Apr 2017 → 21 Apr 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10199 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th European Conference on the Applications of Evolutionary Computation, EvoApplications 2017
Country/Territory	Netherlands
City	Amsterdam
Period	19/04/17 → 21/04/17

Bibliographical note

Publisher Copyright:
© Springer International Publishing AG 2017.

Keywords

Combinatorial optimization
Dial-a-Ride Problem
Genetic Algorithm
Mixed integer programming
Transportation

Access to Document

10.1007/978-3-319-55849-3_38

Cite this

Arikan, D., Öztoprak, Ç., & Sariel, S. (2017). Empirical analysis of optimization methods for the real-world dial-a-ride problem. In J. I. Hidalgo, C. Cotta, T. Hu, A. Tonda, P. Burrelli, M. Coler, G. Iacca, M. Kampouridis, A. M. Mora Garcia, G. Squillero, A. Brabazon, E. Haasdijk, J. Heinerman, F. D Andreagiovanni, J. Bacardit, T. T. Nguyen, S. Silva, E. Tarantino, A. I. Esparcia-Alcazar, G. Ascheid, K. Glette, S. Cagnoni, P. Kaufmann, F. F. de Vega, M. Mavrovouniotis, M. Zhang, F. Divina, K. Sim, N. Urquhart, ... R. Schaefer (Eds.), Applications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings (pp. 589-600). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10199 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-55849-3_38

Arikan, Dilek ; Öztoprak, Çetin ; Sariel, Sanem. / Empirical analysis of optimization methods for the real-world dial-a-ride problem. Applications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings. editor / J.Ignacio Hidalgo ; Carlos Cotta ; Ting Hu ; Alberto Tonda ; Paolo Burrelli ; Matt Coler ; Giovanni Iacca ; Michael Kampouridis ; Antonio M. Mora Garcia ; Giovanni Squillero ; Anthony Brabazon ; Evert Haasdijk ; Jacqueline Heinerman ; Fabio D Andreagiovanni ; Jaume Bacardit ; Trung Thanh Nguyen ; Sara Silva ; Ernesto Tarantino ; Anna I. Esparcia-Alcazar ; Gerd Ascheid ; Kyrre Glette ; Stefano Cagnoni ; Paul Kaufmann ; Francisco Fernandez de Vega ; Michalis Mavrovouniotis ; Mengjie Zhang ; Federico Divina ; Kevin Sim ; Neil Urquhart ; Robert Schaefer. Springer Verlag, 2017. pp. 589-600 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0a06e0aac65f44aea435ef07d3d03373,

title = "Empirical analysis of optimization methods for the real-world dial-a-ride problem",

abstract = "This paper deals with solving the Dial-a-Ride Problem (DARP) for an on-demand delivery start-up company which delivers products to its customers from their corresponding pick-up points within guaranteed time intervals. The primary goal of the company is to minimize its operational costs while fulfilling the orders under the constraints on time window, duration, carrier capacity and ride time. This problem is formulated as the real-world DARP, and two methods are empirically evaluated by using Mixed Integer Programming (MIP) and Genetic Algorithm (GA) frameworks. The experiments are done on the simulated data provided by the company. The results show that a heuristic approach is more suitable for the real-world problem to meet the time window limitations.",

keywords = "Combinatorial optimization, Dial-a-Ride Problem, Genetic Algorithm, Mixed integer programming, Transportation",

author = "Dilek Arikan and {\c C}etin {\"O}ztoprak and Sanem Sariel",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 20th European Conference on the Applications of Evolutionary Computation, EvoApplications 2017 ; Conference date: 19-04-2017 Through 21-04-2017",

year = "2017",

doi = "10.1007/978-3-319-55849-3_38",

language = "English",

isbn = "9783319558486",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "589--600",

editor = "J.Ignacio Hidalgo and Carlos Cotta and Ting Hu and Alberto Tonda and Paolo Burrelli and Matt Coler and Giovanni Iacca and Michael Kampouridis and {Mora Garcia}, {Antonio M.} and Giovanni Squillero and Anthony Brabazon and Evert Haasdijk and Jacqueline Heinerman and {D Andreagiovanni}, Fabio and Jaume Bacardit and Nguyen, {Trung Thanh} and Sara Silva and Ernesto Tarantino and Esparcia-Alcazar, {Anna I.} and Gerd Ascheid and Kyrre Glette and Stefano Cagnoni and Paul Kaufmann and {de Vega}, {Francisco Fernandez} and Michalis Mavrovouniotis and Mengjie Zhang and Federico Divina and Kevin Sim and Neil Urquhart and Robert Schaefer",

booktitle = "Applications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings",

address = "Germany",

}

Arikan, D, Öztoprak, Ç & Sariel, S 2017, Empirical analysis of optimization methods for the real-world dial-a-ride problem. in JI Hidalgo, C Cotta, T Hu, A Tonda, P Burrelli, M Coler, G Iacca, M Kampouridis, AM Mora Garcia, G Squillero, A Brabazon, E Haasdijk, J Heinerman, F D Andreagiovanni, J Bacardit, TT Nguyen, S Silva, E Tarantino, AI Esparcia-Alcazar, G Ascheid, K Glette, S Cagnoni, P Kaufmann, FF de Vega, M Mavrovouniotis, M Zhang, F Divina, K Sim, N Urquhart & R Schaefer (eds), Applications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10199 LNCS, Springer Verlag, pp. 589-600, 20th European Conference on the Applications of Evolutionary Computation, EvoApplications 2017, Amsterdam, Netherlands, 19/04/17. https://doi.org/10.1007/978-3-319-55849-3_38

Empirical analysis of optimization methods for the real-world dial-a-ride problem. / Arikan, Dilek; Öztoprak, Çetin; Sariel, Sanem.
Applications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings. ed. / J.Ignacio Hidalgo; Carlos Cotta; Ting Hu; Alberto Tonda; Paolo Burrelli; Matt Coler; Giovanni Iacca; Michael Kampouridis; Antonio M. Mora Garcia; Giovanni Squillero; Anthony Brabazon; Evert Haasdijk; Jacqueline Heinerman; Fabio D Andreagiovanni; Jaume Bacardit; Trung Thanh Nguyen; Sara Silva; Ernesto Tarantino; Anna I. Esparcia-Alcazar; Gerd Ascheid; Kyrre Glette; Stefano Cagnoni; Paul Kaufmann; Francisco Fernandez de Vega; Michalis Mavrovouniotis; Mengjie Zhang; Federico Divina; Kevin Sim; Neil Urquhart; Robert Schaefer. Springer Verlag, 2017. p. 589-600 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10199 LNCS).

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

TY - GEN

T1 - Empirical analysis of optimization methods for the real-world dial-a-ride problem

AU - Arikan, Dilek

AU - Öztoprak, Çetin

AU - Sariel, Sanem

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - This paper deals with solving the Dial-a-Ride Problem (DARP) for an on-demand delivery start-up company which delivers products to its customers from their corresponding pick-up points within guaranteed time intervals. The primary goal of the company is to minimize its operational costs while fulfilling the orders under the constraints on time window, duration, carrier capacity and ride time. This problem is formulated as the real-world DARP, and two methods are empirically evaluated by using Mixed Integer Programming (MIP) and Genetic Algorithm (GA) frameworks. The experiments are done on the simulated data provided by the company. The results show that a heuristic approach is more suitable for the real-world problem to meet the time window limitations.

AB - This paper deals with solving the Dial-a-Ride Problem (DARP) for an on-demand delivery start-up company which delivers products to its customers from their corresponding pick-up points within guaranteed time intervals. The primary goal of the company is to minimize its operational costs while fulfilling the orders under the constraints on time window, duration, carrier capacity and ride time. This problem is formulated as the real-world DARP, and two methods are empirically evaluated by using Mixed Integer Programming (MIP) and Genetic Algorithm (GA) frameworks. The experiments are done on the simulated data provided by the company. The results show that a heuristic approach is more suitable for the real-world problem to meet the time window limitations.

KW - Combinatorial optimization

KW - Dial-a-Ride Problem

KW - Genetic Algorithm

KW - Mixed integer programming

KW - Transportation

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

U2 - 10.1007/978-3-319-55849-3_38

DO - 10.1007/978-3-319-55849-3_38

M3 - Conference contribution

AN - SCOPUS:85017571121

SN - 9783319558486

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 589

EP - 600

BT - Applications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings

A2 - Hidalgo, J.Ignacio

A2 - Cotta, Carlos

A2 - Hu, Ting

A2 - Tonda, Alberto

A2 - Burrelli, Paolo

A2 - Coler, Matt

A2 - Iacca, Giovanni

A2 - Kampouridis, Michael

A2 - Mora Garcia, Antonio M.

A2 - Squillero, Giovanni

A2 - Brabazon, Anthony

A2 - Haasdijk, Evert

A2 - Heinerman, Jacqueline

A2 - D Andreagiovanni, Fabio

A2 - Bacardit, Jaume

A2 - Nguyen, Trung Thanh

A2 - Silva, Sara

A2 - Tarantino, Ernesto

A2 - Esparcia-Alcazar, Anna I.

A2 - Ascheid, Gerd

A2 - Glette, Kyrre

A2 - Cagnoni, Stefano

A2 - Kaufmann, Paul

A2 - de Vega, Francisco Fernandez

A2 - Mavrovouniotis, Michalis

A2 - Zhang, Mengjie

A2 - Divina, Federico

A2 - Sim, Kevin

A2 - Urquhart, Neil

A2 - Schaefer, Robert

PB - Springer Verlag

T2 - 20th European Conference on the Applications of Evolutionary Computation, EvoApplications 2017

Y2 - 19 April 2017 through 21 April 2017

ER -

Arikan D, Öztoprak Ç, Sariel S. Empirical analysis of optimization methods for the real-world dial-a-ride problem. In Hidalgo JI, Cotta C, Hu T, Tonda A, Burrelli P, Coler M, Iacca G, Kampouridis M, Mora Garcia AM, Squillero G, Brabazon A, Haasdijk E, Heinerman J, D Andreagiovanni F, Bacardit J, Nguyen TT, Silva S, Tarantino E, Esparcia-Alcazar AI, Ascheid G, Glette K, Cagnoni S, Kaufmann P, de Vega FF, Mavrovouniotis M, Zhang M, Divina F, Sim K, Urquhart N, Schaefer R, editors, Applications of Evolutionary Computation - 20th European Conference, EvoApplications 2017, Proceedings. Springer Verlag. 2017. p. 589-600. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-55849-3_38

Empirical analysis of optimization methods for the real-world dial-a-ride problem

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this