考虑时变速度和动态需求的电动车辆路径问题  

Electric Vehicle Routing Problem Considering Time-dependent Speed and Dynamic Demand

作　　者：贾永基[1] 丁慧娜 李嘉 杨东[1] JIA Yongji;DING Huina;LI Jia;YANG Dong(Glorious Sun School of Business&Management,Donghua University,Shanghai 200051,China)

机构地区：[1]东华大学旭日工商管理学院,上海200051

出　　处：《工业工程与管理》2022年第2期59-66,共8页Industrial Engineering and Management

基　　金：上海市哲学社会科学规划基金资助项目(2018BGL018);中央高校基本科研专项资金资助项目(2232018H-07)。

摘　　要：针对时变速度车辆路径问题,考虑动态客户需求并引入电动车替代燃油车。首先采用“wait-and-see”策略对动态需求进行建模,并建立其静态子问题的混合整数规划模型。然后提出了基于时域划分的求解算法,在每个时域的结束时刻处理动态需求,并利用模拟退火结合变邻域搜索的混合启发式算法来求解,从而实现电动车辆路径的循环优化与更新。最后设计了多种类型和规模的测试算例,测试结果表明本文算法既可以有效求解静态问题,也可以实现动态新增需求的实时处理。Aiming at the vehicle routing problem with time-dependent speed,the dynamic demands of customers were considered and electric vehicles were introduced to replace fuel vehicles.The“wait-andsee”strategy was first adopted to model the dynamic demands and the mixed integer programming model of its static sub-problem was established.Then a solution approach based on time horizon division was proposed,which could deal with the dynamic demand at the end of each time horizon.The simulated annealing algorithm combined with variable neighbourhood search was proposed to solve the static subproblem,so as to achieve the periodic optimization and update of routes.Finally,various types and scales of test cases were designed.The test results show that the algorithm can effectively solve the static problem and realize real-time processing of dynamic demands.

关 键 词：电动车辆路径问题 时变速度 动态需求 时域划分 

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