Variational Quantum Algorithms for Solving Vehicle Routing Problem

Muhammad Alsaiyari; Muhamad Felemban

doi:10.1109/ICSCA57840.2023.10087522

Variational Quantum Algorithms for Solving Vehicle Routing Problem

Muhammad Alsaiyari
, Muhamad Felemban

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

4 Scopus citations

Abstract

Vehicle Routing Problem (VRP) is considered one of the most challenging problems with application in several domains, including transportation and logistics distribution. VRP is known to be NP-Hard problem. Several algorithms have been proposed to solve VRP in polynomial time. However, these algorithms are inefficient if the VRP instance increases. Recently, researchers investigated how quantum computing can be used to solve VRP. In particular, two promising variational quantum algorithms have been studied, i.e., Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA). In this paper, we implement both algorithms on IBM Qiskit and compare their evaluation in solving several instances of VRP. We observe that current Noisy-Intermediate Scale Quantum (NISQ) devices cannot solve VRP instances beyond 5 nodes and 2 vehicles. Furthermore, we observe that classical optimizers still provide better results.

Original language	English
Title of host publication	International Conference on Smart Computing and Application, ICSCA 2023
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9798350347050
DOIs	https://doi.org/10.1109/ICSCA57840.2023.10087522
State	Published - 2023
Event	2023 International Conference on Smart Computing and Application, ICSCA 2023 - Hail, Saudi Arabia Duration: 5 Feb 2023 → 6 Feb 2023

Publication series

Name	International Conference on Smart Computing and Application, ICSCA 2023

Conference

Conference	2023 International Conference on Smart Computing and Application, ICSCA 2023
Country/Territory	Saudi Arabia
City	Hail
Period	5/02/23 → 6/02/23

Bibliographical note

Publisher Copyright:
© 2023 IEEE.

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

Keywords

QAOA
Quantum computing
VQE
VRP

ASJC Scopus subject areas

Artificial Intelligence
Computer Science Applications
Computer Vision and Pattern Recognition
Information Systems
Information Systems and Management

Access to Document

10.1109/ICSCA57840.2023.10087522

Cite this

@inproceedings{a25e76c63c254928b5fd3c4f4f2c9718,

title = "Variational Quantum Algorithms for Solving Vehicle Routing Problem",

abstract = "Vehicle Routing Problem (VRP) is considered one of the most challenging problems with application in several domains, including transportation and logistics distribution. VRP is known to be NP-Hard problem. Several algorithms have been proposed to solve VRP in polynomial time. However, these algorithms are inefficient if the VRP instance increases. Recently, researchers investigated how quantum computing can be used to solve VRP. In particular, two promising variational quantum algorithms have been studied, i.e., Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA). In this paper, we implement both algorithms on IBM Qiskit and compare their evaluation in solving several instances of VRP. We observe that current Noisy-Intermediate Scale Quantum (NISQ) devices cannot solve VRP instances beyond 5 nodes and 2 vehicles. Furthermore, we observe that classical optimizers still provide better results.",

keywords = "QAOA, Quantum computing, VQE, VRP",

author = "Muhammad Alsaiyari and Muhamad Felemban",

note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 2023 International Conference on Smart Computing and Application, ICSCA 2023 ; Conference date: 05-02-2023 Through 06-02-2023",

year = "2023",

doi = "10.1109/ICSCA57840.2023.10087522",

language = "English",

series = "International Conference on Smart Computing and Application, ICSCA 2023",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "International Conference on Smart Computing and Application, ICSCA 2023",

address = "United States",

}

Alsaiyari, M & Felemban, M 2023, Variational Quantum Algorithms for Solving Vehicle Routing Problem. in International Conference on Smart Computing and Application, ICSCA 2023. International Conference on Smart Computing and Application, ICSCA 2023, Institute of Electrical and Electronics Engineers Inc., 2023 International Conference on Smart Computing and Application, ICSCA 2023, Hail, Saudi Arabia, 5/02/23. https://doi.org/10.1109/ICSCA57840.2023.10087522

Variational Quantum Algorithms for Solving Vehicle Routing Problem. / Alsaiyari, Muhammad; Felemban, Muhamad.
International Conference on Smart Computing and Application, ICSCA 2023. Institute of Electrical and Electronics Engineers Inc., 2023. (International Conference on Smart Computing and Application, ICSCA 2023).

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

TY - GEN

T1 - Variational Quantum Algorithms for Solving Vehicle Routing Problem

AU - Alsaiyari, Muhammad

AU - Felemban, Muhamad

PY - 2023

Y1 - 2023

N2 - Vehicle Routing Problem (VRP) is considered one of the most challenging problems with application in several domains, including transportation and logistics distribution. VRP is known to be NP-Hard problem. Several algorithms have been proposed to solve VRP in polynomial time. However, these algorithms are inefficient if the VRP instance increases. Recently, researchers investigated how quantum computing can be used to solve VRP. In particular, two promising variational quantum algorithms have been studied, i.e., Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA). In this paper, we implement both algorithms on IBM Qiskit and compare their evaluation in solving several instances of VRP. We observe that current Noisy-Intermediate Scale Quantum (NISQ) devices cannot solve VRP instances beyond 5 nodes and 2 vehicles. Furthermore, we observe that classical optimizers still provide better results.

AB - Vehicle Routing Problem (VRP) is considered one of the most challenging problems with application in several domains, including transportation and logistics distribution. VRP is known to be NP-Hard problem. Several algorithms have been proposed to solve VRP in polynomial time. However, these algorithms are inefficient if the VRP instance increases. Recently, researchers investigated how quantum computing can be used to solve VRP. In particular, two promising variational quantum algorithms have been studied, i.e., Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA). In this paper, we implement both algorithms on IBM Qiskit and compare their evaluation in solving several instances of VRP. We observe that current Noisy-Intermediate Scale Quantum (NISQ) devices cannot solve VRP instances beyond 5 nodes and 2 vehicles. Furthermore, we observe that classical optimizers still provide better results.

KW - QAOA

KW - Quantum computing

KW - VQE

KW - VRP

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

U2 - 10.1109/ICSCA57840.2023.10087522

DO - 10.1109/ICSCA57840.2023.10087522

M3 - Conference contribution

AN - SCOPUS:85153881006

T3 - International Conference on Smart Computing and Application, ICSCA 2023

BT - International Conference on Smart Computing and Application, ICSCA 2023

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2023 International Conference on Smart Computing and Application, ICSCA 2023

Y2 - 5 February 2023 through 6 February 2023

ER -

Variational Quantum Algorithms for Solving Vehicle Routing Problem

Abstract

Publication series

Conference

Bibliographical note

UN SDGs

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this