带模糊工作时间窗的多配送中心同时集散货物车辆路径问题

管理评论 ›› 2022, Vol. 34 ›› Issue (10): 258-269.

带模糊工作时间窗的多配送中心同时集散货物车辆路径问题

邓忆瑞, 郑瑶, 姜明月, 徐小峰

中国石油大学(华东)经济管理学院, 青岛 266580

收稿日期:2019-12-02 出版日期:2022-10-28 发布日期:2022-11-24
通讯作者: 徐小峰,中国石油大学(华东)经济管理学院教授,博士。
作者简介:邓忆瑞,中国石油大学(华东)经济管理学院副教授,博士;郑瑶,中国石油大学(华东)经济管理学院硕士研究生;姜明月,中国石油大学(华东)经济管理学院硕士研究生;徐小峰,中国石油大学(华东)经济管理学院教授,博士。
基金资助:
山东省社会科学规划研究项目(19CGLJ31);教育部人文社会科学研究青年基金项目(20YJC630015)。

VRP of Simultaneous Pickup and Delivery Goods in Multiple Centers with Fuzzy Time Window

Deng Yirui, Zheng Yao, Jiang Mingyue, Xu Xiaofeng

School of Economics and Management, China University of Petroleum, Qingdao 266580

Received:2019-12-02 Online:2022-10-28 Published:2022-11-24

摘要/Abstract

摘要： 在线资源的特性使得配送车辆采用分时租赁的模式为客户进行服务,配送车辆路径问题呈现多模糊时间窗特性。本文构建了带有模糊工作时间窗的多配送中心同时集散货物车辆路径模型,以最小化配送成本、车辆使用数,最大化服务质量为优化目标。根据客户期望时间窗、硬时间窗、软时间窗,改进了线性梯形隶属度函数表示客户模糊满意度。模型的求解采用自适应大规模邻域搜索算法,通过引入多种群搜索机制和非支配排序操作,加快算法收敛速度、增强算法全局寻优能力。最后,通过算例求解验证模型和改进算法的有效性和优越性。

关键词: 模糊时间窗, 模糊满意度, 同时集散货物, 车辆路径问题

Abstract: The characteristics of online resources make it necessary to serve customers by using the lease mode of sharing distribution vehicles, but the resultant distribution routing becomes challenging due to multiple fuzzy time windows. In this paper, a VRP model of simultaneous pickup and delivery goods in multiple centers with fuzzy time window is constructed to minimize the distribution cost and the number of vehicles used, and maximize the service quality. By taking the service time window expected by customers, hard time window and soft time window into consideration, this model improves the linear trapezoid membership function to express customer fuzzy satisfaction, and uses the adaptive large-scale neighborhood search algorithm for solution, with a variety of group search mechanisms and nondominated sorting operations introduced to speed up the algorithm convergence and enhance the global optimization ability of algorithm. Finally, the validity and the superiority of the model and the improved algorithm are verified by solving a numerical example.

Key words: fuzzy time window, fuzzy satisfaction, simultaneous pickup and delivery goods, VRP

邓忆瑞, 郑瑶, 姜明月, 徐小峰. 带模糊工作时间窗的多配送中心同时集散货物车辆路径问题[J]. 管理评论, 2022, 34(10): 258-269.

Deng Yirui, Zheng Yao, Jiang Mingyue, Xu Xiaofeng. VRP of Simultaneous Pickup and Delivery Goods in Multiple Centers with Fuzzy Time Window[J]. Management Review, 2022, 34(10): 258-269.

参考文献

