Exploring Quantum Inspired optimization for the Vehicle Routing Problem (VRP)
Astrid Katrine Kyhl, Troels Steenstrup, Casper Guldager
May 2023
Photo from IBM Research
1
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
Contents�
01 | Substantial saving optimization potential | |
02 | Quantum Inspired Optimization as potential solution | |
03 | Outcomes and discussion | |
04 | Q&A | |
| | |
| | |
2
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
01�Substantial saving potential from technician intraday re-optimization
3
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
Our ambition is to cut technician milage by 25% resulting in improved operating costs and reduced CO2-emission.
4
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
The Problem
~850 Technician Vehilcles
~80000 Km driven daily
~1000 Avg. Jobs/Faults daily
Constraints
Technicians Start and End point
~150 Unique Skills
SLA’s
Overtime
Equipment/Warehouse Visits
Daily Capacity / Absence planning
Lunch time
Multi-Faults
Multi Technicians Required
5
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
We Address the Inefficiency 3 Fold
2. Increase the fraction of auto dispatch from ~30% to 90-100% - Problem is too large for the human brain to beat a large scale optimization engine
(QIO Potential)
1. AI-driven planning day-to-day and long-term by better forecasting of faults and job times
(Ongoing with Classic computers)
3. Utilize intraday re-optimization to address perturbations to original plan most efficiently
(QIO Potential)
6
Document Classification: KPMG Confidential
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
6
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
QIO Potential
Scenario Builder
Fast Intra-Day Re-Optimization
7
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
02�Quantum Inspired Optimization as potential solution
8
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
Three possible roads to quantum optimization:
Gate Based
Quantum Computing
Quantum
Annealing
Quantum Inspired
Optimization
QUBO
QUBO
QUBO
QAOA
Special purpose�quantum hardware
Classical hardware & classical solvers
9
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
Quantum Inspired leverages the power of classical hardware and quantum algorithms to
Flexible – and easily adjustable – models
Solves larger and more complex problems
Identifies solutions of better quality
Finds solutions quicker
10
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
Applications of quantum-inspired optimization problems can yield solutions anywhere from�
1-10% more accurate solutions anywhere from �2-3 times as fast
“
according to Troels Steenstrup, technology head of KPMG’s Global Quantum Hub.”
“
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
11
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
Solving VRP by combining the strengths of quantum and classical
Create an approximate QUBO assignment problem and solve using simulated annealing on QIO hardware.
Create final routes using classical OR based on these assignments.
12
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
03�Outcome and discussion
13
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
Quantum Inspired resulted in measurable KPI improvements
Replace with: 99% (2 hours to 1 minute)
17 %
Technicians
58 %
Milage
99 %
Run time
14
Document Classification: KPMG Confidential
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
14
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
Q&A
04
15
Document Classification: KPMG Confidential
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
15
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
Contact Information
Astrid Katrine Kyhl
astk@tdcnet.dk
Troels Steenstrup Jensen
trsjensen@kpmg.com
Casper Guldager
caguldager@kpmg.com
16
Document Classification: KPMG Confidential
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.
16
Document Classification: KPMG Confidential
RESTRICTED
© 2023 KPMG P/S, a Danish limited liability partnership and a member firm of the KPMG global organisation of independent member firms affiliated with KPMG International Limited, a private English company limited by guarantee. All rights reserved.