An alternate approach to solve two-level hierarchical time minimization transportation problem
- PDF / 462,930 Bytes
- 39 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 204 Views
An alternate approach to solve two-level hierarchical time minimization transportation problem Prabhjot Kaur1 · Anuj Sharma2 · Vanita Verma3 · Kalpana Dahiya1 Received: 28 October 2019 / Revised: 28 October 2019 / Accepted: 17 November 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract This paper discusses a two-level hierarchical time minimization transportation problem, which is an important class of transportation problems arising in industries. This problem has been studied by various researchers (Sharma et al. in Eur J Oper Res 246:700–707, 2015; Sonia and Puri in TOP 12(2):301–330, 2004; Xie et al. in Comput Oper Res 86:124–139, 2017) and therefore, a number of polynomial time iterative algorithms are available to find its solution. All the existing algorithms, though efficient, have some shortcomings. The current study proposes an alternate solution algorithm for the problem that is more efficient in terms of computational time than the existing algorithms. The results justifying the underlying theory of the proposed algorithm are given. Further, a detailed comparison of the computational behaviour of all the algorithms for randomly generated instances of this problem, of different sizes validates the efficiency of the proposed algorithm. Keywords Global optimization · Concave minimization · Transportation problem · Hierarchical optimization Mathematics Subject Classification 90C26 · 90C27
B
Kalpana Dahiya [email protected] Prabhjot Kaur [email protected] Anuj Sharma [email protected] Vanita Verma [email protected]
1
UIET, Panjab University, Chandigarh 160014, India
2
Department of Computer Science and Applications, Panjab University, Chandigarh 160014, India
3
Department of Mathematics, Panjab University, Chandigarh 160014, India
123
P. Kaur et al.
1 Introduction In recent years, with the development of economical globalization, goods transportation problems are focused on by more and more companies and enterprises, especially many multi-national corporations. A transportation problem is an optimization problem which aims at an optimal distribution of a homogeneous product from several sources to various destinations at the minimum cost. The classical transportation problem, also known as cost minimizing transportation problem (CMTP), was originally developed by Hitchcock (1941) and Koopmans (1947) and later studied by several other researchers (Bit et al. 1993; Dahiya and Verma 2007; Ford and Fulkerson 1957; Hammer 1969; Kaur and Dahiya 2015; Khanna et al. 1983; Khanna and Puri 1984; Klingman and Russel 1974; Rachev and Olkin 1999; Zheng et al. 1994). Various strongly polynomial time algorithms to solve CMTP are available (see Orlin 1993, Tardos 1985, 1986). The best strongly polynomial time algorithm for an uncapacitated CMTP with complexity bound O(nlogn(m + nlogn)) was obtained by Orlin (1993) where m and n denote the number of sources and destinations, respectively. Later on, Kleinschmidt and Schannath (1995) developed an algorithm which runs in the time proportional
Data Loading...
