Optimal Travel Route: OpenStreetMap + Traveling Salesman Problem + OR-Tools

Automated route planner using OpenStreetMap and OR-tools [Presentation][Transcript]

Overview

In this article, we will apply travelng salesman problem to solve for an optimal travel route, i.e., given a set of locations on Openstreetmap, we solve the traveling salesman problem to find shortest routing between those locations. This ensures that a tourist visits all his/her places of interests while minimizing the total distance traveled.

To give a brief idea about the traveling salesman problem: A salesman needs to visit \(N\) different locations to sell a product. There are multiple routes connecting these locations. The challenge of the traveling salesman problem is to figure out the shortest path to travel to each \(N\) location while minimizing the distance traveled.

Mathematical model of traveling salesman problem

grapg
Graph is a collection of vertices and edges connecting them

Let \(G=(V,E)\) be a graph with vertices (locations) \(V\) and edges (paths) \(E\). Here, vertex \(V\) denotes the set of \(N\) locations and \(E\) denotes thet set of paths between those \(N\) vertices. Let \(d_e\) denote the length of path \(e, e\in E\). Let \(v_1\in V\) denote the starting point. The traveling salesman problem is to minimize the distance traveled to visit all \(N\) locations.

Optimal travel route

Suppose you are a biker visiting new places for tourism. You have been recommended a list of must visit places by your friends and relatives. You want to explore all those places while minimizing the distance traveled to save money on fuel and also your time. The problem can be reformulated as the traveling salesman problem.

Openstreetmap is an opensource map

For a realistic and user-friendly demonstration, we develop a front-end using html and javascript to select \(N\) locations of interest on Openstreetmap. Openstreetmap facilitates a routing API to calculate shortest distance between any two locations; we use this API to construct adjacency matrix of the graph. Assuming that the first chosen location is the start and end location, we pass the adjacency graph to the solver of traveling salesman problem.

Python is a high-level programming language

We use Python and or-tools, developed by Google, to identify a solution of the traveling salesman problem.

Flowchart

Let’s break down the system into smaller components.

  1. The user types in their desired locations in a search box. For each new entry, the system fetches its GPS coordinates using geocoding service.
  2. Once all places of interest are specified, the user clicks a button to compute the optimal route. This triggers API call to calculate the shortest distance between every pair of locations. To do this efficiently, we should use Matrix API instead of the routing API, since it returns the entire distance matrix in a single call. This saves both time and reduces the number of API requests.
  3. We pass the distance matrix to OR-Tools for solving the traveling salesman problem. The output solution is the sequence in which one should visit the places of interest.
  4. With the optimized location sequence, the next step is to visualize it. For this, the sequence of places is sent to the routing API to fetch the actual route on a map.

Demonstration

Optimal route on Openstreetmap
Optimal route on Openstreetmap for following locations: Srinagar, Delhi, Manali, Shimla, Tabo, Padum, Leh

Figure above shows the optimal path for the traveling salesman problem for following locations: Srinagar, Delhi, Manali, Shimla, Tabo, Padum, Leh. All these locations are located in north India. The optimal route to follow is Srinagar → Leh → Tabo → Shimla → Delhi → Manali → Padum → Srinagar

Source code

To run this code, copy all files in the same directory and launch index.php from a browser. This assumes that you have a webserver installed on your machine. If you haven't done it already, you can the article on installing LAMP on Ubuntu. Also, you need to install Python, OR-tools for solving the traveling salesman problem.

HTML front-end

The code integrates OpenStreetMap in HTML and connects it with the backend for calculating the optimal travel route. You need to update the javascript code with your API key from openrouteservice.

