The Classic Transportation Problem Computer Science Essay Example

profit. 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) considered the total cost of the supply chain as an objective function in their studies.

Despite design tasks not being single objective problems, in this chapter, we provide a comprehensive computational comparison of the basic solution algorithms for solving the CTP. We will discuss the practical aspects of solving CTPs and provide commentary on various CTP methodologies and reporting of computational results. To understand the core elements of the GIS transport model used to solve the CTP, it is necessary to briefly review different types of transportation models and examine the application and issues of GIS in transportation. The chapter concludes with final remarks.

The Classic Transportation Problem (CTP)

The CTP is a specific class of linear programming.

It has been acknowledged as a fundamental network issue. The historical roots of the linear programming Classic transportation problem can be traced back to the contributions of Kantorovich, Hitchcock, Koopmans, and Dantzig. When the simplex method is directly applied to the regular linear-programming problem, it offers effective solutions. However, due to the unique mathematical structure of the CTP, it has been recognized early on that applying the simplex method to this problem can efficiently estimate the necessary information variables for the basis entry, basis exit, and optimality conditions.

The CTP, which stands for fixed cost transportation and minimum with fixed charge in logistics, is a formulation for many practical transportation and distribution problems.

Mathematical Formulation Of The CTP

Many studies have been conducted to develop new models or methods for optimizing transportation

and logistics activities to minimize costs (Gen and Chen, 1997). Logistics is generally defined as the quality of material flow, including factors such as departure frequency and adherence to transportation schedules (Tilaus et al, 1997). Products can be assembled and sent to allocation centers, vendors, or plants. The earliest formulation of a planar transportation model was initiated by Hitchcock in 1941. This model aimed to find the most efficient way to transport homogeneous products from multiple resources to multiple locations, with the goal of minimizing total cost.

According to Jung-Bok Jo, Byung-Ki Kim, and Ryul Kim (2008), there has been an increase in the development of various deterministic and/or stochastic models over the past few decades. The basic problem, sometimes referred to as the general or Hitchcock transportation problem, can be mathematically defined as follows: all parameters are allowed to take non-negative real values. The a's are referred to as supplies, and the b's are referred to as demands. In our discussion here, we will also assume that the costs are...

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), they have suggested a multi-objective genetic optimization in order to distribute the problem in a demand-driven supply chain network (SCN). They measured minimization of the total cost of the system, total delivery days, and equity of the capacity utilization ratio for manufacturers as objectives. Meanwhile, Erol and Ferrel (2004) recommended a model that assigned suppliers to warehouses and warehouses to customers. Additionally, the SCN design problem was formulated as a

multi-objective stochastic mixed integer linear programming model, which was resolved by a control method and branch and bound techniques (Guillen et al., 2005).

Chan et al., 2004, conducted a study on supply chain models and found that the objectives were SC profit and customer satisfaction. They developed a hybrid approach using genetic algorithm and Analytical Hierarch Process (AHP) for production and distribution problems in multi-factory supply chains. In another research, Jung-Bok Jo, Byung -Ki Kim, and Ryul Kim, 2008, measured several objectives including operation cost, service level, and resources utilization. This project aims to integrate the CTP into the GIS environment, which has received little attention in previous research. The study will focus on utilizing GIS software and procedures to solve the CTP problem. To achieve this, two algorithms explained in the literature review will be used to obtain initial feasible solutions, and an optimal solution method will be employed to integrate the optimal solution into the GIS software environment.

Methods of Solving Transportation Problems

The significance of determining the efficiency of different approaches to solving transportation problems is not only demonstrated by the extensive amount of linear programming literature dedicated to these issues, but also by the prevalence of transportation problems in various concrete industrial and military applications of linear programming. Transportation problems often appear as sub-problems within larger contexts, and the industrial applications themselves frequently involve a multitude of variables, making a streamlined algorithm not only preferable but necessary from a practical standpoint. Furthermore, certain additional linear programming problems can be approximated using transportation problem formulations. There are existing efficient algorithms for solving transportation problems, as demonstrated in a computational study conducted by Glover et al.

It

