Objective functions are the criteria used to optimize routes. Under the hood, Pathfinder uses complex mathematics to determine the optimal route at any given time. However, to use Pathfinder it is not required to understand the underlying model. Instead, objective functions are specified using a Domain Specific Language (DSL). If this seems too complicated, don't fret! The Pathfinder dashboard contains two predefined objective functions that cover common use cases: minimizing distance and minimizing time.

Note that the "objective functions" described by this document are strictly speaking not objective functions. If you're interested in how Pathfinder transforms this DSL into mathematical expressions, you can read more about the DSL Compiler.

Concepts and Terminology

An objective function is a function from some variables to a real number and an instruction to either minimize or maximize that number. For Pathfinder, routes are calculated with cluster-granularity. The input to the objective function is the "route" for the cluster for the snapshot in time when it is calculated. There are three parts to a Pathfinder objective function: sense, context and quantity.

Sense

This is the instruction to either minimize or maximize the function.

Context

Since the input to the objective function is all of the routes for transports in the cluster, every objective function will involve iterating over the transports, the commodities or some Cartesian product of those sets. An expression is computed during the iteration and then either a sum, min or max is computed. This is essentially a "foreach loop" from most familiar programming languages.

For instance, I may want to minimize the maximum distance traveled by any transports. In this case, Pathfinder iterates over the set of transports and evaluates a maximum. "max" is referred to as the "method" and transports is referred to as the "entities".

Alternatively, I may want to minimize the total difference between commodity wait times. In this case, Pathfinder iterates over the set of all pairs of commodities and evaluates a sum. The method is "sum" and the entities are the Cartesian product of commodities with commodities.

Quantity

This is the value that will be computed for each iteration of the context. It is an algebraic combination of route variables, a few Pathfinder specific keyword quantities and parameters that are configured for your application and passed in via the metadata of transports and commodities.

The currently supported operations are absolute value, add, subtract, multiply and divide. This list is admittedly limited, however that is due to the need for the expression to be representable by a "linear combination" for Pathfinder's optimizer to function correctly.

Syntax

The Pathfinder DSL is a (very small) subset of YAML. Every objective function has the form

sense: <Sense>
context:
    method: <Method>
    for: <Entity Dictionary>
quantity:
    <Expression>

Sense

Sense = min | max

Context

Method = sum | min | max
Entity Dictionary =
    <name1>: commodity | transport
    <name2>: commodity | transport
    <name3>: commodity | transport

Quantity

Expression = Value | Evaluation

Evaluation =
    <Function>:
        - Quantity Expression
        ...
Value = Constant | <entity name>.<Property>
Constant = <Number> | <Global Keyword>
Property = <Entity Keyword> | <Parameter> 
Function = absolute_value | add | subtract | multiply | divide

Global Keywords

now - UTC timestamp when the route is calculated

Transport Keywords

distance - The route length for the transport
duration - The route duration for the transport

Commodity Keywords

request_time - The UTC timestamp for when the commodity was first set to Waiting status
pickup_time - The UTC timestamp for when the commodity will be picked up in the route
dropoff_time - The UTC timestamp for when the commodity will be dropped off in the route
distance - The distance that the commodity will travel according to the route

Parameters

These must be configured via the Pathfinder dashboard and included in the metadata for commodity or transports when they are created and updated via the SDKs. If the parameters are not present in the metadata, Pathfinder will make intelligent guesses (MAX_INT, MIN_INT, 0) based on your objective function. However, this is strongly discouraged.

Examples

For those who prefer concrete examples to context free grammars.

Minimize total transport distance

sense: min
context:
    method: sum
    for:
        t: transport
quantity: t.distance

Minimize total transport time

sense: min
context:
    method: sum
    for:
        t: transport
quantity: t.duration

Minimize max transport distance

sense: min
context:
    method: max
    for:
        t: transport
quantity: t.distance

Minimize max transport route duration

sense: min
context:
    method: max
    for:
        t: transport
quantity: t.duration

Minimize max time until passenger pickup

sense: min
context:
    method: max
    for:
        c: commodity
quantity: c.pickup_time

Minimize max fuel used by a transport

sense: min
context:
    method: sum
    for:
        t: transport
quantity:
    divide:
        - t.distance
        - t.mpg

Minimize total fuel used by transports

sense: min
context:
    method: sum
    for:
        t: transport
quantity:
    divide:
        - t.distance
        - t.mpg

Minimize max time until passenger dropoff

sense: min
context:
    - method: max
    - for:
        c: commodity
quantity:
    subtract:
        - c.dropoff_time
        - now

Minimize maximum time until dropoff including past wait time

sense: min
context:
    - method: max
    - for:
        c: commodity
quantity:
    subtract:
        - c.dropoff_time
        - c.request_time

Minimize time until pickup weighted by customer priority

sense: min
context:
    method: sum
    for:
        c: commodity
quantity:
    multiply:
        - subtract:
            - c.pickup_time
            - now
        - c.priority

Minimize total time from now until drop off weighted by customer priority

sense: min
context:
    method: sum
    for:
        c: commodity
quantity:
    multiply:
        - substract:
            - c.dropoff_time
            - now
        - c.priority

Minimize maximum distance traveled by commodity

    sense: min
    context:
        method: max
        for:
            c: commodity
    quantity: c.distance

Minimize maximum difference between passenger total wait times

sense: min
context:
    method: max
    for:
        c1: commodity
        c2: commodity
quantity:
    absolute_value:
        subtract:
            - subtract:
                - c1.dropoff_time
                - c1.request_time
            - subtract:
                - c2.dropoff_time
                - c2.dropoff_time

Minimize sum of differences between passenger total wait times

sense: min
context:
    method: sum
    for:
        c1: commodity
        c2: commodity
quantity:
    absolute_value:
        - subtract:
            - subtract:
                - c1.dropoff_time
                - c1.request_time
            - subtract:
                - c2.dropoff_time
                - c2.request_time