Processing math: 100%
  • ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

考虑多充电桩排队和时间窗的电动货车路径规划

胡路 乐诗彤 朱娟秀

刘洋, 邱忠平, 孟涛, 龚正君, 王东梅, 樊超. 高效产纤维素酶曲霉生物转化纤维素乙醇[J]. 西南交通大学学报, 2020, 55(1): 225-230. doi: 10.3969/j.issn.0258-2724.20180477
引用本文: 胡路, 乐诗彤, 朱娟秀. 考虑多充电桩排队和时间窗的电动货车路径规划[J]. 西南交通大学学报. doi: 10.3969/j.issn.0258-2724.20230084
LIU Yang, QIU Zhongping, MENG Tao, GONG Zhengjun, WANG Dongmei, FAN Chao. Biotransformation of Bioethanol from Lignocellulose by High Yield Cellulase-Producing Aspergillus[J]. Journal of Southwest Jiaotong University, 2020, 55(1): 225-230. doi: 10.3969/j.issn.0258-2724.20180477
Citation: HU Lu, LE Shitong, ZHU Juanxiu. Electric Truck Route Planning Considering Multiple Charging Pile Queues and Time Windows[J]. Journal of Southwest Jiaotong University. doi: 10.3969/j.issn.0258-2724.20230084

考虑多充电桩排队和时间窗的电动货车路径规划

doi: 10.3969/j.issn.0258-2724.20230084
基金项目: 国家自然科学基金项目(62203367)
详细信息
    作者简介:

    胡路(1985—),男,副教授,博士,研究方向为共享交通和城市轨道交通,E-mail:hulu@swjtu.edu.cn

    通讯作者:

    朱娟秀(1989—),女,讲师,博士,研究方向为物流与交通系统建模与优化,E-mail:1220190011@mail.xhu.edu.cn

  • 中图分类号: U492

