The Classic Transportation Problem Computer Science Essay

The Classic Transportation Problem Computer Science Essay Classic Transportation Problem is a significant research issue in spatial data analysis and Network analysis in GIS; it helps to answer problems which relate in matching the supply and demand via set of objectives and constraints. The objective is to determine a set of origins and destinations for the supply so as to minimize the total cost. Geographic Information System (GIS) is an intelligent tool which combines characteristic data and spatial features and deal with the relationship connecting them. Although GIS application is extensively utilized in numerous activities, but in transportation its application is still rare. Basically, GIS is an information system which focusing on few factors which included the input, management, analysis and reporting of geographic (spatially related) information. Between all the prospective applications that GIS can be use for, issues on transportation have gained a lot of interest. An exact division of GIS related to issues on transportation has surfaced, which labelled as GIS-T. The Hitchcock transportation dilemma is conceivably one of the most solved linear programming problems in existence (Saul I. Gass, 1990). The addition of GIS into transportation (GIS-T) suggests that it is possible to integrate transportation data into GIS. Many research scholars have discussed computational considerations for solving the Classic Transportation problem (CTP): Shafaat and Goyal developed a procedure for ensuring an improved solution for a problem with a single degenerate basic feasible solution; Ramakrishnan described a variation of Vogels approximation method (VAM) for finding a first feasible solution to the CTP; and Arsham and Kahn described a new algorithm for solving the CTP. According to Brandley, Brown and Craves, 2004, practically the CTP is integrated in all texts on management science or operations management. In classic problem relating to transportation, particular objective for instance minimum cost or maximum profit will be the focus to integrate the GIS and the transportation data available. For example, (Jaryaraman and Prikul, 2001), (Jaryaraman and Ross, 2003), (Yan et al., 2003), (Syam, 2002), (Syarif et al., 2002), (Amiri, 2004), (Gen and Syarif, 2005), and (Trouong and Azadivar, 2005) had consider total cost of supply chain as an objective function in their studies. Nevertheless, there are no design tasks that are single objective problems. In this chapter, we present an in-depth computational comparison of the basic solution algorithms for solving the CTP. We will describe what we know with respect to solving CTPs in practice and offer comments on various aspects of CTP methodologies and on the reporting of computational results. In order to describe the core elements of the GIS transport model that is used to gain the solution to the CTP, it is essential to go over the different types of transportation models briefly, and elaborate on the application and issues of GIS in transportation. The chapter concludes with some final remarks. The Classic Transportation Problem (CTP) The Classic Transportation Problem (CTP) refers to a special class of linear programming. It has been recognized as a fundamental network problem. The Classic transportation problem of linear programming has an early history that can be traced to the work of Kantorovich, Hitchcock, Koopmans and Dantzig. By applying directly the simplex method to the standard linear-programming problem, it actually helps to solve it. Still, because of its very unique mathematical structure, it was acknowledged early that the simplex method applied to the CTP can be quite efficient on how to estimate the needed simplex-method information variable to enter the basis, variable to leave the basis and optimality conditions. Many practical transportation and distribution problems such as the fixed cost transportation, the minimum with fixed charge in logistics can be formulated as CTP. Mathematical formulation of the CTP There have been numerous studies conducted that focusing on new models or methods to verify the transportation or the logistics activities that can offer the least cost (Gen and Chen, 1997). Generally, logistics was defined as the quality of a flow of materials, such as the frequency of departure (number per unit time, adherence to the transportation time schedule and so on (Tilaus et al, 1997). Products can be assemble and sent to the allocation centres, vendors or plants. Hitchcock, 1941 has initiated the earliest formulation of a planar transportation model, which used to find an approach to transport homogeneous products from several resources to several locations so that the total cost can be minimized. According to Jung-Bok Jo, Byung -Ki Kim and Ryul Kim, 2008, the development of a variety of deterministic and / or stochastic models have been increased throughout the past several decades. The basic problem sometimes called the general or Hitchcock transportation problem can be known in a mathematic way as follows: Where m is the number of supply centres and n is the number of demand points. This is subjected to: Without loss of generality, it is assumed that, the problem is balanced, i.e. Total Demand = Total Supply Where; ai, bj, cij, xij à ¢Ã¢â‚¬ °Ã‚ ¥ 0 (non negativity constants) à ¢Ã¢â€š ¬Ã‚ ¦2.4 All the parameters are free to take non negative real values. The ais are called supplies and the bis are called demands. For our discussion here, we also assume that the costs cij à ¢Ã¢â‚¬ °Ã‚ ¥ 0. A number of heuristic methods to solve the classic transportation problem have been proposed. (Gottieb et el., 1998; Sun et al., 1998; Adlakha and Kowalski, 2003; Ida et al., 2004). According to Chan and Chung, 2004, in order to distribute problem in a demand driven SCN, they have suggested a multi- objective genetic optimization. They also measured minimization of total cost of the system, total delivery days and the equity of the capacity utilization ratio for manufacturers as objectives. Meanwhile, Erol and Ferrel, 2004, have recommended a model that assigned suppliers to warehouses and warehouses to customers. In addition, the SCN design problem was formulated as a multi- objective stochastic mixed inter linear programming model, which then was resolved by a control method, and branch and bound techniques (Guillen et al., 2005). Chan et al., 2004, stated that objectives were SC profit over the time horizon and customer satisfaction level and they also developed a hybrid approach regarding to genetic algorithm and Analytical Hierarch Process (AHP) for production and distribution problems in multi-factory supply chain models. Jung-Bok Jo, Byung -Ki Kim and Ryul Kim, 2008, has measured few objectives in their research namely; operation cost, service level, and resources utilization. In this project, it has been considered about the integration of the CTP into the GIS environment, which little or no research has been done into this line of study. Our formulation will be particularly concentrated on the use of several GIS software and procedures to see how the CTP problem can be solved in the GIS environment. In that note and as already stated in chapter one, in trying to integrate CTP into the GIS environment, two of the algorithm explained in this literature review will be used to solved the CTP problem to get the initial basic feasible solutions and one optimal solution method will be used to get the optimal solution that will be integrated into the GIS software environment to solve the CTP problem. 2.4 Methods of solving Transportation problems The practical importance of determining the efficiency of alternative ways for solving transportation problems is affirmed not only because of the sizeable fraction of the linear programming literature has been dedicated to these problems, but also by the fact that an even larger allocation of the concrete industrial and military appliances of linear programming deal with transportation problem. Transportation problems often occur as sub-problems in a bigger problem. Moreover, industrial applications of transportation problems often contain thousands of variables, and hence a streamlined algorithm is not computationally worthwhile but a practical necessity. In addition, many of linear programs that occurred can nevertheless be given a transportation problem formulation and it is also possible to approximate certain additional linear programming problems by such a formulation. Efficient algorithms existed for the solution of transportation. A computational study done by Glover et al. suggested that the fastest method for solving Classic transportation problems is a specialization of the primal simplex method due to Glover et al. Using data structured due to M.A. Forbes, J.N. Holt, A.M Watts, 1994. An implementation of this approached, is capable of handling the general transshipment problem. The method is particularly suitable for large, spares problems where the number of arcs is a small multiple of the number of nodes. Even for dense problems the method is considered to be competitive with other algorithms (M.A. Forbes, J.N. Holt, A.M Watts, 1994). Another consideration of the CTP model is the formulation made by Dantzigs, which is adaptation of the simplex method to the CTP as the primal simplex transportation method (PSTM). This method is known as the method-modified distribution method (MODI); it has also been acknowledged as the row-column sum method (A.Charnes and W. W. Cooper, 1954). Subsequently, another method calledthe stepping-stone method (SSM) has been developed by Charnes and Cooper which gives an option of determining the simplex-method information. According to the paper written by Charnes and Cooper which is entitled The stepping stone method of explaining linear programming calculations in transportation problems. The SSM is a very nice way of demonstrating why the simplex method works without remedy to its terminology or methods although Charnes and Cooper describe how the SSM and PSTM are related. Charnes and Cooper note that the SSM is relatively easy to explain, but Dantzigs PSTM has certain advantages for large-scale hand calculations (Saul I. Gass, 1990) However, the SSM, contrary to the impression one gets from some texts and from the paper by Arsham and Kahn, is not the method of choice for those who are serious about solving the CTP-such as an analyst who is concerned with solving quite large problems and may have to solve such problems repetitively, e.g. where m = 100 origins and n = 200 destinations, leading to a mathematical problem of 299 independent constraints and 20,000 variables (Saul I. Gass, 1990). In addition to the PSTM and the SSM, a number of methods have been proposed to solve the CTP. They include (amongst others) the following: the dual method of Ford and Fulkerson, the primal partitioning method of Grigoriadis and Walker, the dualplex partitioning method of Gass, the Hungarian method adaptation by Munkres, the shortest path approach of Hoffman and Markowitz and its extension by Lageman, the decomposition approach of Williams, the primal Hungarian method of Balinski and Gomory, and, more recently, the tableau-dual method proposed by Arsham and Kahn. (The early solution attempts of Kantorovich, Hitchcock and Koopmans are excluded as they did not lead to general computational methods.) (Saul I. Gass, 1990). The first papers that dealt with machine-based computational issues for solving the TP are Suzuki, Dennis and Ford and Fulkerson. Implementations of CTP algorithms were quite common on the wide range of 1950s and 1960s computers-a listing is given in Gass. CTP computer-based procedures at that time included Charnes and Coopers SSM, the flow (Hungarian) method of Ford and Fulkerson, Munkres Hungarian method, the modified simplex method of Suzuki, Dantzigs PSTM and Dennis implementation of the PSTM. The developers of these early computer codes investigated procedures for finding first feasible solutions such as VAM, the north-west corner method (NWCM), and variations of minimum-cost allocation procedures (Saul I. Gass, 1990). They also investigated various criteria for selecting a variable to enter the basis. Problems of realistic size could be solved, e.g. m + n The work of Glover et al. represents a landmark in the development of a TP computer-based algorithm and in computational testing. Their code is a PSTM that uses special list structures for maintaining and changing bases and updating prices. Glover et al. tested various first-basis finding procedures and selection rules for determining the variable to enter the new basis. They concluded that the best way to determine a first feasible solution is a modified row-minimum rule, in which the rows are cycled through in order, each time selecting a single cell with the minimum cost to enter the basis. The cycling continues until all row supplies are exhausted. This differs from the standard row-minimum rule, in which the minimum cost cells are selected in each row, starting with the first row, until the current row supply is exhausted. The modified row minimum rule was tested against the NWCM, the VAM, a row-minimum rule and a row-column minimum rule in which a row is scanned first for a min imum cell and then a column is scanned, depending on whether the supply or demand is exhausted (Saul I. Gass, 1990). Although VAM tended to decrease the number of basis changes to find the optimal solution, it takes an inordinate amount of time to find an initial solution, especially when compared to the time to perform a basis change (100 changes for 100 x 100 problem in 0.5 s on a CDC 6400 computer). We feel VAM should be relegated to hand computations, if that. Glover et al. tested a number of rules for determining the variable to enter the basis, including the standard most negative evaluator rule. Their computational results demonstrated that a modified row-first negative evaluator rule was computationally most efficient. This rule scans the rows of the transportation cost tableau until it encounters the first row containing a candidate cell, and then selects the cell in this row which violates dual feasibility by the largest amount. They also compared their method to the main competitive algorithms in vogue at that time, i.e. the minimum-cost network out-of-kilter method adapted to solve the TP, the standard simplex method for solving the general linear-programming problem and a dual simplex method for solving a CTP. The results of the comparison showed that the Glover et al. method was six times faster than the best of the competitive methods (Saul I. Gass, 1990). . A summary of computational times for their method showed that the median solution time for solving 1000 x 1000 TPs on a CDC 6000 computer was 17 s, with a range of 14-22 s. As the TP is a special case of a minimum-cost network problem (transhipment problem), methods for solving the latter-type problem (such as the out-of-kilter method) are readily adaptable for solving CTPs. Bradley et al. developed a primal method for solving large-scale trans- shipment problems that utilizes special data structures for basis representation, basis manipulation and pricing. Their code, GNET, has also been specialized to a code (called TNET) for solving capacitated TPs. Various pricing rules for selecting the incoming variable were tested, and a representative 250 x 4750 problem was solved in 135 s on an IBM/360/67 using TNET, with the number of pivots and total time being a function of the pricing rule. The GNET procedure has also been embedded into the MPSIII computer-based system for solving linear-programming problems developed by Ketron Management Science Inc.24 It is called WHIZNET and is designed to solve capacitated trans-shipment problems, of which the TP is a special case. A typical trans-shipment problem with 5000 nodes and 23,000 arcs was solved in 37.5 s on an IBM 3033/N computer (L. Collatz and W. Wetterling, 1975). Another general network problem-solver, called PNET, is a primal simplex method for solving capacitated and uncapacitated transhipment and TPs. It solved a TP with 2500 origins and 2500 destinations in under 4 min of CPU time on a UNIVAC 1108. It uses augmented thread index lists for the bases and dual variables. (Saul I. G ass, 1990). From the above, we see that the present day state-of-the-art for solving TPs on mainframe computers is quite advanced. With the advent of PCs, we find that a number of researchers and software houses have developed PC-based codes for solving TPs. Many of the codes were developed for the classroom and are capable of solving only small, textbook-size problems. For example, the TP procedure in Erikson and Hall (Saul I. Gass, 1990) is able to solve problems of the order of 20 x 20. A typical commercial TP program is that of Eastern Softwares TSP88 which can solve TPs with up to 510 origins and/or destinations. It is unclear as to what algorithms are used in the PC TP codes, but we hazard a guess that they are a version of either PSTM or SSM (Saul I. Gass, 1990). 2.5 Degeneracy in the Classic transportation problem Degeneracy can occur when the initial feasible solution has a cell with zero allocation or when, as a result of real reallocation, more than one previously allocated cell has a new zero allocation. Whenever we are solving a CTP by the PSTM or the SSM, we must determine a set of non-negative values of the variables that not only satisfies the origin and destination constraints, but also corresponds to a basic feasible solution with m + n -1 variables (Saul I. Gass, 1990). . For computational efficiency, all basic cells are kept in a list, with those cells forming the loop being ordered at the top of the list and with the entering cell being first in the list. The remaining cells in the loop are sequenced such that proceeding through them follows the loop. The use of the allocated cells easily handles degeneracy. The PSTM and the SSM do not use a representation of the basis inverse, as does the general simplex method. Instead, these methods take advantage of the fact that any basis to the TP corresponds to a spanning tree of the bipartite network that describes the flows from the origin nodes to the destination nodes (G.B. Dantzig, 1963). Thus, if one is given a basic feasible solution to a CTP which can be readily generated by, say, the NWCM and that solution is degenerate, then one must determine which of the arcs with zero flow should be selected to complete the tree. Having the tree that corresponds to the current basic feasible solution enables us t o determine if the current solution is optimal and, if it is not, to determine the entering and leaving variables and the values of the variables in the new solution (Saul I. Gass, 1990). The problem of selecting a tree for a degenerate basic feasible solution to a CTP was recognized early by Dantzig (G.B. Dantzig, 1963) who described a simple perturbation procedure that caused all basic feasible solutions to be non-degenerate. From our literature gathered from above, the computer-based CTP solution methods described above, degeneracy does not appear to be of concern. We gather that most computer- based methods for solving CTPs invoke some type of perturbation procedure to complete the tree. We note that the problem of selecting a tree for a degenerate basic feasible solution is really only a minor problem if the first basic feasible solution is degenerate. For this case, a perturbation scheme or a simple selection rule that selects a variable or variables with zero value to complete the tree can be applied. (L. Collatz and W. Wetterling, 1975) and (G. Hadley, 1962). As the selection of appropriate zero-valued variables is usually not unique, a simple decision rule is used to make a choice, e.g. to select those variables that have the smallest costs. Once a tree has been established for the first basic feasible solution, the SSM and PSTM prescriptions for changing bases will always yield a new basic feasible solution and corresponding tree, no matter how many degenerate basic feasible variables there are. Subsequent degenerate basic feasible solutions can be generated if there are ties in the selection of a variable to leave the basis. Dropping one and keeping those that were tied at zero level will always yield a tree. Again, a simple decision rule is used to determine which one is dropped from the basis (Saul I. Gass, 1990). Degeneracy can be of concern in that it could cause a series of new bases to be generated without decreasing the value of the objective function-a phenomenon termed stalling. In their paper, Gavish et al. (B. Gavish, P. Schweitzer and E. Shlifer, 1977) study the zero pivot phenomenon in the CTP and assignment problem (AP) and develop rules for reducing stalling, i.e. reducing the number of zero pivots (Saul I. Gass, 1990). For various size (randomly generated) problems, they show that for the CTP the average percentage of zero pivots to total pivots can be quite high, ranging from 8% for 5 x 5 problems to 89% for 250 x 250 problems which are started with the modified row-minimum rule for selecting the first basic feasible solution. They also show that the percentage of zero pivots is not sensitive to the range of values of the cost coefficients, but is sensitive to the range of values of the ais and bjs, with a higher percentage of zero pivots occurring when the latter range is tight. For the m x m AP, which will always have (m 1) basic variables that are zero, the average percentage of zero pivots ranged from 66% for 5 x 5 problems to 95% for 250 x 250 problems. Their rules for selecting a first basic feasible solution, the variable to enter the basis and the variable to leave the basis cause a significant reduction in total computational time (Saul I. Gass, 1990). In their paper, Shafaat and Goyal (A. Shafatt and A.B. Goyal, 1988) develop a procedure for selecting a basic feasible solution with a single degeneracy such that the next solution will improve the objective function value. There procedure forces the entering variable to have an exchange loop that does not involve the degenerate position with a negative increment (Saul I. Gass, 1990). The efficiency of their procedure in terms of computer time versus the small amount of computer time required to perform a number of basis changes (as noted above) is unclear. For large-scale CTPs, we conjecture that a single degenerate basic feasible solution will not cause much stalling, as the chances are that the entering variable will not be on an exchange loop that contains the degenerate variable. We note that a CTP or a linear-programming problem in general, with single degenerate basic feasible solutions will not cycle (Saul I. Gass, 1990). 2.6 Method of finding Initial Basic Feasible Solutions A basic solution is any collection of (n + m 1) cells that does not include a dependent subset. The basic solution is the assignment of flows to the basic cells that satisfies the supply and demand constraints. The solution is feasible if all the flows are non negative. From the theory of linear programming we know that there is an optimal solution that is a feasible solution. The CTP has n+ m constraints with one redundant constraint. A basic solution for this problem is determined by selection (n + m 1) independent variables. The basic variable assumes values to satisfy the supplies and demands, while the non basic values are zero. Thus the m + n equations are linearly dependent. As we will see, the CTP algorithm exploits this redundancy. There are five methods used to determine the initial basic feasible solutions of the classic transportation problem (CTP): these are listed below. The least cost method The northwest corner method The Vogels approximation method Row minimum method Column minimum method The five methods normally differ in the quality of the starting basic solution they produce and better starting solutions yields a smaller objective value. Some heuristics give better performance than the given common methods. The NWCM gives a solution very far from optimal solution. The least cost method finds a better starting solution by concentrating on the cheapest route. The Vogels Approximation method (VAM) is an improved version of the least cost method that generally produces better starting solutions. The row minimum method starts with first row and chooses the lowest cost cell of first row so that either the capacity of the first supply is exhausted or the demand at jth distribution centre is satisfied or both. The column minimum method starts with first column and chooses the lowest cost cell of first column so that either the demand of the first distribution centre is satisfied or the capacity of the ith supply is exhausted or both. However, among the five methods listed above, the North West Corner Method (NWCM), the Lowest Cost Method (LCM), and the Vogels Approximation method are the most commonly used methods used in finding the initial basic feasible solutions of the CTP. The NWCM gives a solution very far from optimal solution and Vogels Approximation method and LCM tries to give result that are often optimal or near to optimal solution. In a real-time application, Vogels Approximation Method (VAM) will yield a considerable savings over a period of time. On the other hand, if ease of programming and memory space are major considerations, the NWCM is still acceptable for reasonable matrix sizes (up to 50 X 50). However, the difference in times between the two loading techniques increases exponentially. (Totschek and Wood,2004). Another work presents an alternative of Vogels Approximation Method for TP and this method is more efficient than traditional Vogels Approximation Method (Mathirajan, Meenakshi, 2004). In this project however, we are making use of the Northwest Corner method (NWCM) and the Least Cost Method (LCM) to find the initial basic feasible solutions to the CTP. These solutions will then be used further to get optimal solutions to the CTP by using the Stepping Stone Method (SSM). The final answers will then be compared with the solutions procedures obtained from the GIS software environment to solve the CTP in a method other than the sophisticated mathematical solutions already explained in this literature. Methods of finding Optimal Solution of the CTP Basically two universal methods are used for finding optimal solutions. These are the Stepping Stone method and the Modified Distribution Method (MODI) method. Some heuristics are generated to getting better performance. Different methods are compared for speed factor. Transportation Simplex Method and Genetic Algorithms are compared in terms of accuracy and speed when a large-scale problem is being solved. Genetic Algorithms prove to be more efficient as the size of the problem becomes greater (Kumar and Schilling, 2004). Proposed digital computer technique for solving the CTP is by the stepping stone method. The average time required to perform an iteration using the method described here depends linearly on the size of the problem, m + n. (Dennis). The solution of a real world problem to efficiently transport multiple commodities from multiple sources to multiple different destinations using a finite fleet of heterogeneous vehicles in the smallest number of discrete time periods g ives improvement by backward decomposition (Poh, Choo and Wong, 2005).The most efficient method for solving CTP arises by coupling a primal transportation algorithm with a modified row minimum start rule and a modified row first negative evaluator rule. (Glover, Karney, Kligman, Napier, 1974) this has already been explained above. Application Software Geographic Information Systems (GIS) is a field of with an exponential growth that has a pervasive reach into everyday life. Basically, GIS provides a mean to convert data from tables with topological information into maps. Subsequently GIS tools are capable of not only solving a wide range of spatially related problems, but also performing simulations to help expert users organized their work in many areas, including public administration, transportation networks, transportation networks and environmental applications. Below gives some of the software that has been used by many researchers in transportation modeling. Much software have been used to solve the CTP problem for example, the MODI Algorithm was coded in FORTRAN V, and further substantial time reductions may result by a professional coding of the algorithm in Assembler language. Zimmer reported that a 20-to-1 time reduction was possible by using Assembler rather than FORTRAN in coding minimum path algorithms. (Srinivasan and Thompson, 1973).One work investigated generalized network problems in which flow conservation is not maintained because of cash management, fuel management, capacity expansion etc (Gottlieb,2002). Optimal solution to the pure problem could be used to solve the generalized network problem. One work introduces a generalized formulation that addresses the divide between spatially aggregate and disaggregate location modelling (Horner and OKelly, 2005). In this research we are making use of ArcGIS Network analyst, together with ArcMap, ArcCatalog, VBA, Python, PuLP, GLPK (GNU Linear Programming Kit) and ArcObject software to design our model to solve the CTP problem. A detail solution algorithm is explained in chapter 4. The GLPK (GNU Linear Programming Kit) is an open source software package intended for solving large scale linear programming (LP), mixed integer programming (MIP), and other related problems. It is a set of routine written in ANSI C and organized in the form a callable library. The GLPK package includes the following main components: Primal and dal simplex methods Primal-dual interior- point method Branch and- cut method Application program interface (API) Translator for GNU Math Program Stand-alone LP/MIP solver PuLP is a LP modeller written in Python. PuLP can generate LP and MPS files and call GLPK, to solve linear problems. PuLP provides a nice syntax for creation of linear problems, and a simple way to call the solvers to perform the optimization. ArcGIS Network Analyst is still relatively new software, so there are not much published materials concerning its application on transportation problems. Only few researchers during the last years have reported the use of the ArcGIS Network Analyst extension in order to solve some transportation problems. ArcGIS Network Analyst (ArcGIS NA) is a powerful tool of ArcGIS desktop 9.3 that provides network- based spatial analysis including routing, travel directions, closest facility, and service area analysis. ArcGIS NA enables users to dynamically model realistic network con