<!DOCTYPE html>
<html>
<head>
  <title>Optimal Routing</title>
  <meta charset="utf-8" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />

  <!-- Bootstrap -->
  <link href="https://cdn.jsdelivr.net/npm/bootstrap@5.3.2/dist/css/bootstrap.min.css" rel="stylesheet">

  <!-- Leaflet & Geocoder -->
  <link rel="stylesheet" href="https://unpkg.com/leaflet/dist/leaflet.css" />
  <link rel="stylesheet" href="https://unpkg.com/leaflet-control-geocoder/dist/Control.Geocoder.css" />
  <script src="https://unpkg.com/leaflet/dist/leaflet.js"></script>
  <script src="https://unpkg.com/leaflet-control-geocoder/dist/Control.Geocoder.js"></script>

  <style>
  h2 {
  font-weight: 700;
  font-size: 2.2rem;
  text-align: center;
  padding: 20px 30px;
  margin-bottom: 20px;

  /* Gradient background */
  /* background: linear-gradient(135deg, #0d6efd, #6610f2, #d63384); */
  background: #efd9c9;
  color: black;
  border-radius: 5px;
  /* Shadow & glow */
  box-shadow: 0 6px 16px rgba(0,0,0,0.25);

  /* Subtle animation */
  transition: transform 0.25s ease, box-shadow 0.25s ease;
}
    #map { height: 650px;
        width: 100%;
        border-radius: 8px;
        box-shadow: 0 4px 12px rgba(0,0,0,0.7); /* subtle shadow */
    }

    #output {
      margin-top: 10px;
      font-family: monospace;
      /* background: #f8f9fa; */
      /* padding: 15px; */
      /* border-radius: 8px; */
      /* border: 1px solid #dee2e6; */
    }
    #status {
      font-family: 'Roboto Mono', monospace; /* nice code-like font */
      font-size: 0.95rem;
      padding: 10px 15px;
      /* margin-top: 10px; */
      border-radius: 8px;
      /* border: 1px solid #dee2e6; */
      background: #f8f9fa;
      color: #212529;
      box-shadow: 0 2px 4px rgba(0,0,0,0.05);
      transition: all 0.3s ease-in-out;
    }

  </style>
</head>
<body class="bg-light">

<div class="container my-4">
  <!-- <h2 class="mb-3 text-center">Optimal Routing with OSM and OR-Tools</h2> -->

  <div class="row">
    <div class="col-12">
      <div id="map"></div>
    </div>
  </div>

  <div class="row mt-3">
    <div class="col text-center">
      <button class="btn btn-primary btn-lg" onclick="routingApp.computeDrivingDistances()">
        <i class="bi bi-geo-alt-fill"></i> Compute Optimal Route
      </button>
      <!-- <button class="btn btn-danger btn-lg ms-2" onclick="routingApp.resetMap()">
      <i class="bi bi-trash"></i> Reset Places
    </button> -->
    </div>
  </div>

  <div class="row mt-3">
    <div class="col">
        <div class="card shadow-sm mt-3">
          <div class="card-header bg-warning text-black">
            <i class="bi bi-signpost-split"></i> Computation Status
          </div>
          <div id="status"></div>
      </div>
      <div id="output"></div>
    </div>
  </div>
</div>

<!-- Bootstrap Icons -->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap-icons@1.11.3/font/bootstrap-icons.css">

<script>
class OptimalRoutingApp {
  constructor(mapId, outputId, statusId) {
    this.outputDiv = document.getElementById(outputId);
    this.statusDiv = document.getElementById(statusId);
    this.points = [];
    this.routeLine = null;
    this.routeMarkers = [];
    this.map = this._initMap(mapId);
    this._initGeocoder(this.map);
    this._loadPointsFromURL();
  }

  resetMap() {
  // Clear points
  this.points = [];

  // Remove route line if present
  if (this.routeLine) {
    this.map.removeLayer(this.routeLine);
    this.routeLine = null;
  }

  // Remove markers
  this.routeMarkers.forEach(m => this.map.removeLayer(m));
  this.routeMarkers = [];

  // Clear output & status
  this.outputDiv.innerHTML = "";
  this.statusDiv.innerHTML = "Map has been reset. ";

  // Reset URL (remove stored points)
  const newUrl = window.location.pathname;
  window.history.replaceState({}, "", newUrl);
  this._initMap();
}


