Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling Salesman Problem

• URL: http://arxiv.org/abs/2403.05318v1
• Date: Fri, 8 Mar 2024 13:49:21 GMT
• Title: Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling Salesman Problem
• Authors: Jingxiao Chen, Ziqin Gong, Minghuan Liu, Jun Wang, Yong Yu, Weinan Zhang
• Abstract summary: We propose a novel learning-based method that uses looking-ahead information as the feature to improve the legality of TSP with Time Windows (TSPTW) solutions. With comprehensive experiments on diverse datasets, MUSLA outperforms existing baselines and shows generalizability potential.
• Score: 36.88003015541172
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many real-world problems can be formulated as a constrained Traveling Salesman Problem (TSP). However, the constraints are always complex and numerous, making the TSPs challenging to solve. When the number of complicated constraints grows, it is time-consuming for traditional heuristic algorithms to avoid illegitimate outcomes. Learning-based methods provide an alternative to solve TSPs in a soft manner, which also supports GPU acceleration to generate solutions quickly. Nevertheless, the soft manner inevitably results in difficulty solving hard-constrained problems with learning algorithms, and the conflicts between legality and optimality may substantially affect the optimality of the solution. To overcome this problem and to have an effective solution against hard constraints, we proposed a novel learning-based method that uses looking-ahead information as the feature to improve the legality of TSP with Time Windows (TSPTW) solutions. Besides, we constructed TSPTW datasets with hard constraints in order to accurately evaluate and benchmark the statistical performance of various approaches, which can serve the community for future research. With comprehensive experiments on diverse datasets, MUSLA outperforms existing baselines and shows generalizability potential.

Related papers

• 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)
• Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows [5.818566833386833]
  We introduce a novel temporal decomposition scheme for solving a class of offline PDPTWs. Our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty.
  arXiv  Detail & Related papers  (2023-03-06T20:07:05Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation [0.4014524824655105]
  Vehicle Routing Problems (VRPs) in real-world applications often come with various constraints. We propose a Reinforcement Learning based method to solve soft-constrained VRPs. We apply the method on three common types of VRPs, the Travelling Salesman Problem with Time Windows (TSPTW), the Capacitated VRP (CVRP) and the Capacitated VRP with Time Windows (CVRPTW)
  arXiv  Detail & Related papers  (2022-07-20T12:51:06Z)
• Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SAT [4.873362301533824]
  Vehicle routing is a well known class of NP-hard optimisation problems. Recent work in reinforcement learning has been a promising alternative approach. This paper proposes a hybrid approach that combines reinforcement learning, policy rollouts, and a satisfiability.
  arXiv  Detail & Related papers  (2022-06-14T06:27:09Z)
• Learning Hard Optimization Problems: A Data Generation Perspective [44.4747903763245]
  This paper demonstrates the volatility of the training data to the ability to approximate it. It proposes a method for producing (exact or approximate) solutions to optimization problems that are amenable to supervised tasks.
  arXiv  Detail & Related papers  (2021-06-04T17:03:44Z)
• Constrained Learning with Non-Convex Losses [119.8736858597118]
  Though learning has become a core technology of modern information processing, there is now ample evidence that it can lead to biased, unsafe, and prejudiced solutions.
  arXiv  Detail & Related papers  (2021-03-08T23:10:33Z)
• 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)
• Probably Approximately Correct Constrained Learning [135.48447120228658]
  We develop a generalization theory based on the probably approximately correct (PAC) learning framework. We show that imposing a learner does not make a learning problem harder in the sense that any PAC learnable class is also a constrained learner. We analyze the properties of this solution and use it to illustrate how constrained learning can address problems in fair and robust classification.
  arXiv  Detail & Related papers  (2020-06-09T19:59:29Z)
• Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection [0.0]
  Traveling-Salesperson-Problem (TSP) is arguably one of the best-known NP-hard optimization problems. We extend existing benchmarking studies by addressing anytime behaviour of inexact TSP solvers. It turns out that performance ranking of solvers is highly dependent on the focused approximation quality.
  arXiv  Detail & Related papers  (2020-05-27T11:36:53Z)

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.