Interval transportation problem: feasibility, optimality and the worst optimal value

Elif Garajová () and Miroslav Rada ()
Additional contact information
Elif Garajová: Charles University
Miroslav Rada: Prague University of Economics and Business

Central European Journal of Operations Research, 2023, vol. 31, issue 3, No 6, 769-790

Abstract: Abstract We consider the model of a transportation problem with the objective of finding a minimum-cost transportation plan for shipping a given commodity from a set of supply centers to the customers. Since the exact values of supply and demand and the exact transportation costs are not always available for real-world problems, we adopt the approach of interval programming to represent such uncertainty, resulting in the model of an interval transportation problem. The interval model assumes that lower and upper bounds on the data are given and the values can be independently perturbed within these bounds. In this paper, we provide an overview of conditions for checking basic properties of the interval transportation problems commonly studied in interval programming, such as weak and strong feasibility or optimality. We derive a condition for testing weak optimality of a solution in polynomial time by finding a suitable scenario of the problem. Further, we formulate a similar condition for testing strong optimality of a solution for transportation problems with interval supply and demand (and exact costs). Moreover, we also survey the results on computing the best and the worst optimal value. We build on an exact method for solving the NP-hard problem of computing the worst (finite) optimal value of the interval transportation problem based on a decomposition of the optimal solution set by complementary slackness. Finally, we conduct computational experiments to show that the method can be competitive with the state-of-the-art heuristic algorithms.

Keywords: Transportation problem; Interval programming; Optimal value (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10100-023-00841-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:cejnor:v:31:y:2023:i:3:d:10.1007_s10100-023-00841-9

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100

DOI: 10.1007/s10100-023-00841-9

Access Statistics for this article

Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger

More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().