Learning to Solve Compositional Geometry Routing Problems
This work addresses the challenge of solving routing problems with non-point tasks (lines, areas, hybrids) for practitioners in logistics and robotics, but the improvements are incremental over existing methods.
The paper introduces DiCon, a differential attention-assisted solver with contrastive learning, for the Compositional Geometry Routing Problem (CGRP), a unified superclass of routing problems with various task geometries. DiCon achieves strong performance, broad versatility, and superior generalization across diverse CGRP instances.
We study the Compositional Geometry Routing Problem (CGRP), a unified superclass of traditional routing problems that covers point-only, line-only, area-only, and arbitrary hybrid task geometries, providing a broad abstraction for real-world routing scenarios. Beyond standard point-based routing, CGRP with non-point tasks can be inherently asymmetric, tightly coupled travel routes with the intrinsic path, and enlarges the action space with numerous feasible yet often irrelevant options, thereby posing significant challenges for both representation learning and decision-making. To address these challenges, we propose DiCon, a differential attention-assisted solver with contrastive learning, as a plug-and-play framework that tackles the problem from two complementary angles. First, we introduce a differential attention mechanism that actively suppresses the probability mass on less competitive candidate actions. Second, we design a double-level contrastive learning objective to promote robust global instance representations and regularize geometry-aware task representations. Extensive experiments demonstrate that DiCon achieves strong performance, broad versatility, and superior generalization across diverse CGRP instances with different compositions.