高级检索

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

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: A mathematical model was established for the simultaneous pickup and delivery vehicle routing problem, to minimize the sum of vehicle carbon emission costs and total delivery distance. This model considered the differences in customer demand for commodities and vehicle heterogeneity, describing 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. One adaptive perturbation operation was incorporated in the global search perturbation phase 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 are used to explore higher-quality neighborhood solution spaces. Finally, test case simulation experiments are conducted using GA, VNS, and ALNS algorithms to verify the effectiveness of EVNS in solving MCHGVRPSPD. The results show that, compared to the three algorithms, EVNS improves solution quality by 15% to 25%, and performs better in terms of convergence and stability, proving to be an effective algorithm for solving MCHGVRPSPD.

     

/

返回文章
返回