报告题目：Novel Formulation and Exact Method for the Automated Guided Vehicle Scheduling Problem with Flexible Charging

报 告 人：李延通

报告时间：2023年10月24日（星期二），14:00-15:30

报告地点：明哲楼504

主办单位：东北财经大学现代供应链管理研究院

【报告人简介】

大连海事大学航运经济与管理学院副教授、硕士生导师，法国巴黎萨克雷大学（软科世界大学排名第16名）自动化专业博士，中国运筹学会排序分会、随机服务与运作管理分会青年理事，大连市“青年才俊”类高层次人才。曾赴香港理工大学、加拿大拉瓦尔大学CIRRELT团队访学。主持国家自然科学青年基金、教育部人文社科青年基金、辽宁省社科规划基金青年项目、中国博士后科学基金面上一等资助等项目。主要研究兴趣为运筹与优化，物流规划，物流系统建模与优化、调度模型、算法及应用等。成果发表在IJOC、EJOR、IJPR、IJPE、Omega、TRE、COR、IEEE TITS, IEEE TASE, IEEE TEM等国际知名期刊。2022年作为参与人获中国物流与采购联合会、中国商业联合会科学技术进步一等奖。目前担任IJOC, Omega, TRE, ANOR, IJPR, COR, CIE, IEEE TITS, SMC, TASE, INFOR等国际期刊审稿人。

【摘要】

Automated Guided Vehicle (AGV) scheduling problems are commonly encountered in manufacturing and logistics systems, where AGVs are used to transfer materials or goods. This paper addresses the AGV scheduling problem with flexible charging and charging setup time (ASP-FLC-ST). It extends the existing AGV scheduling problem with fixed charging (ASP-FIC) by minimizing the completion time of tasks, known as makespan. We propose a novel mixed-integer linear programming model. We show that ASP-FLC-ST is strongly NP-hard since it combines two well-known NP-hard problems by analyzing the problem structure. We then derive a valid lower bound. We develop a tailored exact logic-based Benders decomposition algorithm (LBBD), which effectively decomposes the problem and introduces an “alternating cut generation scheme" to enhance the performance. Computational experiments on the ASP-FLC-ST using 360 instances demonstrate the superiority of our approach over CPLEX. Additionally, we adapt the LBBD method to the ASP-FIC problem and compare it against a state-of-the-art matheuristic method, showing improved results with 173 new best solutions and 161 proven optimality in open instances.