腾讯会议参加人数上限为300人
打赏后的小伙伴，将会被邀请进入讲座临时腾讯会议群
打赏方式见文章末尾处
打赏后请联系“数据魔术师小助手（见文末二维码）”进群
数据魔术师
运筹优化及人工智能系列讲座第30期
【活动信息】
题目：分枝定价算法求解带无人机的车辆路径问题
Title：A Branch-and-Price Algorithm for the Vehicle Routing Problem with Drones
主 讲 人: 程春 东北财经大学现代供应链管理研究院助理教授
主 持 人: 秦虎 华中科技大学管理学院教授
活动时间: 2022年2月23日 晚上19:00-21:00
讲座语言：中文
主办单位：数据魔术师
直播平台：通过讲座临时腾讯会议群发布腾讯会议号及密码
【主讲人简介】
程春，2020年博士毕业于加拿大蒙特利尔大学工学院应用数学专业，2016年硕士毕业于清华大学工业工程系。博士期间曾在新加坡国立大学和麻省理工学院各交流半年。主要研究方向为供应链管理，包含鲁棒性的设施选址问题及无人机配送等。其研究成果以第一作者/通讯作者已发表在Transportation ResearchPart B：Methodological（两篇）, TransportationResearch Part E: Logistics and Transportation Review（两篇），Omega及International Journal of ProductionEconomics等期刊。主持“国家自然科学基金青年基金项目”。
【报告摘要】
This paper considers a new variant of the vehicle routing problem with drones (VRPD), where multiple vehicles and drones work collaboratively to serve customers. Several practical constraints such as customers' delivery deadlines and drones' energy capacityare considered. Different from existing studies, we treat the number of drones taken by each vehicle as a decision variable instead of a given parameter, which provides more flexibility for planning vehicle and drone routes. We also allow a drone to perform multiple back-and-forth trips when its paired vehicle stops at a customer node. We first formulate this problem as a mixed-integer linear programming model, which is solvable by off-the-shelf commercial solvers. To tackle VRPD instances more efficiently, we next develop a set-partitioning model. To solve it, a branch-and-price algorithm is proposed, where a bidirectional labeling algorithm is used to solve the pricing problem. To speed up the algorithm, the cheapest insertion heuristic is developed for initial column generation, and a tabu search algorithm is first applied before the exact labeling algorithm for finding desired columns in each iteration of the column generation process. Extensive numerical tests show that our algorithm can solve most instances within 25 customers to optimality in a short time frame and some instances of 35 customers to optimality within a three-hour timelimit. Results also demonstrate that the allocation decisions of drones can help save the duration of all routes by 3.45% on average for 25-customer instances, compared to the case of fixing the number of paired drones on eachvehicle.
欢迎大家加入数据魔术师粉丝群，我们的活动将会通过粉丝群优先发布， 学习资料将通过粉丝群分享。
欲入群，请转发此文，然后扫描下方二维码联系“数据魔术师小助手”