  _initMap(mapId) {
    const map = L.map(mapId).setView([20.5937, 78.9629], 4);
    L.tileLayer('https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
      attribution: '© OpenStreetMap contributors'
    }).addTo(map);
    return map;
  }

  _initGeocoder(map) {
    L.Control.geocoder({
      defaultMarkGeocode: false,
      placeholder: 'Search location...',
      geocoder: L.Control.Geocoder.photon()
    })
    .on('markgeocode', e => {
      const latlng = e.geocode.center;
      const label = e.geocode.name;

      // Create marker & store in array
      const marker = L.marker(latlng).bindPopup(label).addTo(map);
      this.routeMarkers.push(marker);

      map.setView(latlng, 10);
      this.points.push({ lat: latlng.lat, lng: latlng.lng, label });
      this._displayPoints();
      this._updateURL();
    })
    .addTo(map);
  }

  _loadPointsFromURL() {
    const params = new URLSearchParams(window.location.search);
    const stored = params.get("points");
    if (stored) {
      try {
        this.points = JSON.parse(decodeURIComponent(stored));
        this.points.forEach((pt, i) => {
          const marker = L.marker([pt.lat, pt.lng])
            .bindPopup(`#${i + 1}: ${pt.label}`)
            .addTo(this.map);
          this.routeMarkers.push(marker);   // store reference
        });
        this._displayPoints();
      } catch (err) {
        console.error("Error parsing points from URL:", err);
      }
    }
  }

  _updateURL() {
    const params = new URLSearchParams();
    if (this.points.length > 0) {
      params.set("points", encodeURIComponent(JSON.stringify(this.points)));
    }
    const newUrl = `${window.location.pathname}?${params.toString()}`;
    window.history.replaceState({}, "", newUrl);
  }

  _displayPoints() {
    let cardHtml = `
      <div class="card shadow-sm mt-3">
        <div class="card-header bg-success text-white">
          <i class="bi bi-map"></i> Places of Interest
        </div>
        <ul class="list-group list-group-flush">
    `;

    this.points.forEach((pt, i) => {
      cardHtml += `
        <li class="list-group-item d-flex justify-content-between align-items-center">
          <div>
            <span class="badge bg-secondary me-2">#${i + 1}</span>
            ${pt.label}
            <small class="text-muted">
              (${pt.lat.toFixed(5)}, ${pt.lng.toFixed(5)})
            </small>
          </div>
          <button class="btn btn-sm btn-outline-danger" onclick="routingApp.deletePoint(${i})">
            <i class="bi bi-trash"></i>
          </button>
        </li>`;
    });

    cardHtml += `
        </ul>
      </div>
    `;
    this.outputDiv.innerHTML = cardHtml;
  }

  deletePoint(index) {
    // Remove the selected point
    this.points.splice(index, 1);

    // Remove existing markers & route line
    this.routeMarkers.forEach(m => this.map.removeLayer(m));
    this.routeMarkers = [];
    if (this.routeLine) {
      this.map.removeLayer(this.routeLine);
      this.routeLine = null;
    }

    // Re-add markers for remaining points
    this.points.forEach((pt, i) => {
      const marker = L.marker([pt.lat, pt.lng])
        .bindPopup(`#${i + 1}: ${pt.label}`)
        .addTo(this.map);
      this.routeMarkers.push(marker);
    });

    // Refresh places list & URL
    this._displayPoints();
    this._updateURL();
  }

  async _fetchWithRetry(url, options = {}, retries = 3, delay = 500) {
      this.statusDiv.innerHTML += 'Making API call. ';
      for (let i = 0; i < retries; i++) {
        try {
          this.statusDiv.innerHTML += 'API call attempt ' + (i+1) + '. ';
          const res = await fetch(url, options); // pass options
          this.statusDiv.innerHTML += 'HTTP status: ' + res.status + '. ';
          if (!res.ok) throw new Error("HTTP error " + res.status);
          return await res.json();
        } catch (err) {
          console.error(err);
          if (i === retries - 1) throw err;
          await new Promise(r => setTimeout(r, delay));
        }
      }
    }


    async _drawRoute(coords) {
     if (!coords || coords.length < 2) return;
     if (this.routeLine) this.map.removeLayer(this.routeLine);
     this.routeMarkers.forEach(m => this.map.removeLayer(m));
     this.routeMarkers = [];

     // ORS expects [lng, lat]
     const ORS_API_KEY = "5b3ce3597851110001cf62484d36d5c3385243fc88695bc373f4c7a1";
     const payload = {
       coordinates: coords.map(pt => [pt[1], pt[0]]), // [lng, lat]
       format: "geojson"
     };

     try {
     this.statusDiv.innerHTML += 'Routing API call. ';
       const res = await fetch("https://api.openrouteservice.org/v2/directions/driving-car/geojson", {
         method: "POST",
         headers: {
           "Authorization": ORS_API_KEY,
           "Content-Type": "application/json"
         },
         body: JSON.stringify(payload)
       });

       if (!res.ok) throw new Error("ORS directions error: " + res.status);
       const data = await res.json();

       if (data && data.features && data.features.length > 0) {
       this.statusDiv.innerHTML += 'Routing data received. Adding routing layer. ';
         const routeGeoJSON = data.features[0];
         this.routeLine = L.geoJSON(routeGeoJSON, { style: { color: 'blue', weight: 4 } }).addTo(this.map);
         this.map.fitBounds(this.routeLine.getBounds());
         coords.forEach((pt, i) => {
           const marker = L.marker(pt).bindPopup(`Point ${i + 1}`).addTo(this.map);
           this.routeMarkers.push(marker);
         });
       } else {
         alert("No route found in ORS response.");
       }
     } catch (err) {
       console.error("ORS request failed:", err);
       alert("Failed to fetch route from OpenRouteService.");
     }
   }


  computeDrivingDistances() {
    this.statusDiv.innerHTML = 'Process started. ';
    if (this.points.length < 2) {
      alert("Select at least two points.");
      return;
    }

    this.statusDiv.innerHTML += 'API call for generating distance matrix. ';
    // const coordinates = this.points.map(p => `${p.lng},${p.lat}`).join(';');

    // Replace with your OpenRouteService API key
    const ORS_API_KEY = "5b3ce3597851110001cf62484d36d5c3385243fc88695bc373f4c7a1";
    // Prepare the payload for ORS
    const payload = {
      locations: this.points.map(p => [p.lng, p.lat]), // note: ORS expects [lng, lat]
      metrics: ["distance"], // distances in meters
      units: "m"
    };

    // Send POST request to ORS Matrix API
    this._fetchWithRetry("https://api.openrouteservice.org/v2/matrix/driving-car", {
      method: "POST",
      headers: {
        "Authorization": ORS_API_KEY,
        "Content-Type": "application/json"
      },
      body: JSON.stringify(payload)
    })
    .then(data => {
        if (!data || !data.distances) {
          this.outputDiv.innerText += "\nError fetching distance matrix from ORS.";
          return;
        }
        this.statusDiv.innerHTML += 'API call for distance matrix successful. ';
        const dist = data.distances;

        let tableHtml = `
          <div class="card shadow-sm mt-3">
            <div class="card-header bg-success text-white">
              <i class="bi bi-clipboard-data"></i> Distance Matrix
            </div>
            <div class="card-body p-0">
              <div class="table-responsive">
                <table class="table table-bordered table-sm text-center mb-0">
        `;

        // Header row
        tableHtml += `<tr><th></th>`;
        for (let j = 0; j < dist.length; j++) {
          tableHtml += `<th>Place #${j + 1}</th>`;
        }
        tableHtml += `</tr>`;

        // Data rows
        for (let i = 0; i < dist.length; i++) {
          tableHtml += `<tr><th>Place #${i + 1}</th>`;
          for (let j = 0; j < dist[i].length; j++) {
            tableHtml += i === j
              ? `<td>0</td>`
              : `<td>${(dist[i][j]/1000).toFixed(2)}</td>`;
          }
          tableHtml += `</tr>`;
        }

        tableHtml += `
                </table>
              </div>
            </div>
          </div>
        `;

        this.outputDiv.innerHTML += tableHtml;


        this.statusDiv.innerHTML += 'Solving the traveling salesman problem. ';
        this._solveTSP(dist);
    })
    .catch(err => {
      console.error(err);
      this.outputDiv.innerText += "\nError contacting OpenRouteService API.";
    });

  }

  _solveTSP(dist) {
    fetch('api_traveling_salesman_problem.php', {
      method: 'POST',
      headers: { 'Content-Type': 'application/json' },
      body: JSON.stringify({ distance_matrix: dist })
    })
    .then(res => res.json())
    .then(data => {
        this.statusDiv.innerHTML += 'Traveling salesman solution success. ';
    // Assume PHP returns proper JSON { route: [...] }
    const routeSequence = data.route;

    // Build Bootstrap card HTML
    let cardHtml = `
      <div class="card shadow-sm mt-3">
        <div class="card-header bg-success text-white">
          <i class="bi bi-sign-turn-slight-left"></i> Optimal Route
        </div>
        <ul class="list-group list-group-flush">
    `;

    routeSequence.forEach((index, i) => {
      cardHtml += `
        <li class="list-group-item">
          <span class="badge bg-secondary me-2">${i + 1}</span>
          ${this.points[index].label}
        </li>`;
    });

    cardHtml += `
        </ul>
      </div>
    `;

    this.outputDiv.innerHTML += cardHtml;


      const latlngs = routeSequence.map(id => [this.points[id].lat, this.points[id].lng]);
      this.statusDiv.innerHTML += 'Draw routes. ';
      this._drawRoute(latlngs);
    })
    .catch(err => console.error(err));
  }
}

