Introduction

On top of drivers and jobs, a routing can also have a number of constraints that need to be satisfied. For example, there might be a restriction that a certain type of vehicle cannot carry more than a certain number of boxes. These constraints can take two forms, where some of them must be satisfied, while for others, simply trying to optimize their values suffice. The example of the former would be a capacity constraint, and the example of the latter would be a distance constraint. These conditions are modelled as "hard constraint" and "soft constraint" respectively. You can designate which set of constraints should be hard, and which should be soft.

Also, not all of the constraints should carry the same weight, as their values can vary greatly. For example, because the capacity constraint is either satisfied or not, its value can be either 1 or 0. On the other hand, the value of the distance constraint is defined as the sum of the travel distances among all drivers, and as a result, the range and the magnitude of its value would be markedly different from that of the capacity constraint. Thus, you can also specify the weight for each of the constraints. Note that the "cost" of the solution is a linear combination of the constraints' values.

In the following section, we list all available constraints, along with the required parameters and how their values are determined. If the constraint doesn't have any other parameter, you only have to provide the name of the constraint in "type" field and the weight of the constraint in "constraint" field. For example, Capacity Constraint, which does not take any parameter, can be specified as:

{
  "type"   : "CapacityConstraint",
  "weight" : 1.0
}

On the other hand, Balance Constraint can be specified as:

{
  "type": "BalanceConstraint",
  "weight": 20.0,
  "equation": [
    [
      2.0,
      [ "Task", "Task" ]
    ],
    [
      3.0,
      [ "Distance" ]
    ]
  ]
}

List of all available constraints

Balance Constraint

Balance constraint is, in essence, a requirement that all routes should have the same value for some equation. We provide you four variables (Task, Difficulty, Distance, SkillLevel), and you can construct an equation to be a combination of these variables. Task is the number of tasks in the route, Difficulty is the sum of all tasks' difficulty values, Distance is the travel distance of the route, and SkillLevel is the driver's skill level.The value of the constraint is the difference between the maximum and the minimum values of all routes' equations.

Capacity Constraint

Capacity Constraint limits the volume/weight of the boxes each vehicle can carry. Its value is 1 if the capacity exceeds the limit, or 0 if the constraint is satisfied.

Convex Hull No Intersection Constraint

When the route is created, the points that comprises of the route create convex hull on the map. The constraint makes sure that none of the convex hulls created by the routes overlap with the given lines. The value is the number of lines that intersects with any of the convex hulls.

Distance Constraint

Distance constraint ensures that the lower the total distance travelled by all drivers, the better the solution is. It takes the sum of travel distances of all drivers as its value.

Driver Preference Constraint

In some cases, certain locations, or the "features" of the locations (for example, zip code), are preferred by some drivers. Given the list of the drivers and the labels of their preferred locations, the constraint takes its value the number of tasks in the route that does not satisfy the driver's preference.

Location Label Single Visit Constraint

It is desirable to make sure that the driver visits the locations with certain features only once. For example, it might be required that certain zip code is visited only once by the same vehicle. The constraint counts the number of times any location labels are visited if they are visited more than once.

Max Active Driver Constraint

The constraint aims to make sure that all of the available drivers are used in the solution. Its value is the number of idle drivers, i.e the number of total drivers - the number of drivers occupied with at least one job.

Max Capacity Constraint

Sometimes it is not possible to fully utilize the capacity of the vehicle. The max capacity constraint takes the percentage of the total capacity that can be used (for example, 0.8) for each capacity type and counts the number of vehicles that failed to meet the capacity restriction.

Max Job Size Constraint

Because the drivers have different skill levels, the number of jobs they can handle are different. Given the maximum number of jobs that can be handled by people with certain skill level, the constraint counts the difference between the number of jobs assigned to the driver and the number of jobs the driver is allowed to have, if the driver is assigned more jobs than he can handle.

Max Visit Constraint

Max Visit Constraint ensures that the driver visits maximum of specified number of locations. The value is the number of locations that exceeds the specified maximum number of locations, i.e the number of locations that the driver visits - the allowed maximum number of locations.

Min Load Capacity Constraint

Just like Max Capacity Constraint, for economical reasons, it might be desirable to ensure that all vehicles have at least certain percentage of capacity filled when carrying out the delivery or pick up. The value of the constraint is 1 if the driver satisfies the minimum load constraint, and 0 otherwise.

Min Unique Location Label Constraint

