YAML Metadata Warning:empty or missing yaml metadata in repo card
Check out the documentation for more information.
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.
2.2 Instance Types
| Type | Time Window Characteristics | Capacity |
|---|---|---|
| 1 | Narrow time windows | Low capacity (200 units) |
| 2 | Wide time windows | High capacity (C: 700 units, R & RC: 1000 units) |
2.3 Instance Structure
Example: C101_200.csv
3. Benchmark Adaptation
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
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].
Acceleration and Deceleration Profiles
| Speed Range (km/h) | Acceleration (m/s²) | Deceleration (m/s²) |
|---|---|---|
| 0 – 15 | 1.06 | 1.03 |
| 15.1 – 30 | 0.50 | 0.48 |
| 30.1 – 50 | 0.17 | 0.17 |
| 50.1 – 70 | 0.18 | 0.17 |
| 70.1 – 90 | 1.01 | 0.98 |
8. References
[1] Métropole de Lyon. (2024). Document d’Orientations sur la Logistique des biens et des services (DOLB&S). Direction des Mobilités.
https://www.grandlyon.com/fileadmin/user_upload/media/pdf/deplacements/orientation-logistique-urbaine.pdf
[2] Métropole de Lyon. (2020). Plan de Protection de l'Atmosphère et orientations topographiques urbaines / Aire de mise en valeur de l’architecture et du patrimoine.
https://www.grandlyon.com/fileadmin/user_upload/media/pdf/urbanisme/sites-patrimoniaux/spr_avap_croix_rousse_diagnostic.pdf
[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.