Capacitated Vehicle Routing Problem with Time Windows

Aleyna Tanel; Begüm Kınay; Deniz Karakul; Efecan Özyörük; Elif İskifoğlu; Ezgi Özoğul; Meryem Ustaoğlu; Damla Yüksel; Mustafa Arslan Örnek

doi:10.1007/978-3-030-90421-0_56

Capacitated Vehicle Routing Problem with Time Windows

Aleyna Tanel
, Begüm Kınay
, Deniz Karakul
, Efecan Özyörük
, Elif İskifoğlu
, Ezgi Özoğul
, Meryem Ustaoğlu
, Damla Yüksel^*
, Mustafa Arslan Örnek

^*Corresponding author for this work

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

Abstract

Since distribution activities have great importance for firms, supply management is a widely studied concept in many sectors. This study demonstrates an application of a Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). The problem is in the form of a fixed destination multi depots visited by multi-travelling salesmen and the distance-travel time matrix is assumed to be asymmetric. The objective of the problem is to minimize the longest route time of each vehicle. This is achieved by developing a mixed-integer linear programming model (MILP) for the problem. Additionally, since the problem is NP-hard, a general heuristic method is developed to solve the problem for larger instances in negligible computational times. Results show that the balance between the individual route times of the vehicles is provided and the time window limit is ensured. The paper also discusses the results and presents concluding remarks.

Original language	English
Title of host publication	Digitizing Production Systems - Selected Papers from ISPR 2021
Editors	Numan M. Durakbasa, M. Güneş Gençyılmaz
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	653-664
Number of pages	12
ISBN (Print)	9783030904203
DOIs	https://doi.org/10.1007/978-3-030-90421-0_56
Publication status	Published - 2022
Externally published	Yes
Event	International Symposium for Production Research, ISPR2021 - Virtual, Online Duration: 7 Oct 2021 → 9 Oct 2021

Publication series

Name	Lecture Notes in Mechanical Engineering
ISSN (Print)	2195-4356
ISSN (Electronic)	2195-4364

Conference

Conference	International Symposium for Production Research, ISPR2021
City	Virtual, Online
Period	7/10/21 → 9/10/21

Bibliographical note

Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Keywords

2opt algorithm
Capacitated vehicle routing problem
Heuristics
MDMTSP
Min-Max mTSP
Mixed-integer linear programming
Multi depot
Multi-travelling salesman problem
Time windows

Access to Document

10.1007/978-3-030-90421-0_56

Persistent URL (handle)

Persistent link

Cite this

Tanel, A., Kınay, B., Karakul, D., Özyörük, E., İskifoğlu, E., Özoğul, E., Ustaoğlu, M., Yüksel, D., & Örnek, M. A. (2022). Capacitated Vehicle Routing Problem with Time Windows. In N. M. Durakbasa, & M. G. Gençyılmaz (Eds.), Digitizing Production Systems - Selected Papers from ISPR 2021 (pp. 653-664). (Lecture Notes in Mechanical Engineering). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-90421-0_56

@inproceedings{11faf8246fd94a31a6e308d0d121e497,

title = "Capacitated Vehicle Routing Problem with Time Windows",

abstract = "Since distribution activities have great importance for firms, supply management is a widely studied concept in many sectors. This study demonstrates an application of a Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). The problem is in the form of a fixed destination multi depots visited by multi-travelling salesmen and the distance-travel time matrix is assumed to be asymmetric. The objective of the problem is to minimize the longest route time of each vehicle. This is achieved by developing a mixed-integer linear programming model (MILP) for the problem. Additionally, since the problem is NP-hard, a general heuristic method is developed to solve the problem for larger instances in negligible computational times. Results show that the balance between the individual route times of the vehicles is provided and the time window limit is ensured. The paper also discusses the results and presents concluding remarks.",

keywords = "2opt algorithm, Capacitated vehicle routing problem, Heuristics, MDMTSP, Min-Max mTSP, Mixed-integer linear programming, Multi depot, Multi-travelling salesman problem, Time windows",

author = "Aleyna Tanel and Beg{\"u}m Kınay and Deniz Karakul and Efecan {\"O}zy{\"o}r{\"u}k and Elif İskifoğlu and Ezgi {\"O}zoğul and Meryem Ustaoğlu and Damla Y{\"u}ksel and {\"O}rnek, \{Mustafa Arslan\}",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; International Symposium for Production Research, ISPR2021 ; Conference date: 07-10-2021 Through 09-10-2021",

year = "2022",

doi = "10.1007/978-3-030-90421-0\_56",

language = "English",

isbn = "9783030904203",

series = "Lecture Notes in Mechanical Engineering",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "653--664",

editor = "Durakbasa, \{Numan M.\} and Gen{\c c}yılmaz, \{M. G{\"u}ne{\c s}\}",

booktitle = "Digitizing Production Systems - Selected Papers from ISPR 2021",

address = "Germany",

}

