Constraint Library

Introduction

The Routing Optimization service allows users 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 number of penalty points. 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.

The optimization engine can accept a problem with no constraints, but, it will simply return the first solution it finds (which may be a “solution” with no orders routed). This is clearly not a meaningful or useful exercise! So constraints should always be specified in a routing problem. Detailed descriptions of all constraints can be found in the linked sections below and the associated examples.

As an 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:

  1. We penalize orders that are not visited using the visit_range constraint.
  2. We penalize travel times using the travel_time constraint.

If we have a visit_range constraint with a penalty of 1000, then the optimization engine will seek to visit all orders unless they are more than 1000 seconds “out of the way.” If it is absolutely essential to visit 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 shifts or enough vehicles in the fleet, so that blindly increasing the penalties cannot guarantee that they are satisfied.

Control Levels

The Routing Optimization service offers a variety of constraints to control various aspects of the solutions returned by the underlying optimization engine. These controls can be loosely divided into three categories:

  1. Solution Level — Control global properties such as total travel time or the number of routes.

  2. Order Level — Control treatment of orders such as obeying time windows, appointments, and priorities.

  3. Route Level — Control individual route features such as the number of stops, stop sequence, or total working time.

For each constraint category, we provide a list of all the currently supported constraints, a description of each constraint, and in many cases a detailed example that shows how the inclusion of the constraint in a routing problem helps to shape the solution in a particular way.