Routing Constraints

The MapAnything Routing Engine API allows the user to model many different tradeoffs in a complex vehicle routing problem by using constraints and penalties. The goal of the underlying optimization is to find the best feasible solution to your problem that minimizes the total penalty or score. For every constraint that is violated, the solution incurs a penalty, so the more important a constraint is to your problem, the higher the penalty should be. All constraints receive some mandatory parameters that provide the details on the type of constraint and how penalty is to be calculated. Detailed descriptions of all constraints can be found in the Constraint API Descriptions.

Nearly all problems seek to achieve at least two goals: visit as many stops as possible and minimize the total travel time of the involved vehicles. This is achieved by using the Visit_Range and Travel_Time constraints. In a simple problem where each order is to be visited one time, orders that are not visited are penalized by the Visit_Range constraint. The Travel_Time constraint can be expressed so that every second of travel by a vehicle incurs one unit of penalty.  This allows us to then think of these “penalty points” in terms of a vehicle traveling for one second – violating a constraint with a penalty of 10,000 is then equivalent to adding 10,000 total seconds of travel time to the fleet. For example, if we have a Visit_Range constraint with a penalty of 10,000, then MARE will seek to visit all orders unless they are more than 10,000 seconds “out of the way”. If it is absolutely essential to visit all orders then an even higher penalty can be used. However, eventually the solution may become constrained by not having enough time in the shifts or enough vehicles in the fleet, so that blindly increasing the penalties cannot guarantee that they are satisfied (we refer to this as penalty inflation).

Note that MARE can technically accept a problem/request with no constraints. If you send a routing request without any constraints, MARE will simply return the first solution it finds (which may be a “solution” with no orders routed). For the vast majority of cases, this will not be meaningful and the Visit_Range and Travel_Time constraints should almost always be included in a request. You will need to carefully analyze your use case to decide which objectives are most important and how to penalize them with MARE’s constraints. Many examples are provided to illustrate a variety of use cases that incorporate different constraints and penalties.