// Global instance
const routingApp = new OptimalRoutingApp('map', 'output', 'status');
</script>

</body>
</html>

PHP back-end

The backend receives requests from the front-end from computing optimal travel route.

<?php
$input = file_get_contents("php://input");
$data = json_decode($input, true);

$values = $data["distance_matrix"] ?? [];
$distance_matrix = array_map(function($row){
    return array_map('intval', $row);
}, $values);

$data_to_python = [
    "distance_matrix" => $distance_matrix,
    "num_vehicles" => 1,
    "depot" => 0
];

// Pass JSON to Python
$json_arg = escapeshellarg(json_encode($data_to_python));
$command = "python3 traveling_salesman_problem.py $json_arg";
$output = shell_exec($command);

// Python must print valid JSON
header("Content-Type: application/json");
echo $output;
?>

Python script

We use a modified code from the examples of or-tools. The modified code accepts distance matrix as an input from php and returns the optimal route as a sequence.

# [START program]
"""Simple Travelling Salesperson Problem (TSP) between cities."""

# [START import]
import sys
import json
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

# [END import]

# [START solution_printer]

def print_solution(manager, routing, solution):
    """Returns solution as JSON."""
    route = []
    index = routing.Start(0)
    route_distance = 0

    while not routing.IsEnd(index):
        route.append(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)

    route.append(manager.IndexToNode(index))  # Add end node

    result = {
        "objective_value": solution.ObjectiveValue(),
        "route": route,
        "route_distance": route_distance
    }

    print(json.dumps(result))  # Print as JSON for PHP/JS consumption

    # [END solution_printer]


