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 a‰? 0 (non negativity constants)……………… aˆ¦…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 a‰? 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 selecting a variable to enter the basis. 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 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. 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 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 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 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 Vogel’s 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 Vogel’s 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 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 a real-time application, Vogel’s 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 Vogel’s Approximation Method for TP and this method is more efficient than traditional Vogel’s 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 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.
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 O’Kelly, 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 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 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)
Nowadays, as the use of computers is rapidly increasing, many evolutionary computations methods for solving optimization problems have been introduced such as genetic programming evolutionary strategies or evolutionary programming, Tabu search, simulated annealing and so on (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 (based on a paper by Goya) 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 is a sub-discipline of geography concerned about movements of freight, people and information. It seeks to link spatial constraints and attributes with the origin, the destination, the extent, the nature and the purpose of movements.
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 recognized as key factors in location theories and transport geography began to rely increasingly on quantitative methods, particularly over network and spatial interactions analysis. However, from the 1970s globalization challenged the centrality of transportation in many geographical and regional development investigations. As a result, transportation became underrepresented in economic geography in the 1970s and 1980s, even if mobility of people and freight and low transport costs were considered as important factors behind the globalization of trade and production.
Since the 1990s, transport geography has received renewed attention, especially because the issues of mobility, production and distribution are interrelated in a complex geographical setting. It is now recognized that transportation is a system that considers the complex relationships between its core elements. These core elements are networks, nodes and demand. Transport geography must be systematic as one element of the transport system is linked with numerous others. An approach to transportation thus involves several fields where some are at the core of transport geography while others are more peripheral. However, three central concepts to transport systems can be identified:
Transportation primarily links locations, often characterized as nodes. They serve as access points to a distribution system or as transhipment or intermediary locations within a transport network. This function is mainly serviced by transport terminals where flows originate, end or are being transhipped from one mode to the other. Transport geography must consider its places of convergence and transhipment.
Considers the spatial structure and organization of transport infrastructures and terminals. Transport geography must include in its investigation the infrastructures supporting and shaping movements.
Considers the demand for transport services as well as the modes used to support movements. Once this demand is realized, it becomes an interaction which flows through a transport network. Transport geography must evaluate the factors affecting its derived demand function.
The analysis of these concepts relies on methodologies often developed by other disciplines such as economics, mathematics, planning and demography. Each provides a different dimension to transport geography. For instance, the spatial structure of transportation networks can be analyzed with graph theory, which was initially developed for mathematics. Further, 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.
The role of transport geography is to understand the spatial relations that are produced by transport systems. This gives rise to several fallacies about transportation. A better understanding of spatial relations is essential to assist private and public actors involved in transportation mitigate transport problems, such as capacity, transfer, reliability and integration of transport systems. There are three basic geographical considerations relevant to transport geography:
Location. As all activities are located somewhere, each location has its own characteristics conferring a potential supply and/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 realized. For instance, a city provides employment in various sectors of activity in addition to consume resources.
Complementarity. Locations must require exchanging goods, people or information. This implies that some locations have a surplus while others have a deficit. The only way an equilibrium can reached is by movements between locations having surpluses and locations having demands. For instance, a complementarity is created between a store (surplus of goods) and its customers (demand of goods).
Scale. Movements generated by complementarity are occurring at different scales, pending the nature of the activity. Scale illustrates how transportation systems are established over local, regional and global geographies. For instance, home-to-work journeys generally have a local or regional scale, while the distribution network of a multinational corporation is most likely to cover several regions of the world.
Consequently, transport systems, by their nature, consume land and support the relationships between locations.
Methods in Transportation Geography
Transportation is not a science, but a field of inquiry and application. As such, it tends to rely on a set of specific methodologies since transportation is a performance driven activity and this performance can be measured. Transportation planning and analysis are interdisciplinary by nature, involving civil engineers, economists, urban planners and geographers. Each has developed methodologies dealing with their respective array of problems. Two common traits of transportation studies, regardless of disciplinary affiliation, are a heavy reliance on empirical data and the intensive use of data analytic techniques, ranging from simple descriptive measures to more complex modeling structures.
In some respects, transport geography stands out from many other fields of human geography by the nature and function of its quantitative analysis. In fact, transport geography was one of the main forces in the quantitative revolution that helped to redefine geography in the 1960s. Even if contemporary transport geography has a more diversified approach, the quantitative dimension still plays an important part in the discipline.
Thus, in addition to providing a conceptual background to the analysis of movements of freight, people and information, transport geography is much an applied science. The main goal of methods aims to improve the efficiency of movements by identifying their spatial constraints. It is consequently possible to identify relevant strategies and policies and provide some scenarios about their possible consequences.
The taxonomy of Transportation geography methods
There are various ways of classifying the methods that are used 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 particular, this brings forward the role of integrated information systems which can provide decision-makers, planners and end users with the appropriate information at the right time (Shaopei Chen, Jianjun Tan, Christophe Claramunt and Cyril Ray, 2009).
The need for reliable data information has motivated and favored the application of geographical information systems (GIS) to transportation systems (Thill, 2000). GIS for transportation for transportation (GIS-T) denotes a specific expression that encompasses all the activities that utilize geographic information systems for some aspect of transportation planning and management (Curtin et al., 2003). 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 notable 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 goal of the model is to define an “essential data model” for a GIS user organization within the transportation industry, and in particular for roadway management organizations (e.g. DOTs), as well as for railroads, transit, Airport, and waterway authorities.
In this literature review, many researchers have been done in 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, they still lack any connection to the geometry of the street network. Using GIS software such as ESRI’s ArcMap with the Network analyst, it is possible to create network base supply and demand services areas. Real road network can make the actual distance between supply stations and demand destinations. At the core of many procedures in GIS-T software are algorithms for solving network routing problems. The problems are conceptually simple but mathematically complex and challenging. The next section will provide more details on the models used to solve the CTP in the GIS environment. The model is 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.