COMBINATORIAL OPTIMIZATION WITH D-WAVE OCEAN SDK

Solving Traveling Salesman Problems with D-Wave Quantum Annealing

Visit Every City For the Most Efficient Sales Trip!

Backstory

Imagine you’re a salesperson tasked with visiting several cities and returning to your starting point. You want to take the shortest route possible to save time and fuel. Here’s the catch: you must visit each city exactly once.

This is the Traveling Salesman Problem (TSP): finding the most efficient route that visits all destinations and returns home. The complexity scales factorially (n!) as the number of nodes increases, making brute-force methods infeasible for large instances and challenging even the fastest computers to solve efficiently. TSP is classified as an NP-hard problem because no polynomial-time algorithm is known for finding the optimal solution.

Example

We have cities (vertices, nodes): V = {A, B, C, D} and routes (edges) with weights:

• (A, B) = 10
• (A, C) = 15
• (A, D) = 20
• (B, C) = 35
• (B, D) = 25
• (C, D) = 30