Route optimization web service basics

In the last tutorial, I showed you how to create an optimized route using Google Maps. In this one, I'll explain how to turn the simple API request you made to Google Maps in the last post into a fully functional route optimization web service, complete with authentication, persistence and error handling.

As always, you can find working sample code for this project on Github.

How our Web Service is Structured

Here's a high level overview of what we'll be building. Users authenticate with our web service using a secret key provided to them when they sign up. They make a call to /tsp-long (travelling salesman problem long running job) which our web service uses to call the Google Maps API and return a route solution, which is saved to a database. The user gets back a job_id which he can use to retrieve the route solution separately.

Here are the APIs we will build:

Create Route - Input

Method: POST
URL: /tsp-long

The Create Route API takes a list of visits (delivery locations) and a single fleet object (driver).

{
	"visits": {
		"A": {
			"location": {
				"name": "Stop A",
				"address": "1200 Third Ave, San Diego, CA 92101, United States"
			}
		},
		"B": {
			"location": {
				"name": "Stop B",
				"address": "707 Tenth Ave, San Diego, CA 92101, United States"
			}
		}
	},
	"fleet": {
		"Afian": {
			"start_location": {
				"id": "afian-start",
				"name": "afian-start",
				"address": "1337 India St, San Diego, CA 92101, United States"
			},
			"shift_start": "08:00"
		}
	}
}

Create Route - Output

{
  "job_id": "604a2928-7f6e-4556-994a-4c1114a6d55b"
}

Once the request is made, our web service returns a job_id that can be used to retrieve the route solution from the Get Route endpoint below.

Get Route - Input

Method: GET
URL: /jobs/{job_id}

https://tsp-solver.afi.dev/jobs/{job_id}

The Get Route API returns a route solution for a given job_id.

Get Route - Output

{
	"id": "48907ded-b3f3-49d2-aab2-62be74bf6102",
	"status": "finished",
	"output": {
		"status": "completed",
		"fitness": 0,
		"unserved": [],
		"solution": {
			"Afian": [{
				"location_id": "afian-start",
				"location_name": "afian-start",
				"arrival_time": "08:00",
				"finish_time": "08:01"
			}, {
				"location_id": "A",
				"location_name": "Stop A",
				"arrival_time": "08:01",
				"finish_time": "08:01"
			}, {
				"location_id": "B",
				"location_name": "Stop B",
				"arrival_time": "08:02",
				"finish_time": "08:02"
			}]
		},
		"polylines": {
			"Afian": ["wqufErycjUAoEESlEH?uUnEA?aB?`BjL@AuTI_@Cm[`QC"]
		}

	}
}

How our Code is Organized

Our web backend is built on the Nest.js. Nest.js is a web framework built on Typescript (a version of javascript) that makes it easy to build efficient, scalable Node.js server-side applications. Similar to frameworks such as Ruby on Rails, it forces you to structure your code in a standardized way which makes it easy to read and understand. The code is organized around two main modules - Users and Optimization.

Users

To make our web service accessible, we'll let users sign up using an email address and password. Once they do so, an API key is automatically generated and will be used to let them authenticate with our web service by adding the key to the Authorization header on their API request. This way, not only can we track usage, we can also improve security by making sure that our users can only retrieve route solutions for requests made by them.

Optimization / TSP-Long

Part of the optimization module, TSP-Long stands for  Travelling Salesman Problem - Long running task. Solving for the travelling salesman problem allows us to find the shortest possible route that a driver can take to visit each of his stops exactly once. This is exactly what we are trying to find when we call the Google Maps Directions API. Optimization problems such as TSP are solved using specialized algorithms and if the problem size is large, it can take a long time to solve e.g. a TSP with 1000 stops takes about 5 minutes to solve on modern hardware - too long for the a typical http request that times out after 20 seconds or so.

The TSP problem is solved server side on Google's proprietary hardware. When we make a call to /tsp-long, our web service relays the data from that call to Google Maps, and stores the results in a database row, referenced by a unique job_id, which is immediately returned when you call /tsp-long. This way, the request won't time out if the Google Maps Directions API call takes more than 20 seconds to run.

Note: In practice, the Google Maps API call should never time out because Google limits the number of waypoints in the request to 25 or less, but it is still useful to build our web service this way in case you'd like to swap Google Maps out for a more powerful route optimization engine (such as the kind Afi Labs builds) that can solve optimization problems with multiple vehicles and an unlimited number of stops.

Optimization / Jobs

A job is simply a reference (given by a unique job_id) to a route solution stored in our database. Unlike the result returned by the Google Maps API call, the data stored in jobs is much easier to understand.

Jobs are accessed by calling the Get Route endpoint /jobs/{job_id} authenticated with your API key.

👋 As always, if you have any questions or suggestions for me, please reach out or say hello on LinkedIn.

In the next post, Part 5: Let's Build a Route Optimization Web Service, we'll write some code to bring our web service to life.