Penyelesaian Capacitated Arc Routing Problem dengan Metode Heuristik Path Scanning with Efficiency Rule

Abstract

Capacitated Arc Routing Problem (CARP) merupakan salah satu bentuk permasalahan penentuan rute transportasi yang melibatkan graf dengan sisi tak berarah. Tujuan dari graf CARP adalah melayani semua permintaan pelanggan yang berada pada sisi graf dengan sejumlah kendaraan berkapasitas homogen yang memulai dan mengakhiri perjalanannya di sebuah depot. Salah satu metode heuristik yang dapat digunakan untuk menentukan solusi terbaik graf CARP adalah algoritme path scanning. Metode ini mengarahkan kendaraan yang sedang beroperasi agar melayani sisi terdekat yang belum dilayani sampai sisa kapasitas kendaraan tidak mencukupi untuk melayani sisi berikutnya. Dalam perkembangannya, algoritme path scanning dimodifikasi dengan menambahkan kriteria pembangkit aturan (triggering criteria) dan aturan efisiensi. Penambahan komponen tersebut bertujuan membatasi pemilihan sisi yang belum dilayani ketika sisa kapasitas kendaraan mencapai batas tertentu sehingga solusi dapat lebih optimal. Hasilnya menunjukkan bahwa penggunaan algoritme path scanning dengan aturan efisiensi lebih baik daripada algoritme path scanning perdana. Kata kunci: aturan efisiensi, CARP, graf, metode heuristik, path scanning

Capacitated Arc Routing Problem (CARP) is one of the transportation problems which involves a graph with undirected arcs. The objective of CARP is to service all of the customers’ demands located on the edges of the graph with a fleet of homogenous vehicles with limited capacity that starts and ends its routes at a depot. One of the heuristic methods that can be used to gain the best solution of the CARP is the path scanning algorithm. This method let the current operating vehicle to service the nearest unserviced edge until the remaining vehicle capacity is not sufficient enough to service the next unserviced edge. Several years later, the path scanning algorithm has been modified by adding a triggering criteria and an efficiency rule. The aim of these additional components is to restrict the next unserviced edge to be serviced by the vehicle when the remaining vehicle capacity has reached a certain load threshold, so that the solution could be more optimal. The result shows that the path scanning algorithm with efficiency rule has a better performance than the first path scanning algorithm. Keywords: CARP, efficiency rule, graph, heuristic method, path scanning