Fresh food vehicle routing problem with split deliveries and customer classification

doi:10.13196/j.cims.2021.04.027

›› 2021, Vol. 27 ›› Issue (4): 1238-1248.DOI: 10.13196/j.cims.2021.04.027

Online:2021-04-30 Published:2021-04-30
Supported by:
Project supported by the National Social Science Foundation,China(No.15BGL083),the Research Foundation of Hunan Provincial Education Department,China(No.19B610),the Science Research Start Foundation for Bring in Talents of Central South University of Forestry and Technology,China(No.2019YJ005),the Teaching Reform Foundation of the Central South Forestry University of Science and Technology,China(No.2019-65),the Hunan Provincial Key Laboratory of Intelligent Logistics Technology,China(No.2019TP1015),the China Society of Logistics Program,China(No.2020CSLKT3-089),the Innovation and Entrepreneurship Training Program for College Students of Central South University of Forestry and Technology,China(No.2020-124),and the Campus Student Research Training Program of Central South University of Forestry and Technology,China(No.2020-175,2020-176).

带客户分级和需求可拆分的生鲜车辆路径问题

夏扬坤¹,邓永东¹,庞燕¹⁺,王忠伟¹,高亮²

1.中南林业科技大学物流与交通学院
2.华中科技大学数字制造装备与技术国家重点实验室

基金资助:
国家社会科学基金资助项目(15BGL083);湖南省教育厅优秀青年基金资助项目(19B610);中南林业科技大学引进人才科研启动基金资助项目(2019YJ005);中南林业科技大学教学改革资助项目(2019-65);智慧物流技术湖南省重点实验室资助项目(2019TP1015);中国物流学会课题资助项目(2020CSLKT3-089);中南林业科技大学大学生创新创业训练计划项目(2020-124);中南林业科技大学大学生科技创新项目(2020-175,2020-176)。

Abstract

Abstract: To promote the circulation of fresh agricultural products and reduce the cost of fresh logistics distribution,a fresh food vehicle routing problem with split deliveries and customer classification was studied based on the fresh loss of fresh agricultural products.The type of split deliveries by backpack was a new form of discrete split.It was stipulated that the fresh demand of each customer could be discretely combined by multiple backpacks.According to the importance,the customer was classified.The soft time windows and the type of split deliveries by backpack were used as constraints,and the fresh loss cost was included into the objective.A corresponding multi-objective mathematical model was constructed.To improve the optimization performance of Tabu Search Algorithm (TSA),a dynamic tabu list was designed.Some strategies of the adaptive penalty mechanism,multi-neighborhood structure and tabu list re-initialization were incorporated into the TSA.Therefore,an adaptive TSA with dynamic tabu list was designed to solve the problem.Through comparative analysis,the effectiveness of the new algorithm was verified.

Key words: vehicle routing problem, fresh logistics, tabu search, split deliveries, customer classification, soft time windows

摘要： 为促进生鲜农产品流通、降低生鲜物流配送成本,结合生鲜农产品的生鲜损耗,研究了一种带客户分级和需求可拆分的生鲜车辆路径问题。此文的需求可拆分为需求依背包拆分,是一种需求离散拆分的新类型,即每个客户的生鲜需求量可由多个背包离散组合而成。依据客户的重要性来实施分级处理,将软时间窗和需求依背包拆分纳入约束,并将生鲜损耗费用纳入目标,构建了相应的多目标数学模型。为了提升禁忌搜索算法(TSA)的寻优性能,设计了动态禁忌表,并将自适应惩罚机制、多邻域结构体、禁忌表重新初始化等策略纳入TSA中,设计了一种带动态禁忌表的自适应TSA进行求解。通过对比分析验证了算法的有效性。

关键词: 车辆路径问题, 生鲜物流, 禁忌搜索, 需求可拆分, 客户分级, 软时间窗

CLC Number:

TP18
U116.2

夏扬坤,邓永东,庞燕,王忠伟,高亮. 带客户分级和需求可拆分的生鲜车辆路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1238-1248.

[1]	. Improved simulated annealing algorithm for capacitated vehicle routing problem [J]. , 2021, 27(8): 2260-2269.
[2]	. Algorithms for vehicle routing problem with stochastic demand with soft time window [J]. , 2021, 27(8): 2270-2281.
[3]	. 2L-CVRP vehicle routing problem with LIFO loading constraint [J]. , 2021, 27(7): 2134-2143.
[4]	. Tracking and registration method based on image matching for augmented reality aided assembly system [J]. , 2021, 27(5): 1281-1291.
[5]	. Pollution routing problem based on time window assignment [J]. , 2021, 27(4): 1178-1187.
[6]	. Improved Jaya algorithm and tabu search for flexile job shop scheduling problem [J]. , 2021, 27(11): 3172-3184.
[7]	. Bi-directional annular corridor allocation problem design using hybrid whale optimization algorithm [J]. , 2021, 27(10): 2908-2920.
[8]	. Solving open vehicle routing problem with time windows based on variable neighborhood search algorithm [J]. , 2021, 27(10): 3014-3025.
[9]	. Optimization of low-carbon cold chain vehicle path considering customer satisfaction [J]. , 2020, 26(第4): 1108-1117.
[10]	. Hyper-heuristic for CVRP with reinforcement learning [J]. , 2020, 26(第4): 1118-1129.
[11]	. Hyper-heuristic for time-dependent VRP with simultaneous delivery and pickup [J]. , 2020, 26(7): 1905-1917.
[12]	. Waste furniture recycling vehicle routing optimization based on tabu search algorithm [J]. , 2020, 26(5期): 1425-1433.
[13]	. Bike-sharing rebalancing problem based on double-layer tabu search algorithm [J]. , 2020, 26(12): 3216-3228.
[14]	. Vehicle routing problem with simultaneous delivery and pickup problem solving by backtracking search optimization algorithm [J]. , 2019, 25(第9): 2237-2247.
[15]	. Split loading policies for rural last-mile logistics [J]. , 2019, 25(第9): 2377-2384.