def solve_traveling_salesman_problem(data):
    """Entry point of the program."""

    # Create the routing index manager.
    # [START index_manager]
    manager = pywrapcp.RoutingIndexManager(
        len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
    )
    # [END index_manager]

    # Create Routing Model.
    # [START routing_model]
    routing = pywrapcp.RoutingModel(manager)

    # [END routing_model]

    # [START transit_callback]
    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["distance_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    # [END transit_callback]

    # Define cost of each arc.
    # [START arc_cost]
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    # [END arc_cost]

    # Setting first solution heuristic.
    # [START parameters]
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    # [END parameters]

    # Solve the problem.
    # [START solve]
    solution = routing.SolveWithParameters(search_parameters)
    # [END solve]

    # Print solution on console.
    # [START print_solution]
    if solution:
        print_solution(manager, routing, solution)
    # [END print_solution]

json_data = sys.argv[1]
data = json.loads(json_data)
solve_traveling_salesman_problem(data)
# [END program]

Conclusion

I’ll be the first to admit that the UI still needs work. But since the code is open-sourced, I’m hoping someone can help improve that part. Hopefully, this automated route planner will be helpful for your next road trip. If you spot bugs or have ideas to improve the workflow, do write back and we can discuss further.

Author

Anurag Gupta is an M.S. graduate in Electrical and Computer Engineering from Cornell University. He also holds an M.Tech degree in Systems and Control Engineering and a B.Tech degree in Electrical Engineering from the Indian Institute of Technology, Bombay.

Comment

* Required information
1000
Drag & drop images (max 3)
Captcha Image
Powered by Commentics

Past Comments

No comments yet. Be the first!

Similar content

$topic->title

Remote Controlled (RC) Airplane
$topic->title

Typewriter Effect in Atom Editor
$topic->title

Email Spoofing Attack using a PHP Script
$topic->title

Binomial Theorem
$topic->title

Sequence and Series
$topic->title

Zero Probability Does Not Mean Impossible