Electric Vehicle Routing Problem (EVRP)

Electric Vehicle

Concepts

Why EVs

Advantage of Electric Vehicle over Internal Combustion Engine Vehicle

Zero emission ³
- Reduces global warming
High energy efficiency ³
- Cheaper
Low noise
Flexibility in grid operation and integration

Categorisation

By Medium

Land
- Road network (growing, uncontrolled env, utilizing route)
  - Car ✅
  - Motorcycle ✅
  - Electric bike (usually hybrid)
- Indoor (growing, controlled env, utilizing route)
- Offroad (utilizing route)
- Rails (very limited)
Water
- Sea
- Water network (limited, utilizing route)
Aerial
- High-altitude
- Low-altitude ✅ (growing, uncontrolled env, utilizing route)
  - Drone delivery
  - Flying car
- Indoor (growing, controlled env, utilizing route)

By Engine

Battery EV ✅
Hybrid EV

By Users

Indivisual
Commercial

Features

Energy recuperation ¹

Historical Show Cases

Prius
Tesla

Market Analysis

EV Distance on One Charge

2024: > 200 km ^{🔗 (opens in a new tab)} ^{🔗 (opens in a new tab)}

Daily Average Commuting Distance

USA 2022: 48.44 km
UK 2020: 32.8 km
Australia 2020: 33.2 km
Worldwide 2021: 25 - 50 km

Users Survey 2022 - Electric Vehicle Council AU

80% of owners charge at home > two times per week
90% of owners charge at public chargers < 1 time per week
89.3% of owners charge at work < 1 time per week
Driving range is not a significant barrier

EV Fleets for Organisational and Business Operations

Potential Use ^{🔗 (opens in a new tab)}

Transportation and logistics
- Company support
- Public transportation
- Ride-hailing
- Food delivery
- Car rental
- Courier
Government and Municipal Services
Emergencies and Disasters
Law enforcement
Construction
HVAC
Oil & gas
Healthcare
Education
Food and Beverage Industry
Utilities and Telecommunications

Procurement

Company-owned
Rented from:
- EV renting company
- Personal collaborator
  - Employee
  - Rented personally

Optimisation Strategies

Route optimisation
Battery swapping station
Fast charging
Vehicle-to-everything schemes
In-vehicle renewable energy generator

EVs Challenges

Limited driving range ¹
- Limited battery capacity ² ³
  - Energy consumption increases with velocity ²
Limited charging stations per electric vehicle ³
- Growing sales of EVs need to be supported by a sufficient number of charging stations
Recharging is time-consuming³
Cost

Future Direction of EVs-related Technologies

Energy Circulation Schemes

Vehicle to Everything
Electric Roads
Solar Electric Vehicle
Hydrogen Cars
Battery swapping station
Fast charging

Form of Vehicle

Low Altitude Aerial Vehicle
- Manned
- Unmanned

Electric Vehicle Fleets

Coordination systems

Electric Vehicle Routing Problem (EVRP)

Based on the previous explanation of EV and recent research in EVRP, EVRP algorithms derived from latest EV business model and technological update.

Primary Target User Group

EV for business and organisational use
EV for apartment and flat residents

Optimisation

Minimising energy consumption ¹ ²
Minimising travel time ² ³
Maximising business process output

Internal Variables

Battery condition
- Usage
  - Energy depletion parameter ¹
  - Velocity-dependent energy usage ²
- Charging
  - Energy recuperation ¹ ² ³
  - Charging time ³
  - Charging method ³
  - Overcharging parameter ¹
  - State of Charge (SoC)
    - Dynamic model of SoC ³
Velocity in time intervals²

External Variables

Energy circulation scheme
- Vehicle to grid
- Electric road
- Charging stop locations ³
- Charging stop types ³
Coordination type
- Single vehicle coordination
- Multi-vehicle coordination

Methods

Djikstra's SP Algorithm ¹
- Bicriteria SP (BSP)
Bellman-Ford SP ¹
Johnson's SP Algorithm ¹
A*
- NAMOA*
- A*, Landmarks, Triangle Inequality - ALT (2005)
- Generalization of A* search ³
Contraction Hierarchies ¹
- Core-ALT (2010)
- Bicriteria extention ³
Pareto Front Multi-objective Optimisation ²
Constrained Shortest Path Route Planning
- Capacity Constrained Routing ³
State of Charge function ³

Datasets

Road network data
- FREE: Open Street Map ¹ ³
- PTV AG ² ³
Elevation data
- SRTM Nasa ¹
- FREE: Shuttle Radar Topography Mission (SRTM) 4.1 from CGIAR Consortium for Spatial Information ³
Energy consumption data
- Passenger Car and Heavy Duty Emission Model (PHEM) - Graz University of Technology ²
Charging station location
- ChargeMap ³
Charging station type (BSS / Supercharge / Regular)
- Custom function based on Uhrig et al.

Implementation Technologies

C++ ¹ ² ³

Research Directions

Multi EVRP
- Coordination systems
- Autonomous EV
- Low-altitude EV
- Energy circulation schemes
  - Vehicle to everything
  - In-vehicle renewable energy generator
    - Solar EV

Machine Learning Approach in Optimisation

References

Journal and Conferences

Website Articles

Research Topics 2011 Optimal Evrp Large Networks