Fundamental Concepts

A request to the MARE Routing API consists of the following fundamental objects:

Locations: These are the physical places where you’re actually routing. These consist of latitude / longitude pairs and a location_id for each location.

Orders: You can think of an order as a request for service at some location. Perhaps a large flatbed truck is delivering lumber to a hardware store so that the quantity of lumber and unloading time are relevant. Alternatively, a school bus may be picking up and dropping off passengers with very tight time limits around the pickup and dropoff time at each bus stop. Or an order may represent a sales lead to be visited a certain number of times over a quarter. All these types of service are encapsulated as orders with different attributes that describe the specifics of the service request.
An order may have additional properties: how long to satisfy it, how often it needs to be serviced, pickup / delivery quantities, priorities, urgency, attributes, fixed appointments, and so on. Additionally, in cases where a single order requires multiple visits, this can be represented with a single order object as in this example.

Vehicles: MARE accepts vehicles of various types: “car”, “truck”, “bike”, and “pedestrian”. For problems involving trucks with various height and weight restrictions, we are able to determine compliant routes for these vehicles. Currently, only one vehicle type may be specified, so that vehicles are either all cars, or all trucks, etc. Vehicles may also have attributes such as “bucket truck” or even sets of attributes associated with the driver of the vehicle such as {“plumber”,”electrician”}. This can allow for skill matching in the solution of the underlying problem. One must specify periods of activity of the vehicle by defining shifts.

Shifts: A shift represents a continuous period of time during which a vehicle may travel, take breaks, and service orders. This shift can be a few hours, a day, a week, or even a year. The shift can be broken up by breaks which are time periods when the vehicle must be stopped and not servicing orders. Alternatively, a soft break can be specified – this is a period of time during which the vehicle can be moving, but not servicing an order. MARE even supports the notion of a floating break where a break of a certain duration must occur during a pre-defined window. A shift can also specify either a start location, an end location, or both or neither. In this latter case, the optimization will determine where a shift should start and end. This flexible notion of a shift can be useful when solving problems with long planning horizons. For example, an entire week can be scheduled as a single 24*5=120 hour shift with 10 hour breaks at night for sleep, allowing a vehicle to be routed over a large geographical area where the end location on one day determines the start location on the next day.

Constraints: While minimizing the number of required vehicles and decreasing total travel time are often a primary goal in many routing problems, there are often other objectives in play and many tradeoffs must be considered. For example, a salesperson may be able to visit five more orders in a day, but this may lead to a missed time window at another customer and decreased visits at other high priority customers. Instead of hiding these underlying tradeoffs from the user, we choose to expose many different parameters and constraint types to the user to provide you the ultimate flexibility and power in how you can model and solve these problems. This leads to the final primary concept in MARE, the constraint. MARE allows you to control the nuances of a solution to your routing problem via our rich and ever-growing constraint library. This allows the user to account for a variety of features in the solution.

Items (optional):  In problems that involve the pickup and delivery of objects, these are required to be items that are defined at the top level. Each item has an item_id as well as an optional volume and weight. Vehicles then have their capacity defined in a variety of ways – how much of each item they can carry, how much volume they can hold, how much weight they can carry.

Forced Routes (optional): If the sequence of stops is forced or locked in place, then MARE will simply compute the travel times and other route metrics and not perform any optimization. See these examples.

Times, Timezones, and Units: For consistency’s sake, MARE expresses all time in terms of ISO 8601 and all times are converted to absolute times (Unix time which is the number of seconds since 1970). If a string expression of a time sent to MARE includes a timezone offset, then this is used when converting to absolute time. If no timezone is given, then MARE attempts to associate that particular time with a location and then the timezone of that location is used when converting to absolute time. MARE has its own timezone service to determine that information with the most up to date information available. All units used are metric, with distance in meters. Travel times are always returned in seconds.