- ISSN 0258-2724
- CN 51-1277/U
- EI Compendex
- Scopus
- Indexed by Core Journals of China, Chinese S&T Journal Citation Reports
- Chinese S&T Journal Citation Reports
- Chinese Science Citation Database
| 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, 2025, 60(2): 299-307. doi: 10.3969/j.issn.0258-2724.20230084
|
In the electric truck route planning problem with time windows, electric trucks may need to queue up when they go to charging stations for charging. To study the impact of different charging station configuration schemes on vehicle route planning and system performance, the queuing model was first built to describe the queuing phenomenon at charging stations. Then, a route optimization model was established by considering the power and flow constraints based on the electric truck route planning problem with time windows, with the queuing model of charging stations embedded into the optimization model. The optimization goals included minimizing vehicle power consumption costs, driver’s wages, penalty costs of time windows, and total costs of all charging piles. To solve the model, a hybrid heuristic algorithm combining mileage saving (C-W) and improved large neighborhood search (LNS) was designed, and the system performance metrics of charging stations were obtained by a recursive algorithm. 18 sets of experimental results show that increasing the number of charging piles simultaneously can control the average queuing time of a vehicle for charging within 1–5 minutes and effectively reduce the total cost by 2.6%–21.0%; increasing the number of charging stations can reduce the queuing time but increase the total cost of the entire route; when the customer time window is short, or the service time is long, the change in the number of charging piles has a more significant impact on the satisfaction of the time window.
| [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.
|
| [1] | REN Jianwei, MENG Xiangdong, CHEN Chunhua, ZHANG Jin, ZHANG Xueyan. Methodologies of Pallet Allocation Over Pallet Pool in Intermodal Transportation Network[J]. Journal of Southwest Jiaotong University, 2020, 55(3): 612-619. doi: 10.3969/j.issn.0258-2724.20190340 |
| [2] | DAI Chaohua, LIU Yang, HUANG Chenxi, ZHAO Duo, GUO Ai, CHEN Weirong, LIU Nan. Parameters Optimization for Hybrid Energy Storage System of Electric Vehicles Based on Cross-Entropy Algorithm[J]. Journal of Southwest Jiaotong University, 2020, 55(4): 839-846. doi: 10.3969/j.issn.0258-2724.20190442 |
| [3] | REN Jianwei, CHEN Chunhua, ZHANG Xueyan. Multi-Scenario Optimisation Model for Reusable Logistics Resource Allocation[J]. Journal of Southwest Jiaotong University, 2018, 53(6): 1270-1277. doi: 10.3969/j.issn.0258-2724.2018.06.024 |
| [4] | CHEN Qingshan, XU Yang, HE Xingxing. Heuristic Complete Algorithm for SAT Problem by Using Logical Deduction[J]. Journal of Southwest Jiaotong University, 2017, 30(6): 1224-1232. doi: 10.3969/j.issn.0258-2724.2017.06.025 |
| [5] | MA Liang, GUO Jin, CHEN Guangwei. Constraint Propagation and Heuristics Backtracking Algorithm for Static Wagon-Flow Allocation at a Marshalling Station[J]. Journal of Southwest Jiaotong University, 2014, 27(6): 1116-1122. doi: 10.3969/j.issn.0258-2724.2014.06.027 |
| [6] | ZHANG Jin, WANG Kun. Variational Inequality Model and Algorithm for Stream Line Network Optimization[J]. Journal of Southwest Jiaotong University, 2011, 24(3): 481-487. doi: 10.3969/j.issn.0258-2724.2011.03.021 |
| [7] | ZHANG Jin, WANG Kun. Stream Line Optimization Model with Matching Degree between Logistics Supply and Demand as Objective Function[J]. Journal of Southwest Jiaotong University, 2010, 23(2): 324-330. doi: 10. 3969/ j. issn. 0258-2724. |
| [8] | WANG Zhanzhong, ZHENG Jiabin, XU Hongguo, WU Zhengmei. Optimization of Logistics Buffer Zone Layout in Manufacturing Industry[J]. Journal of Southwest Jiaotong University, 2010, 23(3): 476-481. doi: 10. 3969/ j. issn. 0258-2724. |
| [9] | GAO Qingping, YAN Qipeng, LIN Yu, LUO Yu. Bi-level Programming for Optimal Inventory Control with Offsetting Replenishment Cycles[J]. Journal of Southwest Jiaotong University, 2008, 21(6): 703-708. |
| [10] | ZHANG Jianyong, LI Jun, GUO Yaohuang. Insertion Heuristic Algorithm for Dynamic Vehicle Routing Problem with Fuzzy Due-Time[J]. Journal of Southwest Jiaotong University, 2008, 21(1): 107-113. |
| [11] | TANG Yinying, PENG Qiyuan, SHI Yufeng. Compact Layout of Logistics Facilities Based on O-Tree Representation[J]. Journal of Southwest Jiaotong University, 2007, 20(4): 499-504. |
| [12] | LI Zongping, JIANG Sai. Client Grouping in Distribution System Optimization[J]. Journal of Southwest Jiaotong University, 2006, 19(5): 594-598. |
| [13] | SUN Chaoyuan, PENG Qiyuan, CHEN Xu. DEA Model for Logistics Activity Cost Control of Enterprises[J]. Journal of Southwest Jiaotong University, 2006, 19(5): 649-652. |
| [14] | ZHAO Yi, YING Chuan-zhong, PU Yun. Facility LocationM odel for Multi-levelReturned Logistics and ItsAlgorithm[J]. Journal of Southwest Jiaotong University, 2005, 18(4): 530-534. |
| [15] | ZHANG Jin, MA Xiao-lai, DU Wen. Nonlinear Programming Model and Algorithm of Two-Layer Distribution Network Based on Integrated Transit-Inventory Concept[J]. Journal of Southwest Jiaotong University, 2004, 17(3): 301-305. |
| [16] | FENGHao, HEHong-yun, MI Zu-qiang. Nonlinear System Identification with Recurrent Neural Network Based on Genetic Algorithm[J]. Journal of Southwest Jiaotong University, 2002, 15(4): 404-407. |
| [17] | LIBing, YEHuai-zhen. A Heuristic Layout Restriction Algorithm for Solving Two-Dimensional Rectangular Layout Loading Problems[J]. Journal of Southwest Jiaotong University, 2002, 15(4): 443-447. |
| [18] | XIEBing-lei, LIJun, LIUJian-xin. A Heuristic Genetic Algorithm for the Travelling Salesman Problem with Time Restraints[J]. Journal of Southwest Jiaotong University, 2001, 14(2): 211-213. |
| [19] | LIUHai-yan, LI Zong-ping, YEHuai-zhen. Logistics Distribution Center Allocation Model[J]. Journal of Southwest Jiaotong University, 2000, 13(3): 311-314. |
Figures(4) / Tables(1)
HU Lu, LE Shitong, ZHU Juanxiu. Electric Truck Route Planning Considering Multiple Charging Pile Queues and Time Windows[J]. Journal of Southwest Jiaotong University, 2025, 60(2): 299-307. doi: 10.3969/j.issn.0258-2724.20230084
DownLoad:
