Araştırma Makalesi
BibTex RIS Kaynak Göster

A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems

Yıl 2018, Cilt: 31 Sayı: 2, 489 - 513, 01.06.2018

Öz




In vehicle routing problems, the initial solutions of
the routes are important for improving the quality and solution time of the
algorithm. For a better route construction algorithm, the obtained initial
solutions must be basic, fast, and flexible with reasonable accuracy. In this
study, initial solutions improvement for CVRP is introduced based on a method that
is introduced in the literature. Using a different formula for addressing the
gravitational forces, a new method is introduced and compared with the previous
physics inspired algorithm. By using the initial solutions of the proposed
method and using them as RTR and SA initial routes, it is seen that better
results are obtained when compared with various algorithms from the literature.
Also, in order to fairly compare the algorithms executed on different machines,
a new comparison scale for the solution quality of vehicle routing problems is
proposed that depends on the solution time and the deviation from the best
known solution. The obtained initial solutions are then input to Record-to-Record
and Simulated Annealing algorithms to obtain final solutions. Various test
instances and CVRP solutions from the literature are used for comparison. The
comparisons with the proposed method have shown promising results.




Kaynakça

  • Baker, B. M., & Ayechew, M. (2003). Agenetic algorithm for the vehicle routing problem. Computers & Operations Research, 787 – 800.
  • Battarra, M., Benedettini, S., & Roli, A. (2011). Additional Material for “Leveraging saving-based algorithms by master-slave genetic algorithms”. Engineering Applications of Artificial Intelligence, Appendix A. Supplementary data.
  • Battarra, M., Benedettini, S., & Roli, A. (2011). Leveraging saving-based algorithms by master–slave genetic algorithms. Engineering Applications of Artificial Intelligence, 555-566.
  • Chatterjee, A., Mahanti, G. K., & Pathak, N. (2010). Comparative Performance of Gravitaional Search Algorithm and Modified Particle Swarm Optimization Algorithm for Synthesis of Thinned Scanned Concentric Ring Array Antenna. Progress In Electromagnetics Research B, 331–348.
  • Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y., & Semet, F. (2002). A guide to vehicle routingheuristics. Journal of the Operational Research Society, 512-522.
  • Ding, D., Qi, D., Luo, X., Chen, J., Wang, X., & Du, P. (2012). Convergence analysis and performance of an extended central force optimization algorithm. Applied Mathematics and Computation, 2246–2259.
  • Duman, S., Güvenç, U., & Yörükeren, N. (2010). Gravitational Search Algorithm for Economic Dispatch with Valve-Point Effects. International Review of Electrical Engineering, 2890-2895.
  • Formato, R. A. (2007). Central Force Optimization: A New Metaheuristic with Applications in Applied Electromagnetism. Progress In Electromagnetics Research, 425-491.
  • Groer, C. (2015, 5 5). VRPH. Retrieved from COIN-OR Home: http://www.coin-or.org/projects/VRPH.xml
  • Groer, C., & Golden, B. (2015, 5 5). Parallel and Serial Algorithms for Vehicle Routing Problems. Retrieved from UMD, PhD Thesis, 2008: http://drum.lib.umd.edu/bitstream/1903/9011/1/Groer_umd_0117E_10068.pdf
Yıl 2018, Cilt: 31 Sayı: 2, 489 - 513, 01.06.2018

Öz

Kaynakça

  • Baker, B. M., & Ayechew, M. (2003). Agenetic algorithm for the vehicle routing problem. Computers & Operations Research, 787 – 800.
  • Battarra, M., Benedettini, S., & Roli, A. (2011). Additional Material for “Leveraging saving-based algorithms by master-slave genetic algorithms”. Engineering Applications of Artificial Intelligence, Appendix A. Supplementary data.
  • Battarra, M., Benedettini, S., & Roli, A. (2011). Leveraging saving-based algorithms by master–slave genetic algorithms. Engineering Applications of Artificial Intelligence, 555-566.
  • Chatterjee, A., Mahanti, G. K., & Pathak, N. (2010). Comparative Performance of Gravitaional Search Algorithm and Modified Particle Swarm Optimization Algorithm for Synthesis of Thinned Scanned Concentric Ring Array Antenna. Progress In Electromagnetics Research B, 331–348.
  • Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y., & Semet, F. (2002). A guide to vehicle routingheuristics. Journal of the Operational Research Society, 512-522.
  • Ding, D., Qi, D., Luo, X., Chen, J., Wang, X., & Du, P. (2012). Convergence analysis and performance of an extended central force optimization algorithm. Applied Mathematics and Computation, 2246–2259.
  • Duman, S., Güvenç, U., & Yörükeren, N. (2010). Gravitational Search Algorithm for Economic Dispatch with Valve-Point Effects. International Review of Electrical Engineering, 2890-2895.
  • Formato, R. A. (2007). Central Force Optimization: A New Metaheuristic with Applications in Applied Electromagnetism. Progress In Electromagnetics Research, 425-491.
  • Groer, C. (2015, 5 5). VRPH. Retrieved from COIN-OR Home: http://www.coin-or.org/projects/VRPH.xml
  • Groer, C., & Golden, B. (2015, 5 5). Parallel and Serial Algorithms for Vehicle Routing Problems. Retrieved from UMD, PhD Thesis, 2008: http://drum.lib.umd.edu/bitstream/1903/9011/1/Groer_umd_0117E_10068.pdf
Toplam 10 adet kaynakça vardır.

Ayrıntılar

Bölüm Computer Engineering
Yazarlar

Kenan Karagül

Michael G. Kay

Sezai Tokat

Yayımlanma Tarihi 1 Haziran 2018
Yayımlandığı Sayı Yıl 2018 Cilt: 31 Sayı: 2

Kaynak Göster

APA Karagül, K., Kay, M. G., & Tokat, S. (2018). A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems. Gazi University Journal of Science, 31(2), 489-513.
AMA Karagül K, Kay MG, Tokat S. A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems. Gazi University Journal of Science. Haziran 2018;31(2):489-513.
Chicago Karagül, Kenan, Michael G. Kay, ve Sezai Tokat. “A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems”. Gazi University Journal of Science 31, sy. 2 (Haziran 2018): 489-513.
EndNote Karagül K, Kay MG, Tokat S (01 Haziran 2018) A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems. Gazi University Journal of Science 31 2 489–513.
IEEE K. Karagül, M. G. Kay, ve S. Tokat, “A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems”, Gazi University Journal of Science, c. 31, sy. 2, ss. 489–513, 2018.
ISNAD Karagül, Kenan vd. “A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems”. Gazi University Journal of Science 31/2 (Haziran 2018), 489-513.
JAMA Karagül K, Kay MG, Tokat S. A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems. Gazi University Journal of Science. 2018;31:489–513.
MLA Karagül, Kenan vd. “A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems”. Gazi University Journal of Science, c. 31, sy. 2, 2018, ss. 489-13.
Vancouver Karagül K, Kay MG, Tokat S. A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems. Gazi University Journal of Science. 2018;31(2):489-513.