基于电商承诺送达机制的多目标低碳MDVRP优化研究

doi:10.16381/j.cnki.issn1003-207x.2019.0365

摘要/Abstract

摘要： 针对存在多配送站的电商物流配送问题，首先，考虑实际装载量对物流配送过程中车辆燃料消耗量的影响，建立燃料消耗量模型，并结合电商平台的承诺送达机制，构建配送延迟时间函数。随后，提出了以最小化物流成本和延迟收货时间的多目标多配送站车辆路径规划问题，建立该问题的混合整数规划模型。再次，采用基于分解的多目标遗传求解算法对问题进行求解。该算法采用矩阵编码的方式，设计了基于贪婪搜索策略的启发式初始化方法，考虑到贪婪搜索策略容易陷入局部最优的劣势，在算法迭代过程中，允许部分不可行解存在以扩大解空间的搜索范围，并进一步设计了遗传算法的交叉和变异算子。最后，以具体物流配送案例进行数值实验，实验结果表明所设计的算法对求解本文模型是有效的。

关键词: 多配送站, 燃料消耗量, 延迟收货时间, 多目标, 基于分解的遗传算法

Abstract: Under the background of rapid development of e-commerce, the problem of logistics terminal distribution optimization has become the key to its operational efficiency. For the multi-depot e-commerce logistics distribution problem, firstly, considering the impact of actual loading on vehicle fuel consumption in the process of logistics distribution, a fuel consumption model is established, and combining the commitment delivery mechanism of e-commerce platform, delayed delivery time function is built. Then, the multi-objective multi-depot vehicle routing problem with minimizing logistics distribution cost and minimizing delayed delivery time is proposed, and a mixed integer programming model of the problem is established. Thirdly, considering the NP-Hard characteristics of the problem and the difficulty of solving multi-objective, the problem is solved by the multi-objective genetic algorithm based on decomposition. The algorithm uses matrix coding to design a heuristic initialization method based on greedy search strategy. At the same time, considering that the greedy search strategy is easy to fall into the local optimum, in the iterative process of the algorithm, some unfeasible solutions are allowed to exist to expand the search range of the solution space, and the crossover and mutation operators of the genetic algorithm are further designed. Finally, the numerical experiments are carried out with specific logistics distribution cases. The experimental results verify the effectiveness of the designed algorithm to solve the model, and also show the inverse relationship between logistics distribution cost and delayed delivery time. There is a trade-off between consumer satisfaction and logistics distribution costs. In order to achieve higher consumer satisfaction, it often means increasing the cost of logistics distribution. At the same time, the solution algorithm of this paper provides a solution to the problem of e-commerce terminal delivery.

Key words: multi-depots, fuel consumption, delayed delivery time, multi-objective, genetic algorithm based on decomposition

中图分类号:

C93
TP18

浦徐进, 李秀峰. 基于电商承诺送达机制的多目标低碳MDVRP优化研究[J]. 中国管理科学, 2021, 29(8): 57-66.

PU Xu-jin, LI Xiu-feng. Multi-objective Low Carbon MDVRP Optimization Based on E-commerce Commitment Delivery Mechanism[J]. Chinese Journal of Management Science, 2021, 29(8): 57-66.

参考文献