[1] Allahyari S., Salari M., Vigo D. A Hybrid Metaheuristic Algorithm for the Multi-depot Covering Tour Vehicle Routing Problem[J]. European Journal of Operational Research, 2015,242(3):756-768;
[2] Xu X., Hao J., Yu L., et al. Fuzzy Optimal Allocation Model for Task——Resource Assignment Problem in a Collaborative Logistics Network[J]. IEEE Transactions on Fuzzy Systems, 2018,27(5):1112-1125;
[3] 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(11):296-310;
[4] Dantzig G. B., Ramser J. H. The Truck Dispatching Problem[J]. Management Science, 1959,6(1):80-91;
[5] 姚源果,贺盛瑜. 基于交通大数据的农产品冷链物流配送路径优化研究[J]. 管理评论, 2019,31(4):240-253;
[6] Tillman F. A. The Multiple Terminal Delivery Problem with Probabilistic Demands[J]. Transportation Science, 1969,3(3):192-204;
[7] 王艳敏. 非限定车场车辆路径问题研究[D]. 东北大学硕士学位论文, 2009;
[8] Montoya-Torres J. R., Franco J. L., Isaza S. N., et al. A Literature Review on the Vehicle Routing Problem with Multiple Depots[J]. Computers & Industrial Engineering, 2015,79(1):115-129;
[9] 刘家利,马祖军. 存在车辆租赁及共享且有时间窗的多配送中心开环VRP[J]. 系统工程理论与实践, 2013,33(3):666-675;
[10] 杨翔,范厚明,徐振林,等. 模糊需求下多中心开放式车辆路径优化[J]. 计算机集成制造系统, 2019,25(2):469-479;
[11] 王道平,徐展,杨岑. 基于两阶段启发式算法的物流配送选址-路径问题研究[J]. 运筹与管理, 2017,26(4):70-75;
[12] Deng Y., Zheng Y., Li J. Route Optimization Model in Collaborative Logistics Network for Mixed Transportation Problem Considered Cost Discount Based on GATS[J]. Journal of Ambient Intelligence and Humanized Computing, 2019,10(1):409-416;
[13] 钟石泉,贺国光. 多车场车辆调度智能优化研究[J]. 华东交通大学学报, 2004,21(6):25-29;
[14] Solomon M. M. Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints[J]. Operations Research, 1987,35(2):254-265;
[15] 余海燕,唐婉倩,吴腾宇. 带硬时间窗的O2O生鲜外卖即时配送路径优化[J]. 系统管理学报, 2021,30(3):584-591;
[16] 李国明,李军华. 带软时间窗随机需求车辆路径问题的算法研究[J]. 计算机集成制造系统, 2021,27(8):2270-2281;
[17] Tang J., Pan Z., Fung R. Y., et al. Vehicle Routing Problem with Fuzzy Time Windows[J]. Fuzzy Sets and Systems, 2009,160(5):683-695;
[18] Xu J., Yan F., Li S. Vehicle Routing Optimization with Soft Time Windows in a Fuzzy Random Environment[J]. Transportation Research Part E:Logistics and Transportation Review, 2011,47(6):1075-1091;
[19] 熊桂武. 具有模糊时间窗的多模式联运建模及优化[J]. 工业工程, 2012,15(4):7-11;
[20] 罗耀波,孙延明. 基于模糊时间窗的带容积约束选址路径问题[J]. 系统工程, 2014,32(1):19-25;
[21] 闫芳,王媛媛. 多模糊时间窗车辆路径问题的建模及求解[J]. 交通运输系统工程与信息, 2016,16(6):182-188;
[22] 杨翔,范厚明,张晓楠,等. 基于模糊时间窗的多中心开放式车辆路径问题[J]. 计算机集成制造系统, 2016,22(7):1768-1778;
[23] 曹庆奎,杨凯文,任向阳,等. 基于交通流的多模糊时间窗车辆路径优化[J]. 运筹与管理, 2018,27(8):20-26;
[24] 范厚明,吴嘉鑫,耿静,等. 模糊需求与时间窗的车辆路径问题及混合遗传算法求解[J]. 系统管理学报, 2020,29(1):107-118;
[25] Ghannadpour S. F., Noori S., Tavakkoli-Moghaddam R., et al. A Multi-objective Dynamic Vehicle Routing Problem with Fuzzy Time Windows:Model, Solution and Application[J]. Applied Soft Computing, 2014,14(1):504-527;
[26] 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;
[27] 闫军,常乐,王璐璐,等. 带时间窗的同时取送货车辆路径问题求解算法[J]. 工业工程, 2021,24(5):72-76;
[28] 马艳芳,闫芳,康凯,等. 不确定同时去送货车辆路径问题及粒子群算法研究[J]. 运筹与管理, 2018,27(12):73-83;
[29] Wang X., Yang F., Lu D. Multi-objective Location-Routing Problem with Simultaneous Pickup and Delivery for Urban Distribution[J]. Journal of Intelligent & Fuzzy Systems, 2018,35(4):3987-4000;
[30] Kachitvichyanukul V., Sombuntham P., Kunnapapdeelert S. Two Solution Representations for Solving Multi-depot Vehicle Routing Problem with Multiple Pickup and Delivery Requests via PSO[J]. Computers & Industrial Engineering, 2015,89(11):125-136;
[31] 李双琳,郑斌. 震后路网抢修排程与应急物资配送集成动态优化研究[J]. 管理评论, 2019,31(2):238-251;
[32] 徐小峰,刘靖. 多阶段并发的协同物流网络任务-资源集成调配模型[J]. 运筹与管理, 2018,27(7):43-48;
[33] 张江华,李进,高敏刚. 同时集散货物的开放式车辆路径问题研究[J]. 中国管理科学, 2013,21(4):187-192;
[34] Men??ndez B., Pardo E. G., Alonso-Ayuso A., et al. Variable Neighborhood Search Strategies for the Order Batching Problem[J]. Computers & Operations Research, 2017,78(2):500-512;
[35] Pisinger D., Ropke S. A general Heuristic for Vehicle Routing Problems[J]. Computers & Operations Research, 2007,34(8):2403-2435;
[36] Hintsch T., Irnich S. Large Multiple Neighborhood Search for the Clustered Vehicle-Routing Problem[J]. European Journal of Operational Research, 2018,270(1):118-131;
[37] Bach L., Hasle G., Schulz C. Adaptive Large Neighborhood Search on the Graphics Processing Unit[J]. European Journal of Operational Research, 2019,275(1):53-66;
[38] 李成严,徐晓飞,战德臣. 模糊资源约束的联合补充问题[J]. 计算机集成制造系统, 2008,14(1):113-117;
[39] 晏雨婵,白璘,武奇生,等. 基于多指标模糊综合评价的交通拥堵预测与评估[J]. 计算机应用研究, 2019,36(12):3697-3700