Penerapan Bidirectional Search dan Held-Karp pada Penentuan Rute Pengiriman Produk


I Gede Surya Rahayuda, Ni Putu Linda Santiari, Norsa Yudhi Arso


Bidirectional Search dan Held-Karp merupakan salah satu metode pencarian jalur terdekat atau sering disebut dengan metode shortes path. Bidirectional Search mencari jalur terdekat dengan melakukan pencarian dwi arah, proses pertama dimulai dari level awal graph matrix menuju level selanjutnya dan proses kedua dimulai dari level akhir menuju level sebelumnya. Proses tersebut akan menghasilkan rute awal dan rute akhir, kemudian kedua rute tersebut dirangkai menjadi rute gabungan. Tidak seperti pada metode Bidirectional Search, pada metode Held-Karp hanya dilakukan satu proses pencarian, dan pada metode Held-Karp proses pencarian sudah memperhitungkan mengenai jarak yang ditempuh sampai dengan kembali ke titik awal. Pada penelitian ini metode Bidirectional Search dan Held-Karp akan dikembangkan dalam bentuk program menggunakan bahasa pemrograman visual basic. Program tersebut diterapkan untuk menentukan jalur terbaik pada kasus pengiriman produk. Bidirectional Search juga akan dibandingkan dengan metode Held-Karp. Percobaan yang dilakukan pada beberapa data tes berupa paket pengiriman produk, didapatkan bahwa metode Held-Karp mendapatkan rata-rata hasil rute pengiriman yang lebih baik sekitar 5 % dibandingkan dengan metode Bidirectional Search


Bidirectional Search and Held-Karp is one type of the shortes path methods. Bidirectional Search looks for the nearest path by doing a two way search, the first process starts from the initial level of the graph matrix to the next level and the second process starts from the end level to the previous level. The process will generate the initial route and the final route, then the two routes are assembled into a combined route. Bidirectional Search does not count the process of returning from the final destination to the starting point or appropriate for non circular paths.Unlike Bidirectional Search method, Held-Karp method only performs one way search process, and in the Held-Karp method the search process has calculated the distance traveled up to the return point or appropriate for circular paths. In this research, Bidirectional Search and Held-Karp method will be developed into desktop program using visual basic programming language. The program is implemented to determine the best path in case of product delivery. Bidirectional Search will also be compared to the Held-Karp method. Experiments performed on some tes data in the form of product delivery package, it is found that the Held-Karp method gets the average result of better delivery route about 5% compared to Bidirectional Search method.

Kata Kunci

shortest path, Bidirectional Search, Held-Karp, graph matrix, visual basic

Teks Lengkap:



AN, H.-C., KLEINBERG, R. and SHMOYS, D.B., 2015. Improving Christofides’ Algorithm for the s-t Path TSP. Journal of the ACM, 62(5), pp.1–28.

BECKER, A., FOX-EPSTEIN, E., KLEIN, P.N. and MEIERFRANKENFELD, D., 2017. Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs ∗. (8), pp.1–8.

CHEKURI, C., 2017. Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Time ∗. In: 58th Annual IEEE Symposium on Foundations of Computer Science.

CHEN, J., HOLTE, R.C., ZILLES, S. and STURTEVANT, N.R., 2017. Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions.

CHENTSOV, A., KHACHAY, M. and KHACHAY, D., 2016. Linear time algorithm for Precedence Constrained Asymmetric Generalized Traveling Salesman Problem. IFAC-PapersOnLine, 49(12), pp.651–655.

CHILTON, M.A., 2014. Resource allocation in IT projects: Using schedule optimization. International Journal of Information Systems and Project Management, 2(3), pp.47–59.

DRAMSKI, M., 2014. Bi-directional search in route planning in navigation. Scientific Journals Maritime University of Szczecin, 39(111), pp.57–62.

HOLTE, R.C., FELNER, A., SHARON, G., STURTEVANT, N.R. and CHEN, J., 2017. MM: A bidirectional search algorithm that is guaranteed to meet in the middle. Artificial Intelligence, 252, pp.232–266.

ISLAM, F., NARAYANAN, V. and LIKHACHEV, M., 2016. A∗-Connect: Bounded suboptimal bidirectional heuristic search. In: Proceedings - IEEE International Conference on Robotics and Automation. pp.2752–2758.

KELVIN, A., 2016. Aplikasi Program Dinamis dalam Pemecahan TSP. Jurnal Ilmu Komputer dan Informasi.

KUCHEROV, G., SALIKHOV, K. and TSUR, D., 2014. Approximate String Matching Using a Bidirectional Index. Combinatorial pattern matching, 8486, pp.222–231.

MOORE, T., 2015. Implementing the Held-Karp Lower Bound Algorithm in Python. In: Final Report for CM2SC 4515 – Honors Option.

MOYLETT, D.J., LINDEN, N. and MONTANARO, A., 2016. Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs. pp.1–12.

RAHAYUDA, I.G.S. and SANTIARI, N.P.L., 2017. Penerapan Pemrograman Dinamis Pada Manajemen Pengiriman Produk Menggunakan Metode Held-Karp. In: Konferensi Nasional Sistem & Informatika 2017. pp.513–518.

RAHAYUDA, I.G.S. and SANTIARI, N.P.L., 2018a. Basis Path Testing of Iterative Deepening Search and Held-Karp on Pathfinding Algorithm. Jurnal Ilmiah Kursor, 9(2).

RAHAYUDA, I.G.S. and SANTIARI, N.P.L., 2018b. Implementasi dan Perbandingan Metode Iterative Deepening Search dan Held-Karp pada Manajemen Pengiriman Produk. Sisfo, 07(02).

STURTEVANT, N.R. and CHEN, J., 2016. External memory bidirectional search. In: IJCAI International Joint Conference on Artificial Intelligence. pp.676–682.

SUN, Q., LEE, S. and BATRA, D., 2017. Bidirectional beam search: Forward-backward inference in neural sequence models for fill-in-the-blank image captioning. In: Proceedings - 30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017. pp.7215–7223.

SVENSSON, O., 2015. Symmetric Traveling Salesman Problem.

ZHANG, B., HAO, J. and MOUFTAH, H.T., 2014. Bidirectional multi-constrained routing algorithms. IEEE Transactions on Computers, 63(9), pp.2174–2186.