快递公司协同车辆路径问题的优化

Optimization of Collaborative Vehicle Routing Problem for Express Company

针对快递公司运作模式的特点,建立了基于硬时间窗、车辆载重、行驶里程、多种车型等约束条件的多车场协同车辆路径问题的数学模型,应用基于精英选择、混沌变异及模拟退火机制的混合遗传算法求解。首先应用扫描算法对客户分组,然后应用混合遗传算法求解,最后采用3-opt进行局部寻优。将该算法应用到1个随机产生的实例和3个benchmark算例上,通过总成本、总行驶距离、每辆车的行驶距离和利用率、运行时间及收敛速度来分析模型和算法,结果表明提出的模型优于一般情况下的多车场车辆路径问题模型,能大大节约成本,而且提出的算法优于遗传算法。

Aiming at the operation mode feature of express company,we establish the multi-depot collaborative vehicle routing problem（ MDCVRP） mathematical model based on hard time windows,vehicle load,mileage constraints,various vehicles etc. Hybrid genetic algorithm（ HGA） based on elite selection,chaotic mutation and simulated annealing mechanism is constructed to solve the model. Scanning algorithm is applied to group customers,while HGA is used to search the optimal solution,for local optimization by 3-opt. A random instance and 3 benchmark instances are tested. By way of the total cost,total distance,vehicles＇ mileage and utilization rate,computation time and convergence speed,analyzing models and algorithms show that the proposed model is superior to general multiple vehicle routing problems（ MVRP）,which can save a great amount of cost and is better than genetic algorithm.