带时间窗的汽车总装线物料配送路径规划

工业工程 ›› 2012, Vol. 15 ›› Issue (2): 94-99.

带时间窗的汽车总装线物料配送路径规划

华中科技大学机械学院，湖北武汉 430074

出版日期:2012-04-30 发布日期:2012-05-17
作者简介:王楠（1982-），女，内蒙古自治区人，博士研究生，主要研究方向为生产线仿真与优化、生产物流管理等.
基金资助:
总装预研基金资助项目（9140A04050707JW0507）；通用汽车公司研究基金资助项目（ND22244001 RD 07.245）

Vehicle Routing with Time Windows in Material Delivery for Automobile General Assembly Line

School of Mechanical Science & Engineering, Huazhong University of Science & Technology, Wuhan 430074,China

Online:2012-04-30 Published:2012-05-17

摘要/Abstract

摘要： 分析了现阶段汽车总装线物料配送中存在的问题，建立了适用于汽车总装线物料配送路径规划的混合时间窗模型，提出了解决带时间窗的汽车总装线物料配送路径优化问题的改进遗传算法，使用了一种新的染色体编码方式和与之对应的交叉算子。针对传统轮盘赌随机操作选择误差比较大的弊端，提出改进的轮盘赌选择算子，加大随机数的产生次数并加入排序选择的思想，融合了最佳个体保存选择策略，提高算子的选优性能。实验表明该算法用于求解带时间窗的汽车总装线物料配送路径问题的有效性。

关键词: 汽车总装线, 物料配送路径规划, 遗传算法

Abstract: The status of material delivery for an existing automobile general assembly line is analyzed. Because the materials should be delivered to the line in a given time interval, a vehicle routing problem with time windows (VRPTW) model is developed for the problem of material delivery. Then, an improved genetic algorithm (GA) is presented to solve it. By this algorithm, new chromosome coding and crossover methods are proposed. Also, to overcome the disadvantage of the traditional roulette selection, a new roulette selection method is proposed to increase the number of random number generated. It also keeps the strategy to select the best individuals. The experimental results validate the proposed method.

Key words: automobile general assembly line, vehicle routing problem (VRP) for material delivery, genetic algorithm (GA)

王楠，李世其，王峻峰. 带时间窗的汽车总装线物料配送路径规划[J]. 工业工程, 2012, 15(2): 94-99.

Wang Nan，Li Shiqi，Wang Junfeng. Vehicle Routing with Time Windows in Material Delivery for Automobile General Assembly Line[J]. Industrial Engineering Journal , 2012, 15(2): 94-99.

参考文献

［1］RECKIEK B, PIERRE D L. Designing mixed-product assembly lines ［J］.IEEE Transactions and Automation, 2000,16(3):268-280. ［2］CHOI W,LEE Y.A dynamic part feeding system for an automotive assembly line［J］.Computer & Industrial Engineering,2002,43(1-2):123-134. ［3］汪群,韩翔,肖煌.企业商务电子化物流管理［M］.北京:科学出版社,2004:174-190. ［4］HUANG G Q，ZHANG Y F，JIANG P Y.RFID based wireless manufacturing for walking worker assembly islands with fixed position layouts ［J］.Robotics and Computer Integrated Manufacturing 2007,23(4):469 -477. ［5］Dantzig G,Ramser J.The truck dispatching problem［J］.Management Science,1959(6):80 -91. ［6］李军，郭耀煌.物流配送车辆优化调度理论与方法［M］.北京：中国物资出版社,2001. ［7］Holland J H.Adaptation in natural and artificial systems ［M］.MI: University of Michigan Press, Ann Arbor, 1975.［8］Tong Z,Li N,Sun D B.Genetic algorithm for vehicle routing problem with time window with uncertain vehicle number［C］.The 5th World Congress on Intelligent control and automation,Hangzhou,2004(4):2846-2849. ［9］Jeon G, R Leep H, Shim J Y.A vehicle routing problem solved by using a hybrid genetic algorithm［J］.Computers&Industrial Engineering,2007,53(4):680 -692. ［10］Jung S.A genetic algorithm for vehicle routing problem with time dependent travel times［D］. New York:University of Maryland,2000. ［11］郭耀煌，李军．车辆优化调度问题的研究现状评述［J］．西南交通大学学报,1995,30(8):36-41.Guo Yaohuang,Li Jun.Review of the State of the Art on Vehicle Scheduling Problem［J］.Journal of Southwest Jiaotong University,1995,30(8):36 -41. ［12］张涛，王梦光.遗传算法和3 opt结合求解带有能力约束的VRP［J］.东北大学学报：自然科学版,1999,20(2):254-256. Zhang Tao,Wang Mengguang. Solving the VRP by a Hybrid Algorithm of Genetic Algorithm and 3 opt Algorithm［J］.Journal of Northeastern University: Natural Science,1999,20(2):254-256. ［13］谢秉磊．随机车辆路径问题研究［D］.成都：西南交通大学,2003.Xie Binglei.Research on Stochastic Vehicle Routing Problems［D］.Chengdou:SWJTU,2003. ［14］Fumero F, Vercellis C.Synchronized development of production,inventory,and distribution schedules［J］. Transpotation Science,1999,33(3):330-340. ［15］Tarantilis C D, Zachariadis E E, Kiranoudis C T. A hybrid guided local search for the vehicle routing problem with intermediate replenishment facilities［J］. INFORMS Journal of Computing, 2008,20(1):154-168.

