Computer Science ›› 2020, Vol. 47 ›› Issue (10): 215-221.doi: 10.11896/jsjkx.190600101

• Artificial Intelligence • Previous Articles     Next Articles

Study on Transportation Problem Using Monte Carlo Similarity Based Genetic Algorithm

LI Yuan-feng, LI Zhang-wei, QIN Zi-hao, HU Jun, ZHANG Gui-jun   

  1. College of Information Engineering,Zhejiang University of Technology,Hangzhou 310023,China
  • Received:2019-06-19 Revised:2019-11-08 Online:2020-10-15 Published:2020-10-16
  • About author:LI Yuan-feng,born in 1993,postgra-duate.His main research interests include intelligent information processing and so on.
    ZHANG Gui-jun,born in 1974,is a member of China Computer Federation.His main research interests include intelligent information processing,optimization theory and algorithm design and bioinformatics.
  • Supported by:
    National Natural Science Foundation of China (61573317) and General Project of Education Department of Zhejiang Province (Master of Engineering) (Y201840644)

Abstract: Aiming at the problem of balanced transportation,this paper proposes a Monte Carlo similarity based genetic algorithm.Firstly,the matrix elements are used to initialize the population,which increases the diversity of the population.Secondly,the dynamic mutation rate operator and the random mutation strategy are designed to enhance the search ability of the algorithm and accelerate the convergence speed.Finally,Monte Carlo similarity is adopted to avoid falling into the local optimal solution problem.The effectiveness of the algorithm is verified by the comparison of the convergence rate,the optimal solution deviation rate and the relative standard deviation by the basic genetic algorithm GA and the improved genetic algorithm IGA.According to the geographic data of Hangzhou,the transportation and distribution system based on ArcGIS platform is designed and developed to realize the function of solving the balanced transportation problem.The test results show the effectiveness of the proposed algorithm.

Key words: Cross variation, Genetic algorithm, Monte Carlo similarity, Transportation problem

CLC Number: 

  • TP301.6
