A heuristic for obtaining better initial feasible solution to the transportation problem
- PDF / 1,091,662 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 32 Downloads / 157 Views
A heuristic for obtaining better initial feasible solution to the transportation problem Md. Ashraful Babu1 · M. A. Hoque2 · Md. Sharif Uddin3 Accepted: 15 November 2019 © Operational Research Society of India 2019
Abstract Vogel’s Approximation Method (VAM) is known as the best algorithm for generating an efficient initial feasible solution to the transportation problem. We demonstrate that VAM has some limitations and computational blunders. To overcome these limitations we develop an Improved Vogel’s Approximation Method (IVAM) by correcting these blunders. It is compared with VAM on obtained initial feasible solutions to a numerical example problem. Reduction in the total transportation cost over VAM by IVAM is found to be 2.27%. Besides, we have compared IVAM with each of twelve previously developed methods including VAM on solutions to numerical problems. IVAM leads to the minimal total cost solutions to seven, better solutions to four and the same better solution to the remaining one. Finally, a statistical analysis has been performed over the results of 1500 randomly generated transportation problems with fifteen distinct dimensions, where each of them has 100 problems instances. This analysis has demonstrated better performance of IVAM over VAM by reducing the total transportation cost in 71.8% of solved problems, especially for large size problems. Thus IVAM outperforms VAM by providing better initial feasible to the transportation problem. Keywords Transportation problem · VAM · IVAM · Initial feasible solution · Minimal cost solution
1 Introduction The physical distribution of items from sources to destinations with the minimal total transportation cost subject to satisfying constraints on supplies and demands is referred to as transportation problem (TP). It is a special case of linear * M. A. Hoque [email protected]; [email protected] 1
Department of Quantitative Sciences (Mathematics), International University of Business Agriculture and Technology, Dhaka, Bangladesh
2
BRAC Business School, BRAC University, Dhaka 1212, Bangladesh
3
Department of Mathematics, Jahangirnagar University, Dhaka, Bangladesh
13
Vol.:(0123456789)
OPSEARCH
programming problem. Transport cost minimization is essential for delivering products to customers with reasonable prices. Researchers have tried to decide on the delivery plan that minimizes the total transportation cost while satisfying supply and demand constraints following the various forms of TP. Hochbaum and Woeginger [1] investigate a special case of the bottleneck transportation problem for any fixed number of sources s ≥ 1 and solve it in linear time. Baidya [2] develop the stochastic solid transportation models to minimize the total transport time and ensuring safety with the safety and time objective functions. Sharma and Sharma [3] a heuristic to solve the dual of a transportation problem which ( present ) runs in O cn2 time (n is the number of nodes in the network and c is the constant). Sabbagh and Ghafari [4] propose a new hybrid alg
Data Loading...
