A two‐stage algorithm for vehicle routing problem with charging relief in post‐disaster
Abstract This paper first investigates emergency transportation for power recovery in post‐disaster. The problem is formulated as a mixed‐integer linear programming model called vehicle routing problem with charging relief (VRPCR). The battery state of charge (SoC) implies the working hours that the...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2023-08-01
|
| Series: | IET Intelligent Transport Systems |
| Subjects: | |
| Online Access: | https://doi.org/10.1049/itr2.12344 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850192580197744640 |
|---|---|
| author | Qixing Liu Peng Xu Yuhu Wu Tielong Shen |
| author_facet | Qixing Liu Peng Xu Yuhu Wu Tielong Shen |
| author_sort | Qixing Liu |
| collection | DOAJ |
| description | Abstract This paper first investigates emergency transportation for power recovery in post‐disaster. The problem is formulated as a mixed‐integer linear programming model called vehicle routing problem with charging relief (VRPCR). The battery state of charge (SoC) implies the working hours that the battery can provide. The goal is to make a set of shelters charge before the battery SoC of shelters reaches the minimum bound over time. To this end, a two‐stage algorithm is developed to deal with the problem. In stage I, a reduced road network is obtained from a leading road network by the A‐star search algorithm. Subsequently, to determine the order of power delivery with charging operations at shelters by enhanced genetic algorithm (EGA) in stage II. To evaluate this strategy, the detailed complexity analysis of the three algorithms and results tested on a realistic disaster scenario shows the performance of the A‐star search algorithm for VRPCR that outperforms the Dijkstra and Floyd algorithms. In addition, the EGA is applied to Solomon's benchmarks compared with the state‐of‐the‐art heuristic algorithms, which indicates a better performance of EGA. A real case obtained from a disaster scenario in Ichihara City, Japan is also conducted. Simulation results demonstrate that the method can achieve satisfactory solutions. |
| format | Article |
| id | doaj-art-4be73b93e1e044e1bc5ce893998129f3 |
| institution | OA Journals |
| issn | 1751-956X 1751-9578 |
| language | English |
| publishDate | 2023-08-01 |
| publisher | Wiley |
| record_format | Article |
| series | IET Intelligent Transport Systems |
| spelling | doaj-art-4be73b93e1e044e1bc5ce893998129f32025-08-20T02:14:30ZengWileyIET Intelligent Transport Systems1751-956X1751-95782023-08-011781525154310.1049/itr2.12344A two‐stage algorithm for vehicle routing problem with charging relief in post‐disasterQixing Liu0Peng Xu1Yuhu Wu2Tielong Shen3Key Laboratory of Intelligent Control and Optimization for Industrial Equipment of Ministry of Education, and School of Control Science and Engineering Dalian University of Technology Dalian ChinaKey Laboratory of Intelligent Control and Optimization for Industrial Equipment of Ministry of Education, and School of Control Science and Engineering Dalian University of Technology Dalian ChinaKey Laboratory of Intelligent Control and Optimization for Industrial Equipment of Ministry of Education, and School of Control Science and Engineering Dalian University of Technology Dalian ChinaDepartment of Electrical and Computer Engineering, Department of Mechanical Engineering Sophia University Tokyo JapanAbstract This paper first investigates emergency transportation for power recovery in post‐disaster. The problem is formulated as a mixed‐integer linear programming model called vehicle routing problem with charging relief (VRPCR). The battery state of charge (SoC) implies the working hours that the battery can provide. The goal is to make a set of shelters charge before the battery SoC of shelters reaches the minimum bound over time. To this end, a two‐stage algorithm is developed to deal with the problem. In stage I, a reduced road network is obtained from a leading road network by the A‐star search algorithm. Subsequently, to determine the order of power delivery with charging operations at shelters by enhanced genetic algorithm (EGA) in stage II. To evaluate this strategy, the detailed complexity analysis of the three algorithms and results tested on a realistic disaster scenario shows the performance of the A‐star search algorithm for VRPCR that outperforms the Dijkstra and Floyd algorithms. In addition, the EGA is applied to Solomon's benchmarks compared with the state‐of‐the‐art heuristic algorithms, which indicates a better performance of EGA. A real case obtained from a disaster scenario in Ichihara City, Japan is also conducted. Simulation results demonstrate that the method can achieve satisfactory solutions.https://doi.org/10.1049/itr2.12344optimisationvehicle routing |
| spellingShingle | Qixing Liu Peng Xu Yuhu Wu Tielong Shen A two‐stage algorithm for vehicle routing problem with charging relief in post‐disaster IET Intelligent Transport Systems optimisation vehicle routing |
| title | A two‐stage algorithm for vehicle routing problem with charging relief in post‐disaster |
| title_full | A two‐stage algorithm for vehicle routing problem with charging relief in post‐disaster |
| title_fullStr | A two‐stage algorithm for vehicle routing problem with charging relief in post‐disaster |
| title_full_unstemmed | A two‐stage algorithm for vehicle routing problem with charging relief in post‐disaster |
| title_short | A two‐stage algorithm for vehicle routing problem with charging relief in post‐disaster |
| title_sort | two stage algorithm for vehicle routing problem with charging relief in post disaster |
| topic | optimisation vehicle routing |
| url | https://doi.org/10.1049/itr2.12344 |
| work_keys_str_mv | AT qixingliu atwostagealgorithmforvehicleroutingproblemwithchargingreliefinpostdisaster AT pengxu atwostagealgorithmforvehicleroutingproblemwithchargingreliefinpostdisaster AT yuhuwu atwostagealgorithmforvehicleroutingproblemwithchargingreliefinpostdisaster AT tielongshen atwostagealgorithmforvehicleroutingproblemwithchargingreliefinpostdisaster AT qixingliu twostagealgorithmforvehicleroutingproblemwithchargingreliefinpostdisaster AT pengxu twostagealgorithmforvehicleroutingproblemwithchargingreliefinpostdisaster AT yuhuwu twostagealgorithmforvehicleroutingproblemwithchargingreliefinpostdisaster AT tielongshen twostagealgorithmforvehicleroutingproblemwithchargingreliefinpostdisaster |