[1]	张正敏, 管在林, 岳磊. 基于Lévy Flight的混合GA在柔性作业车间调度问题中的性能分析[J]. 工业工程, 2021, 24(4): 83-92.
[2]	王晓军, 王博, 晋民杰, 杨春霞, 白新利. 改进多种群遗传算法的AutoStore系统多AGV调度优化[J]. 工业工程, 2021, 24(4): 112-118,167.
[3]	王莹莹, 吴立云. 基于改进NSGA-II的多项目多技能人力资源调度研究[J]. 工业工程, 2021, 24(3): 130-138.
[4]	曾创锋, 刘建军, 陈庆新, 毛宁. 求解一类无关并行机调度的遗传迭代贪心算法[J]. 工业工程, 2021, 24(2): 110-118.
[5]	黄露, 纪延光. 考虑顾客延误损失的配送中心选址双层规划问题研究[J]. 工业工程, 2021, 24(2): 141-147.
[6]	王冰怡, 张锦. 考虑网点共享与变更的多级快递网点选址问题[J]. 工业工程, 2021, 24(2): 155-165.
[7]	马跃如, 文铮, 易丹. 考虑老年人满意度的多目标居家养老护理员路径优化[J]. 工业工程, 2021, 24(1): 74-81,103.
[8]	王玖河, 高辉, 刘欢. 基于遗传算法的共享助力车调度问题研究[J]. 工业工程, 2021, 24(1): 90-96.
[9]	吴斌, 宋琰, 程晶, 董敏. 基于密度峰值聚类的VRPTW问题研究[J]. 工业工程, 2020, 23(5): 58-66,74.
[10]	王苏林, 邱菲尔, 陈凡, 刘川昆, 鹿腾, 王芷芸. 基于贪心遗传的地下物流节点选择规划研究[J]. 工业工程, 2020, 23(5): 88-95.
[11]	侯艳, 黄康焕, 张亿仙, 伍乃骐. 原油一次加工过程的多目标调度优化[J]. 工业工程, 2020, 23(4): 131-139.
[12]	王泽, 杨信丰, 刘兰芬. 考虑电量消耗的车辆调度优化研究[J]. 工业工程, 2020, 23(4): 140-147.
[13]	曾垂飞, 刘建军, 陈庆新, 毛宁. 装配作业车间分批调度问题的算法对比[J]. 工业工程, 2020, 23(4): 174-182.
[14]	张巍, 李鹏翔, 仝自强, 岳毅蒙. 基于损坏车辆分布预测与损益阈值分析下的共享单车回收研究[J]. 工业工程, 2020, 23(3): 132-137.
[15]	张国辉, 胡一凡, 孙靖贺. 改进遗传算法求解多时间约束的柔性作业车间调度问题[J]. 工业工程, 2020, 23(2): 19-25,48.