Tanel, A, Kınay, B, Karakul, D, Özyörük, E, İskifoğlu, E, Özoğul, E, Ustaoğlu, M, Yüksel, D & Örnek, MA 2022, Capacitated Vehicle Routing Problem with Time Windows. in NM Durakbasa & MG Gençyılmaz (eds), Digitizing Production Systems - Selected Papers from ISPR 2021. Lecture Notes in Mechanical Engineering, Springer Science and Business Media Deutschland GmbH, pp. 653-664, International Symposium for Production Research, ISPR2021, Virtual, Online, 7/10/21. https://doi.org/10.1007/978-3-030-90421-0_56

Capacitated Vehicle Routing Problem with Time Windows. / Tanel, Aleyna; Kınay, Begüm; Karakul, Deniz et al.
Digitizing Production Systems - Selected Papers from ISPR 2021. ed. / Numan M. Durakbasa; M. Güneş Gençyılmaz. Springer Science and Business Media Deutschland GmbH, 2022. p. 653-664 (Lecture Notes in Mechanical Engineering).

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

TY - GEN

T1 - Capacitated Vehicle Routing Problem with Time Windows

AU - Tanel, Aleyna

AU - Kınay, Begüm

AU - Karakul, Deniz

AU - Özyörük, Efecan

AU - İskifoğlu, Elif

AU - Özoğul, Ezgi

AU - Ustaoğlu, Meryem

AU - Yüksel, Damla

AU - Örnek, Mustafa Arslan

PY - 2022

Y1 - 2022

N2 - Since distribution activities have great importance for firms, supply management is a widely studied concept in many sectors. This study demonstrates an application of a Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). The problem is in the form of a fixed destination multi depots visited by multi-travelling salesmen and the distance-travel time matrix is assumed to be asymmetric. The objective of the problem is to minimize the longest route time of each vehicle. This is achieved by developing a mixed-integer linear programming model (MILP) for the problem. Additionally, since the problem is NP-hard, a general heuristic method is developed to solve the problem for larger instances in negligible computational times. Results show that the balance between the individual route times of the vehicles is provided and the time window limit is ensured. The paper also discusses the results and presents concluding remarks.

AB - Since distribution activities have great importance for firms, supply management is a widely studied concept in many sectors. This study demonstrates an application of a Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). The problem is in the form of a fixed destination multi depots visited by multi-travelling salesmen and the distance-travel time matrix is assumed to be asymmetric. The objective of the problem is to minimize the longest route time of each vehicle. This is achieved by developing a mixed-integer linear programming model (MILP) for the problem. Additionally, since the problem is NP-hard, a general heuristic method is developed to solve the problem for larger instances in negligible computational times. Results show that the balance between the individual route times of the vehicles is provided and the time window limit is ensured. The paper also discusses the results and presents concluding remarks.

KW - 2opt algorithm

KW - Capacitated vehicle routing problem

KW - Heuristics

KW - MDMTSP

KW - Min-Max mTSP

KW - Mixed-integer linear programming

KW - Multi depot

KW - Multi-travelling salesman problem

KW - Time windows

UR - https://www.scopus.com/pages/publications/85119884459

UR - https://www.scopus.com/pages/publications/85119884459#tab=citedBy

U2 - 10.1007/978-3-030-90421-0_56

DO - 10.1007/978-3-030-90421-0_56

M3 - Conference contribution

AN - SCOPUS:85119884459

SN - 9783030904203

T3 - Lecture Notes in Mechanical Engineering

SP - 653

EP - 664

BT - Digitizing Production Systems - Selected Papers from ISPR 2021

A2 - Durakbasa, Numan M.

A2 - Gençyılmaz, M. Güneş

PB - Springer Science and Business Media Deutschland GmbH

T2 - International Symposium for Production Research, ISPR2021

Y2 - 7 October 2021 through 9 October 2021

ER -

Tanel A, Kınay B, Karakul D, Özyörük E, İskifoğlu E, Özoğul E et al. Capacitated Vehicle Routing Problem with Time Windows. In Durakbasa NM, Gençyılmaz MG, editors, Digitizing Production Systems - Selected Papers from ISPR 2021. Springer Science and Business Media Deutschland GmbH. 2022. p. 653-664. (Lecture Notes in Mechanical Engineering). doi: 10.1007/978-3-030-90421-0_56

Capacitated Vehicle Routing Problem with Time Windows

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this