Route Optimization

At the core of Pathfinder is the Traveling Salesman Problem.

Cluster

A cluster is a set of vertexes. Each transport starting location, commodity pickup location and commodity dropoff location is a vertex. If a commodity is currently in transit by a transport, then it will have a drop off vertex, but not a pickup vertex.

Each vertex in this set is referred to as a route action. The cluster's route actions are divided into subsets as follows.

TA = transport start actions
PA = commodity pickup actions
DA = commodity dropoff action
CA = commodity actions = PA + DA
RA = route actions = TA + CA = the cluster

Each vertex is augmented by a capacity vector.

In this document, a transport start action is used synonymously with "a transport" and a commodity (pickup or dropoff) action is used synonymously with "a commodity".

Route

A route is a partition of the set of route actions for a cluster into disjoint directed paths. This partition follows the following rules.

1. Every path must start with a transport action
2. Every transport action must start its own path
3. Every commodity pickup action must be in the same path and sequentially before its corresponding dropoff action
4. Each component of the sum of the capacity vectors up to each vertex along a path must be nonnegative

Variables

These binary variable sufficiently describe a route as described in the previous section

x[k1,k2,i], k1 ∈ RA, k2 ∈ RA, i ∈ TA = transport i's path contains an edge from k1 to k2

Parameters

distances[k1,k2], k1 ∈ RA, k2 ∈ RA = driving distance in meters from k1 to k2
durations[k1,k2], k1 ∈ RA, k2 ∈ RA = driving duration in seconds from k1 to k2
request_time[d], d ∈ DA = the time that commodity with dropoff d originally requested transportation

Supplementary Variables

These variables are not strictly necessary to compute a route, but they are derived from the variables and parameters previously listed and they help in forming complex objective functions

y[k1,k2,i], k1 ∈ RA, k2 ∈ RA, i ∈ TA = transport i's path contains a subpath from k1 to k2
z[k1,k2,k3], k1 ∈ RA, k2 ∈ RA, k3 ∈ TA = the subpath from a transport to commodity action k3 contains an edge from k1 to k2
distance[i], i ∈ TA = the distance of transport i's path
duration[i], i ∈ TA = the duration of transport i's path
distance[d], d ∈ DA = The distance traveled by the commodity dropped off at d
duration[d], d ∈ DA = The in transit by the commodity dropped off at d
pickup_time[d], d ∈ DA = The time that the commodity dropped off at d will be picked up or 0 if it has already been picked up
dropoff_time[d], d ∈ DA = The time that commodity d dropped off at d will be dropped off