Route-sota

The route-sota project is an implementation intended to test, examine, and measure the research results of the paper "Efficient Stochastic Routing in Path-Centric Uncertain Road Networks".

This readme is composed of 3 parts:

Folder overview: Explains what types of files can be found where in the project.
User guide: Gives both a quick guide and a detailed guide for how to transform raw data into routing information.
File overview. Describes what programs in the project requires which files, and where they come from.

Folder overview

The program is split into three important directories:

data
- Contains the files used to generate new files and those generated files. It is split into 3 levels of directories.
  1. The data/ directory contains files concerning themselves with geographic data and time measurements, such as trajectories, graph descriptions, and queries for routing.
  2. The first level of under-directories directly under data/ contains the files generated based on chosen trajectories and geographic locations, as well as the number of threads used to generate these, as that results in different files and processing thereof.
  3. The under-directories can contain a set of one or more under-directories themselves, which files vary depending on the chosen sigma value and the chosen queries to pursue. Note that queries are used to "limit" get_policy_u.py to relevant vertices, not for any actual computation.
generate
- Contains the programs used to generate the files necessary for the routing algorithms. Contains 5 programs of import. For a detailed explanation of their usage, see the user guide. It also contains some shell-files that can be used to run the files, but it is more useful to manually run each individual python file as a number of manual edits are needed inside each for any modifications or changes.
  - get_overlap.py
  - get_policy_U.py
  - get_tpath.py
  - get_vpath.py
  - get_vpath_desty.py
routing
- Contains the routing algorithms that the project uses. Note that it contains both the python files and shell-files to run said files. The python files require manual adjustments and modifications for any most changes, so it is advised to run the python files manually. See the paper for "Efficient Stochastic Routing in Path-Centric Uncertain Road Networks" for descriptions of what each is.
  - T-B-E.py
  - T-B-EU.py
  - T-B-P.py
  - T-BS.py
  - T-None.py
  - V-B-P.py
  - V-BS.py
  - V-None.py

The project still includes the old readmes. See the readme in each of the above three folders or the file OLDREADME.md.

User guide

Quick guide

Requirements:

CSV file of trajectories
- See detailed guide
Speedfile ala AAL_NGR
- Unknown at time of writing how to reproduce. A file for Aalborg was contained in the original project, but its exact nature is unknown.
Vertices.txt
- A csv-like list of all vertices in the graph that is to be used.
- Tab-separated file containing 3 columns
  - vertex id, longitude, latitude
Queries.txt
- Binary file of queries between start and end nodes. Nodes are by ID.

Run "get_tpath"
Run "get_overlap"
Run "get_vpath"
Run "get_vpath_desty"
Run "get_policy_U"
Run your routing algorithm of choice

Detailed guide

Decide on a common subpath in all the files. This is where the files that you are/will be using will be stored.

Download trajectory dataset in the form of a .csv file

Code demands a certain schema for the data

Column name	Type
id	bigint
ntrip_id	bigint
trip_id	bigint
start_time	timestamp without time zone
end_time	timestamp without time zone
vehicle_id	integer
seg_id	text
seq_id	integer
travel_time	integer

The table "trips_short" on the "au_db" databse nearly has the same schema, but has since the original creation of the program been extended with two additional columns, which must be excluded in order to use it, as they will cause the program to fail if included.

Download and structure vertices.txt file
1. format of file should be a tab-separeted file with 3 "columns"
  1. First column is vertex id
  2. Second is longitude
  3. Third is latitude
2. The table "vertices" in the "au_db" database has the correct schema. For a quick file-setup, query the data from the db, and then do a dirty find-and-replace all , with \t
You must also have what the program calls a "speedfile" or "the city map". The file included in the original test data is AAL_NGR.
Running "get_tpath.py"
Running "get_overlap.py"
Running "get_vpath"
Running "get_vpath_desty.py"
Running "get_policy_U.py"

You now have All the files you need to run the routing algorithms. Before running one, remember to set all the paths and values to those that you desire.

file overview

Below table shows an overview of what files are produced and needed for what generator programs.

Program	Requirements	Produces
get_vpath_desty	*.csv path_travel_time_%d.json path_desty%d.json	M_edge_desty.json
get_vpath	AAL_NGR *.csv path_desty%d.json path_count%d.json overlap%d.txt vertices.txt	KKdesty_num_%d.json KKgraph_%d.txt
get_overlap	*.csv path_travel_time_%d.json	path_count%d.json path_desty%d.json overlap%d.json
get_tpath	*.csv	path_travel_time_%d.json
get_policy_U	*.csv KKdesty_num_%d.json M_edge_desty.json KKgraph_%d.json AAL_NGR queries.txt	u_mul_matrix_sig%d/ %d

The below table shows which files are necessary for what routing algorithms. The sigma, eta, and time_budget values are used to adjust some of the algorithms, as can be read about in the paper "Efficient Stochastic Routing in Path-Centric Uncertain Road Networks". Some of the possible eta values programmed into the code are found using an approximate function, and can therefore be invalid, but that is unknown at time of writing.