{"_id":"56a98367257fbc0d00d47627","__v":4,"parentDoc":null,"user":"56a83a6070a9440d00ef5ef8","githubsync":"","category":{"_id":"56a9706013a69a0d00a778c3","project":"56a83b979ec7660d002e07be","pages":["56a970a1cc0f740d005bc15d","56a97494ca491e0d00eb8aaa","56a98367257fbc0d00d47627"],"version":"56a83b989ec7660d002e07c1","__v":3,"sync":{"url":"","isSync":false},"reference":false,"createdAt":"2016-01-28T01:35:28.486Z","from_sync":false,"order":3,"slug":"mathematical-model","title":"Mathematical Model"},"project":"56a83b979ec7660d002e07be","version":{"_id":"56a83b989ec7660d002e07c1","project":"56a83b979ec7660d002e07be","__v":9,"createdAt":"2016-01-27T03:38:00.333Z","releaseDate":"2016-01-27T03:38:00.333Z","categories":["56a83b989ec7660d002e07c2","56a83c282036420d002d21e1","56a96de8f834950d0037b35a","56a9706013a69a0d00a778c3","56a970ec2d8fd90d0036eec7","56a971a62bb3910d000ee934","56a973372d8fd90d0036eece","56a978dc2bb3910d000ee93f","571d5ae118b3c10e003e55cd"],"is_deprecated":false,"is_hidden":false,"is_beta":false,"is_stable":true,"codename":"Beta","version_clean":"1.0.0","version":"1.0"},"updates":[],"next":{"pages":[],"description":""},"createdAt":"2016-01-28T02:56:39.308Z","link_external":false,"link_url":"","sync_unique":"","hidden":false,"api":{"results":{"codes":[]},"settings":"","auth":"required","params":[],"url":""},"isReference":false,"order":0,"body":"<div class=\"corner-ribbon top-left sticky blue\"><a style=\"color: white;\" href=\"https://pathfinder.readme.io/blog/pathfinder-now-in-public-beta\">Public Beta!</a></div>\n\nAt the core of Pathfinder is the Traveling Salesman Problem.\n\n## Cluster\nA 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.\n\nEach vertex in this set is referred to as a route action. The cluster's route actions are divided into subsets as follows.\n\n    TA = transport start actions\n    PA = commodity pickup actions\n    DA = commodity dropoff action\n    CA = commodity actions = PA + DA\n    RA = route actions = TA + CA = the cluster\n\nEach vertex is augmented by a capacity vector.\n\nIn 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\".\n\n## Route\nA route is a partition of the set of route actions for a cluster into disjoint directed paths. This partition follows the following rules.\n\n    1. Every path must start with a transport action\n    2. Every transport action must start its own path\n    3. Every commodity pickup action must be in the same path and sequentially before its corresponding dropoff action\n    4. Each component of the sum of the capacity vectors up to each vertex along a path must be nonnegative\n\n## Variables\n\nThese binary variable sufficiently describe a route as described in the previous section\n\n    x[k1,k2,i], k1 ∈ RA, k2 ∈ RA, i ∈ TA = transport i's path contains an edge from k1 to k2\n\n## Parameters\n\n    distances[k1,k2], k1 ∈ RA, k2 ∈ RA = driving distance in meters from k1 to k2\n    durations[k1,k2], k1 ∈ RA, k2 ∈ RA = driving duration in seconds from k1 to k2\n    request_time[d], d ∈ DA = the time that commodity with dropoff d originally requested transportation\n\n## Supplementary Variables\n\nThese 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\n\n    y[k1,k2,i], k1 ∈ RA, k2 ∈ RA, i ∈ TA = transport i's path contains a subpath from k1 to k2\n    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\n    distance[i], i ∈ TA = the distance of transport i's path\n    duration[i], i ∈ TA = the duration of transport i's path\n    distance[d], d ∈ DA = The distance traveled by the commodity dropped off at d\n    duration[d], d ∈ DA = The in transit by the commodity dropped off at d\n    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\n    dropoff_time[d], d ∈ DA = The time that commodity d dropped off at d will be dropped off","excerpt":"","slug":"route-optimization-as-a-linear-program","type":"basic","title":"Route Optimization"}

Route Optimization


<div class="corner-ribbon top-left sticky blue"><a style="color: white;" href="https://pathfinder.readme.io/blog/pathfinder-now-in-public-beta">Public Beta!</a></div> 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