has been proposed that the most efficient way to solve Classic transportation problems is to use a variation of the primal simplex method created by Glover et al. This approach utilizes data structure developed by M.A. Forbes, J.N. Holt, A.M Watts in 1994. The implementation of this approach is able to address the general transshipment problem.

The method is especially useful for large, sparse problems where the number of arcs is only a small multiple of the number of nodes. It is also considered competitive with other algorithms even for dense problems (M.A. Forbes, J.N. Holt, A.M Watts, 1994).

Another consideration of the CTP model is the formulation made by Dantzig’s, which is an adaptation of the simplex method to the CTP known as the primal simplex transportation method (PSTM). This method is referred to as the method-modified distribution method (MODI) or the row-column sum method (A.Charnes and W. W. Cooper, 1954).

The Stepping-Stone method (SSM) is an alternative method to determine simplex-method information, developed by Charnes and Cooper. According to their paper titled "The stepping stone method of explaining linear programming calculations in transportation problems", the SSM effectively demonstrates why the simplex method works without relying on its terminology or methods. Charnes and Cooper also discuss the relationship between the SSM and Dantzig's PSTM, noting that while the SSM is relatively easy to explain, the PSTM has certain advantages for large-scale hand calculations. However, despite some misleading texts and Arsham and Kahn's paper, the SSM is not the preferred method for solving critical path problems for analysts working with large and repetitive problem solving situations.

According to Saul I. Gass (1990), there is a mathematical problem involving 100

origins (m) and 200 destinations (n), resulting in 299 independent constraints and 20,000 variables. In addition to the PSTM and the SSM, various methods have been suggested to solve the CTP. These methods include 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. Note that the earlier solution attempts of Kantorovich, Hitchcock and Koopmans are not considered as they didn't result in general computational methods.

In the 1950s and 1960s, several papers were published on machine-based computational strategies for solving the transportation problem (TP). Notable authors in this area were Suzuki, Dennis, Ford, and Fulkerson. Implementations of TP algorithms were widely used during this time on various computers. Gass provides a list of such implementations. Among the computer-based methods employed for solving the TP were Charnes and Cooper's SSM, Ford and Fulkerson's flow (Hungarian) method, Munkres' Hungarian method, Suzuki's modified simplex method, Dantzig's PSTM, and Dennis' implementation of the PSTM. The developers of these early computer codes also explored approaches for finding initial feasible solutions, such as VAM, the north-west corner method (NWCM), and different variations of minimum-cost allocation procedures (Saul I).

Gass (1990) conducted investigations on selecting a variable to enter the basis and examined different criteria. Realistic problems, such as m + n < 7,500 on the IBM 704 computer and m + n < 8,000 on a UNIVAC 1103

computer, could be solved. Ford and Fulkerson's procedure reported a computing time of 4 mins 58 s on an IBM 704 for a 220 x 30 problem.

In the 1970s and 1980s, with the emergence of a new generation of computers and fewer types of large-scale computers, specialized codes for solving CTPs became scarce. Instead, general codes for mathematical programming systems (MPS) started gaining popularity in solving large-scale linear programming problems. These MPS had embedded speed, problem-generation methods, and reporting procedures that made them efficient for solving CTPs as standard linear programs. However, advancements in technology and computer programming, along with the need to solve large-scale transportation problems and minimum-cost problems in network distribution, prompted researchers to develop special computer-based CTP codes. The work done by Glover et al. is highly significant in the development of a computer-based algorithm for TP and in conducting computational testing.

Their code is a PSTM that utilizes special list structures for maintaining and modifying bases and updating prices. In their study, Glover et al. examined different methods for identifying the initial basis and selecting the variable to enter the new basis. They found that the most effective approach is a modified row-minimum rule, where each row is iterated through sequentially, selecting the cell with the lowest cost to enter the basis. This iteration continues until all row supplies are depleted. This approach deviates from the standard row-minimum rule, which selects the minimum cost cells in each row, starting from the first row and continuing until the current row supply is depleted.

The modified row minimum rule was tested against various other methods including the NWCM, the VAM, a row-minimum rule,

