考虑众包场景的电动车动态需求车辆路径问题  

Electric vehicle routing problem with dynamic demand in context of crowdsourcing

作　　者：杜千 南丽君 陈彦如[1] DU Qian;NAN Lijun;CHEN Yanru(School of Economics Management,Southwest Jiaotong University,Chengdu 610031,China)

机构地区：[1]西南交通大学经济管理学院,四川成都610031

出　　处：《计算机集成制造系统》2024年第7期2588-2607,共20页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(71771190)。

摘　　要：针对企业自有车辆和社会车辆共同取送货的场景,以及国家节能环保的政策背景,考虑分时电价、部分充电、软时间窗、以及动态需求等因素,以最小化配送总成本为目标,建立考虑众包场景的电动车动态需求车辆路径问题(EDDVRP-CD)的两阶段整数规划模型。考虑动态需求的时效性,设计了启发式算法——改进的禁忌自适应大规模邻域搜索算法(IALNS-TS),增加了新的删除算子和修复算子,同时提出了加速策略。分别与两种算法——自适应大规模邻域搜索算法(ALNS)以及禁忌搜索算法(TS)进行对比,通过大量算例验证了IALNS-TS算法能够快速响应动态需求,并有效降低总配送费用。Based on joint picking up and delivery by company's vehicles and social vehicles and national policies of environmental protection,a two-stage integer programming model was developed considering the Electric Dynamic Demand based Vehicle Routing Problem in the context of Crowdsourcing(EDDVRP-CD)with the goal of minimizing the total cost of delivery.Factors of time-of-use electricity price,partial charging,soft time windows and dynamic demand were simultaneously considered.Aiming at quick response to dynamic demand,an Improved Adaptive Large-scale Neighborhood Search and Tabu Search algorithm(IALNS-TS)was proposed with new destroy operators and repair operators developed,and an acceleration strategy was designed.The IALNS-TS was compared with Adaptive Large-scale Neighborhood Search algorithm(ALNS)and Tabu Search algorithm(TS).Based on extensive experiments,it proved that IALNS-TS algorithm could quickly respond to dynamic demands and effectively reduce the total distribution cost.

关 键 词：众包模式 分时电价 电动车车辆路径问题 动态需求 改进的禁忌自适应大规模邻域搜索算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]