Comparison of Optimisation Techniques for the Electric Vehicle Scheduling Problem
The Electric Vehicle Scheduling Problem (E-VSP) addresses the challenge of efficiently assigning predetermined trips to an electric vehicle fleet while accounting for charging infrastructure and battery range constraints. Despite numerous optimisation approaches proposed in the literature, comparati...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-05-01
|
| Series: | Smart Cities |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2624-6511/8/3/85 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849425874056642560 |
|---|---|
| author | Jacques Wüst Marthinus Johannes Booysen James Bekker |
| author_facet | Jacques Wüst Marthinus Johannes Booysen James Bekker |
| author_sort | Jacques Wüst |
| collection | DOAJ |
| description | The Electric Vehicle Scheduling Problem (E-VSP) addresses the challenge of efficiently assigning predetermined trips to an electric vehicle fleet while accounting for charging infrastructure and battery range constraints. Despite numerous optimisation approaches proposed in the literature, comparative analyses of these methods remain scarce, with researchers typically focusing on developing novel algorithms rather than evaluating existing algorithms. Moreover, studies often employ convenient assumptions tailored to improve the performance of their optimisation technique. This study presents a comprehensive comparison of several optimisation techniques (mixed integer linear programming (MILP) using the branch-and-cut algorithm, metaheuristics, and heuristics) applied to the E-VSP under identical assumptions and constraints. The techniques are evaluated across multiple metrics, including solution quality, computational efficiency, and implementation complexity. Findings reveal that the branch-and-cut algorithm cannot solve instances with more than 10 trips in a reasonable time. Among metaheuristics, only genetic algorithms and simulated annealing demonstrate competitive performance, but both struggle with instances exceeding 100 trips. Our recently developed heuristic algorithm consistently found better solutions in significantly shorter computation times than the metaheuristics due to its ability to efficiently navigate the solution space while respecting the unique constraints of the E-VSP. |
| format | Article |
| id | doaj-art-3f63daa85d8a45fab3a6480331023f8c |
| institution | Kabale University |
| issn | 2624-6511 |
| language | English |
| publishDate | 2025-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Smart Cities |
| spelling | doaj-art-3f63daa85d8a45fab3a6480331023f8c2025-08-20T03:29:38ZengMDPI AGSmart Cities2624-65112025-05-01838510.3390/smartcities8030085Comparison of Optimisation Techniques for the Electric Vehicle Scheduling ProblemJacques Wüst0Marthinus Johannes Booysen1James Bekker2Department of Electrical and Electronic Engineering, Faculty of Engineering, Stellenbosch University, Stellenbosch 7600, South AfricaDepartment of Electrical and Electronic Engineering, Faculty of Engineering, Stellenbosch University, Stellenbosch 7600, South AfricaDepartment of Industrial Engineering, Faculty of Engineering, Stellenbosch University, Stellenbosch 7600, South AfricaThe Electric Vehicle Scheduling Problem (E-VSP) addresses the challenge of efficiently assigning predetermined trips to an electric vehicle fleet while accounting for charging infrastructure and battery range constraints. Despite numerous optimisation approaches proposed in the literature, comparative analyses of these methods remain scarce, with researchers typically focusing on developing novel algorithms rather than evaluating existing algorithms. Moreover, studies often employ convenient assumptions tailored to improve the performance of their optimisation technique. This study presents a comprehensive comparison of several optimisation techniques (mixed integer linear programming (MILP) using the branch-and-cut algorithm, metaheuristics, and heuristics) applied to the E-VSP under identical assumptions and constraints. The techniques are evaluated across multiple metrics, including solution quality, computational efficiency, and implementation complexity. Findings reveal that the branch-and-cut algorithm cannot solve instances with more than 10 trips in a reasonable time. Among metaheuristics, only genetic algorithms and simulated annealing demonstrate competitive performance, but both struggle with instances exceeding 100 trips. Our recently developed heuristic algorithm consistently found better solutions in significantly shorter computation times than the metaheuristics due to its ability to efficiently navigate the solution space while respecting the unique constraints of the E-VSP.https://www.mdpi.com/2624-6511/8/3/85E-VSPoptimisationmixed-integer linear programmingheuristicsmetaheuristic |
| spellingShingle | Jacques Wüst Marthinus Johannes Booysen James Bekker Comparison of Optimisation Techniques for the Electric Vehicle Scheduling Problem Smart Cities E-VSP optimisation mixed-integer linear programming heuristics metaheuristic |
| title | Comparison of Optimisation Techniques for the Electric Vehicle Scheduling Problem |
| title_full | Comparison of Optimisation Techniques for the Electric Vehicle Scheduling Problem |
| title_fullStr | Comparison of Optimisation Techniques for the Electric Vehicle Scheduling Problem |
| title_full_unstemmed | Comparison of Optimisation Techniques for the Electric Vehicle Scheduling Problem |
| title_short | Comparison of Optimisation Techniques for the Electric Vehicle Scheduling Problem |
| title_sort | comparison of optimisation techniques for the electric vehicle scheduling problem |
| topic | E-VSP optimisation mixed-integer linear programming heuristics metaheuristic |
| url | https://www.mdpi.com/2624-6511/8/3/85 |
| work_keys_str_mv | AT jacqueswust comparisonofoptimisationtechniquesfortheelectricvehicleschedulingproblem AT marthinusjohannesbooysen comparisonofoptimisationtechniquesfortheelectricvehicleschedulingproblem AT jamesbekker comparisonofoptimisationtechniquesfortheelectricvehicleschedulingproblem |