Electric Truck Route Planning Considering Multiple Charging Pile Queues and Time Windows

  • 摘要:

    在带时间窗的电动货车路径规划问题(EVRPTW)中,电动货车(EV)在前往充电站充电时可能需要排队. 为研究不同充电站配置方案对车辆路径和系统性能的影响,首先构建排队模型,刻画充电站中的排队现象;在EVRPTW基础上,综合考虑电量和流量约束,建立路径优化模型,并将充电站排队模型嵌入其中;优化目标包括最小化车辆耗电成本、司机工资、时间窗惩罚成本、充电桩总成本;为求解该模型,提出一种结合节约里程(C-W)和改进大邻域搜索(LNS)的混合启发式算法,其中,充电站的系统性能指标采用递归算法获得. 18组实验结果表明:同步增加充电桩数量可将车辆单次充电的平均排队时间控制在1~5 min,并有效减少2.6%~21.0%的总成本;增加充电站数量可缩短排队时间,但会增加整体路径总成本;当客户时间窗较短或服务时间较长时,充电桩数量变化对时间窗满足的影响更为显著.

     

  • 图 1  算法流程

    Figure 1.  Algorithm flowchart

    图 2  不同充电桩数量的影响

    Figure 2.  Impact of different numbers of charging piles

    图 3  不同充电站数量的影响

    Figure 3.  Impact of different numbers of charging stations

    图 4  优化解路径对比

    Figure 4.  Optimized solution path comparison

    表  1  符号说明

    Table  1.   Symbol descriptions

    符号 说明 符号 说明
    di,j 顶点i到顶点j的行驶距离 cs 所有充电站安装充电桩的总费用
    ti,j 顶点i到顶点j的行驶时间 xi,j  当顶点i与顶点j在有向图中的路径被访问时为1,否则为0
    qi 客户点i的需求 yai 到达顶点i时剩余电量
    si 客户点i的服务时间 ydi 离开顶点i时剩余电量
    ei 客户点i的最早服务时间 vi 到达顶点i时的迟到时长
    li 客户点i的最晚服务时间 ai 到达顶点iiV0,n+1的时间
    G0 车辆装载容量 fi  在返回仓库之前,以顶点i为最后访问节点的路线所花费的总时间
    Q 车辆电池容量 ui 抵达顶点i时的剩余货物容量
    g 电池充电速率 wi,k  顶点iiF进行第k次所服务车辆需要的等待时间
    h 电池单位距离消耗速率 zi,k  顶点iiF进行第k次所服务车辆需要的充电时间
    ce 每单位距离消耗的电量成本 ai,k 顶点iiFk次服务的车辆到达时间
    cp 每单位时间惩罚成本 yai(ai,k) 当车辆到达顶点i时间为ai,k时的剩余电量
    cf  每个顶点的运行成本,包括维护、购置成本以及在客户点工作的成本 wi,k(ai,k) 当车辆到达顶点i时间为ai,k时的等待时间
    cd 每单位时间司机工资
    下载: 导出CSV
  • [1] 袁庆达,杜文,周再玲. 带软时间窗的混合车队车辆路线问题的模型和算法研究[J]. 西南交通大学学报,2001,36(4): 401-406. doi: 10.3969/j.issn.0258-2724.2001.04.015

    YUAN Qingda, DU Wen, ZHOU Zailing. Model and algorithms for mixed fleet vehicle routing problem with soft time windows[J]. Journal of Southwest Jiaotong University, 2001, 36(4): 401-406. doi: 10.3969/j.issn.0258-2724.2001.04.015
    [2] SCHNEIDER M, STENGER A, GOEKE D. The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation Science, 2014, 48(4): 500-520. doi: 10.1287/trsc.2013.0490
    [3] DESAULNIERS G, ERRICO F, IRNICH S, et al. Exact algorithms for electric vehicle-routing problems with time windows[J]. Operations Research, 2016, 64(6): 1388-1405. doi: 10.1287/opre.2016.1535
    [4] GOEKE D. Granular tabu search for the pickup and delivery problem with time windows and electric vehicles[J]. European Journal of Operational Research, 2019, 278(3): 821-836. doi: 10.1016/j.ejor.2019.05.010
    [5] PELLETIER S, JABALI O, LAPORTE G. The electric vehicle routing problem with energy consumption uncertainty[J]. Transportation Research Part B: Methodological, 2019, 126: 225-255. doi: 10.1016/j.trb.2019.06.006
    [6] CORTÉS-MURCIA D L, PRODHON C, MURAT AFSAR H. The electric vehicle routing problem with time windows, partial recharges and satellite customers[J]. Transportation Research Part E: Logistics and Transportation Review, 2019, 130: 184-206. doi: 10.1016/j.tre.2019.08.015
    [7] DOPPSTADT C, KOBERSTEIN A, VIGO D. The hybrid electric vehicle–traveling salesman problem with time windows[J]. European Journal of Operational Research, 2020, 284(2): 675-692. doi: 10.1016/j.ejor.2019.12.031
    [8] KESKIN M, ÇATAY B, LAPORTE G. A simulation-based heuristic for the electric vehicle routing problem with time windows and stochastic waiting times at recharging stations[J]. Computers & Operations Research, 2021, 125: 105060.1-105060.15.
    [9] YANG S Y, NING L J, TONG L C, et al. Optimizing electric vehicle routing problems with mixed backhauls and recharging strategies in multi-dimensional representation network[J]. Expert Systems with Applications, 2021, 176: 114804.1-114804.48.
    [10] YAO C Q, CHEN S B, YANG Z Y. Joint routing and charging problem of multiple electric vehicles: a fast optimization algorithm[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(7): 8184-8193. doi: 10.1109/TITS.2021.3076601
    [11] KESKIN M, ÇATAY B. Partial recharge strategies for the electric vehicle routing problem with time windows[J]. Transportation Research Part C: Emerging Technologies, 2016, 65: 111-127. doi: 10.1016/j.trc.2016.01.013
    [12] 葛显龙,竹自强. 带软时间窗的电动车辆路径优化问题[J]. 工业工程与管理,2019,24(4): 96-104,112.

    GE Xianlong, ZHU Ziqiang. The electric vehicles routing problem with soft time window[J]. Industrial Engineering and Management, 2019, 24(4): 96-104,112.
    [13] XIAO Y Y, KONAK A. The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion[J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 88: 146-166. doi: 10.1016/j.tre.2016.01.011
    [14] XU Z T, ELOMRI A, POKHAREL S, et al. A model for capacitated green vehicle routing problem with the time-varying vehicle speed and soft time windows[J]. Computers & Industrial Engineering, 2019, 137: 106011.1-106011.14.
    [15] ZULVIA F E, KUO R J, NUGROHO D Y. A many-objective gradient evolution algorithm for solving a green vehicle routing problem with time windows and time dependency for perishable products[J]. Journal of Cleaner Production, 2020, 242: 118428.1-118428.14.
    [16] MONTOYA A, GUÉRET C, MENDOZA J E, et al. The electric vehicle routing problem with nonlinear charging function[J]. Transportation Research Part B: Methodological, 2017, 103: 87-110. doi: 10.1016/j.trb.2017.02.004
    [17] ZUO X R, XIAO Y Y, YOU M, et al. A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function[J]. Journal of Cleaner Production, 2019, 236: 117687.1-117687.18.
    [18] FROGER A, MENDOZA J E, JABALI O, et al. Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions[J]. Computers & Operations Research, 2019, 104: 256-294.
    [19] POONTHALIR G, NADARAJAN R. Green vehicle routing problem with queues[J]. Expert Systems with Applications, 2019, 138: 112823.1-112823.18.
    [20] KESKIN M, LAPORTE G, ÇATAY B. Electric vehicle routing problem with time-dependent waiting times at recharging stations[J]. Computers & Operations Research, 2019, 107: 77-94.
    [21] SHAW P. Using constraint programming and local search methods to solve vehicle routing problems[M]// GOEBEL R, WAHLSTER W, ZHOU Z H. Lecture notes in computer science. Berlin:Springer, 1998:417-431.
    [22] 刘小兰,郝志峰,汪国强,等. 有时间窗的车辆路径问题的近似算法研究[J]. 计算机集成制造系统,2004,10(7): 825-831. doi: 10.3969/j.issn.1006-5911.2004.07.019

    LIU Xiaolan, HAO Zhifeng, WANG Guoqiang, et al. Improved large neighborhood search algorithm for vehicle routing problem with time windows[J]. Computer Integrated Manufacturing Systems, 2004, 10(7): 825-831. doi: 10.3969/j.issn.1006-5911.2004.07.019
    [23] SINTEF Digital. Transportation optimization portal [DB/OL]. (2008-02-27)[2023-02-19]. https://www.sintef.no/projectweb/top/vrptw.
    [24] KESKIN M, ÇATAY B. A matheuristic method for the electric vehicle routing problem with time windows and fast chargers[J]. Computers & Operations Research, 2018, 100: 172-188.
    [25] EMEÇ U, ÇATAY B, BOZKAYA B. An adaptive large neighborhood search for an E-grocery delivery routing problem[J]. Computers & Operations Research, 2016, 69: 109-125.
  • 加载中
图(4) / 表(1)
计量
  • 文章访问数:  157
  • HTML全文浏览量:  67
  • PDF下载量:  26
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-03-02
  • 修回日期:  2023-07-02
  • 网络出版日期:  2024-11-07

目录

    /

    返回文章
    返回