Route compactness

In the Vehicle Routing Problem (VRP), optimizing routes involves more than just vehicle capacity and customer demand. Route compactness and clusterization are two key concepts used to manage and optimize routes based on spatial location.

Route compactness refers to the geographic density or proximity of the nodes (customers) included in a single route. A compact route is one where the stops are close to each other, minimizing travel time and distance between them. This concept is often visualized as a route that doesn't spread out excessively or have long, inefficient legs connecting distant points. It acts as a desirable quality, guiding the VRP solution towards more efficient and geographically focused territories for each vehicle.

Impact of compactness on planning

Improves Efficiency: Compact routes, resulting from good clustering, minimize the "stem time" (travel from the depot to the service area) and the "route time" (travel between customers).

Easier Planning & Management: Assigning drivers to specific clusters or zones makes daily dispatching simpler and more predictable.

Improved Customer Service: Tighter service areas can lead to more reliable delivery windows and faster response times.

Scalability: This strategy allows businesses to easily add new customers by assigning them to the nearest existing cluster, or to scale up by adding new vehicles to service new clusters.

Example

Imagine a catering company with 100 delivery orders spread across a city. The company has 5 delivery vans, each with a capacity to handle 20 orders.

• Without route compactness: The routing algorithm might create 5 routes that zigzag across the city, overlapping and covering long distances to serve 20 customers each. One van might travel from the north side to the south side, while another does the opposite.

• With route compactness: Each van is assigned one cluster. Van 1 serves only the "Downtown" cluster, Van 2 serves only the "West Suburbs," and so on. The resulting routes are highly compact, as all stops for a single van are in the same neighborhood. This drastically reduces travel time and operational costs compared to the un-clustered, non-compact routes.

Implementation in Stateless API

This feature is an optional capability within a dedicated Logistics Vehicle Routing Problem (VRP) solver. Route compactness is achieved by employing a polylinear model that adds a cost (either time or distance, depending on the optimization goal) to vehicle travel to the nodes

. This model penalizes longer travel, thereby promoting more compact routes. Integrated into the total cost function as a soft constraint, this mechanism automatically increases route compactness, balancing it against other optimization penalties.

Advanced Route Cost Control with travel_matrix_operator

For advanced and flexible control over route costs, including promoting compactness, you can configure the travel_matrix_operator within engine_settings.model_parameters. This powerful operator replaces the standard route-dependent cost calculation with a more general expression, allowing for detailed customization of how travel time and distance contribute to the overall optimization goal.

The total cost value is computed by summing contributions from different routing engines and matrix types. The general formula for the route-dependent part of the cost is:

$${\tt cost} = R(\widetilde{T}_{ij}^{(1)})+R(\widetilde{D}_{ij}^{(1)})+R(\widetilde{T}_{ij}^{(2)})+R(\widetilde{D}_{ij}^{(2)})$$

Here, superscripts (1) and (2) refer to the primary and secondary routing engines, respectively. $\widetilde{T}_{ij}$ and $\widetilde{D}_{ij}$ represent the time and distance matrices. The function $R()$ defines how each matrix contributes to the cost, incorporating both linear and polylinear penalties.

The cost function $R({m}_{ij})$ for a given travel segment consists of linear and polylinear parts:

$$R({m}_{ij}) = m_{ij} \cdot {\tt linear} + \sum_k[({\tt base}_k + (m_{ij}-{\tt threshold}_k) \cdot{\tt rate}_k), \; {\tt if} \;m_{ij}>{\tt threshold}_k]$$

This formula shows that the cost for a travel segment $m_{ij}$ (time or distance) is a sum of a linear component and potentially multiple polylinear penalty components. Each polylinear component $k$ applies a penalty if $m_{ij}$ meets its threshold condition.

How to Use travel_matrix_operator

To configure these advanced settings, define the travel_matrix_operator within engine_settings.model_parameters.

engine_settings.model_parameters.travel_matrix_operator

{
    "travel_matrix_operator": {
        "use_optimize_quantity": false,
        "primary": {
            "time": {
                "linear": 1,
                "polylinear": [
                    {
                        "threshold": 3600,
                        "relation": "greater",
                        "penalty": { "base": 5000, "rate": 2 }
                    }
                ]
            },
            "distance": { "linear": 0.5 }
        },
        "secondary": {
            "distance": {
                "linear": 0.1,
                "polylinear": [
                    {
                        "threshold": 10000,
                        "relation": "greater",
                        "penalty": { "base": 1000, "rate": 0.2 }
                    }
                ]
            }
        }
    }
}

