Solving Travelling Thief Problems using Coordination Based Methods
- URL: http://arxiv.org/abs/2310.07156v1
- Date: Wed, 11 Oct 2023 03:03:50 GMT
- Title: Solving Travelling Thief Problems using Coordination Based Methods
- Authors: Majid Namazi, M.A. Hakim Newton, Conrad Sanderson, Abdul Sattar
- Abstract summary: A travelling thief problem (TTP) is a proxy to real-life problems such as postal collection.
In TTP, city selection and item selection decisions need close coordination since the thief's travelling speed depends on the knapsack's weight.
Existing TTP solvers deal with city selection and item selection separately, keeping decisions for one type unchanged while dealing with the other type.
- Score: 16.685542610215286
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A travelling thief problem (TTP) is a proxy to real-life problems such as
postal collection. TTP comprises an entanglement of a travelling salesman
problem (TSP) and a knapsack problem (KP) since items of KP are scattered over
cities of TSP, and a thief has to visit cities to collect items. In TTP, city
selection and item selection decisions need close coordination since the
thief's travelling speed depends on the knapsack's weight and the order of
visiting cities affects the order of item collection. Existing TTP solvers deal
with city selection and item selection separately, keeping decisions for one
type unchanged while dealing with the other type. This separation essentially
means very poor coordination between two types of decision. In this paper, we
first show that a simple local search based coordination approach does not work
in TTP. Then, to address the aforementioned problems, we propose a human
designed coordination heuristic that makes changes to collection plans during
exploration of cyclic tours. We further propose another human designed
coordination heuristic that explicitly exploits the cyclic tours in item
selections during collection plan exploration. Lastly, we propose a machine
learning based coordination heuristic that captures characteristics of the two
human designed coordination heuristics. Our proposed coordination based
approaches help our TTP solver significantly outperform existing
state-of-the-art TTP solvers on a set of benchmark problems. Our solver is
named Cooperation Coordination (CoCo) and its source code is available from
https://github.com/majid75/CoCo
Related papers
- Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem [12.34897099691387]
This paper develops a learning method for a special class of traveling salesman problems (TSP)
It finds the shortest tour along a sequence of one-to-one pickup-and-delivery nodes.
In PDTSP, precedence constraints need to be satisfied that each pickup node must be visited before its corresponding delivery node.
arXiv Detail & Related papers (2024-04-17T15:05:51Z) - Fair collaborative vehicle routing: A deep multi-agent reinforcement
learning approach [49.00137468773683]
Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other.
Traditional game theoretic solution concepts are expensive to calculate as the characteristic function scales exponentially with the number of agents.
We propose to model this problem as a coalitional bargaining game solved using deep multi-agent reinforcement learning.
arXiv Detail & Related papers (2023-10-26T15:42:29Z) - AffineGlue: Joint Matching and Robust Estimation [74.04609046690913]
We propose AffineGlue, a method for joint two-view feature matching and robust estimation.
AffineGlue selects potential matches from one-to-many correspondences to estimate minimal models.
Guided matching is then used to find matches consistent with the model, suffering less from the ambiguities of one-to-one matches.
arXiv Detail & Related papers (2023-07-28T08:05:36Z) - Keypoint-Guided Optimal Transport [85.396726225935]
We propose a novel KeyPoint-Guided model by ReLation preservation (KPG-RL) that searches for the optimal matching.
The proposed KPG-RL model can be solved by Sinkhorn's algorithm and is applicable even when distributions are supported in different spaces.
Based on the learned transport plan from dual KPG-RL, we propose a novel manifold barycentric projection to transport source data to the target domain.
arXiv Detail & Related papers (2023-03-23T08:35:56Z) - GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
We propose an efficient shared encoding for all agents and the map without sacrificing accuracy or generalization.
We leverage pair-wise relative positional encodings to represent geometric relationships between the agents and the map elements in a heterogeneous spatial graph.
Our decoder is also viewpoint agnostic, predicting agent goals on the lane graph to enable diverse and context-aware multimodal prediction.
arXiv Detail & Related papers (2022-11-04T16:10:50Z) - On the Use of Quality Diversity Algorithms for The Traveling Thief
Problem [11.590506672325668]
In real-world optimisation, it is common to face several sub-problems interacting and forming the main problem.
In this paper, we investigate the inter-dependency of the traveling salesperson problem(TSP) and the knapsack problem(KP) by means of quality diversity(QD) approaches.
arXiv Detail & Related papers (2021-12-16T05:08:39Z) - Solving the Travelling Thief Problem based on Item Selection Weight and
Reverse Order Allocation [8.620967398331265]
The Travelling Thief Problem (TTP) is a challenging optimization problem that attracts many scholars.
In this paper, TTP is investigated theoretically and empirically.
An algorithm based on the score value calculated by our proposed formulation in picking items and sorting items in the reverse order is proposed to solve the problem.
arXiv Detail & Related papers (2020-12-16T12:06:05Z) - Optimising Tours for the Weighted Traveling Salesperson Problem and the
Traveling Thief Problem: A Structural Comparison of Solutions [13.026567958569965]
The Traveling Thief Problem (TTP) addresses such interactions by combining two optimisation problems.
A new problem called the node weight dependent Traveling Salesperson Problem (W-TSP) has been introduced where nodes have weights that influence the cost of the tour.
We investigate the structure of the optimised tours for W-TSP and TTP and the impact of using each others fitness function.
arXiv Detail & Related papers (2020-06-05T07:07:28Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination.
We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
arXiv Detail & Related papers (2020-05-27T01:10:41Z) - Learning to Recover Reasoning Chains for Multi-Hop Question Answering
via Cooperative Games [66.98855910291292]
We propose a new problem of learning to recover reasoning chains from weakly supervised signals.
How the evidence passages are selected and how the selected passages are connected are handled by two models.
For evaluation, we created benchmarks based on two multi-hop QA datasets.
arXiv Detail & Related papers (2020-04-06T03:54:38Z) - A Non-Dominated Sorting Based Customized Random-Key Genetic Algorithm
for the Bi-Objective Traveling Thief Problem [7.088487500434561]
We propose a method to solve a bi-objective variant of the well-studied Traveling Thief Problem (TTP)
We address the BI-TTP, where the goal is to minimize the overall traveling time and to maximize the profit of the collected items.
Our proposed method is based on a biased-random key genetic algorithm with customizations addressing problem-specific characteristics.
arXiv Detail & Related papers (2020-02-11T10:56:13Z)
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.