A Two-Phase Method for Solving Transportation Models with Prohibited Routes

Joseph Ackora-Prah; Valentine Acheson; Benedict Barnes; Ishmael Takyi; Emmanuel Owusu-Ansah

doi:10.1145/1787234.1787249

Author(s)

Joseph Ackora-Prah Department of Mathematics, Faculty of Physical and Computational Sciences, Kwame Nkrumah University of Science and Technology, Kumasi, Ghana

Valentine Acheson Department of Mathematics, Faculty of Physical and Computational Sciences, Kwame Nkrumah University of Science and Technology, Kumasi, Ghana

Benedict Barnes Department of Mathematics, Faculty of Physical and Computational Sciences, Kwame Nkrumah University of Science and Technology, Kumasi, Ghana

Ishmael Takyi Department of Mathematics, Faculty of Physical and Computational Sciences, Kwame Nkrumah University of Science and Technology, Kumasi, Ghana

Emmanuel Owusu-Ansah Department of Mathematics, Faculty of Physical and Computational Sciences, Kwame Nkrumah University of Science and Technology, Kumasi, Ghana

Abstract

The Transportation Problem (TP) is a mathematical optimization technique which regulates the flow of items along routes by adopting an optimum guiding principle to the total shipping cost. However, instances including road hazards, traffic regulations, road construction and unexpected floods sometimes arise in transportation to ban shipments via certain routes. In formulating the TPs, potential prohibited routes are assigned a large penalty cost, M; to prevent their presence in the model solution. The arbitrary usage of the big M as a remedy for this interdiction does not go well with a good solution. In this paper, a two-phase method is proposed to solve a TP with prohibited routes. The first phase is formulated as an All-Pairs Least Cost Problem (APLCP) which assigns respectively a non-discretionary penalty costM? ij M to each of n prohibited routes present using the Floyd’s method. At phase two, the new penalty values are substituted into the original problem respectively and the resulting model is solved using the transportation algorithm. The results show that, setting this modified penalty cost (M?) logically presents a good solution. Therefore, the discretionary usage of the M 1 is not a guarantee for good model solutions. The modified cost M? M so attained in the sample model, is relatively less than the Big M( 1) and gives a good solution which makes the method reliable.

Publication Details

Page(s) 749-758

DOI 10.1145/1787234.1787249

Published Journal: Pakistan Journal of Statistics and Operation Research, Volume: 18, Issue: 3, Year: 2022

Request the full text from PASTIC

Keywords

Adjacency Matrix, All-pairs Least Cost Problem, Large Penalty Cost, Modified Penalty Cost., Shortest-Route Problems, Floyd's Method