LOCAL SEARCH BASED ALGORITHM FOR CVRP WITH STOCHASTIC DEMANDS

Article Sidebar

PDF
Published: Aug 28, 2017
DOI: https://doi.org/10.26483/ijarcs.v8i7.4468
Keywords:
Capacitated Vehicle routing problem, Stochastic demands, Local Search, deviation

Main Article Content

Harshdeep kaur
Punjabi University, Patiala, INDIA
Harmandeep Singh
Punjabi University, Patiala, INDIA

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.

Downloads

Download data is not yet available.

Article Details

Issue
Vol. 8 No. 7 (2017): July-August 2017
Section
Articles

COPYRIGHT

Submission of a manuscript implies: that the work described has not been published before, that it is not under consideration for publication elsewhere; that if and when the manuscript is accepted for publication, the authors agree to automatic transfer of the copyright to the publisher.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work
  • The journal allows the author(s) to retain publishing rights without restrictions.
  • The journal allows the author(s) to hold the copyright without restrictions.
Author Biographies

Harshdeep kaur, Punjabi University, Patiala, INDIA

Research Scholar at Department of Computer Engineering

Harmandeep Singh, Punjabi University, Patiala, INDIA

Assistant Professor at Department of Computer Engineering

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.