Awesome Docker Compose

ibrahim ethem demirci — Wed, 04 Sep 2019 21:21:05 +0000

I created a docker-compose files repository on Github, named as Awesome Docker Compose. Run a well-prepared applications stack with just a single command. Any contributions are welcome! Let your precious hidden stack help the community!

Check it on here.

Galois: An auto-completer for code editors based on OpenAI GPT-2.

ibrahim ethem demirci — Thu, 15 Aug 2019 09:40:18 +0000

Today I introduce Galois (/ɡælˈwɑː/) which is an open-source auto code completer based on OpenAI GPT-2 .

Galois is trained (finetuned) on a curated list of approximately 45K Python (~470MB) files gathered from the Github. Currently, it just works properly on Python but not bad at other languages (thanks to GPT-2's power).

With this project, I aim to create a Deep Learning Based Auto-completer such that anyone can run it on their own computer easily. I originally inspired by TabNine but wanted to make Galois can be run on endusers computer, freely (as in freedom). Thus anyone (especially developers) can benefit from state-of-the-art NLP technologies freely without sharing the codes (or texts) with a server. To fulfill this purpose we need to do the same what EfficientNet did to achieve state-of-the-art results in many datasets. For now, Galois trained on GPT-2 345M without developing such an efficient deep learning model. Check the planned works here for the future of Galois.

You can try it on usegalois.com. It is licensed under MIT, so you can find the trained model, codes and some instructions on github.com/iedmrc/galois-autocompleter for Galois, and on github.com/iedmrc/galois-web for the online editor. Check the link here for the docker-compose file .

Any contributions are welcome. The technology behind the Galois has been developed by the community for many years. So clearly we can say that it belongs to the community.

To democratize the AI, let's spread the word to the world! Have it, use it, contribute to it, share it!

With respect to Évariste Galois ([evaʁist ɡalwa]).

Vehicle Routing Problems And How To Solve Them

ibrahim ethem demirci — Wed, 14 Aug 2019 14:45:50 +0000

Vehicle Routing Problems

Vehicle routing problems (VRP) are essential in logistics. As the name suggests, vehicle routing problems come to exist when we have N vehicle to visit M nodes on any map.

A figure illustrating the vehicle routing problem

We could say VRPs are a subset of Traveling Salesman Problem (TSP). In general, it looks like that:

CVRP, VRPTW ⊆ SVRP, DVRP ⊆ VRP ⊆ TSP ⊆ Graph Theory

CVRP: If you have vehicles restricted by any capacity (e.g. max loading limit) constraint, then we call it Capacitated Vehicle Routing Problem (CVRP)

VRPTW: If you have vehicles restricted with working times, then we call it Vehicle Routing Problem with Time Windows (VRPTW)

SVRP: If the visiting points (nodes) are given, then we call it Static Vehicle Routing Problem

DVRP: If the visiting points (nodes) come to exist while trying to solve or moving on the map, then we call it Dynamic Vehicle Routing Problem

Confused ? 🤔

Here is a map showing the relationship between common VRP subproblems, from Wikipedia.

Graph Theory and VRP Solvers

The leading actor is Graph Theory. It all started with the "The Seven Bridges of Königsberg" question being asked to Euler.
Today we ask more sophisticated questions such as "How are all packages delivered to their addresses in the most efficient way?".

There are many ways to solve a VRP. Heuristics, Constructive Methods, 2-Phase Algorithms, Metaheuristics and more are general methods for VRPs. See here for more information.

Today we have enough compute power to run iterative solutions or optimizers that take long times while solving VRPs with computers.

Real World Map, Routes and Solving on

Open Street Map

So far we have described the problem and introduced some solutions but what about the roads & routes on the real world map? One can think about Google Maps, Yandex Maps, HERE Maps etc.. They are all good but also commercial. Thanks to OpenStreetMap (OSM) and the community, we have a very big and useful real world map updated every week.

Open Source Routing Machine

OpenStreetMap just provides the real world map, not routes and therefore we need something else to give us the routes, distances, durations etc.. Oh, what's that Open Source Routing Machine (OSRM)? You guess right, we love free (as in freedom) software! OSRM uses OpenStreetMap as (map) backend and has the following features:

Nearest - Snaps coordinates to the street network and returns the nearest matches
Route - Finds the fastest route between coordinates
Table - Computes the duration or distances of the fastest route between all pairs of supplied coordinates
Match - Snaps noisy GPS traces to the road network in the most plausible way
Trip - Solves the Traveling Salesman Problem using a greedy heuristic
Tile - Generates Mapbox Vector Tiles with internal routing metadata

Now we can fetch the routes between all the nodes and then run a VRP solver algorithm to have optimized (the fastest or the shortest) sequence of routes of nodes.

But wait! Send me more open source, please! 😂

Vehicle Routing Open-source Optimization Machine

Vehicle Routing Open-source Optimization Machine (VROOM) is a VRP solver. It uses OSRM or OpenRouteService (OSR) as backend to get routes and returns solutions for CVRP, VRPTW, CVRPTW problems. It also has a nice UI (frontend) to show vehicles, nodes and routes on the map.

You should note that VROOM's objective is optimizing the overall duration, not the overall distance. Hence you might need to find another open source solution or write your own in order to calculate the shortest path.

Talk is Cheap Show Me the Code!

Preparing Dependencies in the Traditional Way

That means, without docker. I suggest you jump to the non-traditional.

Running OSRM With an OSM Map

To build OSRM for your OS and architecture follow this guide .

Then, you need to download an OSM map and process it for OSRM. Next, you can run the OSRM backend. Follow this guide to achieve them all.

Running VROOM Backend and Exposing the API

Clone and build VROOM according to this guide. Make sure you have vroom binary in your path (environment variable).

Thus far, we had a routing machine (OSRM) with a map (OSM), and a VRP solver (VROOM) which uses them. We can call VROOM with proper parameters through CLI and have the calculated result. However, it is easier to interact with VROOM via the Node.js HTTP API.

Okay then, let's install and run VROOM Express.js API. It is very easy. Just clone the repository and follow the guide here. One caveat: Don't forget to configure via config.js, before running. You might want to change the MAX_JOBS, MAX_VEHICLES, PORT or routingServers values.

Preparing Dependencies via Docker

First, download an OSM map and process it with dockerized OSRM through this simple guide. But don't run the OSRM as in the last command. Because from now on, we'll use docker-compose with the following compose file:

%[https://gist.github.com/iedmrc/51d02fefa9e3ee91a5608c02c452c965]

Adjust the command and volume parameters to your own. If you wish to edit config files of VROOM backend, clone this repository and build your own image. You can do the same for VROOM frontend by cloning this repository. These repositories are the images I prepared for VROOM backend and frontend. I recommend you to review them.

Fire it up!

docker-compose up -d

One caveat: If you use Docker for Mac, you may need to increase the default Docker resources. I have reserved the following resources for Docker:

CPUs: 4
Memory: 6 GiB
Swap: 2.0 GiB

Links to docker files:

VROOM backend docker repository: https://github.com/iedmrc/vroom-docker
VROOM frontend docker repository: https://github.com/iedmrc/vroom-frontend-docker

Solving VRP via Direct API Request

Now you can have the VRP solved by making a request to VROOM Express API with a JSON payload attached according to this API guide.

An example request:

curl 'http://localhost:3000/' -H 'Content-type: application/json' --data-binary \
'{ "jobs": [ { "id": 1613, "service": 1200, "amount": [ 1 ], "location": [ 29.02988, 40.99423 ] }, { "id": 1665, "service": 1200, "amount": [ 1 ], "location": [ 29.216, 41.008520000000004 ] }, { "id": 21234, "service": 900, "amount": [ 1 ], "location": [ 29.272640000000003, 40.94765 ] }, { "id": 23457, "service": 600, "amount": [ 1 ], "location": [ 29.119659999999996, 40.97359 ] }, { "id": 24145, "service": 900, "amount": [ 1 ], "location": [ 29.16579, 40.925540000000005 ] }, { "id": 33007, "service": 900, "amount": [ 1 ], "location": [ 29.123801, 40.978068 ] }, { "id": 38081, "service": 600, "amount": [ 1 ], "location": [ 29.113429999999997, 40.980259999999994 ] }, { "id": 39163, "service": 900, "amount": [ 1 ], "location": [ 29.25528, 40.87539 ] } ], "vehicles": [ { "id": 7, "start": [ 29.208498, 40.890795 ], "end": [ 29.208498, 40.890795 ], "capacity": [ 25 ], "time_window": [ 30600, 61200 ], "startDescription": "Start", "endDescription": "End" } ], "options": { "g": true }}' --compressed

The response:

{
  "code": 0,
  "summary": {
    "cost": 4387,
    "unassigned": 0,
    "amount": [8],
    "service": 7200,
    "duration": 4387,
    "waiting_time": 0,
    "distance": 72452,
    "computing_times": {"loading": 28,"solving": 4,"routing": 10}
  },
  "unassigned": [],
  "routes": [{
      "vehicle": 7,
      "cost": 4387,
      "amount": [8],
      "service": 7200,
      "duration": 4387,
      "waiting_time": 0,
      "distance": 72452,
      "steps": [{
          "type": "start",
          "location": [29.208498,40.890795],
          "arrival": 30600,
          "duration": 0,
          "distance": 0
        },{
          "type": "job",
          "location": [29.16579,40.925540000000005],
          "job": 24145,
          "service": 900,
          "waiting_time": 0,
          "arrival": 31064,
          "duration": 464,
          "distance": 8110
        },{
          "type": "job",
          "location": [29.02988,40.99423],
          "job": 1613,
          "service": 1200,
          "waiting_time": 0,
          "arrival": 32854,
          "duration": 1354,
          "distance": 25277
        },{
          "type": "job",
          "location": [29.113429999999997,40.980259999999994],
          "job": 38081,
          "service": 600,
          "waiting_time": 0,
          "arrival": 34586,
          "duration": 1886,
          "distance": 34414
        },{
          "type": "job",
          "location": [29.123801,40.978068],
          "job": 33007,
          "service": 900,
          "waiting_time": 0,
          "arrival": 35260,
          "duration": 1960,
          "distance": 35539
        },{
          "type": "job",
          "location": [29.119659999999996,40.97359],
          "job": 23457,
          "service": 600,
          "waiting_time": 0,
          "arrival": 36215,
          "duration": 2015,
          "distance": 36533
        },{
          "type": "job",
          "location": [29.216,41.00852],
          "job": 1665,
          "service": 1200,
          "waiting_time": 0,
          "arrival": 37454,
          "duration": 2654,
          "distance": 47712
        },{
          "type": "job",
          "location": [29.272640000000003,40.94765],
          "job": 21234,
          "service": 900,
          "waiting_time": 0,
          "arrival": 39281,
          "duration": 3281,
          "distance": 57059
        },{
          "type": "job",
          "location": [29.25528,40.87539],
          "job": 39163,
          "service": 900,
          "waiting_time": 0,
          "arrival": 41007,
          "duration": 4107,
          "distance": 67891
        },{
          "type": "end",
          "location": [29.208498,40.890795],
          "arrival": 42187,
          "duration": 4387,
          "distance": 72452
        }
      ]}
  ]}

Solving VRP via Frontend

If you have run the VROOM frontend either via docker-compose or via compiling manually, by uploading the JSON you prepared, you can make VROOM solve the VRP.

A screenshot of VROOM frontend

Final Overview

Download an OSM map here (or wherever you want).
Build OSRM binaries and process .osm file with docker or as described here.
Build VROOM binary and make sure it is in the path.
Run OSRM HTTP Server to listen port 5000 (or whichever you want).
Configure VROOM Express.js API to use the VROOM binary at the path, and to connect to OSRM HTTP Server via the port it listens.
Run the VROOM Express.js API to listen port 3000 (or whichever you want).
Make a JSON file as described here.
Make HTTP request to VROOM Express.js with the JSON file you prepared.
[Optional] Configure VROOM frontend to connect to VROOM Express.js API and run it to listen port 9966 (or whichever you want).

In conclusion

Vehicle routing problems are a very valuable and still active area of research, especially in logistics. The community has good solutions for it. Here we combined them and solved the problem.

If you have any questions, feel free to ask! And please spread the word! 🙏🏼

DEV Community: ibrahim ethem demirci