电动车辆路径问题:可调鲁棒数学模型与算法
Electric vehicle routing problem:Adjustable robust mathematical model and its algorithm
郭静梅 1张瑞友2
作者信息
- 1. 东北大学信息科学与工程学院,辽宁沈阳 110819;东北大学秦皇岛分校数学与统计学院,河北秦皇岛 066004
- 2. 东北大学信息科学与工程学院,辽宁沈阳 110819
- 折叠
摘要
针对行驶时间不确定的允许部分充电的带时间窗电动车辆路径问题,考虑多面体不确定集度量行驶时间的不确定性,建立了一个可调鲁棒优化模型,设计了基于行生成和集划分的求解算法,采用标号法对路径的可行性进行判定,并将不可行的路径作为新的约束加入到模型中.数值实验表明,94％的算例可求得最优解,这验证了本算法的效率;利用多面体不确定集进行度量对总行驶距离和车辆总数目具有正向的影响;相比于普通鲁棒优化,可调鲁棒优化的求解结果有显著提高,可以提升车辆调度的灵活性.
Abstract
An electric vehicle routing problem with uncertain travel times and time windows which allows partial recharges is investigated.An adjustable robust optimization model is constructed to formulate the prob-lem using the polyhedron uncertainty set as the measurement for the uncertainty of travel time.An algorithm based on both row generation and set partitioning is designed to solve the problem.The algorithm checks the feasibilities of routes using the labeling method.The infeasible routes are added to the model as new con-straints.Results from numerical experiments indicate that the optimal solutions for 94％of the instances can be obtained,which confirms the efficiency of the algorithm.The polyhedron uncertainty set measurement has a positive effect on both the total driving distance and the total number of vehicles involved.Compared to the common robust optimization method,the results of the adjustable robust optimization show significant improvements,improveing the flexibility of vehicle scheduling.
关键词
电动车辆路径问题/可调鲁棒优化/不确定行驶时间/行生成/集划分Key words
electric vehicle routing problem/adjustable robust optimization/uncertain travel time/row gener-ation/set partitioning引用本文复制引用
基金项目
国家自然科学基金资助项目(71971050)
国家自然科学基金资助项目(71831006)
出版年
2024
NETL
NSTL
万方数据