Two-stage Interval Time Minimization Transportation Problem with Capacity Constraints

Abstract

This paper discusses a two-stage interval time minimization transportation problem with capacity constraints on each source-destination link. In the current problem, the exact total demand of all the destinations lies in an interval whose end points are equal to the minimum and the maximum total available amount of the homogeneous product (which is being transported), at the sources.  The minimum amount available at the sources is transported in the first stage of transportation, while enough amount of the product is shipped in the second stage so as to meet the exact total demand of the destinations. The objective of the current paper is to obtain a transportation schedule so that the transportation in both the stages is carried out in the minimum possible time. A polynomial time iterative algorithm is proposed which generates a sequence of pairs of Stage-I and Stage-II times. Firstly, a related standard cost minimization transportation problem (CMTP) is solved and then at each iteration, a restricted version of this CMTP is solved in which the time of Stage-I decreases strictly and the time of Stage-II increases. Out of these generated pairs, a pair with the minimum sum of transportation times of Stage-I and Stage-II is considered as the global optimal solution. Numerical illustration is included in the support of the theory.

Keywords: Time transportation problem, Combinatorial optimization, Non-convex programming.