A Hybrid Matheuristic Framework for the Chinese Postman Problem with Load-Dependent Costs

• URL: http://arxiv.org/abs/2607.22542v1
• Date: Sun, 26 Apr 2026 13:36:30 GMT
• Title: A Hybrid Matheuristic Framework for the Chinese Postman Problem with Load-Dependent Costs
• Abstract summary: The Chinese Postman Problem with load-dependent costs ( CPP-LC) arises in real-world logistics and transportation systems.<n>We propose a hybrid optimization framework that integrates metaheuristic search with mathematical programming to efficiently solve CPP-LC.
• Score: 6.086602240954416
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Chinese Postman Problem with load-dependent costs (CPP-LC) arises in real-world logistics and transportation systems where travel costs depend on vehicle load and energy consumption. In this work, we propose a hybrid optimization framework that integrates metaheuristic search with mathematical programming to efficiently solve CPP-LC. The proposed method combines local search procedures with reduced mixed-integer linear programming (MILP) models to balance exploration and intensification. In addition, we develop an Ant Colony Optimization (ACO) algorithm to enhance scalability on large instances. Extensive experiments on benchmark datasets demonstrate that the proposed framework consistently achieves high-quality solutions and outperforms existing approaches in solution quality, while maintaining competitive computational efficiency. These results highlight the effectiveness of hybrid optimization strategies for complex, load-dependent routing problems in practical applications. Our implementation is publicly available at https://github.com/HySonLab/MatCPP

Related papers

• DQAOA-GPT: AI-Accelerated Distributed Quantum Optimization for Combinatorial Problems [1.0380578526859343]
  Variational quantum algorithms offer a promising route for tackling exponentially large search spaces.<n>In this work, we introduce DQAOA-GPT, a hybrid framework that integrates the distributed quantum approximate optimization algorithm (DQAOA)<n>Rather than relying on iterative variational optimization, the proposed approach uses a trained generative model to directly generate high-quality quantum circuits for the sub-problems.
  arXiv  Detail & Related papers  (2026-07-22T14:46:33Z)
• POLCA: Stochastic Generative Optimization with LLM [26.342554900977003]
  We introduce Prioritized Optimization with Local Contextualion (POLCA)<n>POLCA is a scalable framework designed to handle parameterity in optimization.<n>We demonstrate POLCA achieves robust, sample and time-efficient performance.
  arXiv  Detail & Related papers  (2026-03-16T03:07:44Z)
• CACTO-BIC: Scalable Actor-Critic Learning via Biased Sampling and GPU-Accelerated Trajectory Optimization [1.9644272536912284]
  Tray Comparison Optimization (TO) and Reinforcement Learning (RL) offer strengths for optimal control problems.<n>TO efficiently computes locally while CACGO is more robust to struggle with high-dimensional challenges.
  arXiv  Detail & Related papers  (2026-02-23T10:45:36Z)
• Cost Minimization for Space-Air-Ground Integrated Multi-Access Edge Computing Systems [60.586531406445744]
  Space-air-ground integrated multi-altitude edge computing (SAGIN-MEC) provides a promising solution for the rapidly developing low-altitude economy.<n>We present a SAGIN-MEC architecture that enables the coordination between user devices (UDs), uncrewed aerial vehicles (UAVs) and satellites.
  arXiv  Detail & Related papers  (2025-10-24T15:03:07Z)
• Hybrid Learning and Optimization methods for solving Capacitated Vehicle Routing Problem [3.652509571098291]
  The Capacitated Vehicle Routing Problem (CVRP) is a fundamental NP-hard problem in logistics.<n>We propose a hybrid optimization approach that integrates deep reinforcement learning (RL) to automate the selection of penalty parameter values within both classical (RL-C-ALM) and quantum-enhanced (RL-Q-ALM) ALM solvers.
  arXiv  Detail & Related papers  (2025-09-18T08:38:29Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport [51.6416022358349]
  sys is a framework that harnesses optimal transport theory for data repair under Conditional Independence (CI) constraints. We develop an iterative algorithm inspired by Sinkhorn's matrix scaling algorithm, which efficiently addresses high-dimensional and large-scale data.
  arXiv  Detail & Related papers  (2024-03-04T18:23:55Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under the general function approximation. We introduce a novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. We show that our algorithm provides comparable sublinear regret to the existing works.
  arXiv  Detail & Related papers  (2023-10-10T01:39:04Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

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.