国家重点研发计划(No. 2018YFB1201402); 一汽物流有限公司项目（YQWLJS201907161）
Beijing Jiaotong University
National Key Research and Development Program of China ((No. 2018YFB1201402)；Project of FAW Logistics Co., Ltd（YQWLJS201907161）
整车物流中双层轿运车运输问题属于一类需要考虑乘用车装载(vehicle filling problem,VFP)及轿运车路径规划(vehicle routing problem,VRP)的组合优化问题,称此类问题为VFRP(vehicle filling and routing problem).由于VFP和VRP的问题复杂性均为NPC,且VFRP等组合优化问题模型的目标函数及约束往往具有非凸结构,使得该类问题的线性化处理,精确算法的设计及求解效率的提升一直是该领域的研究难点.本文以轿运车使用成本最低为目标,构建了双层轿运车的VFRP模型,在此基础上提出两种线性化方法并设计了改进分支定价算法(branch-and-price algorithm)以求解:以同时表示装载方案及走行路径的相关系数作为模型系数设计限制主问题,以限制主问题的影子价格作为子问题目标函数系数,构造生成新的装载方案及走行路径的相关系数的子问题,将子问题解作为新系数加入限制主问题,进行列生成(column generation)算法的迭代;使用分支定价算法获得整数解,并在此基础上提出结合最为分数策略(most-infeasible-branching strategy)和强分支策略(strong-branching strategy)的分支策略,以及在分支过程中降低可行域维度的降维方法以加速收敛.最后,结合实际数据设计多组算例,并与智能算法比较,验证了本文模型与算法的有效性.
The double stack car carriers transportation problem of vehicle logistics belongs to a kind of combinatorial optimization problem that needs to consider the vehicle filling problem (VFP) and vehicle routing problem (VRP), this kind of problem is called VFRP (vehicle filling and routing problem). Because the problem complexity of VFP and VRP is NPC, and the objective functions and constraints of models of VFRP and other combinatorial optimization problems often have nonconvex structure, the design of accurate algorithm and the improvement of solution efficiency are always the difficulties in this field. In this paper, a VFRP model of double stack car carriers transportation was constructed, which aimed at the lowest cost of car carriers transportation. On this basis, two linearization methods were proposed, and an improved branch-and-price algorithm was designed to solve the problem: the restricted master problem was designed that took the correlation coefficients which represented the vehicle filling and route planning of car carriers as coefficients, taking the shadow price of the restricted master problem as the objective function coefficients and constructed the subproblem to generate the correlation coefficients which represented the vehicle filling and route planning of car carriers, the solution of the subproblem was added to the restricted master problem as new coefficients to iterate the column generation algorithm; the branch-and-price algorithm was used to obtain the integer solution, in which the branch strategy that combined the most-infeasible-branching strategy and the strong-branching strategy and the dimension reduction method to reduce the feasible region’s dimension was used to accelerate convergence. Finally, examples with actual data were designed, and the algorithm was compared with intelligent algorithms, from which the effectiveness of the model and the algorithm in this paper were verified.