多中心联合取送货车辆路径优化与利润分配

doi:10.3778/j.issn.1002-8331.2201-0425

摘要/Abstract

摘要： 共享模式是电商逆向物流的新发展趋势，在共享车辆与客户订单的条件下，考虑带时间窗约束的客户同时取送货情景，建立了MJVRPSDPTW（multi-centers joint vehicle routing problem with simultaneous delivery and pick-up and time window）模型。接着设计一种基于大邻域搜索的混合遗传算法进行求解，针对“多对多网络”设置虚拟中心并利用整体法优化，同时融合大邻域搜索算法中的“破坏”与“修复”算子，增强算法寻优能力。通过多组算例对比实验，证明该算法优于两阶段规划法与经典遗传算法。基于优化后的网络，利用Shapley值法对不同联盟情况下的各物流企业进行利润分配，结果证明大联盟最稳定且共同利润最大。

关键词: 联合取送货, 车辆路径优化, 混合遗传算法, 利润分配, Shapley值法

Abstract: Under the condition of sharing vehicles and orders, considering the simultaneous delivery and pickup scenario with soft time window, this study establishes the MJVRPSDPTW model. Then a hybrid genetic algorithm based on large neighborhood search is designed. The virtual center is set and optimized by wholeness method. The “destruction” and “repair” operators in large neighborhood searchare integrated to enhance the optimization ability of the algorithm. Through several groups of comparative experiments, it is proved that the algorithm is superior to the two-stage programming method and the classical genetic algorithm. Finally, based on the optimized network, the profit distribution of logistics enterprises under different alliances is carried out by using Shapley value method, which proves the effectiveness of the model.

Key words: joint pick-up and delivery, vehicle routing problem, hybrid genetic algorithm, profit distribution, Shapley value

王新杰, 陈淮莉. 多中心联合取送货车辆路径优化与利润分配[J]. 计算机工程与应用, 2023, 59(3): 300-307.

WANG Xinjie, CHEN Huaili. Vehicle Routing Optimization and Profit Distribution for Multi-Center Joint Pick-Up and Delivery[J]. Computer Engineering and Applications, 2023, 59(3): 300-307.

参考文献

[1] 中华人民共和国商务部.中国电子商务报告[R].北京：商务出版社，2020.
Ministry of Commerce of China.China e-commerce report[R].Beijing：Business Press，2020.
[2] ZHANG M，PRATAP S，ZHAO Z，et al.Forward and reverse logistics vehicle routing problems with time horizons in B2C e-commerce logistics[J].International Journal of Production Research，2020.
[3] ZHANG M，PRATAP S，HUANG G Q，et al.Optimal collaborative transportation service trading in B2B e-commerce logistics[J].International Journal of Production Research，2017，55：1-17.
[4] LIU R，JIANG Z，FUNG R，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.
[5] WANG Y，MA X，LIU M，et al.Cooperation and profit allocation in two-echelon logistics joint distribution network optimization[J].Applied Soft Computing，2017，56：143-157.
[6] ZHANG W，CHEN Z，ZHANG S，et al.Composite multi-objective optimization on a new collaborative vehicle routing problem with shared carriers and depots[J].Journal of Cleaner Production，2020，274：122593.
[7] HE P，WEN J，YE S，et al.Logistics service sharing and competition in a dual-channel e-commerce supply chain[J].Computers & Industrial Engineering，2020，149（2）：106849.
[8] LI J，LI Y，PARDALOS P M.Multi-depot vehicle routing problem with time windows under shared depot resources[J].Journal of Combinatorial Optimization，2016，31：515-532.
[9] 刘家利，马祖军.存在车辆租赁及共享且有时间窗的多配送中心开环VRP[J].系统工程理论与实践，2013，33（3）：666-675.
LIU J L，MA Z J.Multi-depot open vehicle routing problem with time windows based on vehicle leasing and sharing[J].Systems Engineering-Theory & Practice，2013，33（3）：666-675.
[10] 葛显龙，王旭，邓蕾.基于联合配送的开放式动态车辆路径问题及算法研究[J].管理工程学报，2013，27（3）：60-68.
GE X L，WANG X，DENG L.Research on open dynamic vehicle routing problem and algorithm based on joint distribution[J].Journal of Industrial Engineering and Engineering Management，2013，27（3）：60-68.
[11] 付朝晖，刘长石.多物流中心共同配送的车辆路径问题研究[J].计算机工程与应用，2021，57（16）：291-298.
FU Z H，LIU C S.Research on multi-depot vehicle routing problem based on joint distribution mode[J].Computer Engineering and Applications，2021，57（16）：291-298.
[12] 范厚明，刘鹏程，刘浩，等.多中心联合配送模式下集货需求随机的VRPSDP问题[J].自动化学报，2021，47（7）：1646-1660.
FAN H M，LIU P C，LIU H et al.The multi-depot vehicle routing problem with simultaneous deterministic delivery and stochastic pickup based on joint distribution[J].Acta Automatica Sinica，2021，47（7）：1646-1660.
[13] YONG W A，JIE Z B，XG C，et al.Collaborative multiple centers fresh logistics distribution network optimization with resource sharing and temperature control constraints-ScienceDirect[J].Expert Systems with Applications，2021，165：113838.
[14] WANG Y，ZHANG J，ASSOGBA K，et al.Collaboration and transportation resource sharing in multiple centers vehicle routing optimization with delivery and pickup[J].Knowledge-Based Systems，2018，160（15）：296-310.
[15] 杨翔.多中心开放式VRP拓展问题建模及算法研究[D].大连：大连海事大学，2019.
YANG X.Modeling and algorithm research on extensions of open multi-depot vehicle routing problem[D].Dalian：Dalian Maritime University，2019.
[16] 廖伟.考虑共同配送和能耗的车辆路径问题优化研究[D].成都：西南交通大学，2014.
LIAO W.Research on vehicle routing optimization under joint distribution and energy[D].Chengdu：Southwest Jiaotong University，2014.
[17] TASAN A S，GEN M.A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries[J].Computers & Industrial Engineering，2012，62（3）：755-761.
[18] ZHEN L，LV W Y，WANG K，et al.Consistent vehicle routing problem with simultaneous distribution and collection[J].Journal of the Operational Research Society，2019，71（5）：813-830.
[19] 饶卫振，朱庆华，金淳，等.协作车辆路径成本分摊问题的B-T Shapley方法[J].管理科学学报，2019，22（1）：107-126.
RAO W Z，ZHU Q H，JIN Z，et al.B-T Shapley method for cooperative vehicle routing cost allocation problem[J].Journal of Management Science in China，2019，22（1）：107-126.
[20] 张晓琴.基于改进Shapley值的冷链药品共同配送成本分摊研究[D].成都：西南交通大学，2017.
ZHANG X Q.Cost allocation of joint distribution of cold chain drugs based on improved Shapley value[D].Chengdu：Southwest Jiaotong University，2017.
[21] 南江霞，王盼盼，李登峰.非合作-合作两型博弈的Shapley值纯策略纳什均衡解求解方法[J].中国管理科学，2021，29（5）：202-210.
NAN J X，WANG P P，LI D F.A solution method for Shapley-based equilibrium strategies of biform games[J].Chinese Journal of Management Science，2021，29（5）：202-210.