货物配装和车辆路径问题的一种联合求解方法

货物配装和车辆路径问题(VRP)都是NP难问题,启发式算法是求解此类问题的常用方法。求解单配送中心多车型的货物配送问题,需要改进传统遗传算法:首先采用双层结构表示染色体,车辆数无需事先确定;然后对随机产生的客户序列,利用三叉树算法进行货物配装确定每辆车的配装方案,从而可以知道每个客户的货物装车顺序;依据先装后卸的原则,可得每辆车的客户装车顺序的逆序便是每辆车的客户配送顺序;最终得到货物配装方案和配送方案。基于此思想,通过Java编程验证了一个实例,证明算法切实可行,对实际作业有一定借鉴作用。

A Method to Solve Cargo Loading Problem and VRP

Both cargo loading problem and VRP are NP-Hard problems,heuristic algorithm is a common way to solve such problems.To solve a cargo distribution problem with multi-type vehicle and one logistics center,this paper improved the traditional genetic algorithm.First,it used two arrays to represent the chromosome,so there is no need to figure out the needing amount of vehicles at the beginning.Then it introduced a heuristic algorithm named three-tree algorithm to find a cargo loading plan.Accord to the plan,we will know the destitution order of clients.The paper gives an example and lists the calculation process,a distribution plan and each vehicle’s cargo loading plan is the solution,which shows that the method is very practical.