考虑动态平衡装卸的点对点取送货车辆路径优化

Optimization on point-to-point pickup and delivery vehicle routing withdynamic balanced loading and unloading constraints

针对点对点取送货车辆路径优化问题,引入动态平衡、后进先出、三维装载等约束,以总路径最短为优化目标,构建多车多客户应用场景下的动态平衡装卸点对点取送货车辆路径优化模型;基于研究问题的特征,采用启发式插入法确定路径初始方案,设计节点交换和重新定位算子,构造路径邻域方案,并将动态平衡装卸纳入路径迭代过程,运用多重指标定序策略和三分空间策略,设计客户动态平衡装卸检算算法,并提出基于禁忌搜索的点对点取送货车辆路径优化算法,制订多车多客户取送货车辆路径方案的同时编制动态平衡装载方案。最后,通过标准算例验证方法的有效性,计算表明:所提方法能高效解决带动态平衡约束的点对点取送货车辆路径优化问题;在多车多客户应用场景下具有更强的寻优能力,求解效率更高。

According to optimization problem of point to point pickup and delivery vehicle routing,this paper introduced the dynamic balanced,last-in-first-out and three-dimensional loading constraints.Taking the minimum of total path length as the optimization objective,this paper established the point to point pickup and delivery vehicle routing problem optimization model with three-dimensional and dynamic balanced loading constraints(3BL-PDVRP)under the application scenario of multi-vehicle and multi-customer(ASMM).Considering the characteristics of research question,this paper used the heuristic insertion method to generate initial path plan.Then it constructed the node-switching and repositioning operators to optimize the path neighborhood structure,while incorporated the dynamic balanced loading into the path iteration process.Based on the multi-index sequencing strategy and three-space strategy,this paper designed the dynamic balanced loading and unloading checking algorithm of multi-customer.Furthermore,it proposed the point-to-point pickup and delivery routing optimization algorithm based on taboo search to make the pickup and delivery vehicle routing and dynamic balanced loading layout scheme under the ASMM at the same time.Finally,the calculation results of the standard example show that the proposed method can effectively solve the 3BL-PDVRP and have stronger optimization ability and higher solving efficiency under the ASMM.