Decomposability-Guaranteed Cooperative Coevolution for Large-Scale Itinerary Planning

• URL: http://arxiv.org/abs/2506.06121v1
• Date: Fri, 06 Jun 2025 14:31:57 GMT
• Title: Decomposability-Guaranteed Cooperative Coevolution for Large-Scale Itinerary Planning
• Authors: Ziyu Zhang, Peilan Xu, Yuetong Sun, Yuhui Shi, Wenjian Luo,
• Abstract summary: Large-scale itinerary planning is a variant of the traveling salesman problem.<n>This paper analyzes the decomposability of large-scale itinerary planning.<n>We propose a novel multi-objective cooperative coevolutionary algorithm for large-scale itinerary planning.
• Score: 6.565536870180592
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large-scale itinerary planning is a variant of the traveling salesman problem, aiming to determine an optimal path that maximizes the collected points of interest (POIs) scores while minimizing travel time and cost, subject to travel duration constraints. This paper analyzes the decomposability of large-scale itinerary planning, proving that strict decomposability is difficult to satisfy, and introduces a weak decomposability definition based on a necessary condition, deriving the corresponding graph structures that fulfill this property. With decomposability guaranteed, we propose a novel multi-objective cooperative coevolutionary algorithm for large-scale itinerary planning, addressing the challenges of component imbalance and interactions. Specifically, we design a dynamic decomposition strategy based on the normalized fitness within each component, define optimization potential considering component scale and contribution, and develop a computational resource allocation strategy. Finally, we evaluate the proposed algorithm on a set of real-world datasets. Comparative experiments with state-of-the-art multi-objective itinerary planning algorithms demonstrate the superiority of our approach, with performance advantages increasing as the problem scale grows.

Related papers

• Plan Your Travel and Travel with Your Plan: Wide-Horizon Planning and Evaluation via LLM [58.50687282180444]
  Travel planning is a complex task requiring the integration of diverse real-world information and user preferences.<n>We formulate this as an $L3$ planning problem, emphasizing long context, long instruction, and long output.<n>We introduce Multiple Aspects of Planning (MAoP), enabling LLMs to conduct wide-horizon thinking to solve complex planning problems.
  arXiv  Detail & Related papers  (2025-06-14T09:37:59Z)
• A Unified Theory of Compositionality, Modularity, and Interpretability in Markov Decision Processes [1.3044677039636754]
  We introduce Option Kernel Bellman Equations (OKBEs) for a new reward-free Markov Decision Process.<n>OKBEs directly construct and optimize a predictive map called a state-time option kernel (STOK) to maximize the probability of completing a goal.<n>We argue that reward-maximization is in conflict with the properties of compositionality, modularity, and interpretability.
  arXiv  Detail & Related papers  (2025-06-11T08:21:22Z)
• Reinforced Reasoning for Embodied Planning [18.40186665383579]
  Embodied planning requires agents to make coherent multi-step decisions based on dynamic visual observations and natural language goals.<n>We introduce a reinforcement fine-tuning framework that brings R1-style reasoning enhancement into embodied planning.
  arXiv  Detail & Related papers  (2025-05-28T07:21:37Z)
• HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking [109.09735490692202]
  We propose HyperTree Planning (HTP), a novel reasoning paradigm that constructs hypertree-structured planning outlines for effective planning.<n> Experiments demonstrate the effectiveness of HTP, achieving state-of-the-art accuracy on the TravelPlanner benchmark with Gemini-1.5-Pro, resulting in a 3.6 times performance improvement over o1-preview.
  arXiv  Detail & Related papers  (2025-05-05T02:38:58Z)
• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  We propose PlanGEN, a model-agnostic and easily scalable agent framework with three key components: constraint, verification, and selection agents.<n>Specifically, our approach proposes constraint-guided iterative verification to enhance performance of inference-time algorithms.
  arXiv  Detail & Related papers  (2025-02-22T06:21:56Z)
