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

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)

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.

References

［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.