Classic Transportation Problem Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

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 Vogel's 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 Dantzig's, 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 Dantzig's 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 Cooper's SSM, the flow (Hungarian) method of Ford and Fulkerson, Munkres' Hungarian method,' the modified simplex method of Suzuki,' Dantzig's 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 deciding on a variable to enter the foundation. Problems of realistic size could be solved, e.g. m + n < 7,500 on the IBM 704 computer and m + n < 8,000 on a UNIVAC 1103 computer. A reported computing time for a 220 x 30 problem was 4 mins 58 s on an IBM 704 using the procedure of Ford and Fulkerson. With the new generation and fewer types of large-scale computers in the 1970s and 1980s, we find that specialized, commercially available codes for solving CTPs seemed to disappear, while general codes mathematical programming systems (MPS) for solving large-scale linear- programming problems came into their own. From what we understand of the situation, it became efficient to solve CTPs as standard linear programs owing to the speed, problem-generation methods and reporting procedures embedded into these MPS. However, technological and computer-programming advances, coupled with the need for solving large-scale transportation problems more generally, network distribution minimum-cost problems led researchers to investigate and develop special computer-based CTP codes (Saul I. Gass, 1990).

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 minimum 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 examines the rows of the transportation cost tableau until it meets the first row including a candidate cell, and then selects the cell in this row which violates dual feasibility by the biggest 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. Gass, 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 Software's 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 take place 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).

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 to 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 set of (n + m - 1) cell that does not contain a dependent subset. The basic solution is the task of flows to the basic cells that satisfies the supply and demand constraints. If all the flows are non negative, it 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 a result, 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 Vogel's approximation method

Row minimum method

Column minimum method

These five methods normally vary 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 focusing on the cheapest route. The Vogel's Approximation method (VAM) is an advanced version of the least cost method that in general creates improved 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 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 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 Vogel's 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 Vogel's Approximation method and LCM tries to give result that are often optimal or near to optimal solution.

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). Poh, Choo and Wong, 2005, has stated that 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. In addition, as explained before, in order to solve the CTP competently, the best way is by coupling the a primal transportation algorithm together with a modified row minimum start rule and a modified row first negative evaluator rule (Glover, Karney, Kligman, Napier, 1974).

Application Software

Basically, GIS functioned as a tool in converting the information from tables with topological data into maps. Subsequently, GIS also execute simulations to assist advanced user to organize their tasks in many areas, including public administration, transportation networks, transportation networks and environmental applications, it is not only to solve the spatially related problems. 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. Srinivasan and Thompson, 1973, reported that, by applying the Assembler in coding minimum path algorithms, it shows that a 20-to-1 time reduction was achievable, this is better than using Fortran application.

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 that means to solve large scale linear programming (LP), mixed integer programming (MIP), and other matters. It is a set of routine written in ANSI C and structured in the form a callable library. The key elements of GLPK package are as follows;

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 produce LP and MPS files and call GLPK, to handle the linear problems. PuLP supplies a nice syntax for creation of linear problems, and a simple way to call the solvers to do the optimization.

Today, there is only a few studies conducted research in the usage of ArcGIS Network Analyst extension to solve several transportation problems, there also not much of published materials relating to ArcGIS Network Analyst and its application in transportation.

ArcGIS Network Analyst (ArcGIS NA) is a great tool of ArcGIS desktop 9.3 that gives network- based spatial analysis including routing, travel directions, closest facility, and service area analysis. ArcGIS NA allows users to dynamically form realistic network conditions, which consist of turn restrictions, speed limits, height restrictions, and traffic conditions for the whole 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 detail explanation of how we used the above mentioned software will be explained in the analysis chapter.

Computational issues of the Classic Transportation Problem (CTP)

These days, there are many evolutionary computation system to solve optimization problems have been created, for instance genetic programming evolutionary strategies, evolutionary programming, simulated annealing and others, this is due to the boosting of computer usage recently (Jung-Bok Jo, Byung -Ki Kim and Ryul Kim, 2008) . The papers written by Ramakrishnan, (C.S. Ramakrishnan, 1988) Shafaat and Goyal and Arsham and Kahn make interesting contributions to the computational side of the CTP. Such work is always of value and importance. Our concern with these papers is that the reader is left with the impression that these contributions represent the state-of-the-art in solving TPs. This impression is due to some of the wording and claims of the papers, and to our sensitivity to the need for better computational testing before such claims are made (Saul I. Gass, 1990).

