Skip to main content

Pair Relocate Operator

Overview​

The Pair Relocate Operator is a powerful local search optimization algorithm employed by the optimization engine. Its main purpose is to iteratively improve existing routes by taking pairs of connected nodes (specifically, a pickup node and its corresponding delivery node) and relocating them to more optimal positions within the planned routes.

By continually exploring different insertion options across all paths, the operator refines the overall solution, minimizing travel times and distances while strictly respecting constraints such as time windows, vehicle capacities, and pickup-delivery sequencing rules.

How It Works​

The operator continuously evaluates every assigned "pair" (a linked pickup and delivery) to see if it can find a more efficient sequence for them.

The continuous cycle proceeds as follows:

  1. Remove the pair from its current place in the vehicle's schedule.
  2. Search every existing route to find the cheapest new spot for the pickup.
  3. Scan forward from that new pickup spot to find a valid spot for the delivery.
  4. Enforce Rules, making sure the delivery still happens after the pickup and both remain assigned to the same vehicle.
  5. Relocate the pair to the new sequence if it lowers the total route cost or duration.

Because it evaluates every possible combination, it explores a vast number of sequence layouts to ensure the smartest possible routing match is found.

Logistics-Optimized Pair Relocation​

In many real-world logistics scenarios, shipments are modeled as pickup-delivery pairs where either all pickups originate from a common location (e.g., a distribution center), or all deliveries arrive at the same destination (e.g., a central processing hub).

Applying a standard relocation operator to these models can generate massive search spaces with redundant variations. For instance, swapping the order of pickups that occur at the exact same physical location might not change the route's cost but still wastes computation time. To address this, our Pair Relocate Operator is heavily optimized by actively grouping nodes that share the exact physical location.

Leveraging the location Parameter​

The solver introduces an internal location parameter for nodes.

This allows the Pair Relocate Operator to recognize clusters of nodes located at the same location. It can then streamline the exploration space by:

  • Grouping pickups or deliveries that occur at the same location.
  • Altering the order of service locally at that specific location when beneficial.
  • Moving not just a single node or pair, but relocating entire clusters of nodes sharing the same location simultaneously.

Handling Shared Locations​

The optimized operator successfully resolves several complex routing situations associated with shared locations:

1. Loop Elimination​

If multiple pickups occur at the same base location and their corresponding deliveries fall sequentially along the path, another distinct stop might be unnecessarily wedged in between the drop-offs. The operator detects this pattern (e.g., a vehicle making an inefficient loop to another stop before returning to finish a clustered delivery) and can shift the drop-offs left or right to merge them, eliminating the redundant loop.

Example: Resolving an Inefficient Loop

Imagine a vehicle that picks up two packages to deliver.

Initial Inefficient Route:

  1. Pickup Package A (at the Warehouse)
  2. Pickup Package B (at the same Warehouse)
  3. Drop-off Package A (at the Office Building)
  4. Detour: Drop-off Package C (at the Coffee Shop)
  5. Drop-off Package B (at the same Office Building)

In this routing, the vehicle makes a detour to the Coffee Shop before taking the second package to the Office Building, effectively visiting the exact same Office Building two separate times.

Optimized Route: The operator recognizes that dropping off Package A and Package B share the exact same physical location. It evaluates consolidating those stops and reorders the route to trim the detour:

  1. Pickup Package A (at the Warehouse)
  2. Pickup Package B (at the Warehouse)
  3. Detour: Drop-off Package C (at the Coffee Shop)
  4. Drop-off Package A (at the Office Building)
  5. Drop-off Package B (at the Office Building)

By shifting the drop-offs together, the vehicle only stops at the Office Building once, cutting out redundant travel time.

2. Shifting Entire Clusters​

When drop-offs are clustered at a single location but separated by a detour, relocating just a single node within the cluster usually won't yield improvement on its own (since the detour would remain for the other nodes). The operator has the proactive ability to move an entire cluster of co-located nodes simultaneously to a different position in the route, achieving true cost reduction.

3. Consolidating Between Vehicles​

When nodes located at the same place are assigned to different vehicles, it might be more efficient to consolidate them. The operator evaluates moving a pickup-delivery pair from one vehicle's path to another vehicle's path. Furthermore, it intelligently handles transferring entire clusters of co-located nodes between distinct vehicles to consolidate trips, group shared locations effectively, and minimize total vehicle usage.

Summary​

In summary, the optimized Pair Relocate Operator effectively manages co-located nodes by treating them as consolidated groups rather than isolated points. This advanced approach drastically prunes redundant computational checks, avoids suboptimal vehicle loops, consolidates shared locations onto the same vehicles, and yields noticeably higher performance and efficiency in complex logistics modeling.

API Integration​

To explicitly enable this operator when making requests to the API, configure the use_local_search_operators property in your optimization settings. Specifically, you should pass "logistics_relocate_pair" in the list of operators.

For full payload details and to find where to include this setting, refer to the Run Optimization API documentation.