IDEAS home Printed from https://ideas.repec.org/a/spr/aqjoor/v20y2022i1d10.1007_s10288-020-00467-6.html
   My bibliography  Save this article

An alternate approach to solve two-level hierarchical time minimization transportation problem

Author

Listed:
  • Prabhjot Kaur

    (UIET, Panjab University)

  • Anuj Sharma

    (Panjab University)

  • Vanita Verma

    (Panjab University)

  • Kalpana Dahiya

    (UIET, Panjab University)

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.

Suggested Citation

  • Prabhjot Kaur & Anuj Sharma & Vanita Verma & Kalpana Dahiya, 2022. "An alternate approach to solve two-level hierarchical time minimization transportation problem," 4OR, Springer, vol. 20(1), pages 23-61, March.
    • Handle: RePEc:spr:aqjoor:v:20:y:2022:i:1:d:10.1007_s10288-020-00467-6
    DOI: 10.1007/s10288-020-00467-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10288-020-00467-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10288-020-00467-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. R. S. Garfinkel & M. R. Rao, 1971. "The bottleneck transportation problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 18(4), pages 465-472, December.
    2. Dahiya, Kalpana & Verma, Vanita, 2007. "Capacitated transportation problem with bounds on RIM conditions," European Journal of Operational Research, Elsevier, vol. 178(3), pages 718-737, May.
    3. Éva Tardos, 1986. "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs," Operations Research, INFORMS, vol. 34(2), pages 250-256, April.
    4. R. K. Ahuja, 1986. "Algorithms for the minimax transportation problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 33(4), pages 725-739, November.
    5. Sonia & Munish Puri, 2004. "Two level hierarchical time minimizing transportation problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 12(2), pages 301-330, December.
    6. Vikas Sharma & Kalpana Dahiya & Vanita Verma, 2010. "Capacitated Two-Stage Time Minimization Transportation Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 27(04), pages 457-476.
    7. L. R. Ford & D. R. Fulkerson, 1957. "A primal‐dual algorithm for the capacitated Hitchcock problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 4(1), pages 47-54, March.
    8. Tomohiko Mizutani & Makoto Yamashita, 2013. "Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables," Journal of Global Optimization, Springer, vol. 56(3), pages 1073-1100, July.
    9. Peter L. Hammer, 1969. "Time‐minimizing transportation problems," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 16(3), pages 345-357, September.
    10. James B. Orlin, 1993. "A Faster Strongly Polynomial Minimum Cost Flow Algorithm," Operations Research, INFORMS, vol. 41(2), pages 338-350, April.
    11. Sharma, Anuj & Verma, Vanita & Kaur, Prabhjot & Dahiya, Kalpana, 2015. "An iterative algorithm for two level hierarchical time minimization transportation problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 700-707.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Fanrong Xie & Zuoan Li, 2022. "An iterative solution technique for capacitated two-stage time minimization transportation problem," 4OR, Springer, vol. 20(4), pages 637-684, December.
    2. Sharma, Anuj & Verma, Vanita & Kaur, Prabhjot & Dahiya, Kalpana, 2015. "An iterative algorithm for two level hierarchical time minimization transportation problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 700-707.
    3. Singh, Gurwinder & Singh, Amarinder, 2023. "Extension of Particle Swarm Optimization algorithm for solving two-level time minimization transportation problem," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 204(C), pages 727-742.
    4. Wang, Gang, 2024. "Order assignment and two-stage integrated scheduling in fruit and vegetable supply chains," Omega, Elsevier, vol. 124(C).
    5. Xie, Fanrong & Butt, Muhammad Munir & Li, Zuoan & Zhu, Linzhi, 2017. "An upper bound on the minimal total cost of the transportation problem with varying demands and supplies," Omega, Elsevier, vol. 68(C), pages 105-118.
    6. Shalabh Singh & Sonia Singh, 2022. "Shipment in a multi-choice environment: a case study of shipping carriers in US," Central European Journal of Operations Research, 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, vol. 30(4), pages 1195-1219, December.
    7. László A. Végh, 2017. "A Strongly Polynomial Algorithm for Generalized Flow Maximization," Mathematics of Operations Research, INFORMS, vol. 42(1), pages 179-211, January.
    8. Hochbaum, Dorit S., 2002. "Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations," European Journal of Operational Research, Elsevier, vol. 140(2), pages 291-321, July.
    9. Kavita Gupta & Ritu Arora, 2017. "More for less method to minimize the unit transportation cost of a capacitated transportation problem with bounds on rim conditions," OPSEARCH, Springer;Operational Research Society of India, vol. 54(3), pages 460-474, September.
    10. Balaji Gopalakrishnan & Seunghyun Kong & Earl Barnes & Ellis Johnson & Joel Sokol, 2011. "A least-squares minimum-cost network flow algorithm," Annals of Operations Research, Springer, vol. 186(1), pages 119-140, June.
    11. Orlin, James B., 1953-, 1995. "A polynomial time primal network simplex algorithm for minimum cost flows," Working papers 3834-95., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    12. Ting Pong & Hao Sun & Ningchuan Wang & Henry Wolkowicz, 2016. "Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem," Computational Optimization and Applications, Springer, vol. 63(2), pages 333-364, March.
    13. Amitai Armon & Iftah Gamzu & Danny Segev, 2014. "Mobile facility location: combinatorial filtering via weighted occupancy," Journal of Combinatorial Optimization, Springer, vol. 28(2), pages 358-375, August.
    14. Shoshana Anily, 1996. "The vehicle‐routing problem with delivery and back‐haul options," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(3), pages 415-434, April.
    15. Mao-Cheng Cai & Xiaoguang Yang & Yanjun Li, 1999. "Inverse Polymatroidal Flow Problem," Journal of Combinatorial Optimization, Springer, vol. 3(1), pages 115-126, July.
    16. Kavita Gupta & Ritu Arora, 2018. "Solving the problem of industry by formulating it as a fractional capacitated transportation problem with bounds on rim conditions," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(2), pages 509-516, April.
    17. Ilan Adler & Martin Bullinger & Vijay V. Vazirani, 2024. "A Generalization of von Neumann's Reduction from the Assignment Problem to Zero-Sum Games," Papers 2410.10767, arXiv.org.
    18. Amirmahdi Tafreshian & Neda Masoud & Yafeng Yin, 2020. "Frontiers in Service Science: Ride Matching for Peer-to-Peer Ride Sharing: A Review and Future Directions," Service Science, INFORMS, vol. 12(2-3), pages 44-60, June.
    19. László A. Végh, 2014. "Concave Generalized Flows with Applications to Market Equilibria," Mathematics of Operations Research, INFORMS, vol. 39(2), pages 573-596, May.
    20. Ravindra K. Ahuja & Dorit S. Hochbaum, 2008. "TECHNICAL NOTE---Solving Linear Cost Dynamic Lot-Sizing Problems in O ( n log n ) Time," Operations Research, INFORMS, vol. 56(1), pages 255-261, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:aqjoor:v:20:y:2022:i:1:d:10.1007_s10288-020-00467-6. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.