The Routing Optimization service allows users to model many different tradeoffs in a complex vehicle routing problem using constraints and penalties. The underlying optimization goal is to find the best feasible solution to your problem that minimizes the total number of penalty points. For every constraint violated, the solution incurs a penalty, so the more critical a constraint is to your problem, the higher the penalty should be.
The optimization engine can accept a problem with no constraints. Still, it returns the first solution it finds (which may be a "solution" with no orders routed). Receiving a simple, initial solution is not a meaningful or useful exercise! So a routing problem should always specify constraints. Detailed descriptions of all constraints are in the linked sections below.
For example, let us consider the nearly universal goals in routing optimization problems of seeking to visit all stops and minimize travel time. In a simple problem where each order is to be visited one time:
- We penalize orders that are not visited using the
- We penalize travel times using the
Suppose we have a
visit_range constraint with a penalty of 1000. In that case, the optimization engine seeks to visit all orders unless they are more than 1000 seconds "out of the way." If it is essential to see all orders, then an even higher penalty can be used, for example, 100,000 or even 1,000,000. However, eventually, the solution may become constrained by not having enough time in the fleet's shifts or enough vehicles. Blindly increasing the penalties cannot guarantee that they are satisfied.
The Routing Optimization service offers various constraints to control multiple aspects of the solutions returned by the underlying optimization engine. These controls loosely divided into three categories:
- Solution Level — Control global properties such as total travel time or the number of routes.
- Route Level — Control individual route features such as the number of stops, stop sequence, or total working time.
- Order Level — Control treatment of orders such as obeying time windows, appointments, and priorities.
- Vehicle Level — Control treatment of vehicles such as obeying work speed.
For each constraint category, we provide a list of all supported constraints, a description of each, and an example showing how the constraint impacts a routing problem solution.
Requests to the Optimization API routing service can include an array of
constraint objects that describe constraints used to control the routing solution. If there are no
constraints, a set of defaults is defined for your problem by the optimization engine.