基于分支定价算法的双层轿运车运输问题

整车物流中双层轿运车运输问题属于一类需要考虑乘用车装载(vehicle filling problem, VFP)及轿运车路径规划(vehicle routing problem, VRP)的组合优化问题,称此类问题为VFRP(vehicle filling and routing problem).由于VFP和VRP的问题复杂性均为NP完全问题(non-deterministic polynomial complete problem, NPC),且VFRP等组合优化问题模型的目标函数及约束往往具有非凸结构,使得该类问题的线性化处理、精确算法的设计及求解效率的提升一直是该领域的研究难点.对此,以轿运车使用成本最低为目标,构建双层轿运车的VFRP模型,在此基础上提出两种线性化方法并设计改进分支定价算法(branch-and-price algorithm)以求解:在分支定价算法的基础上,提出结合最为分数策略(most-infeasible-branching strategy)和强分支策略(strong-branching strategy)的分支策略,以及在分支过程中降低可行域维度的降维方法以加速收敛.最后,结合实际数据设计多组算例,验证了所提出模型与算法的有效性.

整车物流双层轿运车车辆装载与路径整合优化研究

根据启发式算法思想,建立了双层轿运车的车辆配载和路径优化的双层规划模型。在路径优化的求解中融入一定的启发式搜索规则,设计了一种求解该双层规划模型的混合遗传算法,并给出了算法的编码方法、路径搜索方法和适应度函数的定义。案例分析表明,当乘用车种数不超过3种时,采用LINGO商业优化软件能在1 min内求出最优解;超过3种时求解时间呈指数增长。采用本文设计的混合遗传算法,能在较快时间内求出最优解,此模型和算法对编制大规模下的乘用车装载和配送计划具有较强的适用性和可行性。