摘要
整车物流中双层轿运车运输问题属于一类需要考虑乘用车装载(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)的分支策略,以及在分支过程中降低可行域维度的降维方法以加速收敛.最后,结合实际数据设计多组算例,验证了所提出模型与算法的有效性.
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),which is called vehicle filling and routing problem(VFRP). Because the complexity of the VFP and VRP is NPC(nondeterministic polynomial complete problem), and the objective functions and constraints of models of the VFRP and other combinatorial optimization problems often have nonconvex structure, the linearization, the design of accurate algorithms and the improvement of solution efficiency are always the difficulties in this field. Therefore, a VFRP model of double stack car carriers transportation is constructed, aiming at the lowest cost of car carriers transportation. On this basis, two linearization methods are proposed, and an improved branch-and-price algorithm is designed to solve the problem: on the basis of branch-and-price algorithm, a branch strategy of combining the most-infeasible-branching strategy and the strong-branching strategy, and a dimension reduction method of reducing the feasible region’s dimension, are proposed to accelerate convergence. Finally, examples with actual data are designed, which verify the effectiveness of the model and the algorithm.
作者
迟居尚
何世伟
宋子龙
薛守强
冯骁
CHI Ju-shang;HE Shi-wed;SONG Zi-long;XUE Shou-qiang;FENG Xiao(Key Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport Beijing Jiaotong University,Beijing 100044,China)
出处
《控制与决策》
EI
CSCD
北大核心
2022年第1期185-195,共11页
Control and Decision
基金
国家重点研发计划项目(2018YFB1201402)
国家自然科学基金面上项目(62076023)
一汽物流有限公司项目(YQWLJS201907161)。
关键词
公路运输
整车物流
双层轿运车运输
模型线性化
列生成算法
分支定价算法
highway transportation
vehicle logistics
double stack car carriers transportation
model linearization
column generation algorithm
branch-and-price algorithm