Single Path Multicommodity Trading Problem on Acyclic Network: Polyhedral Structure and Approximability

Abstract

The Single Path Multicommodity Trading Problem on Acyclic Network(sMTP) involves finding a single path on an acyclic network that maximizes profits by selectively transporting goods between pairs of nodes as long as the carrying volume does not exceed the capacity. The operator can earn a profit for fulfilling each transportation request, but they also incur costs that are proportional to the volume of transportation for every unit of distance traveled. The objective is to select a path that passes through some of the nodes, maximizes profit, and subtracts the logistic cost from the revenue. In this paper, we explore the structure of the polyhedron and investigate the approximability of sMTP. Our Study involves both theoretical analysis based on integer programming and the development of approximation algorithms.

Theoretical analysis is conducted by first presenting two models for sMTP, along with several families of valid inequalities for each model. We also identify the conditions under which these inequalities serve as facet-defining inequalities and propose efficient separation algorithms. Next, we delve into the approximability of the problem. We discuss the inherent limitations in developing approximation algorithms and address both the inapproximability and the integrality gap. To pave the way for an approximation algorithm, we focus on specific cases and devise approximation algorithms tailored to those scenarios. Building upon these algorithms, we present an approximation algorithm for sMTP. Furthermore, we explore the applicability of the techniques utilized in our proposed approximation algorithms to other related problems. Lastly, we conduct a comparative analysis to evaluate the performance of the algorithms derived from our findings.

무회로 네트워크에서의 단일경로 최대이익다품종거래문제(sMTP)는 정해진 목적지로 가는 차량을 운행하여 마디 쌍 사이에 존재하는 운송 요청을 선택적으로 수행하여 이익을 최대화하는 문제이다. 무회로 유향 네트워크의 각 마디 쌍에는 한 마디에서 다른 마디로의 운송에 대한 요청이 존재한다. 시작 마디에서 마지막 마디까지의 경로가 정해지면, 그 경로 위의 각 요청의 출발지와 목적지 간의 물품을 수송량 제한을 넘지 않는 선에서 운송할 수 있다. 이 때 각 운송량에 비례한 수익을 얻는다. 같은 마디 쌍 사이의 운송 요청이라도 일부만 운송하여 일부의 수익만 얻을 수도 있다. 한 편, 운송을 하는 과정에서 단위 거리를 이동할 때 마다 수송량에 비례하는 비용이 발생한다. 따라서 수송량에 제한이 없더라도, 최대의 수익을 목적으로 모든 마디에 방문하는 것은 너무 멀리 우회를 하게 만들어 더 큰 비용을 초래할 수도 있다. 차량 운행자는 전체 마디 중 일부를 거치는 경로를 선택하고 각 운송 요청의 수행하여, 수익에서 비용을 뺀 이익을 최대화하는 것을 목적으로 한다.

본 논문에서는 sMTP에 대해, 가능해 집합에 대응하는 다면체의 구조와 근사 가능성에 대해 연구한다. 먼저, 정수 최적화 기반의 이론적 분석을 진행한다. sMTP를 위한 두 가지 모형을 제시한다. 각 모형에 대해 먼저 용량 제약이 없는 경우의 유효 부등식 집단들을 얻고, 각각이 강한 유효 부등식이 될 조건에 대해 논한다. 또한 발견한 유효 부등식들에 대응하는 분리 알고리듬을 제시한다. 다음으로, 해당 문제의 근사 가능성에 대한 분석을 진행한다. 먼저 근사해법 개발의 근본적 한계에 대해 다룬다. 계산 불가능성과 함께, 최악의 경우의 선형완화 문제의 해가 상한으로서 제공하는 품질의 한계에 대해 다룬다. 이 문제의 근사해법 개발을 위해, 몇몇 특수한 경우에 적용할 수 있는 근사해법을 제시한다. 제시한 해법들을 바탕으로 sMTP의 근사해법을 제시하고, 제시한 근사해법에 사용된 기법들이 활용될 수 있는 다른 문제들에 대해 다룬다. 마지막으로, 실험적으로 본 연구에서 제시한 유효 부등식을 이용한 다양한 해법의 성능과 근사해법을 활용한 해법의 성능을 비교한다.