• On Sequential Fault-Intolerant Process Planning [60.66853798340345]
  We propose and study a planning problem we call Sequential Fault-Intolerant Process Planning (SFIPP)<n>SFIPP captures a reward structure common in many sequential multi-stage decision problems where the planning is deemed successful only if all stages succeed.<n>We design provably tight online algorithms for settings in which we need to pick between different actions with unknown success chances at each stage.
  arXiv  Detail & Related papers  (2025-02-07T15:20:35Z)
• A Distance Similarity-based Genetic Optimization Algorithm for Satellite Ground Network Planning Considering Feeding Mode [53.71516191515285]
  The low transmission efficiency of the satellite data relay back mission has become a problem that is currently constraining the construction of the system. We propose a distance similarity-based genetic optimization algorithm (DSGA), which considers the state characteristics between the tasks and introduces a weighted Euclidean distance method to determine the similarity between the tasks.
  arXiv  Detail & Related papers  (2024-08-29T06:57:45Z)
• Adaptive Planning with Generative Models under Uncertainty [20.922248169620783]
  Planning with generative models has emerged as an effective decision-making paradigm across a wide range of domains. While continuous replanning at each timestep might seem intuitive because it allows decisions to be made based on the most recent environmental observations, it results in substantial computational challenges. Our work addresses this challenge by introducing a simple adaptive planning policy that leverages the generative model's ability to predict long-horizon state trajectories.
  arXiv  Detail & Related papers  (2024-08-02T18:07:53Z)
• An Auction-based Coordination Strategy for Task-Constrained Multi-Agent Stochastic Planning with Submodular Rewards [7.419725234099728]
  Existing task coordination algorithms either ignore the process or suffer from the computational intensity. We propose a decentralized auction-based coordination strategy using a newly formulated score function. For the implementation on large-scale applications, an approximate variant of the proposed method, namely Deep Auction, is also suggested.
  arXiv  Detail & Related papers  (2022-12-30T10:25:25Z)
• Sequence-Based Plan Feasibility Prediction for Efficient Task and Motion Planning [36.300564378022315]
  We present a learning-enabled Task and Motion Planning (TAMP) algorithm for solving mobile manipulation problems in environments with many articulated and movable obstacles. The core of our algorithm is PIGINet, a novel Transformer-based learning method that takes in a task plan, the goal, and the initial state, and predicts the probability of finding motion trajectories associated with the task plan.
  arXiv  Detail & Related papers  (2022-11-03T04:12:04Z)
• Extended Task and Motion Planning of Long-horizon Robot Manipulation [28.951816622135922]
  Task and Motion Planning (TAMP) requires integration of symbolic reasoning with metric motion planning. Most TAMP approaches fail to provide feasible solutions when there is missing knowledge about the environment at the symbolic level. We propose a novel approach for decision-making on extended decision spaces over plan skeletons and action parameters.
  arXiv  Detail & Related papers  (2021-03-09T14:44:08Z)
• Bottom-up mechanism and improved contract net protocol for the dynamic task planning of heterogeneous Earth observation resources [61.75759893720484]
  Earth observation resources are becoming increasingly indispensable in disaster relief, damage assessment and related domains. Many unpredicted factors, such as the change of observation task requirements, to the occurring of bad weather and resource failures, may cause the scheduled observation scheme to become infeasible. A bottom-up distributed coordinated framework together with an improved contract net are proposed to facilitate the dynamic task replanning for heterogeneous Earth observation resources.
  arXiv  Detail & Related papers  (2020-07-13T03:51:08Z)
• Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot Transfer [71.44215606325005]
  We propose a novel framework called Jump-Operator Dynamic Programming for quickly computing solutions within a super-exponential space of sequential sub-goal tasks. This approach involves controlling over an ensemble of reusable goal-conditioned polices functioning as temporally extended actions. We then identify classes of objective functions on this subspace whose solutions are invariant to the grounding, resulting in optimal zero-shot transfer.
  arXiv  Detail & Related papers  (2020-07-06T05:13:20Z)
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
  We consider alternatives to an implicit sequential planning assumption. We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan. We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
  arXiv  Detail & Related papers  (2020-04-23T18:08:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.