Bir demiryolu ağında boş yük üniteleri arz ve talep trafiği akımının dengelenmesi

Abstract

ÖZET Bugün» toplumun karşılaştığı önemli problemlerin arasında; ulaştırma problemleri çok geniş yer tutmaktadır. Bu problemlerin çözümü ve gelecekteki ulaştırma ihtiyaçlarının previzyonu için çeşitli matematik modeller yapılmış ve çok sayıda algoritma geliştirilmiştir. Bu matematik modellerden ağ- akim tipinden olanlar ise son yıllarda hızla gelişen yöney lem araştırmasının önemli bir bölümünü oluşturmaktadır. Nitekim, çeşitli mühendislik dallarındaki uygulamalara bakıldı- ğında ağları kullanan birçok matematik modellerin geliştirilmiş olduğu görülmektedir. Burada yapılan çalışmada da ağ kavramından geniş ölçüde yararlanılmış ve önerilen silindir biçimindeki yeni diyagramda, problemin çözümüne ağakım cinsinden bir algoritmayla gidilmiştir. Çalışmanın esası, demiryolu ağlarmdaki boş yük ünite lerine ait trafiğin dengelenmesidir. Diğer bir değimle, demiryolu ağındaki boş yük ünitelerini optimal bir şekilde dağıtımıdır. Zaten çalışmada boş yük ünitesi yerine boş ünite veya yalnızca ünite denmekte ve yine boş yük üniteleri trafiğinin dengelenmesine de, boş ünitelerin dağıtımı ifadesi kullanılmaktadır. Birinci bölümde boş yük ünitelerinin neler olabileceği, nasıl hareket edecekleri ve kaç tip olacakları kısaca açık- lanmış ve amacın, bunların optimum dağıtımının yapılması için öncelik metodu yerine daha sıhhatli ve kesin neticeler veren bir algoritmanın bulunması olduğu belirtilmiştir. ikinci bölümün birinci kısmında, Lineer Programlamanın Taşın Problemi üzerinde durulmuştur. Bir demiryolu ağındaki boş ünitelerin dağıtımı problemi taşın problemi aracılığı ile çözülmüş ve bu problemin özel halleri örnekler verilerek incelenmiştir. Burada incelenen özel haller tamamen demiryolu sistemlerini getirdiği `kısıtlamalardan oluşmaktadır, ve bu çalışmada bunların ayrı ayrı çözümleri yapılmıştır.İkinci bölümün`. ikinci kısmında ise ağlar ve ağ-akım bağıntıları etraflıca incelenmiş ve bunlara ait teorem ve algoritmalar açıklanmıştır. Bu kısımda statik maksimal akım, dinamik maksimal akım ve Out-of-Kilter algoritmasının Özel liklerinden bahsedilmiştir. Ayrıca Out-of-Kilter algoritma sının da kullandığı, dinamik ağdan statik ağa geçiş de anlatılmıştır. Üçüncü bölüm, boş üniteler trafiğinin dengelenmesinde kullanılan dağıtım algoritmasının ve bu algoritmanın kullanıldığı ağın tanıtılmasından oluşmuştur. Burada, bir demir yolu ağındaki ünitelerin hareketleri silindir biçimindeki yeni bir diyagram üzerinde gösterilmiş ve bu yeni diyagrama göre problemin formülasyonu yapılmıştır. Yine bu bölüm de, yeni diyagrama göre ünitelerin hareketlerinin, dağıtım ağının tarifi yapılmış, akım kuralları konmuş ve daha sonra formülasyonu yapılan problemi çözecek algoritma etraflıca açıklanmıştır. Dördüncü bölüm iki kısımdan oluşmuştur. Birinci kısımda A istasyon arasında işleyen 8 katarın belli bir süre için deki hareketleri ele alınmış ve 24 düğümlü bir ağda boş ünitelerin dağıtımı üçüncü bölümdeki algoritma yardımı ile yapılmıştır. İkinci kısım ise çalışmanın sonuçlarını kapsamaktadır.

