计算机工程与应用 ›› 2021, Vol. 57 ›› Issue (20): 287-298.DOI: 10.3778/j.issn.1002-8331.2108-0017

• 工程与应用 • 上一篇    

客户分类下生鲜配送两级路径问题与算法研究

马艳芳,李保玉,杨屹夫,冯翠英   

  1. 1.河北工业大学 经济管理学院,天津 300401
    2.浙江工业大学 经贸管理学院,杭州 310014
  • 出版日期:2021-10-15 发布日期:2021-10-21

Two-Echelon Capacitated Vehicle Routing Model and Algorithm for Fresh Products Distribution with Customer Classification

MA Yanfang, LI Baoyu, YANG Yifu, FENG Cuiying   

  1. 1.School of Economics and Management, Hebei University of Technology, Tianjin 300401, China
    2.School of Economics and Trade Management, Zhejiang University of Technology, Hangzhou 310014, China
  • Online:2021-10-15 Published:2021-10-21

摘要:

生活水平的提高使得消费者对生鲜产品的需求不断增长,进而促进了冷链物流行业的快速发展。将客户按重要性分为重要客户和普通客户两类,以总配送成本最小为目标,建立考虑客户分类的两级容量有限车辆路径优化模型。提出两阶段启发式算法求解该模型:第一阶段设计改进的遗传-模拟退火算法增强全局搜索能力,其中采用轮盘赌选择机制结合精英保留策略保留优秀个体,部分匹配交叉算子结合自适应交叉率维持种群多样性,Metropolis准则以一定概率接受较差解;第二阶段使用精确方法求解一级配送路径。基于Perboli的Set2算例集和Hemmelmayr的Set5算例集,共30个基准案例,分别将所提出算法与四种现有算法进行对比分析,验证了改进算法的效果,并测试了算法的收敛性。基于模拟数据进行模型分析,验证了所提出模型和算法的有效性和适用性。

关键词: 生鲜产品, 两级车辆路径问题, 客户分类, 容量有限, 遗传-模拟退火算法

Abstract:

With the improvement of living standards, the demand of fresh products has grown steadily, which has also promoted the development of cold chain logistics. Customers are divided into two categories:important customers and ordinary customers. A Two-Echelon Capacitated Vehicle Routing Model with Customer Classification(2E-CVRP-CC) is proposed to minimize the total delivery cost. Then, a two-stage heuristic algorithm is proposed:The first stage is an improved genetic algorithm with simulated annealing, in which roulette selection mechanism combined with an elite retention strategy is applied to retain excellent individuals, partially-matched crossover operator and adaptive crossover rate are used to maintain the diversity of population, and Metropolis criterion is adopted to accept the poor solution with a certain probability; The second stage is an exact method to solve the first-echelon delivery route. Based on 30 classic benchmarks presented by Perboli Set2 and Hemmelmayr Set5, compared with four existing algorithms, the effectiveness and convergence of the algorithm are proved to be good. Finally, based on simulation data, the model is proved to be valid.

Key words: fresh products, two-echelon vehicle routing problem, customer classification, capacity constraints, Genetic Algorithm-Simulated Annealing(GA-SA)