The paper by Ramakrishnan deals with a modification of VAM for unbalanced TPs, i.e. problems in which the sum of the supplies is not equal to the sum of the demands. The problem is made equivalent to a CTP by the addition of a dummy origin or destination, as appropriate. Most texts suggest giving the new cells thus generated a zero cost. The reason for this (although not usually stated) is that the solution to the problem with the dummy zero costs will yield the value of the true objective function. But, in many applications, zero costs are not appropriate. For example, if a dummy destination was added, this could represent the situation where we have a central storage facility with different costs for sending any surplus from an origin to the storage facility; if a dummy origin was added, this could represent (i) the purchasing of the good from a competitor with costs representing the purchase and shipping charges to each destination, or (ii) just different penalty costs for not meeting the demands at the destinations (Saul I. Gass, 1990). We are firm believers that technical advances such as those of the papers criticized above should be reported. New ideas are always welcome, with and without computational implementation and claims that is not the issue here. The issue is how to report on computational results.

Transportation in Geography

Transportation interests geographers for two main reasons. First, transport infrastructures, terminals, equipment and networks occupy an important place in space and constitute the basis of a complex spatial system. Second, since geography seeks to explain spatial relationships, transport networks are of specific interest because they are the main support of these interactions.

Transport geography, as a discipline, emerged from economic geography in the second half of the twentieth century. Traditionally, transportation has been an important factor behind the economic representations of the geographic space, namely in terms of the location of economic activities and the monetary costs of distance. The growing mobility of passengers and freight justified the emergence of transport geography as a specialized field of investigation. In the 1960s, transport costs were known as main elements in location theories and transport geography started to rely rapidly on quantitative methods, particularly over network and spatial interactions analysis. Though, from the 1970s globalization challenged the centrality of transportation in many geographical and regional development investigations. Accordingly, during the 1970s and 1980s transportation became unpopular in economic geography, even though mobility of people and freight and low transport costs were measured as main issues behind the globalization of trade and production.

Since the 1990s, transport geography has received attention, this is due to the matters of mobility, and production and distribution are interconnected in a complex geographical setting. Recently, the transportation is acknowledged as a system that considers the complex affiliations between its core elements namely; networks, nodes and demand. Transport geography must be organized; this is due to the connection between elements of the transport system. An approach to transportation thus involves several fields where some are at the core of transport geography while others are more peripheral. However, there are three central concepts to transport systems that can be identified as listed below:

Transportation nodes

Transportation mainly connects locations, which characterized as nodes. Within a transportation network, nodes functioned as an access point in distribution systems, transhipment or intermediary locations. It is primarily serviced by transport terminals where flows originate, end or are being transhipped from one mode to the other. Transport geography must consider its locations of connection and transhipment.

Transportation networks

Transport geography should enclose in its investigation the infrastructures sustaining and shaping movements. Its also need to consider the spatial structure and organization of transport infrastructures and terminals.

Transportation demand

Once the transportation demand is recognized, it becomes an interaction which flows through a transport network. Transport geography must calculate the elements that effect its derived demand function.

Methodologies will play an important role to analyse the concept as explained above which consisting other disciplines such as economics, mathematics, planning and demography. Every discipline offers a dissimilar dimension for the analysis. For instance, many models developed for the analyses of movements, such as the gravity model, were borrowed from physical sciences. Multi disciplinarily is consequently an important attribute of transport geography, as in geography in general.

Transport geography is a tool that assist in understanding the spatial relations that created by the transport systems. The understanding is important to assure that those involved in transportation manage to ease the transport problems such as capacity, transfer, reliability and integration of transport systems. There are three essential geographical considerations related to transport geography:

Location - Each location has its own features presenting a potential supply or a demand for resources, products, services or labor. A location will determine the nature, the origin, the destination, the distance and even the possibility of a movement to be recognized. For example, a city supplies an employment in different sectors of activity in addition to consume resources.

