Hydrogen Vehicle Routing Problem with Time Windows (HVRPTW) – Projection
1. Energy Consumption Model for HVRPTW
In the Hydrogen Vehicle Routing Problem (HVRP) literature, most studies assume that energy consumption is proportional to the traveled distance [4] , [3]). However, this simplifying assumption deviates from real-world vehicle behavior, as it ignores dynamic factors that significantly influence energy and hydrogen consumption.
To better represent real operating conditions of fuel cell electric vehicles (FCEVs), we propose an energy consumption model based on the vehicle’s longitudinal dynamics. Unlike distance-only approaches, this model incorporates several physical and operational parameters, including:
Total vehicle mass (including empty weight and carried load)
Road slope (grade)
Travel speed
Acceleration and deceleration phases
Number of intermediate stops (traffic lights, intersections, congestion, slowdowns, etc.)
Characteristics of the electric drivetrain, especially efficiency factors
Energy recovery through regenerative braking
Type of road network
2. Base Benchmark
Given the limited number of hydrogen refueling stations [7] and the absence of a standard benchmark for the HVRPTW, we assume that refueling occurs only at the depot. Consequently, the problem becomes close to the classical VRPTW, with the additional constraint of limited hydrogen vehicle autonomy.
The most widely used benchmark instances for the Vehicle Routing Problem with Time Windows (VRPTW) are the Solomon instances. They consist of 56 instances with a single depot and 100 customers, each defined by demand, time windows, and service times, under vehicle capacity and route duration constraints.
Key characteristics:
Each instance is defined on a synthetic 100 × 100 grid [5]
Speed is normalized so that 1 distance unit equals 1 time unit; thus, distance, travel time, and cost are equivalent [8])
The depot also has a time window, and vehicles must complete routes within it [8])
Distances between customers are computed using Euclidean distance [8])
No explicit energy consumption model is defined in these instances, as this concept was introduced later [11])
2.1 Instance Classes
Class
Description of Customer Distribution
Service Time
C
Clustered customers
90 units
R
Randomly distributed (uniform)
10 units
RC
Mixed (clustered + random)
10 units
All instances within a class share the same customer locations.
To use the Solomon (1987) [11]) instances in our optimization model, we adapted the benchmark by enriching it with additional parameters required to compute energy consumption on each arc.
The main objective is to transform the original benchmark, which consists of abstract Cartesian coordinates without any real geographical meaning, into a realistic road network representation. This enables the computation of hydrogen vehicle energy consumption.
3.1 Definition of the Projection Geographical Area
Projection City
The city of Lyon was selected as the projection area due to its role as one of the main logistics and economic hubs in France, characterized by high urban and suburban mobility demand [1]).
Its road network includes a wide variety of infrastructures, making it suitable for reproducing realistic delivery conditions.
Moreover, Lyon has a diverse topography, with hills and significant elevation changes. This altimetric heterogeneity is particularly relevant for this study, as the energy consumption model explicitly accounts for the effect of slopes on vehicle energy demand [2]).
Projection Area
Lyon is approximately located at:
Latitude ≈ 45.75
Longitude ≈ 4.83
We define a rectangular bounding box covering most of the Lyon metropolitan area, including the city center and part of the surrounding suburbs:
Latitude range: [45.72 ; 45.80]
Longitude range: [4.79 ; 4.90]
3.2 Normalization of Solomon Coordinates
Since Solomon instance coordinates are artificial, they must first be transformed into a homogeneous distribution in [0,1] to allow a controlled and consistent projection onto the Lyon geographic area.
For each instance, we compute:
Each coordinate is then normalized as:
3.3 Affine Transformation to the City of Lyon
The affine transformation resizes the dataset while preserving geometric proportions and spatial relationships between points.
For each coordinate, we apply:
3.4 Correction of Projected Coordinates
After projection, some customers may end up located in unrealistic positions (e.g., parks, buildings, rivers such as the Rhône or the Saône). To address this issue, we use the OSRM (OpenStreetMap Routing Machine) API to snap each point to the nearest road segment.
For each customer (i):
We compute:
where:
: a point on the road network
: distance between the two points
: argument minimizing the distance
The final corrected position is:
These snapped coordinates become the official customer locations.
Finally, the original Solomon instance coordinates are replaced with these projected coordinates to generate the new adapted datasets.
Example
C101_200_coords.csv
Texte alternatif
3.5 Benchmark Enrichment
The projection of customers onto a real road network provides geographically consistent coordinates within the urban environment of Lyon. However, this information alone is not sufficient to compute hydrogen vehicle energy consumption.
For this reason, the Solomon benchmark was enriched by generating a second file (JSON format) containing detailed characteristics of each arc connecting two customers.
For each node pair (i, j), the following information is computed and stored:
Field
Level
Type
Description
from_node
arc
int
Origin node index
to_node
arc
int
Destination node index
distance_euclidean_m
arc
float
Euclidean distance between nodes (m)
distance_road_m
arc
float
Road distance computed using OSRM (m)
duration_s
arc
float
Total estimated travel time from OSRM (s)
travel_time_min
arc
float
Travel time on the arc (min)
road_type
arc
str
Road type extracted from OpenStreetMap (“highway” classification, e.g., residential road)
speed_limit_kmh
arc
float
Speed limit (km/h)
nb_stops
arc
int
Number of stops (traffic lights, stop signs, pedestrian crossings, mini-roundabouts, and other traffic-calming devices) along the arc extracted from OpenStreetMap
n_segments
arc
int
Number of segments (nb_stops + 1)
v_peak_kmh
arc
float
Maximum reached speed (km/h)
has_cruise
arc
bool
Indicates whether a cruising phase exists
a_acc_ms2
arc
float
Acceleration computed from speed limit (m/s²)
a_dec_ms2
arc
float
Deceleration computed from speed limit (m/s²)
d_acc_m
arc
float
Acceleration phase distance (m)
d_dec_m
arc
float
Deceleration phase distance (m)
t_acc_s
arc
float
Acceleration phase duration (s)
t_dec_s
arc
float
Deceleration phase duration (s)
segments
arc
list
List of kinematic segments
segments[s].s
segment
int
Segment index
segments[s].theta_acc
segment
list[float]
Road slope angles during acceleration phase (rad)
segments[s].theta_dec
segment
list[float]
Road slope angles during deceleration phase (rad)
segments[s].cruise_samples
segment
list[obj]
Cruise phase samples
cruise_samples[k].dk
cruise
float
Sub-segment length (m)
cruise_samples[k].theta
cruise
float
Road slope angle at midpoint (rad)
Acceleration Model
Due to the lack of experimental data on acceleration and deceleration profiles for light-duty fuel cell electric vehicles (FCEVs), we use values reported for battery electric vehicles (BEVs) with similar characteristics. This substitution is justified by the close architectural similarity between both technologies:
A BEV uses an electric motor, battery pack, and controller, while a FCEV (or fuel cell electric vehicle) uses the same electric drivetrain architecture, except that energy is supplied by a hydrogen fuel cell instead of a rechargeable battery [6] , [9].
Longitudinal dynamics follow Newton’s second law regardless of powertrain type, where the traction force required to overcome resistances and produce acceleration is determined by the vehicle mass (m) and motor torque, which depends on wheel radius [10].
[3] Abibou, M., et al. (2024). The Hydrogen Vehicle Routing Problem with Time Windows: Formulations and distance-proportional approximations. European Journal of Operational Research.
[4] Abibou, M., et al. (2025). Optimizing green logistics: Models and metaheuristics for hydrogen fleet deployment. Computers & Operations Research, 164, 106-121.
[5] Gendreau, M., & Tarantilis, C. D. (2010). Managing Bio-inspired and Metaheuristic Algorithms for Vehicle Routing Problems. In Managing Green Logistics, Springer, pp. 115-142.
[6] Gondal, I. A., et al. (2018). Comparative Review of Energy Drivetrains: Fuel Cell Electric Vehicles versus Battery Electric Vehicles. International Journal of Hydrogen Energy, 43(11), 5912-5929.
[7] Guo, X., et al. (2025). Strategic Planning and Location Optimization for Hydrogen Refueling Infrastructure under Autonomy Constraints. Transportation Research Part E: Logistics and Transportation Review, 182, 103-124.
[8] Kumar, R., et al. (2012). On the Equivalence of Distance, Time, and Energy in Normalized Network Space for Routing Problems. Journal of Operational Research Society, 63(8), 1089-1102.
[9] Parikh, S., et al. (2023). Performance Evaluation and Architectural Similarities of Electric Powertrains: BEV vs. FCEV. IEEE Transactions on Transportation Electrification, 9(3), 3120-3135.
[10] Settey, T., et al. (2021). Application of Longitudinal Vehicle Dynamics and Newton’s Second Law to Powertrain Efficiency Assessment. Transport, 36(4), 289-301.
[11] Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35(2), 254-265.Constraints*. Operations Research, 35(2), 254-265.
