高级检索

多商品分批次取送货的异构绿色车辆路径问题研究

Research on Multi-commodity Heterogeneous Green Vehicle Routing Problem with Split Pickup and Delivery

  • 摘要: 针对同时取送货车辆路径问题,考虑客户商品需求差异及车辆异型的因素,以最小化车辆碳排放成本及总配送距离之和为目标,建立多商品分批次取送货的异构绿色车辆路径问题 (multi-commodity heterogeneous green vehicle routing problem with split pickup and delivery,MCHGVRPSPD)的数学模型,且提出1种增强型变邻域搜索(ehanced variable neighborhood search,EVNS)算法对数学模型进行求解。在EVNS的初始阶段,采用距离–容量平衡法(distance–capacity balancing,DCB)生成初始解;在全局搜索扰动阶段,结合1种自适应扰动操作,防止算法过早收敛陷入局部最优;在局部搜索阶段,采用4种带容量约束的邻域搜索操作,以探测更优质的邻域解空间。最后,采用GA,VNS和ALNS算法进行测试案例仿真实验,验证EVNS算法求解MCHGVRPSPD的有效性。结果表明:与3种对比算法相比,EVNS算法在求解质量方面提升了15%~25%的性能,同时在收敛性和稳定性方面更优,是1种求解MCHGVRPSPD的有效算法。

     

    Abstract: Aiming at the vehicle routing problem with simultaneous pickup and delivery, considering the differences in customer commodity demands and vehicle heterogeneity, a mathematical model was established with the objective of minimizing the sum of vehicle carbon emission costs and total delivery distance. This model was used to describe the multi-commodity heterogeneous green vehicle routing problem with split pickup and delivery (MCHGVRPSPD). An enhanced variable neighborhood search (EVNS) algorithm was proposed to solve this problem. In the initial phase of EVNS, distance-capacity balancing (DCB) was designed to generate the initial solution. In the global search perturbation phase, one adaptive perturbation operation was incorporated to prevent the algorithm from prematurely converging to a local optimum. In the local search phase, four types of neighborhood search operations with capacity constraints were used to explore higher-quality neighborhood solution spaces. Finally, test case simulation experiments were conducted using GA, VNS, and ALNS algorithms to verify the effectiveness of EVNS in solving MCHGVRPSPD. The results show that compared to the three benchmark algorithms, the EVNS algorithm improves solution quality by 15% to 25%, while also demonstrating superior convergence and stability. Thus, EVNS is an effective algorithm for solving the MCHGVRPSPD.

     

/

返回文章
返回