Araç Planlama Problemi Ve Problem İçin Web Tabanlı Coğrafi Bilgi Sistemi Tasarımı

Abstract

Araç Planlama ve Rotalama Problemleri (APP ve ARP) en etkin yöneylem araştırma alanlarının başında gelmektedir. 1958 yılında Dantzig ve Ramser in Araç Sevkiyat Problemi ile başlayan araştırmalar bugün bu problemden türemiş çeşitli problem sınıflarında devam etmektedir. Bu problemlerin en fazla dikkat çekenleri arasında Geri Dönüşlü Araç Rotalama Problemi yer almaktadır. Bu çalışma Geri Dönüşlü Araç Planlama Problemlerinin sadece geri dönüşü dikkate alınan türünü incelemektedir. Amaç en düşük maliyete sahip araç-talep(ler) eşleşmesini sağlamaktır. İnternet dünyasında yaşanan gelişmeler coğrafi bilgi sistemlerinin (CBS) yaygınlaşmasını sağlamıştır. CBS ler ile birlikte APP ve ARP lerin ele alınış şekilleri de değişmiştir. CBS ler ile birlikte daha geniş bir coğrafi bilgi veritabanına erişim sağlanabilmektedir. Ayrıca problemlerin ve çözümlerin haritalar üzerinde görselleştirilmesi de mümkün olmuştur. Karar destek sistemleri (KDS) ile CBS lerin ortak çalışması sonucu taşımacılıkta araç takibi, büyük filoların yönetilmesi ya da daha geniş sonuçları olan kararların merkezileştirilmesi mümkün olmuştur. Hızlı ulaşılan veri ile hızlı çözüm üreten algoritmalar düşük maliyetli planlamalar ile rotalamaların önünü açmıştır. Bu çalışmada amaç uluslararası karayolu taşımacılığında karşılaşılan bir araç planlama problemi türü için en uygun modeli kurmak, modeli uygun algoritmalar ile test etmek ve çözüm ararken geliştirilen modeli kullanan bir web tabanlı karar destek sistemi oluşturmaktadır. Çözüm oluşturulurken araçların teknik özellikleri ve kapasiteleri ile taleplerin zaman pencerelerine dair kısıtlarının yanı sıra sürücülerin sürüş ve çalışma sürelerine dair yasalarla belirlenen kısıtlamalar da dikkate alınmıştır. Ayrıca herhangi bir taleple eşleştirilmeyen araçlar için, araçların konumlarına dayalı bir maliyet modeli geliştirilmiştir. Böylelikle herhangi bir taleple eşleştirilmeyen araçlar için de en uygun bekleme konumları tespit edilebilmektedir. Maliyetler araçların katedeceği mesafe ve gerçekleştirilen faaliyetlerin alacağı süre dikkate alınarak hesaplanmaktadır. Birim mesafe ve birim süre maliyetlerinin önceden belli olduğu varsayılmıştır. Bir araç-talep eşleşmesinde eğer aracın hizmeti geç kalarak gerçekleştirmesi söz konusu oluyorsa talebin geç hizmet edilmesi durumunda dikkate alınması gereken ceza fonksiyonu ile geç kalma maliyeti hesaplanmaktadır. Oluşturulan model öncelikle The General Algebraic Modeling System (GAMS - Genel Cebirsel Modelleme Sistemi) ile test edilmiş, ardından Macar Algoritması ile çözüm arayan bir program geliştirilmiştir. Bu program bir karar destek sistemi olarak kullanılacaktır. Karar destek sistemi Google Maps teknolojisi ile entegre bir sistem olarak geliştirilmiştir. Üretilen sonuçlar kullanıcı dostu bir arayüz kullanılarak görselleştirilebilmektedir.

