LOCAL SEARCH BASED ALGORITHM FOR CVRP WITH STOCHASTIC DEMANDS

Harshdeep kaur, Harmandeep Singh

Abstract


This paper studies about the capacitated vehicle routing problem (CVRP). Since the problem is NP-hard, a local search based algorithm is used for the CVRP with the target to limit the aggregate visited distance and number of vehicles. This algorithm is proven to be effective and as efficient for CVRP by checking its comparability with existing best-known results. In this paper, this algorithm is used for CVRPSD by increasing the demands the customers by 10%, 15%, and 20% orderly. This algorithm is tested on the 5 problem set obtained from Augerat et. al CVRP benchmark problems which include instances range from 13 to 51 service nodes and a number of homogeneous vehicles are changed from 2 to 8 according to problem set. The empirical outcomes demonstrate that this algorithm gives better arrangements than understood benchmark problems contrasted with those detailed in the literature.

Keywords


Capacitated Vehicle routing problem, Stochastic demands, Local Search, deviation

Full Text:

PDF

References


Xinyu Wang, Tsan-Ming Choi, Haikuo Liu, and Xiaohang Yue, "Novel Ant Colony Optimization Methods for Simplifying Solution Construction in Vehicle Routing Problems," IEEE Transactions on Intelligent Transportation Systems, vol. 17, no. 11, pp. 3132--3141, 2016.

Qianguo Chen, Tao Qian, and Kui Liu, "A Logistic Distribution Routes Solving Strategy Based on the Physarum Network and Ant Colony Optimization Algorithm," in 2015 IEEE 17th International Conference on High Performance Computing and Communications (HPCC), 2015 IEEE 7th, 2015, pp. 1743-1748.

Udom Janjarassuk and Ruedee Masuchun, "An ant colony optimization method for the capacitated vehicle routing problem with stochastic demands," in Computer Science and Engineering Conference (ICSEC), 2016 International, 2016, pp. 1--5.

Abel Garcia-Najera and John Bullinaria, "An evolutionary approach for multi-objective vehicle routing problems," Computers & Industrial Engineering, vol. 81, pp. 90--108, 2015.

Marwa Amous, Said Toumi , Bassem Jarboui, and Mansour Eddaly, "A variable neighborhood search algorithm for the capacitated vehicle routing problem," Electronic Notes in Discrete Mathematics, vol. 58, pp. 231-238, 2017.

TUNCDAN Baltacioglu, MILORAD Vidovic, O Yurt , and G Ozkan, "Matching algorithms for the vehicle routing in containers delivery and collecting problems," in Proc. of The 7th Balkan Conf. on Operational Research (BACOR 05), Constanta, Romania, May 25, vol. 28, 2005.

Ying Zhou and Jiahai Wang, "A Local Search-Based Multiobjective Optimization algorithm for multiobjective vehicle routing problem with time windows," IEEE Systems Journal, vol. 9, no. 3, pp. 1100--1113, 2015.

Jiahai Wang et al., "Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: formulation, instances, and algorithms," IEEE transactions on cybernetics, vol. 46, no. 3, pp. 582--594, 2016.

Jiafu Tang, Jing Guan, Yang Yu, and Jinyu Chen, "Beam Search Combined With MAX-MIN Ant Systems and Benchmarking Data Tests for Weighted Vehicle Routing Problem," IEEE Transactions on Automation Science and Engineering, vol. 11, pp. 1097-1109, OCT 2014.

Marwa Amousa, Said Toumia, Bassem Jarbouia, and Mansour Eddaly, "A variable neighborhood search algorithm for the capacitated vehicle routing problem," Electronic Notes in Discrete Mathematics, vol. 58, pp. 231--238, 2017.

Chun-Chao Yeh , Da-Yuan Liu , and Yan-Kai Liao, "Two-Stage Iterated Local Search for Solving capacitated vehicle routing problems," in Computer, Consumer and Control (IS3C), 2016 International Symposium on, 2016, pp. 45-48.




DOI: https://doi.org/10.26483/ijarcs.v8i7.4468

Refbacks

  • There are currently no refbacks.


Bookmark and Share


Copyright (c) 2017 International Journal of Advanced Research in Computer Science