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

DOI10.1007/S10100-023-00841-9MaRDI QIDQ6166938zbMATH OpenOpenAlexFDO

Authors Elif Garajová, Miroslav Rada

Publication date 4 August 2023

Published in CEJOR. Central European Journal of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2301.12785

zbMATH Keywords

interval programmingoptimal valuetransportation problem

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

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.

Recommendations

• On the transportation problems with interval data
• On the transportation problems with interval data
• The worst case finite optimal value in interval linear programming
• Bounds on the worst optimal value in interval linear programming
• Analysis of interval programming in different environments and its application to fixed-charge transportation problem

Cites work

• A heuristic solution technique to attain the minimal total cost bounds of transporting a homogeneous product with varying demands and supplies
• Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides
• Linear Optimization Problems with Inexact Data
• On strong optimality of interval linear programming
• On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows
• On the optimal solution set in interval linear programming
• Optimization and decision science: methodologies and applications. ODS, Sorrento, Italy, September 4--7, 2017
• The transportation paradox
• The worst case finite optimal value in interval linear programming
• Zur lösung linearer ungleichungssysteme bei störimg der rechten seite und der koeffizientenmatrix

Cited in

(4)

• 60 years of OR in Slovenia: development from a first conference to a vibrant community
• Complexity of computing the worst optimal value of interval transportation problems
• Recent theoretical and practical contributions to the or environment and CEJOR from the perspective of SSI-SOR
• Range of optimal values in absolute value linear programming with interval data

This page was built for publication: Interval transportation problem: feasibility, optimality and the worst optimal value

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166938)