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

Kenan KARAGÜL [1] , Michael G. KAY [2] , Sezai TOKAT [3]

94 110


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.


Constructive Routing Heuristics, Vehicle Routing Problem, Initial Routing Solutions, Physics-Inspired Optimization, Capacitated Vehicle Routing Problem
  • 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
Konular Fen
Dergi Bölümü Computer Engineering
Yazarlar

Yazar: Kenan KARAGÜL
Ülke: Turkey


Yazar: Michael G. KAY
Ülke: United States


Yazar: Sezai TOKAT
Ülke: Turkey


Bibtex @araştırma makalesi { gujs318604, journal = {Gazi University Journal of Science}, issn = {}, eissn = {2147-1762}, address = {Gazi Üniversitesi}, year = {}, volume = {31}, pages = {489 - 513}, doi = {}, title = {A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems}, key = {cite}, author = {TOKAT, Sezai and KAY, Michael G. and KARAGÜL, Kenan} }
APA KARAGÜL, K , KAY, M , TOKAT, S . (). A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems. Gazi University Journal of Science, 31 (2), 489-513. Retrieved from http://dergipark.gov.tr/gujs/issue/37206/318604
MLA KARAGÜL, K , KAY, M , TOKAT, S . "A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems". Gazi University Journal of Science 31 (): 489-513 <http://dergipark.gov.tr/gujs/issue/37206/318604>
Chicago KARAGÜL, K , KAY, M , TOKAT, S . "A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems". Gazi University Journal of Science 31 (): 489-513
RIS TY - JOUR T1 - A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems AU - Kenan KARAGÜL , Michael G. KAY , Sezai TOKAT Y1 - 2018 PY - 2018 N1 - DO - T2 - Gazi University Journal of Science JF - Journal JO - JOR SP - 489 EP - 513 VL - 31 IS - 2 SN - -2147-1762 M3 - UR - Y2 - 2018 ER -
EndNote %0 Gazi University Journal of Science A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems %A Kenan KARAGÜL , Michael G. KAY , Sezai TOKAT %T A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems %D 2018 %J Gazi University Journal of Science %P -2147-1762 %V 31 %N 2 %R %U
ISNAD KARAGÜL, Kenan , KAY, Michael G. , TOKAT, Sezai . "A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems". Gazi University Journal of Science 31 / 2 489-513.