This is a Python program to solve the Chinese postman problem.
Python 3.x and QGIS 3.x is required for the plugin to run.
Download the "Chinese Postman Solver", using the QGIS plugin manager.
- Clone this repository.
- Run
./install.sh.
Alternatively, run ./bundle.sh, and install the generated zip file as a plugin.
- Select the layer for which you want to solve the CPP.
- Select the features that you want to use. The "Select Features by Polygon" tool works great if you only want to use a small part of a large network.
- Run Plugins -> Chinese Postman -> Chinese Postman.
It should create a new layer with the results.
Requirements:
- Python2.7 or Python 3.x
- NetworkX
- Optionally, if you want to export PNG images from the command line (not needed for using the QGIS-plugin):
- Graphviz, and
- One of:
- For all NetworkX versions except 1.10: PyGraphviz (preferred), or
- For NetworkX <=1.10 and >=2.0: pydot, or
- For NetworkX 1.10 and 1.11: PyDotPlus
Input data file must be in CSV format, with each row containing the following columns:
- Start node ID
- End node ID
- Segment length in meters
- Segment name or ID
- Start longitude, for example 18.4167
- Start latitude, for example -33.9167
- End longitude
- End latitude
Example:
Start Node,End Node,Segment Length,Segment ID,Start Longitude,Start Latitude,End Longitude,End Latitude
1,13,57,Segment 1,18.4167,-33.9167,18.6532,-33.8561
13,22,80,Segment 2,18.6532,-33.8561,18.7650,-33.7930
Then run (assuming the file is saved as input.csv):
python postman.py --csv path.csv --gpx path.gpx input.csv
The segment ID and GPS coordinates in the input file are not used for any calculations, but are used for the CSV and GPX output.
Use option --png to create a graph visualization of the route in PNG image format:
python postman.py --csv path.csv --gpx path.gpx --png path.png input.csv
All code is licensed under The MIT License (MIT).