多车型集配货一体化车辆路径问题研究

Research on heterogeneous fixed fleet vehicle routing problem with pick-up and delivering

针对客户存在收货和发货双重需求的物流配送问题,讨论具有多种车型的集配货一体化车辆路径问题。在综合考虑各车型的固定成本和可变配送成本的前提下,以总成本最小为目标,以尽可能提高车辆满载率、减少出行次数为思路,构建多车型集配货一体化车辆路径优化模型。基于最小插入费用法设计初始可行解生成算法,通过引入基于概率的多算子邻域操作、最优解记忆装置、多准则终止原则对模拟退火算法进行改进,给出求解思路。设计算例并对多车型单/双向集配货模型的求解结果进行比较,以验证模型的实用性和算法的有效性。研究结果表明:使用改进后的模拟退火算法对构建的多车型集配货一体化车辆路径问题模型求解更直接简便,对多车型集配货一体化车辆路径优化后能有效降低配送成本。

Considering that heterogeneous fixed fleet vehicle routing problem with pickups and deliveries（HFFVRPPD）in logistics distribution is a widespread NP problem, which is more complex than single/multi vehicle with one way routing problem, HFFVRPPD optimization model was established to improve the load rate of vehicle, and reduce travel times. The algorithm of producing initial feasible solutions of the model was constructed, the improved simulated annealing algorithm was designed, which includes the operation of multi operators neighborhood based on the probability,embedding of memory devices, and the termination of many standard ways. The multi vehicle routing with one way problem and HFFVRPPD were compared to verify the effectiveness of the model and algorithm. The results show that the improved simulated annealing algorithm solving the HFFVRPPD is more convenient, and the HFFVRPPD optimization can effectively reduce the distribution costs.