Min Unique Location Label Constraint ensures that minimum number of the "representation" of locations are visited. For example, it might be required, or advantageous, for each driver to visit only the region covered by one zip code. The value of the constraint is the number of the unique location labels that the driver visits if no labels are supplied. If the set of labels are provided, only the location labels in the set are considered.

No Convex Hull Overlap Constraint

Similar to Convex Hull No Intersection Constraint, which prevents the convex hulls created by routes from intersecting the given lines, No Convex Hull Overlap Constraint makes sure that none of the convex hulls created by routes cover the same region. The constraint's value is the number of convex hulls that overlap with each other.

No Cross Route Constraint

No Cross Route Constraint is similar to No Convex Hull Overlap Constraint in a sense that they both consider the regions / locations covered by drivers. One difference is that the value of No Cross Route Constraint is determined by the number of times the routes intersect each other, and as a result it is possible for two routes that overlap with each other to contribute to the value of the constraint by more than 1. Also, since creating the convex hull of a route is effectively same as adding an "edge" between the start and the end of the route, there exist cases which violate No Convex Hull Overlap Constraint but not No Cross Route Constraint.

No Intersection Constraint

The relationship between No Convex Hull Overlap Constraint and No Cross Route Constraint is very similar to the relationship between Convex Hull No Intersection Constraint and No Intersection Constraint. While Convex Hull No Intersection Constraint counts the number of convex hulls that intersect with the given lines, No Intersection Constraint counts the actual number of intersections between the routes and the given lines.

Preference Center Constraint

In some cases, some drivers prefer to perform pick up and delivery in certain location, as they might be familiar with that region. Using the constraint increases the probability of satisfying those preferences. The value of the constraint is the sum of the distances between the preferred location and the task locations in the route.

Preference No Intersection Constraint

Although Preference Center Constraint helps creating routes that satisfy the preferences of drivers by preventing jobs assigned to drivers from being too far from their preferred locations, the measure might not truly reflect the preference in some cases. For example, if a driver is familiar with certain
region but is unaccustomed to the mountain right next to it, the delivery to the mountain might be assigned to the driver if we simply enforce jobs to be near the preferred location. Using the constraint mitigates the situation by penalizing the route every time the line created by connecting the preferred location and the task locations intersect with the given line. In this case, the given line can be the line across the mountain. The value of the constraint is the count of the intersection between the given line and the line from the preferred location to the task location.

Route Dispersion Constraint

In general, a tightly packed route spanning small region is preferred to the route covering a large region, because the former implies that the driver travels less and covers less area. The constraint helps creating such routes by enforcing the "diagonal distance" (the longest distance between the tasks in a route) to be small. The value of the constraint is the square of the diagonal distance of a given route.

Route Duration Constraint

Similar in concept to Route Dispersion Constraint, a route that takes small amount of time is desirable. The constraint has the total travel time (the sum of the travel time among all routes, not to be confused with the difference between the earliest start time and the latest end time among all routes) as its value, thus penalizing routes that take long time.

Single Driver Visit Constraint

If there are multiple deliveries or pick ups to be made in one location (for example, the driver might have to deliver packages to different people in one apartment complex), it is often desirable for a single driver to visit location, as capacity permits, to avoid wasting resources. The constraint's value is the number of locations that are visited by more than one driver, effectively penalizing solutions with locations visited by multiple drivers.

Single Visit Constraint

While it is important for a location to be visited by a single driver, it is also important for the driver to not return to the location after he already made a visit. The constraint enforces this restriction by having a value of 1 if the constraint is violated, and 0 otherwise.

Task Assignment Constraint

Given a list of tasks and the drivers that can perform each of those tasks, the constraint helps generating a solution that satisfies the task assignment as much as possible. The value of the constraint is the number of the tasks that are not carried out by one of the designated drivers.

Task Vehicle Constraint

Similar to Task Assignment Constraint, some tasks can be performed only by certain types of vehicles. In order to penalize the solution that does not fulfill those requirements, the constraint's value is the number of the tasks not carried out by the required vehicle.

Time Window Constraint

Some tasks have to be carried out within certain time period if, for example, requested by the customer. The value of the constraint is the number of tasks that is performed outside of the required time window. Note that the time window is a part of the task object, and is not supplied as an argument to the constraint.

Zone Assignment Constraint

Due to a company policy, there might be a requirement that certain areas should only be served by designated drivers. The constraint penalizes solutions that fails to meet the requirement: its value is the number of tasks performed in the restricted zones by unqualified driver.

Zone Vehicle Constraint

The constraint is exactly same as Zone Assignment Constraint, except instead of IDs of drivers, the vehicle features are used.