Key Parameters

• use_optimize_quantity (boolean, default false when travel_matrix_operator is present):

  • If true (for backward compatibility), the system uses only one penalty type based on the optimize_quantity value. For example, if optimize_quantity = "total_distance", then primary.time and secondary.time configurations are ignored.
  • If false, the optimize_quantity value is ignored, and all parameters defined within travel_matrix_operator contribute to the cost calculation. This offers maximum flexibility for creating complex cost functions.

• primary and secondary (objects): These sections allow you to define cost contributions from two independent routing engines. This is particularly useful for promoting compactness.

  • Use Case: The primary engine can compute real-world road network distances/times, while the secondary engine (e.g., spheroid or euclidean) computes straight-line "as-the-crow-flies" distances. By adding a small cost factor to the secondary engine's distance, you penalize geographically dispersed nodes, encouraging the solver to create more visually compact routes.

  • time / distance (objects): Within primary and secondary, you can specify how time and distance matrices contribute to the cost.

    • linear (number, default 0): A scaling factor applied directly to the travel value ($m_{ij}$). A value of 1 means the travel time/distance is added to the cost as-is. A value of 2 doubles its contribution.
    • polylinear (array of objects): A list of penalty conditions, ideal for defining compactness rules.

polylinear Penalty Configuration

Each object in the polylinear array is a penalty rule with the following parameters:

• threshold (number, default 0): The value at which the penalty rule is triggered. Units match the matrix type (meters for distance, seconds for time).
• relation (string, required): Must be "greater" or "less". Determines if the penalty applies to travel values above or below the threshold.
• penalty (dictionary, optional, default {"base": 0, "rate": 0}):
  • base (number, optional, default 0): A fixed penalty added if the threshold condition is met.
  • rate (number, optional, default 0): An additional penalty per unit of travel exceeding (or below) the threshold.
• ignore_first (optional, default true): If true, no penalty is applied to the trip from a partial_route (e.g., depot) to the first stop.
• ignore_last (optional, default true): If true, no penalty is applied to the trip from the last stop back to partial_route_end (e.g., depot).

Important Notes

• If relation is set to less, the rate must be negative to result in a positive penalty for shorter trips.
• Each polylinear condition is evaluated independently, and their impacts are summed to compute the total penalty.
• The total travel cost between any two nodes is capped at a non-negative value to prevent unrealistic optimizations.
• For mixed fleets, penalties may differ based on a vehicle's matrix_id.

Practical Example: Promoting Compact Routes

Let's create a cost function that primarily optimizes for travel time but also encourages geographic compactness and penalizes very long individual trips.

Goal:

1. Main objective: Minimize total travel time.
2. Soft constraint: Penalize individual trips longer than 1 hour (3600 seconds) to avoid long, inefficient legs.
3. Soft constraint: Encourage routes to be geographically compact by adding a small penalty for straight-line distance between stops.

Configuration:

engine_settings

{
    "routing_engine": { "routing_engine_name": "osrm" },
    "secondary_routing_engine": { "routing_engine_name": "spheroid" },
    "model_parameters": {
        "travel_matrix_operator": {
            "use_optimize_quantity": false,
            "primary": {
                "time": {
                    "linear": 1,
                    "polylinear": [
                        {
                            "threshold": 3600,
                            "relation": "greater",
                            "penalty": { "base": 5000, "rate": 2 }
                        }
                    ]
                }
            },
            "secondary": {
                "distance": {
                    "linear": 0.1
                }
            }
        }
    }
}

Explanation:

1. primary.time.linear: 1: This makes total travel time (from the primary engine, osrm) the main component of the cost function.
2. primary.time.polylinear: This adds a significant penalty for any single trip that takes longer than 1 hour.
   • base: 5000: A large fixed penalty is added if a trip exceeds 3600 seconds.
   • rate: 2: For every second over the 1-hour threshold, an additional penalty of 2 is added.
3. secondary.distance.linear: 0.1: This adds a small cost based on the straight-line distance between stops (calculated by the secondary engine, spheroid). This penalty is small enough not to override the primary time optimization but significant enough to guide the solver towards choosing geographically closer stops when travel times are similar, thus promoting compactness.

Playground

You can try out the Route Compactness concept using the playground below.

Loading...