and a row-column minimum rule which scans a row first and then a column depending on supply or demand (Saul I. Gass, 1990). While the VAM tended to reduce the number of basis changes needed to find the optimal solution, it took a significantly longer time to find an initial solution compared to performing a basis change (100 changes for a 100 x 100 problem in 0.5 seconds on a CDC 6400 computer). We believe that VAM should only be used for manual computations. Glover et al. also tested various rules for determining the variable to enter the basis, including the standard most negative evaluator rule.

Their study showed that a revised row-first negative evaluator rule was the most efficient computationally. This rule works by scanning the rows of the cost tableau for transportation until it finds the first row with a potential cell. It then selects the cell in this row that goes against dual feasibility by the greatest extent. They also compared their approach to the leading algorithms being used at that time, such as the minimum-cost network out-of-kilter method for solving the transportation problem (TP), the standard simplex method for solving general linear-programming problems, and a dual simplex method for solving a capacitated transportation problem (CTP).

The comparison results indicated that the Glover et al. method was six times faster compared to the most competitive methods (Saul I. Gass, 1990). Their method's computational times for solving 1000 x 1000 TPs on a CDC 6000 computer were summarized, with a median solution time of 17 s and a range of 14-22 s. Since the transhipment problem (TP) is a specific case of a minimum-cost network

problem, methods used to solve the latter problem, such as the out-of-kilter method, can be easily adapted for solving CTPs. This was stated by Bradley et al.

A primal method for solving large-scale trans-shipment problems has been developed. This method uses special data structures for basis representation, basis manipulation, and pricing. The code, GNET, has been specialized into a code called TNET for solving capacitated TPs. Different pricing rules were tested to select the incoming variable. Using TNET, a representative 250 x 4750 problem was solved in 135 s on an IBM/360/67. The number of pivots and total time were dependent on the pricing rule. The GNET procedure has been incorporated into the MPSIII computer-based system for linear-programming problems by Ketron Management Science Inc. It is known as WHIZNET and is designed for solving capacitated trans-shipment problems, including TP as 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.

In 1975, Collatz and W. Wetterling developed a general network problem-solving method called PNET. PNET is a primal simplex method that solves capacitated and uncapacitated transhipment problems (TPs). It efficiently solved a TP with 2500 origins and 2500 destinations in less than 4 minutes of CPU time on a UNIVAC 1108. This method utilizes augmented thread index lists for the bases and dual variables. (Saul I)

Gass, 1990) demonstrates that the current level of expertise in solving TPs on mainframe computers is highly advanced. The introduction of PCs has led to the development of PC-based codes by numerous researchers and software houses for solving TPs. However, most of these codes were designed for educational purposes

and can only handle small, textbook-size problems. Erikson and Hall's TP procedure (Saul I.) serves as an example of this limited capability.

Gass (1990) states that the Gass algorithm is capable of solving problems of the size 20 x 20. The TSP88 program, developed by Eastern Software, is a commercial transportation problem solver that can handle TPs with up to 510 origins and/or destinations. It is not clear which algorithms are used in PC TP codes, but it is speculated that they are a variation of either PSTM or SSM (Saul I. Gass, 1990).

Degeneracy In The Classic Transportation Problem

Degeneracy may occur when the initial feasible solution contains a cell with zero allocation, or when reallocation leads to multiple previously allocated cells having a new zero allocation. When solving a CTP using PSTM or SSM, it is necessary to find a set of non-negative values for the variables that satisfy both the origin and destination constraints, while also representing a basic feasible solution with m + n -1 variables (Saul I. Gass).

All basic cells are organized in a list for computational efficiency. The loop cells are prioritized and the entering cell is placed at the beginning of the list. The remaining cells in the loop are then sequenced to follow the loop. Dealing with degeneracy is made simple by using the allocated cells. Unlike the general simplex method, the PSTM and SSM do not require a representation of the basis inverse. Instead, these methods leverage the fact that any basis to the TP corresponds to a spanning tree of the bipartite network that describes the flows from origin nodes to destination nodes (G.B.).

According to Dantzig

