PERANCANGAN PROGRAM APLIKASI OPTIMALISASI RUTE PENDISTRIBUSIAN PAKET POS PADA KANTOR MPC YOGYAKARTA DENGAN METODE SIMULATED ANNEALING Ngarap Imanuel Manik,Drs.,M.Kom.; Kristian Aji Nugroho Zebua; Holder Simorangkir,S.Si., M.Kom.
ABSTRACT Distribution is crucial for PT Pos Indonesia Yogyakarta. If the distribution route to be taken too far it will slow the time it takes for goods to destination and increase the expenditure to be incurred for transportation costs of delivery. The longer time taken in the distribution process will increasingly lead to the accumulation of goods that have not been distributed at the post office. To overcome the problems faced by the distribution route of PT Pos Indonesia Yogyakarta simulated annealing algorithm is used to find the optimal route by path is available and take the minimum distance. Using the optimal distribution route will minimize the distance traveled and time taken in the distribution of goods. Keyword : Distribution routes, simulated annealing, parcel post, optimization, traveling salesman problem
ABSTRAK Pendistribusian adalah hal yang krusial bagi PT Pos Indonesia Yogyakarta. Apabila rute pendistribusian yang ditempuh terlalu jauh akan memperlambat waktu yang dibutuhkan barang untuk sampai ke tempat tujuan dan menambah pengeluaran yang harus dikeluarkan untuk biaya transportasi pengiriman. Semakin lama waktu yang dibutuhkan dalam proses distribusi akan semakin menimbulkan penumpukan barang yang belum terdistribusi di dalam kantor pos. Untuk menanggulangi masalah rute pendistribusian yang dihadapi oleh PT Pos Indonesia Yogyakarta digunakanlah algoritma simulated annealing yang dapat mencari rute optimal dengan membandingkan tiap jalur yang tersedia dan mengambil total jarak yang paling minimum. Menggunakan rute distribusi yang optimal, akan meminimalkan jarak tempuh dan waktu yang dibutuhkan dalam proses pendistribusian barang. Kata Kunci : Rute pendistribusian, simulated annealing, paket pos, optimalisasi, travelling salesman problem
INTRODUCTION The process of distributing goods is an activity that can never be separated fromlife. Distances as well as the widespread deployment of community is one reasonfor people to use a freight forwarder rather than deliver the goods to be delivered.Problems of distribution of goods became an important point for freight services company. It is in great need of consideration and a precise calculation because it is associated with transport costs to be incurred in the distribution process. PT Pos Indonesia is one company that is engaged in the delivery of goods in Indonesia. PT Pos Indonesia has branches in every city in There are many ways to solve the problem of optimal routing in the distribution of goods, one of which is to use simulated annealing algorithm. Simulated annealing algorithm can be applied in scheduling problems and the problems of traveling salesman problem (TSP). Problems including the problems of distribution of goods traveling saleman problem (TSP). TSP itself is the problem of determining the route visit by a salesman. The shorter the distance the path it takes to visit all places visited, the more optimal results. In this thesis, the author will apply the Simulated Annealing algorithm for TSP problem solving in a computer program. With the implementation of this algorithm in the field of distribution of goods, the matter the cost for transportation and delivery time can be reduced to a minimum. Indonesia and one of them is in Yogyakarta. In the face of competition from similar companies, PT Pos Indonesia should be able to take appropriate decisions and in pressing cernat costs. One source of expenditure is the cost of transport to the distribution of goods. Routes with distances would make the cost of spending more and getting bigger and if not matched by the number of items distributed will reduce corporate profits.
DISCUSSION Optimalization
Optimization is the act to obtain the best results with a given situation. In the design, construction, and maintenance of engineering systems, have taken a number of technologies and managerial decisions in several stages. The final goal of all such decisions is to minimize the effort required or desired to maximize the benefits. Referring to the opinion Singiresu S Rao, John Wiley and Sons (2009) can also be defined as an optimization process to obtain a state that gives the maximum or minimum value of a function. It can be seen from Figure 1, that if the point x * related to the minimum value of the function f (x), the same point is alsorelated to a negative maximum value of the function f (x). Without losing generality,the optimization can be defined to minimize, for a maximum of a function can be obtained through a negative minimum of the same function.
Figure 1 Minimum of f (x) equal to the maximum of-f (x) Distribution
Distribution can be interpreted as an attempt to facilitate the marketing activities and simplify the delivery of goods and services from producers to consumers, allowing their use in accordance with the required. Distribution process is a marketing activity that is able to: 1. Create value-added products 2. Accelerate the flow of physical marketing channel and non-physical. The definition of current is the flow of marketing activities that took place between the institutions involved in marketing in the marketing process.
Graph A graph is a set of (V, E), where V is the set point and E is the set of vertices formed by the partner node. E is a multiset, in other words, the elements can appear more than once so that each element has a diversity(Rouhonen, translated by Keijo Tamminen, KungChung Lee, & Robert, 2008). Graph can be denoted as G (V, E). point (V) are usually labeled with letters (a, b, c,... etc.), number (1, 2, 3, ... etc.) or a combination of both. Example graph is shown in figure 2 below:
Figure 2 Graph Travelling Salesman Problem(TSP)
Travelling salesman problem (TSP) is a classic problem that tries to find the shortest route or the distance through which the salesmen who want to visit some places that should go to each place of each one. Formally, the TSP is an indirect graph, where each graph node has a value and will look for Hamilton circuits with minimum total value (Letchford, Adam, 2010). TSP problem is not just about travel problems traders, but can be applied in everyday cases, such as: 1. Delivery of mail and goods. 2. Transportation issues. 3. delivery order 4. Series analysis of water or electricity. The core of the problem traveling salesmen problem (TSP) is to find or seek distance and the shortest route. Travelling salesman problem (TSP) is also a wellknown problem in graph theory. There are various theories that the algorithm can be used to solve the problems of traveling salesman problem (TSP) as a brute force algorithms, greedy algorithms, genetic algorithms, branch and bound algorithm, and others. Problem traveling salesman example is shown in figure 3.
Figure 3 Example of a route Travelling Salesman Problem
Simulated Annealing Algorithm In 1953, Metropolis developed a method to solve optimization problems by mimicking the thermodynamic system goes from one energy level to another level. Metropolis thinking about this after doing a simulation of a hot water bath on a particular chemical. This method requires that the particle system shows the energy level by maximizing the entropy termodinakima at a certain temperature value and the average energy level should be proportional to the temperature constant. This method is called simulated annealing. Kirkpatrick was originally thinking of using simulated annealing on computerrelated problems. Kirckpatrick doing that in 1983 and apply simulated annealing to optimization problems. Then more and more people who apply the simulated annealing method to other optimization problems. Simulated annealing algorithm which is good because it is relatively common and tend to not get stuck in a local minimum or maximum. Simulated annealing method based on the cooling of the metal. If the metal is cooled slowly, will form a smooth piece of metal because the molecule has been entered into the crystal structure. Crystal structure represents the minimum energy state or the optimal solution for optimization problems. If the metal is cooled too quickly, the metal will form a rough and jagged pieces of metal coated with a bump. Bumps and jagged edges represent the local minimum and maximum. Metropolis algorithm creates a rule, also known as the metropolis of propabilitas tosimulate the cooling of the metal through a series of movements. In each movement, the system has the possibility to change the current configuration to get worse. Opportunities configuration changes can be calculated from
⎧ 1 ⎪ ⎪ P( Δ E , T) ⎨ ⎪ exp ⎛⎜ − ΔE ⎞⎟ ⎪⎩ ⎝ KT ⎠
bila ΔE ≤ 0
bila ΔE > 0
(1) Where ΔE : Change in energy / configuration, T : Temperature dan K : Konstanta Bolztmann 1.3860 x 10 −23 JK −1 and 8.6174 x 10 −5 eV K −1 . Equation (1) is also called
(
)
(
)
the metropolis criterion. The ability to change the configuration of simulated annealing makes it possible to jump out of local maxima and minima where most of the other algorithms get stuck in it. Some parametersrequired in the implementation of simulated annealing and has been wellsummarized by Davidson and Harel: • The set of configuration or state of the system, including the initial configuration (which is often chosen at random). • A rule for the generation of new configurations, which are usually obtained by defining the environment and the configuration of each next configuration choose randomly from the current environment configuration. • Target, or cost, function, should be minimized through the configuration space (this is the analog of energy). • Schedule the cooling of the control parameters, including initial values and rulesfor when and how to change it (this is the analog of temperature and decline). • termination condition, which is usually based on the time and cost or value of thefunction of the control parameter. In the simulated annealing algorithm is first necessary to determine the beginning and end of the temperature. This is important because the temperature (T) will be used in the equation of probability. Probability equation, as defined by themetropolis in equation (1), where K is a constant, while obtained from
ΔE = E 2 − E1 (2) Where is the new configuration, and is the current configuration. If the new configuration has a smaller cost and better than the current configuration of the new configuration will be accepted automatically. This is also true when applied to the metropolis into the equation (1). Simulated annealing starts with choosing a random configuration which solves the problem. There is a objective function that determines the cost of a given configuration. This function is minimized (or maximized depends on the optimal solution to search. Original cost randomly selected from the configuration is then calculated. Given remain at the original temperature, simulated annealing configuration generate a new one at a time n, where n is the number of the selected user before simulated annealing starts. Each new configuration comes from the old configuration. cost of the two configurations were compared. If the new configuration is better than the current configuration is automatically accepted. If the new configuration is worse than the one currently on the admissibility of of calculation propabilitas, which is the cost ofthe current configuration and the cost of the new configuration. After the process of finding a new configuration, then compared and determined to be accepted orwhether the new configuration, the next step is the change in temperature. rate oftemperature change based on a specific issue and and amount of time a userwants to simulated annealing run. number of iterations (n) is also selected by theuser. process is then repeated until the final temperature is reached. When the temperature cools, the probability of selecting a new configuration to be reduced,just like molecules in a piece of metal that is not moving a lot.
Simulated Annealing Algorithym and Travelling Salesman Problem Simulated annealing method can be used in a variety of optimization problems,one of them is traveling salesman problem (TSP). The TSP will be given a number of n nodes are connected, and will look for the optimal route by passing througheach node of each one and return to the initial node. Optimal route itself has ameaning such as the path with the least amount of cost, or the fastest travel time. If there are many nodes it will take a very long time to be able to find the optimum path. Simulated Annealing can be applied in the case of TSP. The algorithm will start at random. Then the sequence of moves will be taken during the temperature. In every movement will be created a new configuration and then be accepted or rejected according to the calculation of the probability equation (1). When a motion is received will the temperature change. The process of movement will be repeateduntil the temperature reaches the final temperature. The greater the higher the temperature the greater the possibility of displacement of less than optimal. Configuration or energy in simulated annealing is a cost or purpose of the search for the solution of optimization problems. In the TSP energy obtained from the distance as it passes through each node. Energy can be found using the equation n
E = ∑ di i =1
(3) Where E : energy function after iteration, d i : distance between node(i) and node(i+1), n : total of all node. Simulated annealing algorithm also depends on the temperature and the temperature will decrease at each iteration. Decrease in temperature can not be done haphazardly. There is a function of cooling schedule is used to find the temperature had dropped.
⎛T ⎞ Ti = T0 ⎜⎜ n ⎟⎟ ⎝ T0 ⎠
i N
(4) where Ti : temperature of cooling schedule at-I, T0 : start temperature, Tn : temperature of cooling schedule, N : total of all iteration, and i : iteration (value i : 1,2,3,…). In solving the TSP problem with simulated annealing method of the calculation process may take a few steps before reaching the optimal solution. The process iscarried out are: 1. Generating the condition (state) and the initial temperature. 2. Calculate the initial energy is produced on initial conditions. 3. Update state and calculate the resulting energy back after the update. 4. Generate a uniformly distributed random numbers [0,1], denoted by (p).
⎛ ΔE ⎞ 5. Test criteria, if p < exp⎜ − ⎟ state update is received, apart from this ⎝ KT ⎠ condition ditolak.nilaiE can be found using equation (3). 6. Lower the temperature (T) with the cooling schedule (4). 7. Repeat step 3 to reach the criterion. If it has reached the stop criterion. Flowchart of simulated annealing algorithms (Larrosa, 2008) can be seen in Figure4.
Figure 4 Flowchart Algorithm Simulated Annealing Evaluation
In the experimental program used 10 transactions from the transaction data in the region Warungboto PT Pos Indonesia Yogyakarta on 1 December 2011. Of the 10initial transaction gained 8 points a different way. 8 way point can be seen in table 1. Table 1 Position 8 points the way experiments Warungboto
JalanID
Nama Jalan
Koordinat X
Koordinat Y
JLWR0001 kusuma negara
350
50
JLWR0002 veteran
660
200
JLWR0004 mondoliko
600
230
JLWR0005 warung boto I
540
380
JLWR0006 putra bangsa
500
330
JLWR0011 gajah
295
150
JLWR0012 persatuan
295
295
JLWR0017 garuda
165
175
Parameter used in this experiment, namely temperature = 10000, cooling rate = 0,9999, and minimum temperature = 0,00001. Result of search for optimal routes of 8 points in table 1 are : Start Æ JLWR0001 Æ JLWR0011 Æ JLWR0017 Æ JLWR0012 Æ JLWR0006 Æ JLWR0005 Æ JLWR0004 ÆJLWR0002 Æ Finish. Total distance from the optimal route generated is 3557.93 meter. Excellence in this application program are : 1. This application program can be easily understood because the distribution lines shown in picture form above the map of Yogyakarta. 2. The application program can display and edit all data from the tables in thedatabase. So if the user wants to view or edit the database, the user does notneed to open the master database. 3. In the application program is used simulated annealing method. This method will compare all the routes that can be passed to a collection point and the node will generate a route with the minimum distance. So that the route found is optimalor near-optimal routes. 4. The application program is equipped with a feature validation. Thus minimizing the chances of error due to an invalid value. 5. Display a simple program so that users can easily run and use the program. 6. Simulated annealing method has several advantages compared with other algorithms (Djikstra, genetic, ant colony) that the iteration process that much andwill do a comparison of each solution so that the algorithm will produce a solution that has a value close to optimal. While the drawback to the program application are : 1. Each completed the process of adding data and updates, new data can not be displayed directly on the screen but the program must first be done by pressing there fresh button refresh.
Conclusion and Reccomendation After doing the analysis and application program to the topic of Program Design Optimization of Distribution Routes At The Post Office Parcel Post MPC Yogyakarta With Simulated Annealing method, it can be concluded as follows.
1. The application program is equipped with a simulated annealing algorithm, so the program can compare all the existing distribution routes in a network area and find a route with the shortest distance. 2. This application program can help the process of editing the data contained in the database. So the user does not need to open the master database. 3. The program comes with a visualization map, making it easier for users to know the position of the location of the points the way in which optimal route will be skipped. Based on the theories that have been discussed previously and the results oftesting of this application program, then there are a few suggestions that may be provided to improve the application program if carried further development. 1. Further development is recommended to add a variable congestion factor in determining the optimal route, so that the resulting route will be optimized again. 2. Further development is recommended to develop more delivery areas such asprovinces or territories more widely. 3. Further development is recommended to add features zoom in and zoom out to help the user in navigating the map. 4. Further development is recommended to make the map more extensively, so thealley and the alley will appear on the map.
REVERENCE
Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. USA: Princeton University Press. Chibante, R. A. (2010). Simulated Annealing Theory with Applications. Sciyo. De Vicente, J., Lanchares, J., & Hermida, R. (2003). Placement by thermodynamic simulated annealing. Physics Letters , 415–423. Dharwiyanti, S. (n.d.). Retrieved from http://setia.staff.gunadarma.ac.id/Downloads/files/6077/Modul_UML.pdf Gutin G, P. A. (2002). The Traveling Salesman Problem and Its Variations. USA: Kluwer Academic Publishers. Letchford, A. (2010). The Travelling Salesman Problem. Swansea: Lancaster University Management School. Michalewicz, Zbigniew, & Fogel, D. (2000). How to Solve It : Modern Heuristics. Springer. Pearson, Letchford, A. N., & A, N. (2005). Good Triangulations Yield Good Tours. 1-13.
Press, W., Teukolsky, S., Vetterling, W., & Flannery, B. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University. Pressman, R. (2005). Software engineering : a practitioner's approach (sixth edition). New York: McGraw-Hill Science/Engineering/Math. Rao, S. S. (2009). Engineering Optimization : Theory and Practice, 4th. New Jersey: John Wiley and Sons. Rizal, J. (2007). Optimasi Pada Traveling Salesman Problem (TSP) dengan Pendekatan. Jurnal Gradien Vol.3 No.2 , 286-290. Ruohonen, K. (2008). Graph Theory. Tampereen teknillinen korkeakoulu. Shneiderman, B. (2005). Designing the User Interface: Strategies for Effective HumanComputer Interaction 4th Edition. USA: Addison-Wesley. Thomas M, C. (2009). Database Systems: A Practical Approach to Design, Implementation and Management (5th Edition). USA: Addison Wesley. Anonim, http://www.codeproject.com/ Akses : Oktober 2011 Anonim, http://www.posindonesia.co.id/ Akses : Oktober 2011
PERANCANGAN PROGRAM APLIKASI OPTIMALISASI RUTE PENDISTRIBUSIAN PAKET POS PADA KANTOR MPC YOGYAKARTA DENGAN METODE SIMULATED ANNEALING Ngarap Imanuel Manik,Drs.,M.Kom.; Kristian Aji Nugroho Zebua; Holder Simorangkir,S.Si., M.Kom.
ABSTRACT Distribution is crucial for PT Pos Indonesia Yogyakarta. If the distribution route to be taken too far it will slow the time it takes for goods to destination and increase the expenditure to be incurred for transportation costs of delivery. The longer time taken in the distribution process will increasingly lead to the accumulation of goodsthat have not been distributed at the post office. To overcome the problems faced by the distribution route of PT Pos Indonesia Yogyakarta simulated annealing algorithm is used to find the optimal route by path is available and take the mnimum distance. Using the optimal distribution route will minimize the distance traveled and time taken in the distribution of goods. Keyword : Distribution routes, simulated problem
annealing, parcel
post,
optimization, travelingsalesman
ABSTRAK Pendistribusian adalah hal yang krusial bagi PT Pos Indonesia Yogyakarta. Apabila rute pendistribusian yang ditempuh terlalu jauh akan memperlambat waktu yang dibutuhkan barang untuk sampai ke tempat tujuan dan menambah pengeluaran yang harus dikeluarkan untuk biaya transportasi pengiriman. Semakin lama waktu yang dibutuhkan dalam proses distribusi akan semakin menimbulkan penumpukan barang yang belum terdistribusi di dalam kantor pos. Untuk menanggulangi masalah rute pendistribusian yang dihadapi oleh PT Pos Indonesia Yogyakarta digunakanlah algoritma simulated annealing yang dapat mencari rute optimal dengan membandingkan tiap jalur yang tersedia dan mengambil total jarak yang paling minimum. Menggunakan rute distribusi yang optimal, akan meminimalkan jarak tempuh dan waktu yang dibutuhkan dalam proses pendistribusian barang. Kata Kunci : Rute pendistribusian, simulated annealing, paket pos, optimalisasi, travelling salesman problem
PENDAHULUAN Proses pendistribusian barang adalah kegiatan yang tidak pernah lepas dari kehidupan. Jarak yang jauh serta penyebaran masyarakat yang meluas menjadi salah satu
alasan bagi masyarakat untuk menggunakan jasa pengiriman barang daripada mengantar sendiri barang yang akan dikirimkan. Permasalahan pendistribusian barang menjadi poin penting bagi perusahaan penyedia jasa pengiriman barang. Hal ini sangat memerlukan pertimbangan dan perhitungan yang tepat karena berkaitan dengan biaya transportasi yang harus dikeluarkan dalam proses pendistribusian. PT Pos Indonesia merupakan salah satu perusahaan yang bergerak dalam bidang pengiriman barang di Indonesia. PT Pos Indonesia memiliki cabang disetiap kota di Ada banyak cara untuk menyelesaikan masalah pencarian rute optimal dalam pendistribusian barang, salah satunya adalah dengan menggunakan algoritma simulated annealing. Algoritma simulated annealing dapat diterapkan dalam permasalahan penjadwalan dan permasalahan travelling salesman problem (TSP). Masalah pendistribusian barang termasuk dalam permasalahan travelling saleman problem (TSP). TSP sendiri adalah permasalahan dari penentuan rute kunjungan oleh seorang salesman. Semakin pendek jarak jalur yang diperlukan untuk mengujungi seluruh tempat kunjungan maka semakin optimal hasil yang dicapai. Dalam skripsi ini, penulis akan menerapkan algoritma Simulated Annealing untuk penyelesaian masalah TSP dalam bentuk program computer. Dengan penerapan algoritma ini dalam bidang pendistribusian barang maka permasalahan biaya untuk transportasi serta waktu pengiriman dapat dikurangi seminimal mungkin. Indonesia dan salah satunya adalah di Yogyakarta. Dalam menghadapi persaingan dengan perusahaan sejenis, PT Pos Indonesia harus dapat mengambil keputusan dengan cernat dan tepat dalam menekan biaya yang dikeluarkan. Salah satu sumber pengeluaran biaya adalah biaya transportasi untuk proses pendistribusian barang. Rute dengan jarak yang jauh akan membuat biaya pengeluaran semakin bertambah besar dan apabila tidak diimbangi dengan jumlah barang yang didistribusikan akan mengurangi keuntungan perusahaan.
PEMBAHASAN Optimalisasi
Optimalisasi adalah tindakan untuk memperoleh hasil yang terbaik dengan keadaan yang diberikan. Dalam desain, konstruksi, dan pemeliharaan dari sistem teknik, harus diambil beberapa teknologi dan keputusan managerial dalam beberapa tahap. Tujuan akhir dari semua keputusan seperti itu adalah meminimalkan upaya yang diperlukan atau untuk memaksimalkan manfaat yang diinginkan. Mengacu pada pendapat Singiresu S Rao, John Wiley dan Sons (2009) optimalisasi juga dapat didefinisikan sebagai proses untuk mendapatkan keadaan yang memberikan nilai maksimum atau minimum dari suatu fungsi. Hal ini dapat dilihat dari gambar 1, bahwa jika titik x* berkaitan dengan nilai minimum fungsi f(x), titik yang sama juga berkaitan dengan nilai maksimum dari negatif fungsi tersebut –f(x). Tanpa menghilangkan keumumannya, optimasi dapat diartikan meminimalkan, karena maksimum suatu fungsi dapat diperoleh melalui minimum dari negatif fungsi yang sama.
Gambar 1 Minimum dari f(x) sama dengan Maksimum dari –f(x) Pendistribusian Pendistribusian dapat diartikan sebagai kegiatan pemasaran yang berusaha memperlancar dan mempermudah penyampaian barang dan jasa dari produsen kepada konsumen, sehingga penggunaannya sesuai dengan yang diperlukan. Proses distribusi merupakan aktivitas pemasaran yang mampu : 1. Menciptakan nilai tambah produk 2. Memperlancar arus saluran pemasaran secara fisik dan non-fisik. Yang dimaksud dengan arus pemasaran adalah aliran kegiatan yang terjadi diantara lembaga-lembaga pemasaran yang terlibat di dalam proses pemasaran. Graph Suatu graph merupakan sepasang set dari (V, E), dimana V adalah himpunan titik dan E adalah himpunan simpul yang dibentuk oleh pasangan simpul. E adalah multiset, dengan kata lain unsur-unsurnya dapat muncul lebih dari sekali sehingga setiap elemen memiliki sebuah keanekaragaman (Rouhonen, Keijo yang diterjemahkan oleh Tamminen, KungChung Lee, & Robert, 2008). Graph dapat dinotasikan sebagai G(V,E). titik (V) biasanya dilabeli dengan huruf (a, b, c,…dst), nomor (1, 2, 3,…dst) atau gabungan keduanya. Contoh graph dapat dilihat pada gambar 2 dibawah ini :
Gambar 2 Graph Travelling Salesman Problem(TSP)
Travelling Salesmen Problem (TSP) merupakan masalah klasik yang mencoba mencari rute atau jarak terpendek yang dilalui salesmen yang ingin mengunjungi beberapa tempat yang harus mendatangi tiap tempat masing-masing satu kali. Secara formal TSP merupakan sebuah graph tidak langsung, dimana tiap titik simpul graph memiliki nilai dan akan dicari sirkuit Hamilton dengan nilai total minimum (Letchford, Adam, 2010). Permasalahan TSP tidak hanya mengenai masalah perjalanan pedagang, namun penerapaannya bisa dalam kasus sehari-hari, misalnya seperti : 1. Pengiriman surat dan barang. 2. Masalah Transportasi. 3. Delivery order 4. Analisis rangkaian air atau listrik. Inti dari permasalahan travelling salesmen problem (TSP) adalah menemukan atau mencari jarak dan rute terpendek. Travelling Salesmen Problem (TSP) juga merupakan masalah yang terkenal dalam teori graf. Terdapat beragam teori algoritma yang dapat digunakan untuk menyelesaikan permasalahan Travelling Salesmen Problem (TSP) seperti algoritma brute force, algoritma greedy, algoritma genetic, algoritma branch and bound, dan lain-lain. Contoh travelling salesman problme dapat dilihat pada gambar 3.
Gambar 2 Contoh rute Travelling Salesman Problem
Algoritma Simulated Annealing Pada tahun 1953, Metropolis mengembangkan metode untuk memecahkan masalah optimasi dengan cara meniru sistem termodinamika yang pergi dari satu tingkat energi ke tingkat lainnya. Metropolis memikirkan hal ini setelah melakukan simulasi sebuah pemandian air panas pada bahan kimia tertentu. Metode ini mensyaratkan bahwa sistem partikel menunjukkan tingkat energi dengan cara memaksimalkan entropi termodinakima pada nilai suhu tertentu dan juga tingkat energi rata-rata harus proporsional dengan temperatur yang konstan. Metode ini disebut simulated annealing. Kirkpatrick awalnya berpikir untuk menggunakan simulated annealing pada masalah yang berkaitan dengan komputer. Kirckpatrick melakukan hal tersebut pada tajun 1983 dan menerapkan simulated annealing untuk berbagai masalah optimasi. Kemudian semakin banyak orang lain yang menerapkan metode simulated annealing untuk permasalahan optimasi lainnya. Simulated annealing adalah algoritma yang bagus karena relatif umum dan cenderung untuk tidak terjebak dalam lokal minimum atau maksimum. Metode simulated annealing berdasarkan pada pendinginan dari logam. Jika logam didinginkan perlahan-lahan, akan terbentuk sebuah potongan logam yang halus karena molekulnya telah masuk masuk ke dalam struktur kristal. Struktur kristal mewalkili keadaan energi minimum atau solusi yang optimal untuk permasalahan optimalisasi. Jika logam didinginkan terlalu cepat, logam akan membentuk potongan logam bergerigi kasar dan dilapisi dengan benjolan. Benjolan dan tepi bergerigi mewakili lokal minimum dan maksimum. Metropolis menciptakan sebuah algoritma yang juga dikenal sebagai aturan metropolis dari propabilitas untuk mensimulasikan pendinginan logam melalui serangkaian gerakan. Pada tiap pergerakan, sistem memiliki kemungkinan untuk merubah konfigurasi saat ini menjadi lebih buruk. Peluang perubahan konfigurasi dapat dihitung dari
⎧ 1 ⎪ ⎪ P( Δ E , T) ⎨ ⎪ exp ⎛⎜ − ΔE ⎞⎟ ⎪⎩ ⎝ KT ⎠
bila ΔE ≤ 0
bila ΔE > 0
(1) dimana ΔE : Perubahan energi/konfigurasi, T : Temperatur dan K : Konstanta Bolztmann 1.3860 x 10 −23 JK −1 dan 8.6174 x 10 −5 eV K −1 . Persamaan (1) ini juga disebut kriteria metropolis. Kemampuan untuk mengubah konfigurasi membuat simulated annealing memungkinkan untuk melompat keluar dari lokal maksima dan minima dimana sebagian besar algoritma lain terjebak di dalamnya. Beberapa parameter diperlukan dalam implementasi simulated annealing dan telah dirangkum baik oleh Davidson dan Harel : • Himpunan konfigurasi atau keadaan dari sistem, termasuk konfigurasi awal (yang sering dipilih secara acak). • Sebuah aturan generasi untuk konfigurasi baru, yang biasanya diperoleh dengan mendefinisikan lingkungan konfigurasi masing-masing dan memilih konfigurasi berkutnya secara acak dari lingkungan sekitar konfigurasi saat ini. • Target, atau biaya, fungsi, harus diminimalkan melalui konfigurasi ruang (ini adalah analog dari energi).
(
)
(
)
•
Jadwal pendinginan dari parameter kontrol, termasuk nilai-nilai awal dan aturan untuk kapan dan bagaimana cara mengubahnya (ini adalah analog dari suhu dan penurunannya). • Kondisi terminasi, yang biasanya didasarkan pada waktu dan nilai dari fungsi biaya atau parameter kontrol. Pada algoritma simulated annealing pertama perlu ditentukan awal dan akhir dari suhu. Hal ini penting karena suhu (T) akan digunakan dalam persamaan probabilitas. Persamaan probabilitas, seperti yang didefinisikan oleh metropolis pada persamaan (1), dimana K merupakan konstanta, sedangkan ΔE didapat dari
ΔE = E 2 − E1 (2) dimana E 2 adalah konfigurasi baru, dan E1 adalah konfigurasi saat ini. Jika konfigurasi baru memiliki biaya yang lebih kecil dan lebih baik daripada konfigurasi saat ini maka konfigurasi baru akan diterima secara otomatis. Hal ini juga berlaku jika diterapkan kedalam persamaan metropolis (1). Simulated annealing dimulai dengan memilih beberapa konfigurasi acak yang memecahkan masalah. Ada sebuag fungsi objektif yang menentukan biaya dari konfigurasi yang diberikan. Fungsi inilah yang sedang diminimalkan (atau dimaksimalkan tergantung dari solusi optimal yang ingin dicari. Biaya asli dipilih secara acak dari konfigurasi kemudian dihitung. Mengingat masih berada pada saat suhu asli, simulated annealing menghasilkan n konfgurasi baru satu persatu, dimana n adalah angka yang dipilih user sebelum simulated annealing dimulai. Setiap konfigurasi baru berasal dari konfigurasi lama. Biaya dari dua konfigurasi kemudian dibandingkan. Jika konfigurasi baru lebih baik dari konfigurasi saat ini maka secara otomatis diterima. Jika konfigurasi baru yang lebih buruk dari yang ada saat ini maka diterima atau tidaknya berdasarkan dari perhitungan propabilitas, dimana E1 adalah biaya dari konfigurasi saat ini dan E 2 adalah biaya dari konfigurasi baru. Setelah proses menemukan konfigurasi baru, kemudian dibandingkan dan ditentukan akan diterima atau tidaknya konfigurasi baru, langkah selanjutnya adalah perubahan suhu. Laju perubahan suhu berdasarkan pada masalah spesifik dan dan jumlah waktu yang user inginkan untuk simulated annealing berjalan. Jumlah iterasi (n) juga dipilih oleh user. Proses ini kemudian akan diulangi sampai suhu akhir tercapai. Ketika suhu mendingin, probabilitas untuk memilih konfigurasi baru menjadi berkurang, sama seperti molekul dalam sepotong logam yang tidak bergerak banyak. Algoritma Simulated Annealing dan Travelling Salesman Problem Metode simulated annealing dapat dipakai pada berbagai masalah optimasi, salah satunya adalah Travelling Salesmen Problem (TSP). Dalam TSP akan diberikan sejumlah n node yang terhubung, dan akan dicari rute optimal dengan melewati setiap node masingmasing satu kali dan kembali ke node awal. Rute optimal sendiri memiliki arti seperti jalur dengan jumlah biaya terkecil, atau waktu tempuh yang paling cepat. Jika terdapat banyak node maka akan membutuhkan waktu yang sangat lama untuk dapat menemukan jalur optimum. Simulated Annealing dapat diterapkan dalam kasus TSP. Algoritma akan dimulai pada suhu acak. Kemudian urutan bergerak akan diambil selama suhu tersebut. Dalam tiap gerakan akan diciptakan konfigurasi baru dan kemudian akan diterima atau ditolak sesuai
dengan perhitungan persamaan probabilitas (1). Ketika sebuah gerakan diterima suhu akan berubah. Proses gerakan akan dilakukan secara berulang-ulang hingga suhu mencapai suhu akhir. Semakin besar tinggi suhu maka akan semakin besar kemungkinan terjadi perpindahan yang kurang optimal. Konfigurasi atau Energi dalam simulated annealing merupakan biaya atau tujuan dari pencarian solusi permasalahan optimasi. Dalam TSP energi didapat dari jarak yang ditempuh saat melewati tiap node. Energi dapat dicari dengan menggunakan persamaan n
E = ∑ di i =1
(3) dimana E : Fungsi energi setelah iterasi, d i : jarak antara node(i) dan node(i+1), n : jumlah node. Algoritma simulated annealing juga bergantung pada nilai temperatur suhu dan nilai temperatur suhu akan mengalami penurunan pada tiap iterasi. Penurunan suhu tidak bisa dilakukan dengan sembarangan. Terdapat fungsi cooling schedule yang digunakan untuk mencari nilai suhu yang telah turun.
⎛T ⎞ Ti = T0 ⎜⎜ n ⎟⎟ ⎝ T0 ⎠
i N
(4) dimana Ti : temperatur cooling schedule ke-I, T0 : temperatur awal, Tn : temperatur cooling schedule, N : jumlah iterasi, dan i : iterasi (nilai i : 1,2,3,…). Dalam menyelesaikan masalah TSP dengan metode simulated annealing diperlukan beberapa langkah proses perhitungan sebelum mencapai solusi optimal. Proses yang dilakukan adalah : 1. Membangkitkan kondisi(state) awal dan temperatur. 2. Menghitung energi awal yang dihasilkan pada kondisi awal. 3. Update state dan hitung kembali energi yang dihasilkan setelah dilakukan update. 4. Bangkitkan bilangan random berdistribusi uniform [0,1], dilambangkan dengan (p). ⎛ ΔE ⎞ 5. Uji kriteria, bila p < exp⎜ − ⎟ update state diterima, selain dari kondisi ini ⎝ KT ⎠ ditolak.nilai E dapat dicari dengan menggunakan persamaan (3). 6. Turunkan temperatur (T) dengan fungsi cooling schedule (4). 7. Ulangi langkah ke-3 sampai mencapai kriteria. Jika telah mencapai kriteria maka berhenti. Flowchart dari algoritma simulated annealing (Larrosa, 2008) dapat dilhat pada gambar 4.
Gambar 3 Flowchart Algoritma Simulated Annealing Evaluasi
Pada percobaan program digunakan 10 transaksi diwilayah warungboto dari data transaksi PT Pos Indonesia Yogyakarta pada tanggal 1 desember 2011. Dari 10 transaksi awal didapatkan 8 titik jalan yang berbeda. 8 titik jalan tersebut dapat dilihat pada tabel 1. Tabel 1 Posisi 8 titik jalan percobaan wilayah warungboto Koordinat Koordinat JalanID Nama Jalan X Y
JLWR0001 kusuma negara
350
50
JLWR0002 veteran
660
200
JLWR0004 mondoliko
600
230
JLWR0005 warung boto I
540
380
JLWR0006 putra bangsa
500
330
JLWR0011 gajah
295
150
JLWR0012 persatuan
295
295
JLWR0017 garuda
165
175
Parameter yang digunakan dalam percobaan ini yaitu temperatur = 10000, cooling rate = 0,9999, dan temperatur minimum = 0,00001. Hasil dari pencarian rute optimal dari 8 titik pada tabel 1 adalah : Start Æ JLWR0001 Æ JLWR0011 Æ JLWR0017 Æ JLWR0012 Æ JLWR0006 Æ JLWR0005 Æ JLWR0004 ÆJLWR0002 Æ Finish. Total jarak dari rute optimal yang dihasilkan adalah 3557.93 meter. Keunggulan pada program aplikasi ini adalah : 1. Program aplikasi ini dapat dengan mudah dimengerti karena jalur pendistribusian ditampilkan dalam bentuk gambar diatas peta wilayah yogyakarta. 2. Program aplikasi dapat menampilkan dan mengedit seluruh data dari tabel-tabel yang ada di dalam database. Sehingga jika user ingin melihat atau mengedit database, user tidak perlu lagi membuka database master. 3. Pada program aplikasi ini digunakan metode simulated annealing. Metode ini akan membandingkan semua rute yang dapat dilalui pada suatu kumpulan titik node dan akan menghasilkan rute dengan jarak yang paling minimum. Sehingga rute yang ditemukan adalah rute optimal atau mendekati optimal. 4. Program aplikasi ini dilengkapi dengan fitur validasi. Sehingga meminimalkan peluang terjadinya proses error karena nilai yang tidak valid. 5. Tampilan program yang sederhana sehingga user dapat dengan mudah menjalankan dan menggunakan program. 6. Metode simulated annealing yang memiliki beberapa keunggulan dibandingkan dengan algoritma lainnya (djikstra, genetik, ant colony) yaitu proses iterasi yang banyak dan akan melakukan perbandingan terhadap tiap solusi sehingga algoritma akan menghasilkan solusi yang memiliki nilai mendekati optimal. Sedangkan kekuarangan pada program aplikasi ini adalah : 1. Setiap selesai melakukan proses tambah data dan update, data baru tidak langsung dapat ditambilkan di dalam layar program tetapi harus terlebih dahulu dilakukan proses refresh dengan menekan button refresh.
PENUTUP Setelah melakukan analisis dan pembuatan program aplikasi dengan topik Perancangan Program Optimalisasi Rute Pendistribusian Paket Pos Pada Kantor Pos MPC
Yogyakarta Dengan Metode Simulated Annealing, maka dapat disimpulkan sebagai berikut. 1. Program aplikasi ini dilengkapi dengan algoritma simulated annealing, sehingga program dapat membandingkan semua rute distribusi yang ada dalam suatu jaringan wilayah dan menemukan rute dengan jarak tempuh terpendek. 2. Program aplikasi ini dapat membantu proses mengedit data yang terdapat di dalam database. Sehingga user tidak perlu lagi membuka database master. 3. Program dilengkapi dengan visualisasi map, sehingga memudahkan user untuk mengetahui posisi letak titik-titik jalan dalam rute optimal yang akan dilewati.
Berdasarkan teori-teori yang telah dibahas sebelumnya dan hasil pengujian terhadap program aplikasi ini, maka ada beberapa saran yang dapat diberikan untuk meningkatkan program aplikasi jika dilakukan pengembangan lebih lanjut. 1. Pengembangan lebih lanjut disarankan untuk menambah variabel faktor kemacetan dalam menentukan rute optimal, sehingga rute yang dihasilkan akan lebih optimal lagi. 2. Pengembangan lebih lanjut disarankan untuk mengembangkan lagi wilayah pengiriman seperti wilayah provinsi atau lebih luas lagi. 3. Pengembangan lebih lanjut disarankan untuk menambah fitur zoom in dan zoom out untuk membantu user dalam melakukan navigasi pada peta. 4. Pengembangan lebih lanjut disarankan untuk membuat peta secara lebih rinci lagi, sehingga jalan kecil dan gang akan tampak di dalam peta.
DAFTAR PUSTAKA
Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. USA: Princeton University Press. Chibante, R. A. (2010). Simulated Annealing Theory with Applications. Sciyo. De Vicente, J., Lanchares, J., & Hermida, R. (2003). Placement by thermodynamic simulated annealing. Physics Letters , 415–423. Dharwiyanti, S. (n.d.). Retrieved from http://setia.staff.gunadarma.ac.id/Downloads/files/6077/Modul_UML.pdf Gutin G, P. A. (2002). The Traveling Salesman Problem and Its Variations. USA: Kluwer Academic Publishers.
Letchford, A. (2010). The Travelling Salesman Problem. Swansea: Lancaster University Management School. Michalewicz, Zbigniew, & Fogel, D. (2000). How to Solve It : Modern Heuristics. Springer. Pearson, Letchford, A. N., & A, N. (2005). Good Triangulations Yield Good Tours. 1-13. Press, W., Teukolsky, S., Vetterling, W., & Flannery, B. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University. Pressman, R. (2005). Software engineering : a practitioner's approach (sixth edition). New York: McGraw-Hill Science/Engineering/Math. Rao, S. S. (2009). Engineering Optimization : Theory and Practice, 4th. New Jersey: John Wiley and Sons. Rizal, J. (2007). Optimasi Pada Traveling Salesman Problem (TSP) dengan Pendekatan. Jurnal Gradien Vol.3 No.2 , 286-290. Ruohonen, K. (2008). Graph Theory. Tampereen teknillinen korkeakoulu. Shneiderman, B. (2005). Designing the User Interface: Strategies for Effective HumanComputer Interaction 4th Edition. USA: Addison-Wesley. Thomas M, C. (2009). Database Systems: A Practical Approach to Design, Implementation and Management (5th Edition). USA: Addison Wesley. Anonim, http://www.codeproject.com/ Akses : Oktober 2011 Anonim, http://www.posindonesia.co.id/ Akses : Oktober 2011