The most popular problems in operations research literature are Vehicle Routing and Scheduling Problems (VRSP). Since the paper Truck Dispatching Problem by Dantzig and Ramser in 1958, there has been massive amount of articles published about the topic. The main problem is matching vehicles with the customers with a least cost manner. The cost here could be expressed differently from problem to problem. The most common cost component is the oil being consumed. There are other components of cost like the time spent, the service quality, handling costs...etc. Choosing the most appropriate cost function depends on the activity being considered. The area itself has popular sub problems. The Pickup and Delivery Problems , The Vehicle Routing Problem with Time Windows and The Vehicle Routing Problems with Backhauls are among the many. There are several surveys classifying these problems but since the area is so wide, there is yet no generally accepted typography covering all the problems. During the last decades several articles are published mainly covering the time windows and capacity constraints. There are also papers about driving hours restrictions of drivers or other legal restrictions. The solution approaches are covering a wide range as well. Besides exact algorithms, there are many algorithms adapted or generated to solve the problems. The most popular of them are Tabu Search, Column Generation, Branch and Cut and Swarm algorithms. The international trade in Turkey to European countries could be examined with one of the many approaches. The problem could be expressed as the popular problems mentioned here, or as a combination of these problems. The transportation activity itself will determine the model. The transportation is moving the goods from where they are produced to where they are needed. The transportation activities are generally monitored and managed from central offices. The system including all the components for managing the transportation activities is called Transportation Management System. Transportation Management Systems deals with decisions at different decision levels. The three levels of decisions are the strategic level, where strategic decisions concerning the most general issues are, the tactical level, where middle level decisions are and the operation level, where the decisions about everyday activities are handled. The system may include computerized tools as well. The most common used tools are Decision Support Systems and Geographic Information Systems. To construct a well suited Transportation Management System for the activity at hand, all these systems has to be integrated successfully. Decision Support Systems can be classified with subject to many aspects like purpose, users, platform...etc. The generated results with the decision support systems are used in order to help the decision maker to give most suitable decisions. The geographic information systems are used to store, to get, to use and/or to monitor the geographical data where needed. The development of internet technologies has raised the need to reach geographical data. There are lots of researches where spatial data are used. Some companies has seen the interest in the area and developed geographical information systems or tools that are used to develop the geographical information systems. Among these companies Google, Microsoft, Yahoo are the most popular ones. The main idea behind this dissertation is the development of a module combining both geographic information system and decision support system for the transportation management system already being used by a logistics provider in Turkey. The company owns a truck fleet. Besides, private fleets are used whenever needed. Among the many operations, the one being considered is the freight transportation between Turkey and Western Europe. The vehicles load the goods and complete the customs procedures. Then they travel to the delivery location. After arrival they clear the customs and unload the goods. A vehicle needs to have permissions before using the roads of a third country to pass through. The permissions previously obtained limit the number of route alternatives. The total travel time is between ten to twenty days. To construct stable schedules, the total transportation activity is divided into two different problems. The first problem deals with the pickup scheduling while the second problem deals with the scheduling of backhauls. In this dissertation only the backhauls are considered with the time windows, capacity and drivers working hours limitations constraints. In the generated model the cost function consists of the cost of matched vehicle-customer pairs which is determined by the sum of the multiplication of unit distance cost with distance covered and the multiplication of unit time consumption cost with the time spent for the activity, the cost of delayed services which is determined by a penalty function of delayed time known for all customers, the cost of private fleet usage and the cost of the vehicles not scheduled for the current planning horizon. There are several constraints including the constraint that states there has to be one and only one vehicle for the customer, the constraint that states there has to be at most one customer matched for each vehicle, the capacity constraints and the constraint that states the specification of the vehicles must match with the demanded specifications by the customers. All data required, to solve the problem, is not known in advance until a reasonable planning horizon is selected. If the duration of the planning horizon is too long, then there will be several stochastic data that needs special attention. For example if a long planning horizon is selected then since the travel duration is too long, to estimate the arrival times to the delivery location will be much harder. Even the results will be generated for the most probable cases, if an unexpected event occurs, a new problem has to be created and solved including new data. This could be a choice, but on the other hand with a smaller planning horizon, it s much easier to create robust schedules since the data will be deterministic after some point of time. The disadvantage of smaller planning horizon is the lack of ability to predict future needs in order to take action in time. The model tested with The General Algebraic Modeling System (GAMS) and the results are generated in significantly short durations. Since GAMS is inefficient to use for several reasons, a more user friendly approach is searched. Because of the geographical interface support and the inclusion of more precise geographical data, Google Maps is chosen for the purposes mentioned. Google Maps provides the geographical data with an Application User Interface (API) developed for programmers in need of geographical information. With callback functions sent to the Google Maps servers, the client can get the requested data as a result of the request. The returned data could also be used on maps styled by the programmers as well. To solve the problem, an appropriate algorithm has to be embedded in the new system. The problem considered here is a Generalized Assignment Problem which deals with matching the sources with the demands. There several exact algorithms used to solve Generalized Assignment Problems. The Hungarian Algorithm is one of the most famous and is used to solve the model. The algorithm is coded using Javascript scripting language. For the dynamic data Google Maps used and for the static data Javascript Object Notation (JSON) is chosen because of the ease of use with Javascript language. The developed decision support system integrated with the geographical information system provided by Google Maps, is a web-based system which works without dependence of any platform. Any device supporting a browser could run the application. \par} {The test problems are generated randomly for different problem sizes. The decision support system uses more time than GAMS to produce solutions since GAMS directly uses rounded distances from a limited distance matrix, while the geographic information system produces the distances between the exact locations of the vehicles and the delivery(if any),pickup and custom locations. This phase takes time depending on the speed of internet connection and the traffic of data transactions at the time of calculation. The algorithm works as fast as the algorithm used by GAMS. The result is the most appropriate matching, considering the constraints of the model. \par} {One of the most important features of the generated model is the construction of the strategy for the remaining vehicles that are not used for service for the current planning horizon. If a vehicle is decided to wait until a suitable activity occurs, the result generates the best location for the vehicle to wait. To find the best location, the model calculates the probabilities of service demands around a reasonable neighborhood of the vehicle s current location. If the sum of the cost of sending the truck to another location and cost of waiting there is less than the cost of waiting at the current location, then the vehicle is sent to new location. With this approach the cost of probable future travels and service delays are avoided. Another important feature is the use of drivers working hours constraints. The restrictions about derivers working hours do not affect the short-term transportation activities but has great importance in long-term transportations. A truck may reach to the destination on time but because of running out of working hours, the driver may wait for the next working day or even a weekend may prevent to conclude the activity. Then a big penalty value may be charged to the activity. With the development of better devices to track the drivers working hours, the restrictions has to be calculated in detail. The increasing number of papers concerning these limitations shows the rising attention. As a result a new system is generated for the scheduling activities previously handled by experienced office personnel with lack of any measure to compare the results. The system takes into account the specific details the transportation activity contains like the representation of service locations by two points, pickup and customs points. The best output is generated considering not only the cost of vehicle-customer matching but also the cost of unscheduled vehicles. For future researches the work in this dissertation will be a reference point to improve the quality of solutions of long-distance vehicle routing and scheduling problems by use of more stochastic data included in the nature of the problem.