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

doi:10.3778/j.issn.1002-8331.2108-0017

Abstract

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）

摘要：

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

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

MA Yanfang, LI Baoyu, YANG Yifu, FENG Cuiying. Two-Echelon Capacitated Vehicle Routing Model and Algorithm for Fresh Products Distribution with Customer Classification[J]. Computer Engineering and Applications, 2021, 57(20): 287-298.

马艳芳，李保玉，杨屹夫，冯翠英. 客户分类下生鲜配送两级路径问题与算法研究[J]. 计算机工程与应用, 2021, 57(20): 287-298.

References

[1] 马艳芳，应斌，周晓阳，等.基于冲突合作关系的生鲜选址-路径多主体优化模型与算法[J].系统工程理论与实践，2020，40（12）：3194-3209.
MA Y F，YING B，ZHOU X Y，et al.Multi-agent optimization model and algorithm for perishable food location-routing problem with conflict and coordination[J].Systems Engineering-Theory & Practice，2020，40（12）：3194-3209.
[2] 冯杰，史立.生鲜产品的纯电动冷藏车配送路径问题研究[J].计算机工程与应用，2019，55（9）：237-242.
FENG J，SHI L.Research on vehicle routing problem of fresh products with pure electric refrigerator truck[J].Computer Engineering and Applications，2019，55（9）：237-242.
[3] 李军涛，刘明月，刘朋飞.生鲜农产品多车型冷链物流车辆路径优化[J].中国农业大学学报，2021，26（7）：115-123.
LI J T，LIU M Y，LIU P F.Route optimization of multi-vehicle cold chain logistics for fresh agricultural pro-
ducts[J].Journal of China Agricultural University，2021，26（7）：115-123.
[4] CHEN L，LIU Y，LANGEVIN A.A multi-compartment vehicle routing problem in cold-chain distribution[J].Computers and Operations Research，2019，111：58-66.
[5] YAO B，CHEN C，SONG X，et al.Fresh seafood delivery routing problem using an improved ant colony optimization[J].Annals of Operations Research，2019，273（1/2）：163-186.
[6] LIANG Y J，LIU F，LIM A，et al.An integrated route，temperature and humidity planning problem for the distribution of perishable products[J].Computers & Industrial Engineering，2020，147：1-22.
[7] HSIAO Y H，CHEN M C，CHIN C L.Distribution planning for perishable foods in cold chains with quality concerns：formulation and solution procedure[J].Trends in Food Science & Technology，2017，61：80-93.
[8] 杜琛，李怡靖.基于客户满意度和最小损耗的冷链配送路径问题研究[J].工业工程与管理，2020，25（6）：163-171.
DU C，LI Y J.Research on cold chain distribution routing problem based on customer satisfaction and minimum loss[J].Industrial Engineering and Management，2020，25（6）：163-171.
[9] 张惠珍，刘云，倪静.基于客户满意度的MOVRPFTW的单亲遗传混合蚁群算法[J].系统管理学报，2019，28（5）：927-933.
ZHANG H Z，LIU Y，NI J.A partheno-genetic hybrid ant colony algorithm for solving the MOVRPFTW based on customer satisfaction[J].Journal of Systems & Management，2019，28（5）：927-933.
[10] 夏扬坤，邓永东，庞燕，等.带客户分级和需求可拆分的生鲜车辆路径问题[J].计算机集成制造系统，2021，27（4）：1238-1248.
XIA Y K，DENG Y D，PANG Y，et al.Fresh food vehicle routing problem with split deliveries and customer classification[J].Computer Integrated Manufacturing Systems，2021，27（4）：1238-1248.
[11] 任腾，陈玥，向迎春，等.考虑客户满意度的低碳冷链车辆路径优化[J].计算机集成制造系统，2020，26（4）：1108-1117.
REN T，CHEN Y，XIANG Y C，et al.Optimization of low-carbon cold chain vehicle path considering customer satisfaction[J].Computer Integrated Manufacturing Systems，2020，26（4）：1108-1117.
[12] 户佐安，贾叶子，李博威，等.考虑客户满意度的车辆路径优化研究[J].工业工程，2019，22（1）：100-107.
HU Z A，JIA Y Z，LI B W，et al.An optimization of the vehicle routing problem based on customer satisfaction[J].Industrial Engineering Journal，2019，22（1）：100-107.
[13] CHEN H K，HSUEH C F，CHANG M S.Production sche-
duling and vehicle routing with time windows for perishable food products[J].Computers & Operations Research，2009，36（7）：2311-2319.
[14] 郑树泉，王倩，武智霞，等.工业智能技术与应用[M].上海：上海科学技术出版社，2019：250-251.
ZHENG S Q，WANG Q，WU Z X，et al.Industrial intelligence technology and application[M].Shanghai：Shanghai Science and Technology Press，2019：250-251.
[15] KIRKPATRICK S，GELATT C D，VECCHI M P.Optimization by simulated annealing[J].Science，1983，220（4598）：671-680.
[16] 刘兰芬，杨信丰.基于混合遗传算法的有效路径求解[J].计算机工程与应用，2019，55（11）：244-249.
LIU L F，YANG X F.Searching algorithm for efficient paths based on hybrid genetic algorithm[J].Computer Engineering and Applications，2019，55（11）：244-249.
[17] 马艳芳，应斌，康凯，等.模糊需求下绿色同时取送货问题与算法研究[J].计算机工程与应用，2020，56（16）：248-257.
MA Y F，YING B，KANG K，et al.Algorithms for green simultaneous pickup and delivery problem with fuzzy demand[J].Computer Engineering and Applications，2020，56（16）：248-257.
[18] PERBOLI G，TADEI R，VIGO D.The two-echelon capacitated vehicle routing problem：models and math-based heuristics[J].Transportation Science，2011，45（3）：364-380.
[19] HEMMELMAYR V C，CORDEAU J F，CRAINIC T G.An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics[J].Computers & Operations Research，2012，39（12）：3215-3228.
[20] ZENG Z Y，XU W S，XU Z Y，et al.A hybrid GRASP+VND heuristic for the two-echelon vehicle routing problem arising in city logistics[J].Mathematical Problems in Engineering，2014，2014（1）：1-11.
[21] 许维胜，曾正洋，徐志宇.一种求解两级车辆路径问题的Memetic算法[J].控制与决策，2013，28（10）：1587-1590.
XU W S，ZENG Z Y，XU Z Y.A memetic algorithm for solving two-echelon vehicle routing problem[J].Control and Decision，2013，28（10）：1587-1590.
[22] BREUNIG U，SCHMID V，HARTL R F，et al.A large neighbourhood based heuristic for two-echelon routing problems[J].Computers & Operations Research，2016，76：208-225.
[23] 胡乔宇，杨琨，刘冉.考虑随机客户需求的两级车辆路径问题研究[J].工业工程与管理，2018，23（5）：74-81.
HU Q Y，YANG K，LIU R.Vehicle routing problem with stochastic demands in two-echelon logistics[J].Industrial Engineering and Management，2018，23（5）：74-81.