Background:
This API provides an exact solution to the traveling-salesperson problem, using the Held-Karp algorithm.. In addition to the classic problem that optimizes a closed ("Hamiltonian") path, this algorithm also optimizes open paths (for which the starting/ending locations may or may not be specified) or paths which are subject to certain constraints (e.g., Town-A must be visited prior to Town-B).
Instructions: (General)
For each endpoint except for the random ones, the user inputs the location list in a particular order, and this order matters for the remaining two bullets. For random ones, you may view many different results simply by repeatedly clicking your browser's refresh button.
:isOpen, :isFirstFixed, and :isLastFixed are booleans. The first specifies whether or not this is a Hamiltonian path. If :isOpen is false, the remaining two booleans are ignored. If :isOpen is true, then either :isFirstFixed or :isLastFixed constitute a constraint if it true. If :isFirstFixed is true, the path must start at the first location specified by the user. If :isLastFixed is true, the path must end at the last one in the list. The user may indicate that a boolean's value is truthy with either T, TRUE, True, or true, or analogously for the falsy one.
:contraints is a (possibly empty) array of 2-element arrays. Each of these 2-element arrays specifies a separate constraint about the sequencing of visits to two locations, because both elements of this array are integers that specify locations. For instance the constraint [7,4] means that location-7 must be visited prior to location-4.
Endpoints:
/matrix/:isOpen/:isFirstFixed/:isLastFixed/:matrix/:constraints
This is the most basic endpoint, in which :matrix is the cost matrix for this list of locations. The matrix is square, and the i-j element of this matrix indicates the "cost" of going from location-i to location-j. The diagonal elements of this matrix are zero. Note actually that I make each element an object having two fields: costs and path. The former is an array of numbers. In this array the first element is the most important cost, in that it defines the quantity being minimized in a route's optimization (e.g., duration). Any subsequent elements indicate secondary costs (e.g., miles or tolls). The path field contains an array of 2-element inner arrays, with each element of the inner array representing a waypoint along the path between location-i and location-j. For simple implementations path consists of only two points: location-i and location-j (expressed in longitude-latitude form). For real driving paths this is usually a larger array.
/coordinates/:isOpen/:isFirstFixed/:isLastFixed/:coordinateSets/:constraints
For this endpoint each location is specified geometrically by two coordinates. The user may also provide a third element in the coordinate set, to serve as a string labelling the location. (If none is provided, this role will simply be filled by the location's index.) Each element of the cost matrix will then simply be the straight-line distance between the two points.
/errands-random/:isOpen/:isFirstFixed/:isLastFixed/:numberOfErrands
This endpoint randomly sets the coordinates of a specified number (= :numberOfErrands) of locations. Because of the randomness of the points' locations, there is no allowance here for specifying a sequencing constraint. The optimal path should contain no crossings.
/shipments-random/:numberOfShipments/:priority
The purpose of this endpoint is to optimize the path taken by a vehicle that picks up and drops off a specified number (= :numberOfShipments) of "shipments" (which may be considered as either people or objects) along a closed path. Like the previous endpoint, it randomly generates the coordinates of these locations. Unlike the previous endpoint, it (of course) incorporates the constraints that the vehicle must visit the pick-up location for a shipment prior to visiting the drop-off location of that shipment. The :priority quantity should be comparable to (or even larger than) 1 for the case of time-conscious shipments such as people, or smaller than 1 (or even zero) for objects. Note that low values of :priority may result in a shipment travelling a considerable distance between pick-up and drop-off.
/cities-random/:isOpen/:isFirstFixed/:isLastFixed/:numberOfCities
The cost matrix for this endpoint is constructed with drive times (primary cost) and distances (secondary cost) fetched from the Google Routes API. To control costs, I limit this to pre-fetched values for largest cities in each of the contiguous 48 states (plus DC). The user-specified number (= :numberOfCities) of these is chosen randomly. The matrix for this includes the path field which is an approximation (to save storage) for the actual one returned by Google's API.
NOTE: Type /api before any of these url fragments listed above if you want the results in json rather than in html.