基于社会化库存的多回程物流配送问题的拉格朗日松弛算法

Improved Lagrangian relaxation algorithm based on socialized inventory for multi-trip distribution problem

社会化库存是同城配送快速发展所呈现出的一种新特征。在社会化库存模式下,顾客可从多个同城商店订购货物,其物流配送服务需要通过配送车辆在商店与顾客间的多次往返而实现,这是一类特殊的多回程混合取送物流配送问题。针对该问题,建立了混合整数规划模型及改进的拉格朗日松弛算法;考虑到传统拉格朗日松弛算法存在无法有效提供上界的缺陷,引入了基于次短路的可行解生成思想,实现了问题上界的有效求解。仿真算例表明,所提算法能够取得优于CPLEX求解器的计算效率。

Socialized inventory is a new feature of the rapid development of city distribution.Under the mode of socialized inventory,customers can order goods from multiple stores in the same city,and their logistics distribution service needs to be realized through multiple rounds of vehicles between stores and customers.This is a special kind of multi-return mixed pick-up and delivery logistics distribution problem.Aiming at this problem,a mixed integer programming model and an improved Lagrangian relaxation algorithm were established.Considering that the traditional Lagrangian relaxation algorithm could not provide the upper bound effectively,the idea of generating feasible solutions based on sub-short circuit was introduced to realize the effective solution of the problem bound.The simulation results showed that the proposed algorithm could achieve the better computational efficiency than CPLEX solver.