Abstract: In order to solve the problems that the materials could not be delivered in time due to the uncertain travel time in assembly line material distributions, a vehicle routing planning method with interval uncertain travel time was proposed. The uncertain travel time was represented by interval data. By the robust optimization, the vehicle routing model for assembly lines was formulated based on a route-dependent uncertain parameter. In the model, the objective was to minimize the total travel distance of vehicles with three dimensional loading and time window constraints. A hybrid genetic algorithm was proposed to solve the model. In the algorithm, tournament selection was used to avoid the conversion of fitness values, and a discrete Levy flight was proposed to improve the algorithm search performance. The effectiveness of the proposed algorithm was verified after the comparisons of different algorithms. Finally, the routing planning problem of a gearbox assembly line material distributions was used as an example. The solutions with different degrees of uncertainty were obtained by the proposed method. And the abilities of different solutions to resist the uncertain travel time were analyzed by Monte Carlo method. 

Key words: assembly line, routing planning, interval uncertainty, robust optimization, improved genetic algorithm

摘要： 为解决装配线物料配送中车辆行驶时间不确定导致物料不能及时送达的问题，提出行驶时间区间不确定的路径规划方法。不确定行驶时间由区间数表示，采取鲁棒优化方法，引入路径相关不确定参数，以最小化车辆行驶距离为目标，考虑三维装载和时间窗约束，建立装配线路径规划模型，并设计了一种混合遗传算法求解模型。算法中，采用锦标赛选择避免适应度值转换，设计一种离散莱维飞行提高算法搜索性能，通过与不同算法对比，表明了该算法的有效性。最后以变速器装配线物料配送路径规划问题为例，通过该方法得到了不同不确定程度下的路径方案，使用蒙特卡罗方法分析了不同方案抵抗不确定行驶时间的能力。

关键词: 装配线, 路径规划, 区间不确定, 鲁棒优化, 改进遗传算法