SUMMARY Transportation problems are amongst the most important problems faced by today's society. Although the railway transport is one of the oldest of the modern modes of transport, there are still many problems to be solved. Among these, there is the balancing of the supply demand traffic flow of empty freight units in a railway network. This is commonly known as the distribution of the empties in a railway network. In this study this problem is taken and it has been tried to make an engineering approach to it solution. Instead of freight wagons, the term of railway freight units it used throughout the work. The reason of using unit instead of wagon is that today on the railways there is not only the wagon but the container as well. Therefore the problem is to optimize the movements of different railway units.The use of network models has been increasingly widespread in the recent development of operational research,. Because of the basic s imp lie ty and generality of network concepts and because of the amenability of network calculations to digital computation, networks have proved idealy suited for mathematical modeling in a variety of scientific and engineering applications. In this study different kinds of solutions of the problem are explanied and a network fiow type algorithm is choosen, to be the best method for its solution. The study consists of four parts. The first part is an introduction. Before explaning the method of solution; it is thought that it would be. rather useful, to clarify the meaning of the problem by explaning it very briefly and giving the earlier and the actual distribution methods used by the railway dispatchers. One of the important problems of the railways is the great cost of the unit fleet ant its low level of productivity. In order to emprove the productivity of the unit fleet a central unit authority should be established and the duty of this authority should be the organisation of the distribution of empty units. In the earlier days some degree of central control existed. Each district officer arranged distribution within is own area and then reported the overall position to regional headquarters where adjustments between districts were arranged. In some countries the central unit authority exists and there is a direct liaison between the authority and the districts for the submission of the daily rolling stock reports and the issue of distribution orders. This liaison helps very much the dispatchers to make the optimum distribution of the empty freight units. The aims of the distribution of the freight units are: -To so arrange empty unit supply that when and wherever acceptable traffic is offered, the right number of units to move that traffic are then and there available -In arranging that availability to utilise the least number of resourcesXIII -To measure and demonstrate the efficiency of the performance of these two tasks. By the proper distribution of the empties the number of the units is decreased and the reliability of the service provided to the customer is increased. At the end of the introduction section it is mentioned that the aim of the study is to find a solution to this optimisation problem with the aid of linear programming techniques. The second part of the study consists of two sections. In the first section the classical transportation problem of the linear programming is examined in details. The reason of examining the transportation problem is that it is used by many scientists as a solution to the problem of the distribution of the empty freight units in a railway network. The transportation problem is a special case of linear programming. The methods for its solution are simpler than the general methods designed to solve any linear programming problem. However, many practical problems are of transportation type, and many others can be transformed into transportation problems. The general method for solving the linear programming problems is Dantzig's Simplex Method, but for the solution of the transportation problem the Stepping-stone method is used. This section consists of two parts. In the first part a railway network with nine stations is taken and it is assumed that certain units have to be transported from four stations -to five different stations. The first four stations are called sources and the last five are called destinations. In this example the supply of units is accepted to be equal to the demand. The formulation of the problem is made and the method of shadow costs for the improvement of the solution is explained.XIV In the second part special cases of transportation problem is studied. Some restrictions of the railway systems are included in the problem and two special cases are obtained. The first case is obtained by assuming that the total demand is not equal to the t&tal supply and an imaginary destination is invented because the demand was less than the supply, if the demand were more than the supply an imaginary source would haven been invented. The second case is obtained by eliminating a link between two stations of the system. More than one link can be eliminated or a capacity restriction of the train running between two stations can be introduced. as well. In this case a very large cost clement is placed instead of the element of the eliminated link. In the second part of the study the flows in transportation networks are studied. This part consists of there sections. In the first section the static maximal flow is examined. Before the direct examination of the static maximal flow, the networks and the flows in networks are explained and then the theorems concerning the maximal flow are stated. The most important theorem is the max-flow min-cut theorem of Ford and Fulkerson. At the end of the section a network with four nodes is taken and the famous labelling method is explained. The labelling method is known as Ford and Fulkerson algorithm as well. The labelling method gives the static maximal -flow in a network. In the second section the dynamic maximal flow is examined. In this section the same network with four nodes is taken as above and the dynamic flow is illustrated on it. Then the formulation of the dynamic flow is done and the conditions of the maximal dynamic flow are stated. The last part of the section is the construction of a static network from a dynamic network. In the third section the famous Out-of-Kilter algorithm of Ford and Fulkerson is briefly examined. The teorem itself. is stated, and a comparison between this algorithm and the simplex method is briefly done as well.XV The third part of the study consists of the method choosen for the solution of the distribution of the empties in a railway network. As it was mentioned before, the method of solution explained in this section is a network flow type algorithm. The movements of the railway freight units are described as arrows of the network which will be solved by the algorithm, tt is worth to mention that there are two kinds of arrows, those are temporal arrows and physical arrows. Physical arrows represent the movement of units on -a train between two different stations. Temporal arrows represent the waiting period of units at the same station between the arrival and/or the departure of a train. The nodes of the network represent events. Here, an event is a departure or an arrival of a train running on the railway system. The relations between arrows of the network and the particularities of the network are described in detail, and the flow rules are given. After the description of nodes, arrows and events the movements of the units are drawn on a cylinder and a new cylindrical diagram is obtained. On this new cylindrical diagram the beginning and the end of a distribution period are adjacent. Thus, if the distribution is started in the middle of one period it, will be finished without any cut in the middle of the next period. The algorithm used here is a special form of the Out- of-Kilter algorithm, therefore it is a linear programming algorithm. It can be seen from the formulation of the problem as well, because the problem itself is a linear programming problem. The algorithm uses an inductive method of solution. Instead of examining the whole network, only a part of it is solved at any one time. Once a subnetwork is solved, another subnetwork is taken. At any stage of the algorithm the nodes can be marked nodes or unmarked nodes. All of the marked nodes are examined by the algorithm, the rest of the nodes are unmarked or markable nodes. Some.'of the arrows are distinguishedXVI by the algorithm and a flow can be sent only over distinguished arrows of the network. With each node of the network a dual variable or potential is associated. The potential can also be called the node price and it represents the marginal cost of. getting an additional car to the node which is examined at present, from the source node. At the end of the third part the computation of the algorithm is given. It consists of initial step, step 1, step 2 and step 3. The fourth part of the study consists of two sections. The first section is a numerical example. The example taken to illustrate the algorithm is a' twenty-four node problem. These twenty four nodes are formed by the movements of eight trains between four stations. Every stage of the algorithm is shown on the figures. The second section contains the results of the study.