周蓉;沈维蕾
出版日期:
2018-11-25
发布日期:
2018-11-27
基金资助:
ZHOU Rong;SHEN Weilei
Online:
2018-11-25
Published:
2018-11-27
摘要: 为了同时实现总配送成本最低、车辆行驶距离最短、车辆数最小等目标,综合考虑车辆指派成本及运输路径成本,建立了装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性,提出了一种自适应并行遗传算法。算法以C-W节约法为基础,设计了三种基于双重需求的启发式种群初始化方法,缩小搜索空间并优化初始解;引入多样性种群和高质量种群的双种群并行策略,实现深度与广度的同步搜索;设计自适应交叉变异操作,改善高质量种群个体搜索停滞,并针对全局最优个体采用特殊变异的后优化操作以进一步提高全局优化性能。采用标准数据集作为算例进行寻优测试,验证了所提算法的可行性和有效性。
中图分类号:
周蓉, 沈维蕾. [供应链调度]装卸一体化车辆路径问题的自适应并行遗传算法[J]. 中国机械工程.
ZHOU Rong, SHEN Weilei. An Adaptive Parallel Genetic Algorithm for VRPSPD[J]. China Mechanical Engineering.
[1]THIERRY M,SALOMON M,VAN N J,et al.Strategic Issues in Product Recovery Management [J].Califonia Management Review,1995,37(2):114-135. [2]郎茂祥.物流配送车辆调度问题的模型和算法研究[D].北京:北方交通大学,2002. LANG Maoxiang.Study on Model and Algorithms of Logistics Distribution Vehicle Scheduling Problem [D].Beijing:Beijing Jiaotong University,2002. [3]王科峰,叶春明,唐国春.节点具有双重需求的车辆路径问题及其性质[J].系统科学与数学,2011,31(10):1185-1196. WANG Kefeng,YE Chunming,TANG Guochun.The Vehicle Routing Problem and Its Property with Nodes Having Double Demands [J].Journal of System Science and Mathematical,2011,31(10):1185-1196. [4]TASAN A S,GEN M.A Genetic Algorithm Based Approach to Vehicle Routing Problem with Simultaneous Pick-up and Deliveries [J].Computers and Industrial Engineering,2012,62(3):755-761. [5]NAGY G,SALHI S.Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Deliveries [J].European Journal of Operational Research,2005,162 (1):126-141. [6]柳毅,余福茂,俞武扬.同时取送货车辆路径问题的改进人工鱼群算法[J].杭州电子科技大学学报,2014,34(3):34-37. LIU Yi,YU Fumao,YU Wuyang.The Improved AFSA Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pickup [J].Journal of Hangzhou Dianzi University,2014,34(3):34-37. [7]彭春林,梁春华,周泓.求解同时取货和送货车辆路径问题的改进遗传算法[J].系统仿真学报,2008,20(9):2266-2270. PENG Chunlin,LIANG Chunhua,ZHOU Hong.Improved Genetic Algorithm for Vehicle Routing Problem with Simultaneous Pickups and Deliveries [J].Journal of System Simulation,2008,20(9):2266-2270. [8]龙磊,陈秋双,华彦宁,等.具有同时集送货需求的车辆路径问题的粗粒度并行遗传算法[J].系统仿真学报,2009,21(7):1962-1968. LONG Lei,CHEN Qiushuang,HUA Yanning,et al.Coarse-grained Parallel Genetic Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pick-up[J].Journal of System Simulation,2009,21(7):1962-1968. [9]TANG F A,GALVO R D.A Tabu Search Algorithm for the Vehicle Routing Problems with Simultaneous Pickup and Delivery Service [J].Computers and Operations Research,2006,33(3):595-619. [10]WASSAN N A,WASSAN A H,NAGY G.A Reactive Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pickups and Deliveries [J].Journal of Combinatorial Optimization,2008,15(4):368-386. [11]WANG H F,CHEN Y Y.A Genetic Algorithm for the Simultaneous Delivery and Pickup Problems with Time Window [J].Computers and Industrial Engineering,2012,62 (1):84-95. [12]POTVIN J,DUHAMEL C,GUERTIN F.A Genetic Algorithm for Vehicle Routing with Backhauling [J].Applied Intelligence,1996,6(4):345-355. [13]PRINS C.A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem [J].Computers and Operations Research,2004,31(12):1985-2002. [14]DUHAMEL C,LACOMME P,PRODHON C.A Hybrid Evolutionary Local Search with Depth First Search Split Procedure for the Heterogeneous Vehicle Routing Problems [J].Engineering Applications of Artificial of Intelligence,2012,25(2):345-358. [15]CLARKE G,WRIGHT J W.Scheduling of Vehicles from a Central Depot to a Number of Delivery Points [J].Operations Research,1964,12(4):568-581. [16]MESTER D,BRAYSY O,DULLAERT W.A Multi-parametric Evolution Strategies Algorithm for Vehicle Routing Problems [J].Expert Systems with Applications,2007,32(2):508-517. [17]OSMAN I.Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problems [J].Annals of Operations Research,1993,41(4):421-451. [18]STARKWEATHER T,MCDANIEL S,WHITLEY C,et al.A Comparison of Genetic Sequencing Operators [C]//Proceedings of the Fourth International Conference on Genetic Algorithms.San Diego,1991:69-76. [19]PAN Q K,TASGETIREN M F,LIANG Y C.A Discrete Particle Swarm Optimization Algorithm for the No-wait Flowshop Scheduling Problem [J].Computers and Operations Research,2008,35(9):2807-2839. [20]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社,2001. LI JUN,GUO Yaohuang.Theory and Methodology of Logistics Distribution Vehicle Optimization Scheduling[M].Beijing:China Materials Press,2001. [21]AUGERAT P,BELENGUER J M,BENAVENT E,et al.Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem [R].Grenoble:ARTEMIS-IMAG,1998:1-24. |
[1] | 翁剑, 庄可佳, 浦栋麟, 丁汉, . 基于机器学习和多目标算法的钛合金插铣优化[J]. 中国机械工程, 2021, 32(07): 771-777. |
[2] | 裴植, 戴旭, 袁依轮, 易文超, 陈勇. 应急装备制造网络的动态资源配置[J]. 中国机械工程, 2021, 32(07): 839-848. |
[3] | 郭保苏;庄集超;章钦;吴凤和. 基于多分量卷积神经网络的多晶硅晶片颜色差异检测[J]. 中国机械工程, 2021, 32(03): 297-304. |
[4] | 王英聪1;张领1;肖人彬2. 一种求解等圆Packing问题的柔性位置选择算法[J]. 中国机械工程, 2021, 32(03): 305-313. |
[5] | 田素坤1;戴宁1;袁福来1;孙玉春2;俞青3;程筱胜1. 基于条件生成对抗网络的缺失牙体功能性咬合面形态设计方法[J]. 中国机械工程, 2021, 32(03): 331-340. |
[6] | 仇永涛1;吉卫喜1,2;张朝阳1,2. 结合混合进化算法和知识的多目标车间调度[J]. 中国机械工程, 2020, 31(24): 2979-2987. |
[7] | 孙晓龙, 张志鹏, 计效园, 童家良, 管雅倩, 张焕东, 周建新. [材料成形中的数字化与智能化产品设计]法向算子和D2算子相结合的铸件三维模型分类算法[J]. 中国机械工程, 2020, 31(22): 2655-2662. |
[8] | 李锋1;程阳洋1,2;陈勇1;汤宝平3. 用于旋转机械状态趋势预测的量子注意力循环编码解码神经网络[J]. 中国机械工程, 2020, 31(21): 2573-2582. |
[9] | 孙殿柱1;沈江华1;贾宗福1;李延瑞2;林伟1. 散乱点云局部形貌标架量化及特征识别方法[J]. 中国机械工程, 2020, 31(19): 2332-2339. |
[10] | 王冠1;张骞2;寇琳媛1;刘志文3;李世康3. 基于混合元胞自动机算法的连续体结构非线性拓扑优化[J]. 中国机械工程, 2020, 31(18): 2161-2173. |
[11] | 戴稳1;张超勇1;孟磊磊1;薛燕社1;肖鹏飞1;尹勇2. 采用深度学习的铣刀磨损状态预测模型[J]. 中国机械工程, 2020, 31(17): 2071-2078. |
[12] | 岳彩旭;刘鑫;刘智博;谢娜;王彦武. 基于有限元仿真的拼接模具铣削用刀具优化[J]. 中国机械工程, 2020, 31(17): 2085-2094. |
[13] | 庞世宝1;郭顺生1;王磊1;李西兴2. 面向大规模个性化制造的车间制造服务协作链构建方法[J]. 中国机械工程, 2020, 31(17): 2104-2111. |
[14] | 张文旭, 肖人彬, 林文广. 基于产品性能词典的评论数据驱动客户需求模型研究[J]. 中国机械工程, 2020, 31(15): 1866-1876. |
[15] | 王发麟, 郭学鹏, 李志农, 宋利康. 坐标系导引下的线缆布线点位对应关系自动提取方法[J]. 中国机械工程, 2020, 31(14): 1708-1716. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||