Penalizing Zone Crossings

In many real-world logistics scenarios, crossing between defined zones can be costly, inefficient, or impractical. Bridges, tunnels, and other infrastructural limitations can make frequent crossings undesirable.

With the new Zone Crossing Penalization feature in JOpt.TourOptimizer, users can assign a cost penalty when a resource crosses a zone boundary. This allows for better routing decisions where crossings are minimized unless absolutely necessary.

Reminder: Defining Territories via ZoneCodes

Resources in logistics operations are often subject to constraints, such as geographical territories or customer preferences. These territories may change dynamically, requiring flexible optimization.

To address this, ZoneCodes function similarly to regional postcodes, defining service areas for resources.

Resources and Nodes are assigned ZoneCodes, restricting which resources can visit which nodes.
Each resource's working hours can include multiple ZoneCodes, allowing flexibility.
Nodes near territory borders can be assigned multiple ZoneCodes, letting the optimizer choose the most cost-effective assignment.

Figure - ZO 1 shows a typical zone setup.

Screenshot

Figure - ZO 1

By using ZoneCodes, you can define precise territory-based scheduling while still allowing dynamic optimization.

Extension: Zone Crossing - Problem Statement

By default, the optimizer selects the best route, even if it requires frequent zone crossings. However, in many real-world cases, minimizing crossings is beneficial.

Consider a truck driver operating in two zones separated by a bridge or tunnel:

Without penalization, the truck crosses multiple times throughout the day, increasing fuel consumption, toll costs, and inefficiency.
Ideally, the truck should cross only when necessary - typically at the start and end of the working shift.

Below, the default scenario shows frequent crossings.

Default Zone Crossing Behavior

Extension: Zone Crossing - Penalization

To prevent unnecessary crossings, we introduced zone crossing penalties. By setting a higher cost for traveling between zones, the optimizer prioritizes routes that avoid crossing unless absolutely necessary.

Before applying penalties: The driver crosses multiple times.
After penalization: The driver crosses only twice - once in the morning and once in the evening.

Below, we see the optimized and penalized solution with zone crossing penalties:

Optimized Zone Crossing with Penalty

Zone Crossing Penalization: How It Works

When Zone Crossing Penalization is enabled, an additional cost multiplier applies whenever a resource crosses from one zone to another.

This penalty is controlled by the following optimizer property:

props.setProperty("JOpt.Clustering.PenlalizeZoneCodeCrossingMultiplier", "3.0");

This means that if the default distance cost between two nodes is 1 unit, the penalized cost will be:

baseDistanceCost + (baseDistanceCost * multiplier) = 4 * baseDistanceCost

Effect: The optimizer discourages unnecessary crossings, but allows them if absolutely required.

Enabling the Feature in the Optimizer

To enable Zone Crossing Penalization, configure the optimizer with the following properties:

Properties props = new Properties();

// Enable zone crossing penalties
props.setProperty("JOpt.Clustering.PenlalizeZoneCodeCrossing", "true");

// Define the penalty multiplier
props.setProperty("JOpt.Clustering.PenlalizeZoneCodeCrossingMultiplier", "10.0");

// Add properties to the optimizer
opti.addElement(props);

Assigning Zones to Nodes

Usually, to use ZoneNumbers, both resources (vehicles/workers) and nodes (locations) must be assigned zone qualifications. In our scenario, it is sufficient to assign ZoneNumbers only to nodes. If a resource is not assigned a ZoneNumber, it is eligible to visit all zones.

2. Assigning Zones to Nodes

Nodes are assigned specific zones, ensuring that only relevant resources (in our scenario, all resources) can visit them.

public static void addNodes(IOptimization opti) {
    List<IOpeningHours> weeklyOpeningHours = new ArrayList<>();

    weeklyOpeningHours.add(new OpeningHours(
        ZonedDateTime.of(2030, MAY.getValue(), 6, 8, 0, 0, 0, ZoneId.of("Europe/Berlin")),
        ZonedDateTime.of(2030, MAY.getValue(), 6, 17, 0, 0, 0, ZoneId.of("Europe/Berlin"))
    ));

    // Define Zone Numbers
    ZoneNumber zoneOne = new ZoneNumber(1);  // Manhattan
    ZoneNumber zoneTwo = new ZoneNumber(2);  // Additional Manhattan area
    ZoneNumberQualification manhattanQuali = new ZoneNumberQualification(zoneOne);
    manhattanQuali.addExtraCode(zoneTwo);

    ZoneNumber zoneThree = new ZoneNumber(3);  // Jersey City
    ZoneNumber zoneFour = new ZoneNumber(4);   // Additional Jersey area
    ZoneNumberQualification jerseyQuali = new ZoneNumberQualification(zoneThree);
    jerseyQuali.addExtraCode(zoneFour);

    // Add Manhattan Nodes
    addManhattanNodes(opti, weeklyOpeningHours, manhattanQuali);

    // Add Jersey City Nodes
    addJerseyCityNodes(opti, weeklyOpeningHours, jerseyQuali);
}


private static void addManhattanNodes(IOptimization opti, List<IOpeningHours> weeklyOpeningHours,
    ZoneNumberQualification zoneNumber) {

    List<Position> poss = new ArrayList<>();

    poss.add(Position.of(40.764279, -73.988988));
    poss.add(Position.of(40.761822, -73.968600));
    poss.add(Position.of(40.764162, -73.991906));
    poss.add(Position.of(40.723670, -73.998738));
    poss.add(Position.of(40.796056, -73.967102));
    poss.add(Position.of(40.761964, -73.972156));
    poss.add(Position.of(40.737567, -74.009090));
    poss.add(Position.of(40.733846, -74.009090));

    Duration visitDuration = Duration.ofMinutes(60); // visit duration of each node

    for (int ii = 0; ii < poss.size(); ii++) {

        INode curNode = new TimeWindowGeoNode("Manhattan-" + ii, poss.get(ii), weeklyOpeningHours, visitDuration,
            1);

        curNode.addQualification(zoneNumber);

        opti.addElement(curNode);
    }

}

//... other methods

This ensures that nodes in Manhattan and Jersey City are correctly assigned to their respective zones. If a resource needs to cross between them, it will incur the defined penalty.

Example

Please visit our GitHub-Page for this ZoneCrossing-Example.

(If you are new to JOpt-TourOptimizer, please also read our page on setting up your first optimization.)

Closing Words

Key Takeaways:

Zone Numbers allow fine-tuned territory definitions for resources and nodes.
The Zone Crossing Penalization discourages frequent crossings unless necessary.
Resources and nodes are assigned zones via ZoneNumberQualification.
This results in more efficient and realistic routing particularly in high-density geographical areas, reducing unnecessary bridge and tunnel crossings.