(1963), if a degenerate basic feasible solution to a CTP is given, one must determine which of the arcs with zero flow should be selected to complete the tree. This can be done using the NWCM to generate the initial basic feasible solution. By having the tree corresponding to the current basic feasible solution, we can determine if it is optimal. If it is not, we can determine the entering and leaving variables and the values of the variables in the new solution (Gass, 1990). Dantzig (1963) recognized the problem of selecting a tree for a degenerate basic feasible solution and proposed a simple perturbation procedure that ensured all basic feasible solutions are non-degenerate.

Based on the literature we reviewed, it seems that the computer-based methods for solving CTPs mentioned earlier are not affected by degeneracy. It is common for these methods to use a perturbation procedure to finalize the tree. We observe that selecting a tree for a degenerate basic feasible solution is only a small issue if the initial basic feasible solution is degenerate. In such cases, a perturbation scheme or a straightforward selection rule can be used to choose a variable or variables with zero value to complete the tree.

(L. Collatz and W. Wetterling, 1975) and (G. Hadley, 1962). A simple decision rule is commonly employed to select the appropriate zero-valued variables, since there are usually multiple options available.

When selecting variables with the smallest costs, a tree is established for the first basic feasible solution. The SSM and PSTM prescriptions ensure that changing bases always result in a new basic feasible solution and corresponding tree, regardless of the number of degenerate basic feasible

variables. If there are ties in selecting the variable to leave the basis, a new tree can be generated by dropping one variable and keeping those tied at zero level. The decision on which one to drop is determined using a simple decision rule (Saul I.).

According to Gass (1990), degeneracy can be problematic as it may lead to the creation of new bases without a decrease in the objective function's value, a situation referred to as stalling. In the paper by Gavish et al. (B. Gavish, P.), this issue is discussed.

Schweitzer and E. Shlifer (1977) conducted a study on the zero pivot phenomenon in the CTP and assignment problem (AP). They devised rules to address stalling by reducing the occurrences of zero pivots (Saul I. Gass, 1990). Through randomly generated problems of various sizes, they found that in the case of the CTP, the average percentage of zero pivots to total pivots could be significant. The percentage ranged from 8% for 5 x 5 problems to 89% for 250 x 250 problems. These calculations were based on the modified row-minimum rule for selecting the initial basic feasible solution.

According to the research, the percentage of zero pivots is unaffected by the range of cost coefficient values, but it is affected by the range of ais and bjs values, especially when the latter range is narrow. For an m x m AP, which always has (m – 1) basic variables that are zero, the average percentage of zero pivots ranges from 66% for 5 x 5 problems to 95% for 250 x 250 problems. The authors propose rules for selecting the first basic feasible solution, determining

which variable should enter and leave the basis. These rules significantly reduce the overall computational time (Saul I. Gass, 1990). In their paper, Shafaat and Goyal (A. Shafatt and A.B. Goyal) discuss this topic further.

According to Goyal (1988), a method was developed to select a basic feasible solution with a single degeneracy that will improve the objective function value in the next iteration. This method ensures that the entering variable does not involve the degenerate position with a negative increment (Saul I. Gass, 1990). The efficiency of this procedure in terms of computer time compared to the minor amount of time required for basis changes is uncertain. However, it is conjectured that for large-scale CTPs, a single degenerate basic feasible solution will not cause significant stalling, as it is unlikely that the entering variable will be part of an exchange loop involving the degenerate variable.

We acknowledge that according to Saul I. Gass (1990), a CTP or a linear-programming problem in general, with single degenerate basic feasible solutions, will not cycle.

Method of finding Initial Basic Feasible Solutions

A basic solution refers to any group of (n + m – 1) cells that does not involve a dependent subset. The basic solution comprises assigning flows to the basic cells to meet the supply and demand constraints. The solution is considered feasible when all flows are non-negative.

According to linear programming theory, we understand that an optimal solution exists and is feasible. The CTP has a total of n + m constraints, one of which is redundant. The selection of (n + m – 1) independent variables determines a basic solution for this problem. The basic variables

are assigned values to meet the supplies and demands, while the non-basic variables have a value of zero. Consequently, the m + n equations are linearly dependent. The CTP algorithm leverages this redundancy effectively.

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 Vogel’s approximation method
• Row minimum method
• Column minimum method

