主管：中国科学院
主办：中国优选法统筹法与经济数学研究会
　　　中国科学院科技战略咨询研究院
中国管理科学

中国管理科学 ›› 2026, Vol. 34 ›› Issue (4): 144-155.doi: 10.16381/j.cnki.issn1003-207x.2024.0142cstr: 32146.14.j.cnki.issn1003-207x.2024.0142

• • 上一篇    下一篇

带取货点选择的电动车取送货路径优化的自适应大邻域搜索算法

吴廷映1,2,3, 刘兵兵1,2,3(), 余玉刚1,2,3   

  1. 1.中国科学技术大学管理学院，安徽 合肥 230026
    2.中国科学技术大学国际金融研究院，安徽 合肥 230601
    3.中国科学技术大学安徽省数智供应链重点实验室，安徽 合肥 230601
  • 收稿日期:2024-01-22 修回日期:2024-05-15 出版日期:2026-04-25 发布日期:2026-03-27
  • 通讯作者: 刘兵兵 E-mail:lbb1224@ustc.edu.cn
  • 基金资助:
    国家自然科学基金项目(U25A20381);国家自然科学基金项目(72542005);国家自然科学基金项目(72091215);国家自然科学基金项目(72091210);中央高校基本科研业务费专项资金项目(WK2040000037)

An Adaptive Large Neighborhood Search Algorithm for Electric Vehicle Pickup-and-Delivery Routing Problem with Pickup-Points Selection

Tingying Wu1,2,3, Bingbing Liu1,2,3(), Yugang Yu1,2,3   

  1. 1.School of Management，University of Science and Technology of China，Hefei 230026，China
    2.International Institute of Finance，University of Science and Technology of China，Hefei 230601，China
    3.Anhui Provincial Key Laboratory of Digital Intelligence Supply Chain，University of Science and Technology of China，Hefei 230601，China
  • Received:2024-01-22 Revised:2024-05-15 Online:2026-04-25 Published:2026-03-27
  • Contact: Bingbing Liu E-mail:lbb1224@ustc.edu.cn

RichHTML

2

PDF (PC)

39

摘要：

在线上电商与线下门店相结合的消费模式下，消费者购买的商品可由线下多家门店同时提供，导致货物取货点不固定，配送货物时需要同时对取货点选择和取送货路径进行决策。因此，针对取货点不固定的情形，本文研究了带有取货点选择的电动车取送货路径优化问题。通过刻画取货点和客户送货点的时间窗、充电时间和电池容量等约束，建立了以配送总成本最小为目标的混合整数规划模型，进一步针对模型特点设计了改进的自适应大邻域搜索算法。为扩大问题可行解的搜索空间，针对充电站节点和取送货节点专门设计了多种破坏算子和修复算子；使用自适应算子选择策略以提高搜索效率。本文首次提出贪婪随机自适应修复算子和最小生成树破坏算子。通过综合算例分析，验证了所提算法的有效性和优越性，并深入分析了取货点选择对总成本的影响。本文研究结果不仅丰富了取送货电动车路径优化的方法论研究，也为物流企业设计配送方案提供了决策参考依据。

关键词: 取送货, 取货点选择, 破坏算子, 修复算子, 自适应大规模邻域搜索

Abstract:

In the consumption mode of combining online e-commerce and offline stores， the goods purchased by consumers can be provided by multiple offline stores at the same time， which leads to the unfixed pickup point of goods. Therefore， it is necessary to make decisions on the selection of pickup points and the delivery routing when distributing goods. The electric vehicle pickup and delivery problem with pickup-point selection in the case of unfixed pickup point is studied. After characterizing the constraints such as time window， charging time and battery capacity of the pickup point and the customer delivery point， a mixed integer programming formulation is formulated to minimize the total distribution cost. According to the characteristics of the model， an improved adaptive large neighborhood search algorithm is developed. In order to expand the search space of feasible solution， a variety of destroy operators and repair operators are designed for charging station nodes and pickup-and-delivery nodes， and a new solution acceptance criterion based on simulated annealing is used to improve the search efficiency. In this paper， the greedy random adaptive repair operator and the minimum spanning tree destruction operator are first proposed. The effectiveness and superiority of the proposed algorithm are verified by a comprehensive numerical experiment analysis， The numerical results show that： （1） The influence of the selection of the pickup points on the total cost and the improvement effect of the proposed new operators on the algorithm are emphatically analyzed. （2） Considering the selection of pickup points can greatly reduce the number of vehicles and delivery costs. When logistics enterprise operators plan the route of pickup and delivery vehicles， the selection of pickup and delivery points should be made at the same time as the planning of the pickup and delivery path， rather than first deciding the pickup point and then optimizing the pickup and delivery routes. The selection of pickup points and the pickup and delivery routing are isolated into two independent issues for decision-making.The research results of this paper not only enrich the study of the route optimization of electric vehicles for pickup and delivery， but also provide a decision-making reference for logistics enterprises to design distribution and delivery schemes.

Key words: pickup and delivery, pickup-point selection, destroy operator, repair operator, adaptive large neighborhood search

中图分类号: