Nama : GUSTINA KURBAITA
NIM : 2011 251 2035
Dosen Pengasuh : Prof. Chuzaimah D. Diem, M. L. S., Ed. D
1. Title of the article
A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing Problem
Cabang atau bagian dari proses suatu permasalahn algoritma terletak pada bagaimana permasalahan tersebut dapat di selesaikan dengan mudah dari kapasitasnya. Atau dengan kata lain bagaimana membatasi masalah algoritma agar mudah di pahami.
2. Author (s)
Adam N. Letchford, Jens Lysgaard and Richard W. Eglese
3. Background (Problem/Fact and What Should be)
a. Algorithm for the capacitated open vehicle routing problem
b. The first present exact optimization algorithm for the open version of well-known capacitated vehicle routing problem (CVRP)
c. To compare the relative difficulty of open and closed versions of the same problem
a. Membatasi masalah algoritma agar mudah di pahami
b. Optimasi algoritma pertama yang tepat untuk masalah versi terbuka yaitu CVRP
c. Membandingkan kesulitan relatif versi algoritma terbuka dan tertutup dari masalah yang sama.
4. Methodology
In this research Computational results are given for several standard test instances, which enables us for the first time to asses teh quality of exiting heuristic methods, and to compare the relative difficulty of open and closed versions of the same problem.
Pada penelitian ini menunjukkan hasil perhitungan yang diberikan untuk beberapa kasus uji standar, yang memungkinkan kita untuk pertama kalinya menilai kualitas dari metode heurustik yang ada, dan untuk membandingkan kesulitan relatif versi terbuka dan tertutup dari masalah yang sama
Ø Penelitian ini menggunakan Metode Heuristik
Penelitian ini
· In the cassical version of Vehicle Routing Problems (VRPs), the vehicles are required to return to the depot after completing service (see for example Toth & Vigo, 2002).
· Although the CVROP appears to be variant of the standard CVRP, we have seen that it is intermediate in generality between the CVRP and the ACVRP. As a result, some subtle modifications to the formulation, additional classes of inequalities, and adjustments to the separation algorithms. Our results show that small to medium-scale instances of the COVRP are just as amenable to exact solution by branch-and-cut as their CVRP counterparts. In fact, if anything, the open versions often appear to be slighty easier.
5. Results
a. Formulation and Valid Inequalities
Definition 1 The partially asymmetric CVRP (PACVRP) is the generalization of the CVRP in which the cost of travel c0i is permitted to be different from ci0.
Proposition 1 The COVRP and the PACVRP are equivalent.
Symmetric inequalities
Proposition 2 Let be valid for the CVRP. Then ) ≤ β is valid for the COVRP.
Asymmetric inequalities
Theorem 1 Let H Vc (the handle) and T1 , . . . , Tt V (the teeth) be such that :
Every tooth property intersects with handle, i.e., Ti H and Ti \ H are non – empty for all i ;
If any pair of teeth intersect, then either all vertices in the intersection lie in the handle or all lie outside, i.e., for 1 , either Ti Tj H or Ti Tj H = .
b. The Branch-and-Cut Algorithm
1. Saparation of symmetric inequalities
2. Separation of balancing inequalities
3. Separation of mixed strengthened comb inequalities
4. Saparation strategy
c. Computational Experiments
Our algorithm has been coded in the C programming language using the Microsoft Visual C++ v. 6.0 compiler. For solving LPs you have used the CPLEX callable library v. 9.0. All ecperiments have been done on a PC with a 1.6 GHz Intel Pentium M processor and 512 MB of RAM running Microsoft Windows XP .
6. Discussion interpretation of the results
7. Conclusion and implication
1. As a results, some subtle modifications are needed to adapt a branch-and-cut code for the CVRP to the COVRP. This includes modifications to the formulation, additional classes of enequalities, and adjustments to the separation algorithms.
2. Our results show that small to medium-scale instances of the COVRP are just as amenable to exact solution by branch-and-cut as their CVRP counterparts. In fact, if anything, the open versions often appear to be slightly easier.
3. Future research could include the incorporation of column generation, leading to a full branch-cut-and-price algorithm along the lines of the one presented in Fukasawa et al.(2006). This would no doubt lead to the solution of even more instances, especially those with small vehicle capacities and a large number of vehicle.
8. References
L, Adam, Lysgaard., J, Eglese., R, Eglese.(2006). A branch-and-cut algorithm for the capacitated open vehicle routing problem. Journal of the Operational Research Society, 58 (10), 1642 – 1651.
9. Summary
A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing roblem, disini maksudnya adalah Cabang / bagian dari proses suatu permasalahan algoritma terletak pada bagaimana permasalahan tersebut dapat di selesaikan dengan mudah dari kapasitasnya, atau dengan kata lain bagaimana membatasi masalah algoritma agar mudah di pahami.
Pada artikel ini peneliti menyajikan optimasi yang pertama algoritma yang tepat versi terbuka untuk masalah kapasitasnya yang terkenal yaitu CVRP (Capacitated Vehicle Routing Problem). Algoritma ini didasarkan pada cabang-potong. Meskipun versi algoritma terbuka CVRP awalnya tampak seperti variasi kecil dari CVRP standar, integer perumusan pemrograman dan memotong ternyata perlu dimodifikasi dengan cara yang halus.
Penelitian ini menggunakan Metode Heuristik, dimana hasil perhitungan yang diberikan untuk beberapa kasus uji standar menunjukkan, yang memungkinkan untuk kita pertama kalinya menilai kualitas yang ada, dan membandingkan kesulitan relatif versi terbuka dan tertutup dari masalah yang sama. Algoritma versi terbuka biasa dikenal dengan COVRP (Capaciatated Open Vehicle Routing Problem) sedangkan algoritma versi tertutup dikenal dengan nama CVRP (Capacitated Vehicle Routing Problem).
Peneliti memberikan formulasi pemrograman bilangan bulat untuk COVRP dan menyajikan beberapa kesenjangan yang valid, dimana hasil penelitian menujukkan bahwa kesenjangan yang lebih kompleks diperlukan untuk versi terbuka daripada versi tertutup. Secara umum penelitian ini menunjukkan bahwa versi terbuka biasanya sedikit lebih mudah untuk memecahkan masalah algoritma daripada versi tertutup.
Tidak ada komentar:
Posting Komentar