The five methods differ in the quality of the starting basic solution they produce. Better starting solutions result in a smaller objective value. Some heuristics outperform the common methods. The northwest corner method yields a solution far from optimal. The least cost method finds a better starting solution by focusing on the cheapest route.

The Vogel’s Approximation Method (VAM) is an enhanced version of the least cost method that generally produces superior initial solutions. The row minimum method starts by examining the first row and selecting the cell with the lowest cost. This is done until either the capacity of the first supply is exhausted or the demand at the jth distribution centre is met, or both conditions are satisfied. On the other hand, the column minimum method begins with the first column and selects the cell with the lowest cost. This is done until either the demand of the first distribution centre is met or the capacity of the ith supply is exhausted, or both conditions

are satisfied. However, among the five methods mentioned above, the North West Corner Method (NWCM), the Lowest Cost Method (LCM), and Vogel’s Approximation method are the most commonly employed techniques for determining the initial basic feasible solutions of the CTP. While NWCM tends to provide a solution that deviates significantly from the optimal solution, Vogel’s Approximation method and LCM strive to produce results that are often optimal or close to it. In real-time applications, VAM can lead to substantial savings over time.

Alternatively, if you prioritize ease of programming and memory usage, the NWCM is still suitable for reasonably sized matrices (up to 50 X 50). Nevertheless, the time difference between the two loading techniques grows exponentially. (Totschek and Wood, 2004). Another study proposes a more efficient alternative to Vogel's Approximation Method for TP (total processing) compared to the traditional Vogel's Approximation Method (Mathirajan, Meenakshi, 2004).

In this project, the Northwest Corner method (NWCM) and the Least Cost Method (LCM) are being used to find initial basic feasible solutions to the CTP. These solutions will then be utilized with the Stepping Stone Method (SSM) to obtain optimal solutions to the CTP. The final results will be compared with solutions obtained from GIS software, which offers an alternative method to solve the CTP without using complex mathematical solutions described in this literature.

Methods for Finding Optimal Solutions of the CTP

There are two main methods commonly used to find optimal solutions: the Stepping Stone method and the Modified Distribution Method (MODI) method. Some heuristics are developed to improve performance.

The speed factor is compared between different methods. The Transportation Simplex Method and Genetic Algorithms are compared for accuracy and speed in

solving large-scale problems. As the size of the problem increases, Genetic Algorithms are found to be more efficient (Kumar and Schilling, 2004). The stepping stone method is a proposed digital computer technique for solving the CTP. The time required for each iteration using this method 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 gives 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.

The CTP problem has been solved using various software. For instance, the MODI Algorithm was implemented in FORTRAN V, and coding the algorithm in Assembler language can potentially result in significant time reductions. Zimmer found that using Assembler instead of

FORTRAN for coding minimum path algorithms led to a 20-to-1 time reduction (Srinivasan and Thompson, 1973).

In another study, generalized network problems were examined where flow conservation is not maintained due to factors like cash management, fuel management, and capacity expansion (Gottlieb, 2002). The optimal solution to the pure problem can be applied to solve the generalized network problem.

Furthermore, a study introduced a generalized formulation that bridges the gap between spatially aggregate and disaggregate location modelling (Horner and O’Kelly, 2005).

Our research is focused on solving the CTP problem by utilizing various software tools such as ArcGIS Network analyst, ArcMap, ArcCatalog, VBA, Python, PuLP, GLPK (GNU Linear Programming Kit), and ArcObject. Chapter 4 contains a detailed explanation of our solution algorithm. The GLPK (GNU Linear Programming Kit) is an open-source package designed to address large scale linear programming (LP), mixed integer programming (MIP), and similar problems. It consists of routines implemented in ANSI C and arranged as 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 conditions, including turn restrictions, speed limits, height restrictions, and traffic conditions at different times of the day.

The algorithm used by the ArcGIS NA route solver attempts to find a route through the set of stops with minimum cost (a combination of travel times and time window valuations). Networking in transportation has already been discussed in the above paragraphs. A detailed explanation of how we used the above-mentioned software will be explained in the analysis chapter.

Computational Issues of the Classic Transportation Problem (CTP)

Currently, with the growing usage of computers, various evolutionary computation methods are being implemented to address the challenges faced in solving the classic transportation problem (CTP).