DNA //evolutions

Zone Crossing Penalization

Asymmetric directional costs for boundary transitions

In dense urban areas, a route that looks optimal on paper may cross a bridge, tunnel, or toll boundary multiple times per day. Each crossing costs time, fuel, and toll fees. Without explicit modeling, the optimizer treats these transitions as ordinary road segments and produces schedules where drivers zig-zag across zone boundaries unnecessarily.

Zone Crossing Penalization solves this by adding an explicit cost whenever a route transitions from one zone to another. The penalty is configurable per direction: crossing from Zone A to Zone B can carry a different cost than crossing from Zone B to Zone A. This asymmetric modeling captures real-world directional differences such as toll structures, morning/evening congestion patterns, or one-way infrastructure constraints.

Overview

The problem: invisible crossing costs

By default, the optimizer selects routes that minimize total distance and time while respecting constraints. In areas separated by bridges, tunnels, or congestion zone boundaries, the locally cheapest route often crosses the boundary multiple times during a single shift.

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

  • Without penalization, the truck crosses the bridge multiple times throughout the day. Each local routing decision looks efficient, but the cumulative cost of bridge crossings (tolls, congestion, fuel) is significant.
  • With penalization, the truck crosses only when necessary, typically once in the morning and once in the evening. The optimizer clusters work within each zone first and crosses only when the global benefit outweighs the penalty.

Default zone crossing behavior: frequent crossings

Figure 1: Without penalization, the route crosses the zone boundary multiple times.

Penalized zone crossing: minimal crossings

Figure 2: With penalization, crossings are reduced to the minimum necessary.

How penalization works

When zone crossing penalization is enabled, the optimizer applies an additional cost multiplier to every route edge that transitions from one zone to another. The cost is additive to the normal distance cost:

totalEdgeCost = baseDistanceCost + (baseDistanceCost * crossingMultiplier)

For example, with a multiplier of 3.0, a crossing edge becomes 4 times as expensive as the same edge without a crossing. The optimizer responds by clustering visits within zones and crossing boundaries only when the overall plan benefits.

The crossing is detected by comparing the ZoneCode qualifications of consecutive nodes in the route. If they belong to different zones, the crossing penalty applies. If they share at least one common zone, no penalty is applied. This works naturally with multi-zone nodes: a border node qualified for both Zone 1 and Zone 2 does not trigger a crossing penalty when visited between a Zone 1 node and a Zone 2 node.

Asymmetric directional penalties

Real-world crossing costs are often directional. A bridge toll may be charged only in one direction. Morning congestion is heavier inbound than outbound. A controlled border crossing may have different processing times depending on direction.

JOpt supports this through ZoneConnection objects that define per-direction multipliers:

// Crossing from Zone 1 to Zone 3: multiplier 5.0 (expensive)
ZoneConnection connection13 = ZoneConnection.builder()
    .fromZoneId("1")
    .toZoneId("3")
    .crossingPenaltyMultiplier(5.0)
    .build();

// Crossing from Zone 3 to Zone 1: multiplier 0.0 (free)
ZoneConnection connection31 = ZoneConnection.builder()
    .fromZoneId("3")
    .toZoneId("1")
    .crossingPenaltyMultiplier(0.0)
    .build();

In this example, crossing from Manhattan (Zone 1) to Jersey City (Zone 3) costs 5x the base distance. Crossing back from Jersey City to Manhattan is free. This models a toll bridge that charges only in one direction.

A multiplier of 0.0 effectively deactivates the penalty for that specific direction while keeping it active for the other. This is the mechanism for modeling asymmetric infrastructure costs.

To our best knowledge, asymmetric directional zone crossing penalties are not available in other route optimization engines. Google OR-Tools and Others do not provide a native concept for direction-dependent boundary transition costs.

Configuration

Global properties

Properties props = new Properties();

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

// Set the global default multiplier
props.setProperty("JOpt.Clustering.PenlalizeZoneCodeCrossingMultiplier", "10.0");

opti.addElement(props);

The global multiplier applies to all zone transitions that do not have a specific ZoneConnection override. If you define a ZoneConnection for a particular pair, its multiplier takes precedence over the global value.

The ZoneManager and ZoneConnections

The ZoneManager is the central registry for zone-to-zone transition rules. It holds all ZoneConnection objects and is attached to the optimization instance.

// Get the ZoneManager from the optimization
IZoneManager zm = opti.getZoneManager();

// Define directional connections
ZoneConnection conn13 = ZoneConnection.builder()
    .fromZoneId("1").toZoneId("3")
    .crossingPenaltyMultiplier(5.0).build();

ZoneConnection conn31 = ZoneConnection.builder()
    .fromZoneId("3").toZoneId("1")
    .crossingPenaltyMultiplier(0.0).build();

zm.putZoneConnection(conn13);
zm.putZoneConnection(conn31);

You only need to define ZoneConnections for pairs where the penalty differs from the global default. Undeclared pairs fall back to the global multiplier.

This architecture supports complex scenarios with many zones and varying transition costs. A city with 10 zones might have 3 toll bridges (6 directional connections) and leave all other transitions at the global default. Only the 6 exceptions need explicit ZoneConnections.

Example: Manhattan and Jersey City

Example on GitHub: BridgeTunnelCrossingZoneNumberConstraintExample.java.

This example models two macro areas separated by the Hudson River. Manhattan nodes are qualified with Zone 1 (and Zone 2 for testing multi-zone). Jersey City nodes are qualified with Zone 3 (and Zone 4). Two directional ZoneConnections define asymmetric toll costs.

The example includes a toggle (doPenalizeZoneCrossings) that lets you compare the routes with and without penalization. Both results are exported to KML files for visual inspection in Google Earth.

When penalization is enabled, the routes visibly cluster within each side of the river and cross the bridge only when the global benefit outweighs the penalty. Without penalization, the same routes zig-zag across the boundary multiple times.

Zone setup

// Manhattan zones
ZoneNumber zoneOne = new ZoneNumber(1);
ZoneNumber zoneTwo = new ZoneNumber(2);
ZoneNumberQualification manhattanQuali = new ZoneNumberQualification(zoneOne);
manhattanQuali.addExtraCode(zoneTwo);

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

In this setup, resources are not assigned zone constraints (they can visit all zones). The penalization is applied purely through crossing costs, not territory restrictions. This is a valid pattern: use zone crossing penalization to discourage crossings without prohibiting them.

Combining with territory enforcement

Zone crossing penalization and territory enforcement via ZoneCodes (see ZoneCodes feature guide) are independent features that work together.

A common production pattern combines both:

  1. Territory enforcement (hard ZoneCodes on WorkingHours): Resource A can only visit Zone 1 and Zone 2 on this shift. Resource B can only visit Zone 3.
  2. Crossing penalization: Within Resource A's allowed zones (1 and 2), switching between them during a single route is penalized. The resource should cluster work in Zone 1 first, then transition to Zone 2 once, rather than alternating.

This separation gives you two layers of control:

  • Feasibility (which zones are allowed) through territory enforcement.
  • Efficiency (how often to cross) through crossing penalization.

Closing Words

Zone Crossing Penalization produces realistic, efficient routes in areas with infrastructure boundaries. The asymmetric directional model captures toll structures, congestion patterns, and one-way crossing costs that standard distance matrices cannot represent. Combined with the ZoneCode territory system, it provides a comprehensive approach to geographic intelligence in route optimization.

For territory management (defining which resources can visit which nodes, per shift), see the ZoneCodes feature guide.

Authors

A product by dna-evolutions ©

ZoneCodes & Territories

Special features