Performance evaluation of the saving method and the optimal partitioning method for a vehicle routing problem  

Oleh:

Koga, Hiroki ; Goto, Hiroyuki ; Chiba, Eishi

Jenis: Article from Proceeding
Dalam koleksi: The 14th Asia Pacific Industrial Engineering and Management Systems Conference (APIEMS), 3-6 December 2013 Cebu, Philippines, page 1-11.
Topik: Mathematical Models; Operations Research (OR); Optimization/Artificial Intelligence Techniques; Transportation
Fulltext: 1237.pdf (408.19KB)

Isi artikel

This research focuses on the saving method and the optimal partitioning method for a Vehicle Routing Problem (VRP). The two methods are examined as good approximate methods for a variant of VRP. We do not consider the number of vehicles used. The optimal partitioning method needs to determine a sequence of visiting all customers. To determine the sequence, an approximation method solving the Traveling Salesman Problem (TSP) is applied. This research first formulates the variant of VRP. Then, from computational experiments, we compare the two approximate methods in terms of approximate solution and computation time. We confirm that, if the number of customers is large, the solution quality of the saving method is better than that of the optimal partitioning method. However, if the number of customers is small, the solution quality of the optimal partitioning method is better than that of the saving method. Regarding computation time, the computation time using the saving method is faster than that of the optimal partitioning method. Moreover, we show, from computational experiments, average approximation ratios of the two methods. The results obtained show that the ratios are almost one.

Opini Anda

Klik untuk menuliskan opini Anda tentang koleksi ini!

Kembali