服务差异二级选址路径问题及大邻域搜索算法

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

摘要/Abstract

摘要： 在电子商务背景下，物流公司为了实现及时交付并缓解交通拥堵，可按照客户不同的服务需求，将其分为自取型和配送型，进而选择开放自助点或配送点对客户进行服务。自助点和配送点作为二级物流设施，配送中心作为一级物流设施，由此形成了二级选址-路径问题。在配送车数量约束、自助点容量约束等限制下，兼顾客户点物品回收，以总物流成本最小为目标，建立考虑服务差异的二级选址-路径问题模型。设计自适应大邻域搜索算法进行求解，通过Nguyen的2E-LRP算例进行测试，更新了1个算例的全球最优解，其余算例达到或接近最优解，平均Gap值在1.22%以内，验证了算法的有效性及良好的收敛性。实际案例模拟分析验证了模型的有效性和适用性，可以为相关物流企业提供决策依据和参考。

关键词: 两级选址-路径, 客户服务差异化, 同时取送货, 自适应大邻域搜索

Abstract: With the growing popularity of e-commerce, in order to achieve faster delivery and reduce inner-city traffic congestion, one alternative approach is to divide customers into self-service and distribution service according to customers’ different needs, and then some self-service points or satellites are chosen to serve customers. The self-service points and satellites are the secondary logistics facilities, and the distribution center is the first-level logistics facility, which forms a two-echelon location-routing problem. In order to minimize the total logistics cost, a two-echelon location-routing problem with different service modes model is established, considering the constraints like the number of distribution vehicles and the capacity of self-service points. Then, an adaptive large neighborhood search（ALNS） algorithm is designed to solve the proposed model. Tested by Nguyen’s 2E-LRP instances, the best known solution of one instance is updated by the ALNS, and the other instances reach or close to the best known solution, and the average gap value is within 1.22%, and the effectiveness and good convergence of the algorithm are verified. Finally, based on simulation data, the model is proved to be valid and applicable. This study can provide decision support for relevant logistics enterprises.

Key words: two-echelon location-routing problem, different service modes, simultaneous pick-up and delivery, , adaptive large neighborhood search（ALNS）

杨屹夫, 孙冰, 马艳芳, 程聪, 冯翠英. 服务差异二级选址路径问题及大邻域搜索算法[J]. 计算机工程与应用, 2023, 59(3): 282-292.

YANG Yifu, SUN Bing, MA Yanfang, CHENG Cong, FENG Cuiying. Adaptive Large Neighborhood Search Algorithm for Two-Echelon Location-Routing Problem with Different Service Modes[J]. Computer Engineering and Applications, 2023, 59(3): 282-292.

参考文献

[1] 郭晓宇.基于混合蚁群算法和干扰管理的多目标物流配送应用研究[D].大连：大连交通大学，2020.
GUO X Y.Research on multi-objective logistics distribution application based on hybrid ant colony algorithm and disruption management[D].Dalian：Dalian Jiaotong University，2020.
[2] 夏扬坤，邓永东，庞燕，等.带客户分级和需求可拆分的生鲜车辆路径问题[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.
[3] 刘秋萍.考虑客户等级划分的多目标冷链物流配送车辆路径优化[D].镇江：江苏大学，2019.
LIU Q P.Optimization of multi-objective cold chain logistics distribution vehicle path considering customer rating classification[D].Zhenjiang：Jiangsu University，2019.
[4] 黄秋彬.基于客户重要度的城市物流配送网络优化研究[D].重庆：重庆交通大学，2019.
HUANG Q B.Optimization study of urban logistics distribution network based on customers’ importance[D].Chongqing：Chongqing Jiaotong University，2019.
[5] 王超.配送企业车辆路径问题模型与算法研究[D].北京：北京交通大学，2015.
WANG C.Modeling and algorithms for vehicle routing problem of distribution companies[D].Beijing：Beijing Jiaotong University，2015.
[6] NGUYEN V，PRINS C，PRODHON C.Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking[J].European Journal of Operational Research，2011，216（1）：113-126.
[7] CONTARDO C，HEMMELMAYR V，CRAINIC T G.Lower and upper bounds for the two-echelon capacitated location-routing problem[J].Computers & Operations Research，2012，39（12）：3185-3199.
[8] SCHWENGERER M，PIRKWIESER S，RAIDL G R.A variable neighborhood search approach for the two-echelon location-routing problem[C]//Proceedings of the 12th European Conference on Evolutionary Computation in Combinatorial Optimization，Málaga，Apr 11-13.Berlin，Heidelberg：Springer，2012：13-24.
[9] ENTHOVEN D L J U，JARGALSAIKHAN B，ROODBERGEN K J，et al.The two-echelon vehicle routing problem with covering options：city logistics with cargo bikes and parcel lockers[J].Computers and Operations Research，2020，118：104919.
[10] MIN H.The multiple vehicle routing problem with simultaneous delivery and pick-up points[J].Transportation Research Part A：General，1989，23（5）：377-386.
[11] DETHLOFF J.Vehicle routing and reverse logistics：the vehicle routing problem with simultaneous delivery and pick-up[J].OR-Spektrum，2001，23（1）：79-96.
[12] 李博威，户佐安，贾叶子，等.带软时间窗的同时取送货车辆路径问题研究[J].工业工程，2020，23（5）：75-81.
LI B W，HU Z A，JIA Y Z，et al.A research on vehicle routing problem with simultaneous pick-up and delivery and soft time windows[J].Industrial Engineering Journal，2020，23（5）：75-81.
[13] 张烜荧，胡蓉，钱斌.超启发式分布估计算法求解带软时间窗的同时取送货车辆路径问题[J].控制理论与应用，2021，38（9）：1427-1441.
ZHANG X Y，HU R，QIAN B.Hyper-heuristic estimation of distribution algorithm for solving vehicle routing problem with simultaneous pickup and delivery and soft time windows[J].Control Theory & Applications，2021，38（9）：1427-1441.
[14] 张庆华，吴光谱.带时间窗的同时取送货车辆路径问题建模及模因求解算法[J].计算机应用，2020，40（4）：1097-1103.
ZHANG Q H，WU G P.Modeling and memetic algorithm for vehicle routing problem with simultaneous pickup-delivery and time windows[J].Journal of Computer Applications，2020，40（4）：1097-1103.
[15] 王超，刘超，穆东，等.基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题[J].计算机集成制造系统，2018，24（3）：570-582.
WANG C，LIU C，MU D，et al.VRPSPDTW problem solving by discrete cuckoo search[J].Computer Integrated Manufacturing Systems，2018，24（3）：570-582.
[16] 郭放，黄志红，黄卫来.考虑前置仓选址与服务策略的同时取送货车辆路径问题研究[J].系统工程理论与实践，2021，41（4）：962-978.
GUO F，HUANG Z H，HUANG W L.Integrated sustainable planning of fast-pick area network and vehicle routing with simultaneous delivery and pick-up[J].Systems Engineering Theory & Practice，2021，41（4）：962-978.
[17] CHEN S F，CHEN R，WANG G，et al.An adaptive large neighborhood search heuristic for dynamic vehicle routing problems[J].Computers and Electrical Engineering，2018，67：596-607.
[18] 康凯，韩杰，普玮，等.生鲜农产品冷链物流低碳配送路径优化研究[J].计算机工程与应用，2019，55（2）：259-265.
KANG K，HAN J，PU W，et al.Optimization research on cold chain distribution routes considering carbon emissions for fresh agricultural products[J].Computer Engineering and Applications，2019，55（2）：259-265.