THE METHODS OF COMPUTER SUPPORTED MODELING
OF TRANSPORTATION NETWORK
Zvonko Čapko, Slavomir Vukmirović
Faculty of Economics
University of Rijeka
Ivana Filipovića 4
CROATIA
Abstract: In this article we are analysing the meaning, functioning and effects of the computer applications on basic model for resolving the transport problems. Using the scientific perceptions based on the new applicative model of the information technology, which is connected on computer system tools and matrix functions, enable the automatic computer steps in optimising of the transport, as on the operative as well as on the tactic and strategic level. The article considers the methodological framework of transportation network designing as the base of usage the computer aids and programs on the example of Solver and LINGO. Application of the computer tools in connection with sophisticated mathematical functions interfaced with Excel calculation table is ranged in the table modelling methods intended for the strategic modelling of the quantitative business models. Observed model is the result of the new paradigm, and its task is to redirect application of the calculative tables from the standard mathematical and statistical calculations to modelling and resolving of the complicated problems in the quantitative analysis. One of such kind of problem area is also modelling the transport networks with complicated configuration. The calculative table interface combined with mathematical functions and the computer tools enables not only in the standard calculations performance, but also complicated modelling in the strategic processes. Observed transport network contains starting, final and loading knots (points) with limited capacity of the arches. Using the model of calculative tables during the procedure of resolving the transport network problems we can determine on the strategic level the number, the size and location of the plant, distribution centres and senders. The basis of the model, which is in function of optimising the transport, includes all the essential elements for modelling the transport system: the providing sources and the plans for positioning of all plants, distribution centres and receivers. Also, over the results generated by application of the basic transport network model, we can define information background in purpose of modelling the circulation of the goods and information through the transport system.
Key-words: modelling, transport, network, optimising, computer applicatons, Solver, LINGO
1
1. Introduction
The problem of scientific research. Although, for almost fifty years, all human activities have successfully used information technologies, the mathematical model of simulation, theoretical knowledge quantum of informatics modelling of transport network models and applied knowledge of such models within the production processes of transport, i.e. traffic and logistics services obtained by the experts and managers in transport, traffic and logistics praxis, are below the necessary level of minimum.
The result of the presented research problem is the purpose and goal of the research - to explore the ways of intensities of the transport system that could use the results given by the usage of model base during the transport optimization. Accomplishing that goal means necessary application of the scientific research methods to determine the sub-goals of the research:
- Defining the features and possibilities of usage of the computer tools and applications within the context of new paradigm of computer-supported modelling of transport network model
- Defining the optimization methods of transport as a function of solving different types of transport problems of different level of complexity
- Consider the area of usage and functioning of computer-supported models in modelling the transport problems on computer
- Suggest mutual methodological scope of usage of information technologies in modelling the transport networks models for solving the different types of optimization problems
Having in mind, the problem and subject of research, there is a foundation scientific hypothesis: using the scientific perceptions of information technologies, models and transport networks, it is possible to determine the general model of transport network that could be adjusted and implemented to different types of computer applications for solving the transport problem, and therefore to rationalize the transport networks. Spreadsheets combined with the computer tools and applications determine representative software package for complex problems of mathematical programming and as such enable modelling of transport network models.
2. Theoretical features of transport network designing
Computer technology development strongly influences the meaning, functioning and usage of information technologies in solving transport problems. It is necessary to elaborate a mathematical model of organisation of transport process (planning and booking of transport capacities, choice of transport relation and type of vehicle, determination of ways of transport, transport deadlines, elaboration of price list calculations). Data, information, sizes and connections estimated to be relevant in solving the certain transport problem are entered into models. Usage of computers and computer applications became basic tools for transport optimization processes [3].
Transport network could be presented as the group of nodes connected with arches. The picture shows transport-trading centres in shape of the nodes. They are named nodes according to the terminology of the network flow problem, and the lines that connect the nodes are called arches. Network arches refer to the valid directions, paths or connections between the nodes within the network flow problem. When the lines that connect the nodes in network are the arrows that show the direction, than the arches in network are called directional arches [1]. This chapter is primarily discussing the directional arches, although from the practical reason they are going to be called arches. The example of the transport network is shown on the scheme 1.
1
Scheme 1. - Example of Transport Network
1
The concept of supply nodes (or dispatch nodes) and demand nodes (or acceptance nodes) is yet another mutual element of the network flow problem shown on scheme 1. There has been assigned system of nodes X1, X2,…;X9. Nodes X1, X2, X3, X4, X7 and X9 that represent the origin transport centres which distribute the goods. They are marked as the origins I1 ,..., I6. Nodes X5, X6 and X8 are destination centres and marked as origins O5, O6 and O8. The goal of the model is to calculate minimal transport network costs, where the outgoing turnover from the starting nodes could not be greater than its supply, and the receipt turnover to final nodes should be equal to its demand. Also, all network flows should be greater or equal to zero.
Net supply or demand for each network node is marked by positive or negative number, which is placed by the each node. Positive number represents demand of the relevant node and negative number represents available supply to the node. For example, the value +30 placed by the node 1 refers to the 30-unit supply of that node. The value -100 at node 5 refers to the 100-unit demand. Loading node could have the net supply or demand, or it could be strictly transitional node. The number of outgoing and receipt goods, with transitional node, is equal to zero. There are no transitional nodes in this example.
The goal of the transport network model is to determine the optimal disposition of flows of the goods through the given arches between the nodes, i.e. transport paths. Therefore, the outgoing turnover of the goods from starting nodes could not be greater that its supply, and the receipt turnover to final nodes should be equal to its demand. Also, all network flows should be greater or equal to zero. The example shows that the foundation goal of this transport problem is to determine the most economic method of transport through different types of arches, as shown by the scheme 1. and to transport them when necessary. Therefore, each network flow model arch represents the decision-making variable. Establishing of the optimal flow for each arch is the equivalent of determing the optimal value for the relevant decision-making variable.
Basing upon the above stated, the following relations could be mathematically formulated:
1. Quantity of goods (Xi) transported through arches of the transport network (flows) cannot have the negative value, expressed by the formula:
(1) (1) X1, X2,…,Xn >= 0
2. The difference of sum of goods quantity delivered to node and of sum of quantities dispatched out of that node should be equal to the capacity of that node. Node capacity can be positive, negative or zero.
(2)
3. Computer designing of transport networks interfaced by Excel spreadsheets
The simplex method is appropriate method for solving the transport network model. It is supported by the computer tool Solver being the additional module of spreadsheets. Further, there shall be described modelling and functioning of computer-supported model of transport networks interfaced by the Excel spreadsheet. Information modelling of the transport network starts from the mathematical formulation of the relation within the transport network shown as formulas 1 - 3. Scheme 1. shows the applicative model of transport network minimisation.
Each model's address area is defined with relevant title with support of function Insert/Name/Define [5]. Starting nodes, origins (OR) and destinations (DE) represent adjusted pairs that determine the transport network arches (ARCS), as well as unit costs (CO) and capacities of arches (CA). Outgoing results that should be calculated represent the flow load (FL) and minimal value of transport costs.
1
Scheme 1. Transport network model interfaced by Excel spreadsheet
1
The simplex method is appropriate method for solving the transport network model. It is supported by the computer tool Solver as the additional module of spreadsheet. Further, there shall be described modelling and functioning of computer-supported model of transport networks interfaced by the Excel spreadsheet (6). Information modelling of the transport network starts from the mathematical formulation of the relation within the transport network shown as formulas 1 - 3.
Herewith below are the parameters entered to the Solver card:
1
Subject to the Constraints:
Flows >= 0
Flows <= CapArcs
FlowNodes = CapNodes
Set Target Cell: MinCosts
Equal To: Min
By Changing Cells: Flows
4. Modeling Language LINGO in designing of transport network
Designing languages enable presentation of the problem in form of mathematical formula of indexes and bases. Its main feature is designing and capability of grouping similar entities into sets (2). When the entities are grouped to the certain set, they are shown by characteristics of that set. This way the entity groups could be presented by single algebra expression. Lingo software is designed for effective solving of the mathematical programming problem.
Lingo 8.0 has several new characteristics among which the most significant are [4]:
- Simple solver that shall confirm by itself that some solution is a unique optimum
- Multiprocessing possibility for finding faster problem solution
- Quadrant recogniser (indicator) and solver for identification and solving the quadrant programming (QP)
- Faster and stronger program for solving dual simplex method
- Improved integrated solver for better and more accurate solving of many types of problems
- Possibility of linearization, i.e. transformation of non-linear problems to linear ones
- Simple tool for analysis for identification and defining of given problem
- Decompensaton characteristics for checking whether the model (problem) includes independent sub-model as well
- Very reliable for different types of models
Lingo makes it possible to group the parts of one variable to groups or sets. Sets (groups) can be simple (primitive) or derived (derivative). In order the sets cold be used in a model, especially the part of the lingo program under name SETS, first, must be exactly and clearly defined. This part begins with the mark SETS and ends with the mark ENDSETS [4].
Scheme 1 shows the LINGO program in process of solving the transport network. Here has been used the same example of transport network so the results given by the LINGO could be compared with results of computer tool Solver interfaced with the Excel spreadsheet. Scheme 2. shows the output data and results of post optimal analysis. The scheme shows that minimal values of transport costs are equal to the 2527 units of goods, as well as inside the calculation of Excel.
MODEL:
SETS:
NODES:CAPNODES;
ARCS(NODES,NODES):
FLOWS,COSTS,CAPARCS;
ENDSETS
DATA:
NODES = 1..9;
ARCS=@ole("clanak1.xls");
COSTS=@ole("clanak1.xls");
CAPNODES=@ole("clanak1.xls");
CAPARCS=@ole("clanak1.xls");
ENDDATA
MIN=@SUM(ARCS:COSTS*FLOWS);
@FOR(ARCS(I,J):FLOWS(I,J)<=CAPARCS);
@FOR(NODES(I):
@SUM(ARCS(I,J):FLOWS(I,J))
-@SUM(ARCS(J,I):
FLOWS(J,I))=CAPNODES(I));
END
Segment SETS defines the group of data. The nodes and arches are defined in transport network. Arches (ARCS) are defined as groups of arranged node pairs where assigned relevant distance for each node pair given for that arch (arranged pair relation).
Segment DATA defines given values. The program shows that with usage of command @OLE LINGO it can relate to Excel spreadsheet and be used as a container for the input data. The Excel example shows the saved input data for variables ARCS, COSTS and CapArcs.
The most significant part of the program is the segment of processing, which, in this example, contains of the following programming lines:
1) MIN=@SUM(ARCS:COSTS*FLOWS);
2) @FOR(ARCS(I,J):FLOWS(I,J)>=0);
3) @FOR(ARCS(I,J):FLOWS(I,J)<=CAPARCS);
4) @FOR(NODES(I):
@SUM(ARCS(I,J):FLOWS(I,J))
-@SUM(ARCS(J,I)
FLOWS(J,I))=CAPNODES(I));
The Line 1. shows the goal function where the sum of the given distance values and unit values of nodes on its critical way should gain minimal total distance value between the first and the last node. Lines 2 and 3 define the limitations for flows that need to be greater than zero and less than costs capacities. Line 4 specifies the limitation relevant to the flow inside the nodes where the difference of sum of entering the node and leaving the node should be equal to node capacity. Each unit node has input and output arch. Scheme 2. shows the solution for transport network model
1
Scheme 2. - Solution of transport network model
Global optimal solution found at iteration: 9
Objective value: 2575.00
Variable Value Reduced Cost
FLOWS( 1, 2) 0.000000 8.000000
FLOWS( 1, 3) 0.000000 6.000000
FLOWS( 1, 4) 0.000000 9.000000
FLOWS( 2, 1) 30.00000 0.000000
FLOWS( 2, 4) 0.000000 3.000000
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
FLOWS( 9, 7) 55.00000 0.000000
FLOWS( 9, 8) 0.000000 6.000000
1
5. Methodological scope of computer tools and programs in modelling the transport networks
General applicative model is used as a foundation for modelling the actual applicative model by certain computer tool or program. Table 1. shows the functions of the goal and the limitations of considered transport problem in form of mathematical model, and form appropriate for program language LINGO and computer tool Solver of Excel spreadsheet interface. Table also presents the user orientation of subject programs. In the
example of solving the transport problems, suggested methodological scope of modelling the applicative model for optimization could be used by managers as the end user and encourage them to use the computer programs and tools in matter of solving the optimization problems.
1
Scheme 3. Adjusting the general applicative model to computer program
1
Table shows that presented applications, Excel and LINGO, have minor differences in syntax where the entering of mathematical formula for the function of goal and limitations are largely analogue to the mathematical model. For example, when entering the formula for goal function Excel uses function SUMPRODUCT for summing unit costs and quantity of goods on arches (transport paths). Computer tool solver defines the address where the function has been entered and the goal (marked as "Min"). LINGO, program language directly inserts the entire formula where are entered sum (SUM) functions in sequences and mathematical operator for multiplying (*). Arches (transport routes) are defined as new data sets, i.e. groups of arranged pairs of nodes where each pair has been assigned with the unit expenses, capacities and quantities.
Limitation function is somewhat complex. Defining the conditions of equality between the nodes flow and nodes capacity is the same as in the Excel application and LINGO program. Complex part of the formula represents the difference in usage of Excel and LINGO, i.e. nodes flow calculation as a difference between the quantity of goods that enter and leave the node. Both programs use the same SUM function. The difference is in identification method of relevant nodes. In Excel, the connection with the SUM function uses IF function that selects the relevant arches and compare the table addresses with marks of original and destination. Than, it adds the flows of selected arches to the relevant node.
LINGO program, calculates node flows by selection of nodes from arches that are relevant for that node and sums those flows. The difference is in syntax where, opposite to Excel, uses function of SUMIF, LINGO uses SUM functioning connection with the FOR function that is defined by the program loop. LINGO enables preparation of data in form of sets which further enables multi-index marking of variables, so when calculating each node, (defined by the function @FOR(NODES(I):…), the values of flows are selected that way that one index is made fixed and the other changeable. This means that for each node are added values of flows, where the value of changeable index correspond to the value of fixed index as defined in the set of input data.
6. Conclusion
The study is elaborated problem area and functionality of computer programs in modelling of transport network model. There has been proved hypothesis of possibility of defining the general model of transport network that could be adjusted and implemented in different computer programs for solving the transport problems.
Spreadsheets in connection to the computer tools and programs feature the representative software package for complex problems of mathematical programming and as such it enables modelling of transport network models. Spreadsheets user-orientation allows capability to observe input and output variables as well as computer-supported processes of optimization, which is a foundation of recognition and understanding of integration of, mathematical and computer logic. LINGO program language is more abstract in relation to the Excel spreadsheets and requires certain programming knowledge. Defining and presentation of problem logic in Excel, in the way that is acceptable to the computer programme, represents the ideal basis for designing in LINGO program language, faster and more effective implementation of mathematical model.