Scholarlink

<p>In the context of collaborative transportation in short food supply chains, we aim to theoretically characterize semicore allocations and Traveling Salesman Games (TSG). The objective is to help a group of agents (in our case, farmers) to pool the pickup and delivery facilities by proposing (i) an optimal solution for the transportation problem and (ii) a practical method to allocate induced costs among the agents in an explainable and fair way. Based on discussions with the logistics manager of an association of farmers, we argue that the semicore is a seemingly reasonable solution concept. Finding allocations in the semicore is less computationally demanding than in other solution concepts such as the core while conveying fairness concepts that can be arguably easily understood without a deep understanding of mathematical language, as opposed to other methods from cooperative game theory (such as the Shapley value or the nucleolus). Applying this concept to the development of a Decision Support System (DSS) naturally raises the question of whether there could be instances of the TSG that can have an empty semicore (like it can be the case for the core). In this paper we first provide a necessary and sufficient condition for the semicore of an instance of the TSG to be empty. Then, we prove that the set of cost functions that characterize Symmetric TSGs is a union of polyhedra. Implementing this characterization as a Satisfiability Modulo Theories (SMT) program, we are able to exhibit instances of the symmetric TSG with 6 or more players where the semicore is indeed empty. To further complete the characterization of the semicore of TSGs, we provide a proof of the NP-hardness of deciding semicore non-emptiness, which implies that it remains computationally hard to compute semicore allocations. We advocate that precisely knowing when the semicore can be empty is crucial for the DSS we aim to develop, to warn the stakeholders in some situations that a fair allocation might not exist. Finally, we conclude by giving a short description of the proof of concept of a first version of our DSS.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Traveling salesman games: semicore allocations for collaborative transportation in short food supply chains

  • 期刊论文

  • 发表日期：

    2026年5月27日

查看全文
  • Nicolas Besson,
  • Sylvain Bouveret,
  • Nadia Brauner,
  • Nicolas Brulard

摘要

In the context of collaborative transportation in short food supply chains, we aim to theoretically characterize semicore allocations and Traveling Salesman Games (TSG). The objective is to help a group of agents (in our case, farmers) to pool the pickup and delivery facilities by proposing (i) an optimal solution for the transportation problem and (ii) a practical method to allocate induced costs among the agents in an explainable and fair way. Based on discussions with the logistics manager of an association of farmers, we argue that the semicore is a seemingly reasonable solution concept. Finding allocations in the semicore is less computationally demanding than in other solution concepts such as the core while conveying fairness concepts that can be arguably easily understood without a deep understanding of mathematical language, as opposed to other methods from cooperative game theory (such as the Shapley value or the nucleolus). Applying this concept to the development of a Decision Support System (DSS) naturally raises the question of whether there could be instances of the TSG that can have an empty semicore (like it can be the case for the core). In this paper we first provide a necessary and sufficient condition for the semicore of an instance of the TSG to be empty. Then, we prove that the set of cost functions that characterize Symmetric TSGs is a union of polyhedra. Implementing this characterization as a Satisfiability Modulo Theories (SMT) program, we are able to exhibit instances of the symmetric TSG with 6 or more players where the semicore is indeed empty. To further complete the characterization of the semicore of TSGs, we provide a proof of the NP-hardness of deciding semicore non-emptiness, which implies that it remains computationally hard to compute semicore allocations. We advocate that precisely knowing when the semicore can be empty is crucial for the DSS we aim to develop, to warn the stakeholders in some situations that a fair allocation might not exist. Finally, we conclude by giving a short description of the proof of concept of a first version of our DSS.