李国明，李军华

(南昌航空大学 江西省图像处理与模式识别重点实验室，江西 南昌 330063)

0 引言

物流配送线路规划问题(logistics distribution route planning problem)是目前大型物流配送管理中的核心问题之一，通常归结为车辆路径问题(Vehicle Routing Problem, VRP)。该问题指配送中心根据客户需求安排车辆对货物进行派发，车辆从配送中心出发，到达指定地点，最后回到配送中心，其中需要考虑车辆的时间约束、容量约束等约束条件。因为研究VRP能有效处理运输过程中订单分配不合理、运输延误率高等情况，所以该问题自提出以来就受到国内外众多学者的广泛关注，并提出基于VRP的精确算法[1-3]和基于VRP的启发式算法[4-7]。VRP主要有3个不同的研究角度：

(1)带时间窗的车辆路径问题

在实际配送中，客户会对货物送达时间区间提出严格要求。针对此类问题，XU等[8]提出混合遗传算法和粒子群优化(Particle Swarm Optimization, PSO)算法，利用粒子实数编码方法对路径进行解码来减轻计算负担，同时与遗传算法的交叉算子相结合，避免陷入局部最优。NIU等[9]提出基于膜计算(membrane computing)的混合进化算法，将遗传算法中常用的二进制编码改进为整数编码，既可避免编码冗余问题，又可提高算法的实用性和计算效率。该方法在单次配送VRP中效果较好，但未考虑多个配送中心同时配送的情景。戚远航等[10]提出一种离散蝙蝠算法(Discrete Bat Algorithm,DBA)，利用DBA寻优能力强、鲁棒性好等特性来解决带时间窗的VRP，然而该算法未考虑客户需求的随机性。

(2)随机需求车辆路径问题

在实际配送中，若设定客户需求为随机变量，则称为随机需求车辆路径问题(Vehicle Routing Problem with Stochastic Demand,VRPSD)。……