[1] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.
[2] Renaud J, Boctor F F, Laporte G. An improved petal heuristic for the vehicle routeing problem[J]. Journal of the Operational Research Society, 1996, 47(2): 329-336.
[3] Mirabi M, Ghomi S M T F, Jolai F. Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem[J]. Robotics and Computer-Integrated Manufacturing, 2010, 26(6): 564-569.
[4] Kuo Y, Wang C C. A variable neighborhood search for the multi-depot vehicle routing problem with loading cost[J]. Expert Systems with Applications, 2012, 39(8): 6949-6954.
[5] Liu Ran, Jiang Zhibin, Fung R Y K, et al. Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration[J]. Computers & operations research, 2010, 37(5): 950-959.
[6] Salhi S, Imran A, Wassan N A. The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation[J]. Computers & Operations Research, 2014, 52: 315-325.
[7] de Oliveira F B, Enayatifar R, Sadaei H J, et al. A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem[J]. Expert Systems with Applications, 2016, 43: 117-130.
[8] Bektaş T, Laporte G. The pollution-routing problem[J]. Transportation Research Part B: Methodological, 2011, 45(8): 1232-1250.
[9] Xiao Yiyong, Konak A. The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion[J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 88: 146-166.
[10] Van W T, Creten R, Vandaele N. Managing the environmental externalities of traffic logistics: the issue of emissions[J]. Production & Operations Management, 2010, 10(2): 207-223.
[11] Demir E, Bekta T, Laporte G. A comparative analysis of several vehicle emission models for road freight transportation[J]. Transportation Research Part D: Transport and Environment, 2011, 16(5): 347-357.
[12] Sun Peng, Veelenturf L P, Hewitt M, et al. The time-dependent pickup and delivery problem with time windows[J]. Transportation Research Part B: Methodological, 2018, 116: 1-24.
[13] McNabb M E, Weir J D, Hill R R, et al. Testing local search move operators on the vehicle routing problem with split deliveries and time windows[J]. Computers & Operations Research, 2015, 56: 93-109.
[14] 颜瑞, 朱晓宁, 张群, 等.考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究[J].中国管理科学, 2017, 25(7): 67-77. Yan Rui, Zhu Xiaoning, Zhang Qun, et al. Research of the model and algorithm for two-dimensional multi-depots capacitated vehicle routing problem with time window constrain[J]. Chinese Journal of Management Science, 2017, 25(7): 67-77.
[15] Qureshi A G, Taniguchi E, Yamada T. An exact solution approach for vehicle routing and scheduling problems with soft time windows[J]. Transportation Research Part E: Logistics and Transportation Review, 2009, 45(6): 960-977.
[16] Afshar-Bakeshloo M, Mehrabi A, Safari H, et al. A green vehicle routing problem with customer satisfaction criteria[J]. Journal of Industrial Engineering International, 2016, 12(4): 529-544.
[17] Japanese Government Website. 乗用車の燃費·CO2排出量[EB\OL]. (2010-03-18) [2019-03-13]. http://www.mlit.go.jp/common/a)000037099.pdf.
[18] Suzuki Y. A dual-objective metaheuristic approach to solve practical pollution routing problem[J]. International Journal of Production Economics, 2016, 176: 143-153.
[19] Sahin B, Yilmaz H, Ust Y, et al. An approach for analysing transportation costs and a case study[J]. European Journal of Operational Research, 2009, 193(1): 1-11.
[20] Xiao Yiyong, Zhao Qiuhong, Kaku I, et al. Development of a fuel consumption optimization model for the capacitated vehicle routing problem[J]. Computers & operations research, 2012, 39(7): 1419-1431.
[21] McNabb M E, Weir J D, Hill R R, et al. Testing local search move operators on the vehicle routing problem with split deliveries and time windows[J]. Computers & Operations Research, 2015, 56: 93-109.
[22] 刘虹, 顾东晓, 张悦, 等.转型时期电商物流企业顾客忠诚度实证研究[J]预测, 2016, 35(6):44-49. Liu Hong, Gu Dongxiao, Zhang Yue, et al. An empirical study on customer loyalty for e-business logistics industry in the transitional period[J]. Forecasting, 2016, 35(6): 44-49.
[23] Voorhees C M, Baker J, Bourdeau B L, et al. It depends: Moderating the relationships among perceived waiting time, anger, and regret[J]. Journal of Service Research, 2009, 12(2): 138-155.
[24] 李劲, 李洪, 徐丽丽, 等.基于改进遗传算法的置换装配线调度问题研究[J].中国管理科学, 2016, 24(12): 63-71. Li Jin, Li Hong, Xu Lili, et al. Research on assembly line scheduling problem based on improved genetic algorithm[J]. Chinese Journal of Management Science, 2016, 24(12):63-71.
[25] Jozefowiez N, Semet F, Talbi E G. An evolutionary algorithm for the vehicle routing problem with route balancing[J]. European Journal of Operational Research, 2009, 195(3): 761-769.
[26] Miettinen K. Nonlinear multiobjective optimization[M]. Jyväskylä: Springer Science & Business Media, 2012.
[27] Baptista F, Tavares J. Bio-inspired algorithms for the vehicle routing problem[M]. México: Springer, 2009.