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.