Complementarity - Locations need exchanging goods, people or information. This implies that some locations have a surplus while others have a deficit. To balance the circumstances is by movements between locations having surpluses and locations having demands. For example, a complementarity is generated between a shop (surplus of goods) and its purchasers (demand of goods).

Scale - Movements created by complementarity are happening at different scales, pending the nature of the activity. Scale demonstrates how transportation systems are established over local, regional and global geographies. For example, home-to-work journeys usually have a local or regional scale, while the distribution network of a multinational corporation is almost certainly to cover some regions of the world.

As a result, transport systems are consuming land and supporting the relationships between locations.

Methods in Transportation Geography

Transportation is a ground of inquiry and application. Due to that, since transportation operates as a performance driven activity and it can be determined, transportation tends to rely on a set of particular methodologies. Transportation planning and analysis are involving civil engineers, economists, urban planners and geographers. Each has developed methodologies which to deal with their respective range of problems. Heavy dependence on empirical data and the demanding use of data analytic methods are the two common features of transportation researches, despite of disciplinary relations.

Fundamentally, transport geography stands out from numerous other fields of human geography by the nature and purpose of its quantitative analysis. In 1960s, geography has been redefined by transport geography which was one of the major forces in the quantitative revolution. Even though current transport geography has a more expanded approach, the quantitative dimension still plays an essential role in the discipline.

Therefore, transport geography is an applied science in order to provide a conceptual background to the analysis of movements of freight, people and information.

The taxonomy of Transportation geography methods

Listed below are the different approaches to classify the methods that are utilized by transport geographers:

1. Whether they are qualitative or quantitative.

2. Whether they deal with infrastructures or flows.

3. Whether it provides interpolation or extrapolation.

4. Whether the technique provides description, explanation or optimization.

5. According to the level of data aggregation, the nature of the assumptions or the complexity of the calculations.

GIS data model

In response to the issues outlined above, a lot of attentions in recent years have been given to potential GIS-T applications that can integrate GIS and transportation systems. Existing GIS-T data models provide several modeling elements to integrate and represent multiple transportation networks (Shaopei Chen, Jianjun Tan, Christophe Claramunt and Cyril Ray, 2009). This implies that new planning methods and approaches are needed to support the development and planning of transportation systems (Shaopei Chen, Jianjun Tan, Christophe Claramunt and Cyril Ray, 2009). In addition, according to Shaopei Chen, Jianjun Tan, Christophe Claramunt and Cyril Ray, 2009, this brings forward the function of integrated information systems which can offer decision-makers, planners and end users with useful data at the right time.

According to Thill, 2000, the application of GIS to transportation systems is prompted due to the need for reliable data. Curtin et al., 2003 reported that the GIS for transportation (GIS-T) indicate a particular expression that includes all the activities that are using GIS methods related to planning and management in transportation. These elements include location referencing methods, spatio-temporal data structures, multiple representations of transportation data, and multiple topological representations. Amongst existing GIS-T data models, the ESRI's GIS-T data model is a distinguished transportation GIS data model for CTP (Shaopei Chen, Jianjun Tan, Christophe Claramunt and Cyril Ray, 2009). The ESRI's transportation data model was developed by a group of ESRI transportation industry users, consultants, ESRI business partners, and academics (ESRI, 2007). At the core of the model lie road and rail network topology, linear referencing systems, dynamic events representation and asset location and management. The objective of the model is to describe an "essential data model" for a GIS user organization contained by the transportation industry, and in particular for roadway management organizations.

Chapter Summary

In this literature review, many researchers have conducted the operational research on the solution of the CTP and many algorithms and models have been developed but the integration of these models into the GIS software environment has little or no existence in the GIS environment, unfortunately, the studies of connection to the geometry of the street network are still less. It is possible to create a network base supply demand services areas using GIS software such as ESRI's ArcMap with the Network analyst. The details on the models that used to solve the CTP in the GIS environment will be explained in the next chapter. The models are not an econometric one but a GIS based model. As outlined in the introduction, given a point to point O-D matrix per group of commodities, it assigns a transport flow of each commodity to each destination.