[1]HITCHCOCK F L.The distribution of a product from several sources to numerous localities[J].Journal of Mathematics and Physics,1941,20(1/2/3/4):224-230.
[2]KOOPMANS T C.Optimum utilization of the transportationsystem[J].Econometrica:Journal of the Econometric Society,1949,17:136-146.
[3]ORLIN J B.A faster strongly polynomial minimum cost flow algorithm[J].Operations research,1993,41(2):338-350.
[4]KLOSE A.Algorithms for solving the single-sink fixed-chargetransportation problem[J].Computers & Operations Research,2008,35(6):2079-2092.
[5]ZHU L L.Inteligent Optimization Algorithm for Upper Minimal Total Cost Bound of Transportation Problem with Varying Demands and Supplies[D].Nanchang:Nanchang University,2015.
[6]SHARMA R R K,PRASAD S.Obtaining a good primal solution to the uncapacitated transportation problem[J].European Journal of Operational Research,2003,144(3):560-564.
[7]PAPAMANTHOU C,PAPARRIZOS K,SAMARAS N.Computational experience with exterior point algorithms for the transportation problem[J].Applied Mathematics and Computation,2004,158(2):459-475.
[8]ADLAKHA V,KOWALSKI K,VEMUGANTI R R.Heuristic algorithms for the fixed-charge transportation problem[J].OPSEARCH,2006,43(2):132-151.
[9]KANNAN G,KUMAR P S,VINAY V P.Comments on nonli-near fixed charge transportation problem by spanning tree-based genetic algorithm by Jung-Bok Jo,Yinzhen Li,Mitsuo Gen,Computers & Industrial Engineering (2007)[J].Computers & Industrial Engineering,2008,55(2):533-534.
[10]KIRALY Z,KOVACS P.Efficient implementations of mini-mum-cost flow algorithms[J].Acta Universitatis Sapientiae,Informatica,2012,4(1):67-118.
[11]LOTFI M M,TAVAKKOLI-MOGHADDAM R.A genetic algorithm using priority-based encoding with new operators for fixed charge transportation problems[J].Applied Soft Computing,2013,13(5):2711-2726.
[12]MOLLA-ALIZADEH-ZAVARDEHI S,NEZHAD S S,TAVAK-KOLI-MOGHADDAM R,et al.Solving a fuzzy fixed charge so-lid transportation problem by metaheuristics[J].Mathematical &Computer Modelling,2013,57(5/6):1543-1558.
[13]SABBAGH M S,GHAFARI H,MOUSAVI S R.A new hybrid algorithm for the balanced transportation problem[M]//Pergamon Press,2015.
[14]XIE F,BUTT M M,LI Z,et al.An upper bound on the minimal total cost of the transportation problem with varying demands and supplies[J].Omega,2017,68:105-118.
[15]KARAGUL K,SAHIN Y.A Novel Approximation Method to
Obtain Initial Basic Feasible Solution of Transportation Problem[J].Journal of King Saud University-Engineering Sciences,2020(32):211-218.
[16]LIU Y M,WEI O,HUANG M Y,et al.Feature Selection Optimization Based on Atomic Set and Genetic Algorithm in Software Product Line [J].Journal of Chinese Computer Systems,2017,38(1):35-39.
[17]YANG X W,YANG L J.An Improved Genetic Algorithm Based on Crossover Model [J].Control and Decision,2016,31(10):1837-1844.
[18]HAN K K,XIE Z P,LV X.Fog Computing Task Scheduling Strategy Based on Improved Genetic Algorithm [J].Computer Science,2018,45(4):137-142.
[19]WU X L,XIAO X,ZHAO N.Flexible Job Shop Dual Resource Scheduling Problem Considering Loading and Unloading [J].Control and Decision,2020,35(10):2475-2485.
[20]SHI T F.Research on Path Planning for Mobile Robot Based on Improved Genetic Algorithm [J].Computer Simulation,2011,28(4):193-195.
[21]WEN Y,PAN D Z.Improved Genetic Algorithm for Traveling Salesman Problem[J].Computer Science,2016,43(S1):90-92.
[1] YANG Hao-xiong, GAO Jing, SHAO En-lu. Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery [J]. Computer Science, 2022, 49(6A): 191-198.
[2] SHEN Biao, SHEN Li-wei, LI Yi. Dynamic Task Scheduling Method for Space Crowdsourcing [J]. Computer Science, 2022, 49(2): 231-240.
[3] WU Shan-jie, WANG Xin. Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks [J]. Computer Science, 2021, 48(7): 308-315.
[4] ZHENG Zeng-qian, WANG Kun, ZHAO Tao, JIANG Wei, MENG Li-min. Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster [J]. Computer Science, 2021, 48(6): 261-267.
[5] WANG Jin-heng, SHAN Zhi-long, TAN Han-song, WANG Yu-lin. Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network [J]. Computer Science, 2021, 48(6): 338-342.
[6] ZUO Jian-kai, WU Jie-hong, CHEN Jia-tong, LIU Ze-yuan, LI Zhong-zhi. Study on Heterogeneous UAV Formation Defense and Evaluation Strategy [J]. Computer Science, 2021, 48(2): 55-63.
[7] YAO Ze-wei, LIU Jia-wen, HU Jun-qin, CHEN Xing. PSO-GA Based Approach to Multi-edge Load Balancing [J]. Computer Science, 2021, 48(11A): 456-463.
[8] GAO Shuai, XIA Liang-bin, SHENG Liang, DU Hong-liang, YUAN Yuan, HAN He-tong. Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm [J]. Computer Science, 2021, 48(11A): 166-169.
[9] GAO Ji-xu, WANG Jun. Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm [J]. Computer Science, 2021, 48(1): 72-80.
[10] JI Shun-hui, ZHANG Peng-cheng. Test Case Generation Approach for Data Flow Based on Dominance Relations [J]. Computer Science, 2020, 47(9): 40-46.
[11] DONG Ming-gang, HUANG Yu-yang, JING Chao. K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection [J]. Computer Science, 2020, 47(8): 178-184.
[12] LIANG Zheng-you, HE Jing-lin, SUN Yu. Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition [J]. Computer Science, 2020, 47(8): 227-232.
[13] YANG De-cheng, LI Feng-qi, WANG Yi, WANG Sheng-fa, YIN Hui-shu. Intelligent 3D Printing Path Planning Algorithm [J]. Computer Science, 2020, 47(8): 267-271.
[14] BAO Zhen-shan, GUO Jun-nan, XIE Yuan and ZHANG Wen-bo. Model for Stock Price Trend Prediction Based on LSTM and GA [J]. Computer Science, 2020, 47(6A): 467-473.
[15] MA Chuang, LV Xiao-fei and LIANG yan-ming. Agricultural Product Quality Classification Based on GA-SVM [J]. Computer Science, 2020, 47(6A): 517-520.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!