目的 建立电动车-无人机联合配送路径规划模型,以系统总成本最小化为目标,涵盖固定成本、能耗成本及碳排放成本,兼顾时间窗、载重与能源约束,为实现绿色低碳物流提供决策依据。方法 设计一种基于FCM聚类的多种群遗传算法,首先采用FCM聚类策略实现客户点在中转站间的优化分配,继而运用混沌初始化方法生成高质量初始种群,并通过子种群内及种群间的协同交叉变异机制提升算法性能。结果 在12个小规模算例中,CPLEX在限制时间内均可以求得最优解。模型规模较大时,CPLEX在限制时间内均无法求得最优解,部分算例能输出当前找到的最优上界解,其余算例无法给出可行解。相较而言,算法在求解时间上有着很大优势,平均运行时间分别为30.27 s和2.30 s,均优于CPLEX。与LNS-GA相比,MPCGA-FCM在求解质量上更优。结论 与CPLEX、大规模邻域搜索思想改进的遗传算法对比,本文算法在求解质量和求解速度方面均展现出显著优势,验证了该算法能够有效求解2E-VRPD问题优化配送路径,提升车机协同配送效率,降低配送成本。
Abstract
The work aims to establish a joint distribution route planning model for electric vehicles and drones, with the goal of minimizing the total system cost, including fixed costs, energy consumption costs, and carbon emission costs and also take into account time windows, load capacity, and energy constraints to provide a decision-making basis for achieving green and low-carbon logistics. A multi-population genetic algorithm based on FCM clustering was designed. Firstly, the FCM clustering strategy was used to optimize the allocation of customer points among transfer stations. Then, a high-quality initial population was generated with a chaotic initialization method, and the performance of the algorithm was improved through a collaborative crossover and mutation mechanism within and between subpopulations. In 12 small-scale examples, CPLEX could find optimal solutions within the time limit. However, for larger models, CPLEX could not find optimal solutions within the time limit, and some examples could only output the best upper bound solution found, while others could not produce feasible solutions. Compared to LNS-GA, MPCGA-FCM showed significant advantages in solving time, with average running time of 30.27 s and 2.30 s, both better than CPLEX. The experimental results show that compared to CPLEX and the genetic algorithm improved by large-scale neighborhood search, this algorithm demonstrates significant advantages in both solving quality and speed. It verifies that the algorithm can effectively solve the 2E-VRPD problem for optimizing distribution routes, improving the efficiency of vehicle-drone collaborative distribution, and reducing distribution costs.
关键词
车辆-无人机联合配送 /
改进遗传算法 /
碳排放 /
模糊C均值聚类
Key words
vehicle-drone collaborative distribution /
improved genetic algorithm /
carbon emission /
fuzzy C-means clustering
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] DUKKANCI O, CAMPBELL J F, KARA B Y.Facility Location Decisions for Drone Delivery: A Literature Review[J]. European Journal of Operational Research, 2024, 316(2): 397-418.
[2] 邱瑞, 江键忠, 丁宇, 等. 传染病检测样本转运的多物流无人机路径规划[J]. 数学的实践与认识, 2024, 54(10): 152-166.
QIU R, JIANG J Z, DING Y, et al.Path Planning for Distributed Multiple Unmanned Aerial Vehicles in Infectious Disease Testing Sample Transfer[J]. Mathematics in Practice and Theory, 2024, 54(10): 152-166.
[3] 魏明, 吴蕾, 孙博. 一类多物资类型无人机应急配送路径优化模型[J]. 数学的实践与认识, 2024, 54(6): 141-150.
WEI M, WU L, SUN B.Optimization Model of Emergency Delivery Routing of UAVs with Multi-Type Goods[J]. Mathematics in Practice and Theory, 2024, 54(6): 141-150.
[4] ZHAO Y X, ZHAO S C, ZHU H F, et al.Research on the Sales Model of Scenic Area Drone Logistics and Distribution—Taking Jueshan Scenic Area in Shanxi Province as an Example[J]. Academic Journal of Business & Management, 2023, 5(11): 051125.
[5] MURRAY C C, CHU A G.The Flying Sidekick Traveling Salesman Problem: Optimization of Drone-Assisted Parcel Delivery[J]. Transportation Research Part C: Emerging Technologies, 2015, 54: 86-109.
[6] KIM S, MOON I.Traveling Salesman Problem with a Drone Station[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 49(1): 42-52.
[7] DORLING K, HEINRICHS J, MESSIER G G, et al.Vehicle Routing Problems for Drone Delivery[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017, 47(1): 70-85.
[8] JEONG H Y, SONG B D, LEE S.Truck-Drone Hybrid Delivery Routing: Payload-Energy Dependency and No-Fly Zones[J]. International Journal of Production Economics, 2019, 214: 220-233.
[9] TAMKE F, BUSCHER U.The Vehicle Routing Problem with Drones and Drone Speed Selection[J]. Computers & Operations Research, 2023, 152: 106112.
[10] 马佰钰, 李贺鑫, 马千里, 等. 碳排放约束下无人机-卡车联合配送问题[J]. 系统工程, 2024, 42(2): 60-69.
MA B Y, LI H X, MA Q L, et al.Drone-Truck Joint Distribution under Carbon Emission Constraints[J]. Systems Engineering, 2024, 42(2): 60-69.
[11] KYRIAKAKIS N A, STAMADIANOS T, MARINAKI M, et al.The Electric Vehicle Routing Problem with Drones: An Energy Minimization Approach for Aerial Deliveries[J]. Cleaner Logistics and Supply Chain, 2022, 4: 100041.
[12] MARA S T W, SARKER R, ESSAM D, et al. Solving Electric Vehicle-Drone Routing Problem Using Memetic Algorithm[J]. Swarm and Evolutionary Computation, 2023, 79: 101295.
[13] 张帅, 刘思亮, 张文宇. 电动车-无人机协同配送模式下带时间窗的车辆路径优化问题[J]. 中国管理科学, 2025, 33(4): 131-141.
ZHANG S, LIU S L, ZHANG W Y.Vehicle Routing Problems with Time Windows under the Collaborative Delivery Mode of Electric Vehicle-Drone[J]. Chinese Journal of Management Science, 2025, 33(4): 131-141.
[14] 范厚明, 张跃光, 田攀俊. 时变路网下多中心电动车-无人机协同配送路径优化[J]. 管理工程学报, 2023, 37(2): 131-142.
FAN H M, ZHANG Y G, TIAN P J.Multi-Depot Electric Vehicle Routing Problem with Drones under Time-Dependent Networks[J]. Journal of Industrial Engineering and Engineering Management, 2023, 37(2): 131-142.
[15] 伍国华, 毛妮, 徐彬杰, 等. 基于自适应大规模邻域搜索算法的多车辆与多无人机协同配送方法[J]. 控制与决策, 2023, 38(1): 201-210.
WU G H, MAO N, XU B J, et al.The Cooperative Delivery of Multiple Vehicles and Multiple Drones Based on Adaptive Large Neighborhood Search[J]. Control and Decision, 2023, 38(1): 201-210.
[16] HUANG J R, ZHANG W.Research on Collaborative Optimisation of Urban Agricultural Product Distribution Centre Location and Routing Based on Improved Adaptive Large-Scale Neighbourhood Search Algorithm[J]. International Journal of Wireless and Mobile Computing, 2022, 22(1): 9.
[17] 李楠, 辛春阳. 基于聚类-Floyd-遗传算法的“车辆+无人机”城市物流配送路径优化[J]. 科学技术与工程, 2024, 24(21): 9186-9193.
LI N, XIN C Y.Urban Logistics Distribution Routing Optimization of "Vehicle-Drone" Based on Clustering-Floyd-Genetic Algorithm[J]. Science Technology and Engineering, 2024, 24(21): 9186-9193.
[18] 温廷新, 吕艳华. 考虑客户价值的卡车与无人机联合配送时变路径优化方法[J]. 计算机应用研究, 2022, 39(10): 2984-2988.
WEN T X, LYU Y H.Research on Time-Varying Route Optimization Method for Truck and UAV Joint Delivery Considering Customer Value[J]. Application Research of Computers, 2022, 39(10): 2984-2988.
[19] 魏洁, 王佳鑫. 生鲜农产品多配送中心连续选址FCM-ISA算法及应用[J]. 运筹与管理, 2019, 28(11): 85-90.
WEI J, WANG J X.FCM-ISA Algorithm for Continuous Location Model of Fresh Produce Multi-Distribution Centers and Application[J]. Operations Research and Management Science, 2019, 28(11): 85-90.
[20] XIAO Y Y, ZHAO Q H, KAKU I, et al.Development of a Fuel Consumption Optimization Model for the Capacitated Vehicle Routing Problem[J]. Computers & Operations Research, 2012, 39(7): 1419-1431.
[21] BREUNIG U, SCHMID V, HARTL R F, et al.A Large Neighbourhood Based Heuristic for Two-Echelon Routing Problems[J]. Computers & Operations Research, 2016, 76: 208-225.
基金
辽宁省社会科学规划基金项目（重点项目）（L20CGL012）
PDF(2330 KB)
渝公网安备 50010702501716号 渝ICP备15012534号-2
