Given a starting location and a list of drop-off locations, this project finds the shortest driving path by making use of a map provider (Google Maps Distance Matrix API) and applying a Travelling Salesman algorithm (brute force or Held & Karp).
SIU, Ching Pong (a.k.a. Asuka Kenji)
Any commercial use of this project and products derived from it is prohibited, except with the prior written approval of the author. For non-commercial use, the MIT License applies.
- Getting Started
- System Architecture Diagram
- Directory Structure
- Project Structure
- Project Architecture
- Dependencies
- To Be Improved
Building Front-Tier
Create a new directory and change the current directory to it:
mkdir temp1
cd temp1
Download the Docker config file Dockerfile:
curl -O https://raw.githubusercontent.com/asukakenji/151a48667a3852a43a2028024ffc102e/master/cmd/frontier/Dockerfile
Download the app config file frontier.json:
curl -O https://raw.githubusercontent.com/asukakenji/151a48667a3852a43a2028024ffc102e/master/cmd/frontier/frontier.json
Edit the config file to fit the environment.
Build the Docker image:
docker build -t frontier-image .
Building Back-Tier
Create a new directory and change the current directory to it:
mkdir temp2
cd temp2
Download the Docker config file Dockerfile:
curl -O https://raw.githubusercontent.com/asukakenji/151a48667a3852a43a2028024ffc102e/master/cmd/backtier/Dockerfile
Download the app config file backtier.json:
curl -O https://raw.githubusercontent.com/asukakenji/151a48667a3852a43a2028024ffc102e/master/cmd/backtier/backtier.json
Edit the config file to fit the environment.
Build the Docker image:
docker build -t backtier-image .
Building Garbage Collector
Create a new directory and change the current directory to it:
mkdir temp3
cd temp3
Download the Docker config file Dockerfile:
curl -O https://raw.githubusercontent.com/asukakenji/151a48667a3852a43a2028024ffc102e/master/cmd/garbagecollector/Dockerfile
Download the app config file garbagecollector.json:
curl -O https://raw.githubusercontent.com/asukakenji/151a48667a3852a43a2028024ffc102e/master/cmd/garbagecollector/garbagecollector.json
Edit the config file to fit the environment.
Build the Docker image:
docker build -t garbagecollector-image .
Running Task Queue
docker run schickling/beanstalkd
Running Front-Tier
docker run frontier-image
Running Back-Tier
docker run backtier-image
Running Garbage Collector
docker run garbagecollector-image
Visit here for the full-size diagram.
+ (project root)
├── bitstring
├── cmd
│ ├── backtier
│ │ ├── internal
│ │ │ └── getdm
│ │ └── lib
│ ├── frontier
│ │ └── lib
│ └── garbagecollector
├── common
├── constant
├── matrix
├── taskqueue
└── tsp
├── bruteforce
└── heldkarp
bitstring: Contains algorithms for bit string manipulations intended to be used by Held & Karp algorithm (Dynamic Programming algorithm) for Travelling Salesman Problem.cmd/backtier: Contains the backbone logic of Back-Tier.cmd/backtier/internal/getdm: Contains a short program for testing Google Maps API.cmd/backtier/lib: Contains functions called by the backbone of Back-Tier.cmd/frontier: Contains the backbone logic of Front-Tier.cmd/frontier/lib: Contains functions called by the backbone of Front-Tier.cmd/garbagecollector: Contains the implementation of Front-Tier.cmd/common: Contains code shared by Front-Tier, Back-Tier, and Garbage Collector.cmd/constant: Contains constants used by the project.cmd/matrix: Contains algorithms for matrix operations intended to be used by Branch-and-Bound algorithm for Travelling Salesman Problem.cmd/taskqueue: Contains APIs for accessing the Task Queue.cmd/tsp/bruteforce: Contains a brute force algorithm (trying all permutations) for Travelling Salesman Problem.cmd/tsp/heldkarp: Contains an implementation of Held & Karp algorithm (Dynamic Programming) for Travelling Salesman Problem.
The project is mainly divided into 4 parts:
- Front-Tier (
frontier) - Task Queue (
taskqueue) - Back-Tier (
backtier) - Garbage Collector (
garbagecollector)
Front-Tier is an HTTP server responsible for accepting requests from the clients. There are 2 kinds of requests.
The first kind contains a starting location and a list of drop-off locations. The client would like to know the shortest driving path which begins from the starting location, and visits all drop-off locations once. After receiving a request from the client, Front-Tier generates a token and sends the Question to Task Queue for being retrieved by Back-Tier. It then sends back the token to the client immediately so that it could come back for the result.
The second kind contains a token. Front-Tier looks up Task Queue and returns the Answer to the client.
Task Queue deals with 3 kinds of entities:
Question is received from Front-Tier (and in turn, from the request of the client). It contains the starting location and a list of drop-off locations.
Answer is received from Back-Tier. It contains the status of the query, the shortest driving path, or the error occurred during the process.
Garbage is received from Back-Tier. It contains information to help cleaning up entries no longer useful in Task Queue.
Back-Tier is responsible for finding the solution for the query. After receiving a Question from Task Queue, it retrieves a distance matrix via the map provider. Then it calculates the shortest driving path by applying a Travelling Salsman algorithm. After that, it sends the Answer to Task Queue for being retrieved by Front-Tier.
Garbage Collector is responsible for cleaning up Task Queue. Questions and Answers that are too old are deleted to free the memory they used.
TODO: Write this (description)
Gorilla Mux implements an HTTP request router and dispatcher. It is used to implement Front-Tier.
- Website: http://www.gorillatoolkit.org/pkg/mux
- GitHub: https://github.com/gorilla/mux
Beanstalk is a simple, fast work queue (task queue / job queue). It is used to implement Task Queue.
- Website: https://kr.github.io/beanstalkd/
- GitHub (Server): https://github.com/kr/beanstalkd
- GitHub (Client): https://github.com/kr/beanstalk
Google Maps Distance Matrix API provides duration and distance values based on the recommended route between start and end points. It is used to implement Back-Tier.
- Website: https://developers.google.com/maps/documentation/distance-matrix/
- GitHub: https://github.com/googlemaps/google-maps-services-go
This package provides pure Go implementation of Universally Unique Identifier (UUID). It is used in the common package to generate new tokens.
Google Logging Module provides leveled execution logs for Go. It is used everywhere in the project. It is the main logging mechism.
- Write a connection pool for Task Queue.
- Orchestra to make the tiers to be-born if down.
- Implement Branch-and-Bound to support more locations, and use less memory, and use shorter execution time.
- Use the Golang
"context"mechanism to cascade runtime limits of each task.
TODO: Write this