EAR-EVRPTW

Abstract

Overview This dataset provides a geospatially enriched version of the EVRPTW benchmark instances of Schneider et al. (2014). It is intended for evaluating routing algorithms for electric vehicles when route optimization and physically based energy consumption must be studied together. Every node of every instance (depot, charging stations, customers) was projected onto the real road network of Amiens, France. Every directed arc between two nodes was then described with physical attributes taken from a real driving route: road distance, characteristic speed, characteristic acceleration and mean slope. Each arc also carries its estimated energy consumption (kWh), computed with the physical power model of Wu et al. (2015) for a Nissan Townstar EV light commercial vehicle. Motivation To our knowledge, no open dataset makes it possible to test routing optimization and vehicle energy consumption at the same time. The two kinds of data exist, but separately: Routing benchmarks such as Solomon (VRPTW) and Schneider et al. (EVRPTW) define customers, demands, time windows and charging stations. Their nodes are placed in an abstract Euclidean plane, however. Arcs have only a straight-line length, and energy is assumed to be proportional to distance (a constant consumption rate r). They contain no information on speed, acceleration or road gradient. Energy consumption datasets, such as on-board CAN-bus telemetry, record real speed, altitude and motor power. They describe individual trips, however, and contain no routing problem: there are no customers, demands, time windows or fleet constraints. A physical energy model needs the real distance, speed, acceleration and slope of each trip, and none of these can be derived from Euclidean coordinates. This dataset bridges the gap. It keeps the full problem definition of the established benchmark, which preserves comparability with the literature, and adds to every arc the road-based physical attributes and energy estimate needed for energy-aware optimization. Source instances The original instances (Schneider et al., 2014) extend Solomon's VRPTW instances with a battery capacity and charging stations. They are grouped as follows: By customer distribution: class C (clustered), R (random) and RC (mixed). A second digit of 1 or 2 (for example c1xx or c2xx) indicates short or long scheduling horizons, as in Solomon's instances. By size: large instances with 100 customers and 21 charging stations, and small instances with 5, 10 or 15 customers (suffix C5, C10 or C15, for example c101C5), extracted from the large ones. Each original node has an identifier, a type (d depot, f station, c customer), Euclidean coordinates (x, y), a demand, a time window [ReadyTime, DueDate] and a service time. Each instance also sets the vehicle parameters: battery capacity Q, load capacity C, consumption rate r, inverse recharging rate g and average velocity v. Construction pipeline The pipeline is implemented using Python and runs once per instance. It turns an abstract benchmark instance into a road-based instance in five stages. 1. Projection into a real city The original instance file is read to extract the depot, the charging stations, the customers and their attributes. The abstract coordinates are then rescaled into a bounding box of about 30 × 25 km around Amiens, France. The rescaling keeps the relative layout of each instance, so clustered, random and mixed distributions stay recognizable. A safety margin keeps nodes away from the edges of the box. 2. Snapping nodes to real locations A projected point may fall in a field, a building or a river, so every node is moved to a realistic nearby location: The depot and customers are moved to the nearest drivable road point, using the OSRM Nearest service. Every trip therefore starts and ends on the road network. The charging stations are moved to the nearest site in a list of existing public EV charging locations in the Amiens area. The node attributes (demand, time window and service time) are not modified. 3. Real driving routes For every ordered pair of distinct nodes, the OSRM Route service computes the driving route on the OpenStreetMap road network. For each route, it returns: the route length; the detailed path geometry; a breakdown of the route into successive road sections between manoeuvres, each with its own length and travel time. Arcs are directed, because the route from A to B can differ from the route from B to A in length, speed and gradient. The result is a complete directed graph between all nodes of the instance. 4. Physical attributes of each arc Each route is then summarized by the quantities a physical energy model needs: Road distance: the length of the driving route, expressed in kilometres. Characteristic speed: a typical driving speed for the arc. A speed is computed for each road section, degenerate sections (zero length or near-zero duration) are discarded, and the median is taken so that isolated very short or very fast sections do not distort the value. Characteristic acceleration: a typical rate of speed change along the arc. It is derived from the speed changes between consecutive road sections, again summarized by the median. A negative value indicates net deceleration, and single-section routes get zero acceleration. Mean slope: the average road gradient along the arc. Ten points are sampled evenly along the path, including both endpoints, so that intermediate hills and valleys are captured and not only the difference between start and end. Their elevations are retrieved from the Open-Elevation service, and the slope is the length-weighted average of the gradients between consecutive samples, expressed in percent. 5. Energy estimation The distance, speed, acceleration and slope of each arc are combined with the reference vehicle parameters in the physical model of Wu et al. (2015). The model gives the power required to drive the arc, and this power multiplied by the travel time gives the energy consumed. Data dictionary Column Description Unit FROM Identifier of the origin node (depot, station or customer) – TO Identifier of the destination node – lat_from, lon_from Coordinates of the origin node after projection and snapping degrees lat_to, lon_to Coordinates of the destination node after projection and snapping degrees demand Demand of the origin node (0 for the depot and stations) load units (original) ReadyTime Start of the time window of the origin node time units (original) DueDate End of the time window of the origin node time units (original) ServiceTime Service duration at the origin node time units (original) real_distance Length of the OSRM driving route from FROM to TO km speed_kmh Characteristic speed of the arc (median step speed) km/h acceleration_ms2 Characteristic acceleration (median over step transitions; negative = deceleration) m/s² slope_mean_pct Distance-weighted mean road gradient (positive = uphill) % energy_kWh Energy consumption estimated with the Wu et al. (2015) model (negative = regeneration) kWh The node attributes (demand, ReadyTime, DueDate, ServiceTime) are copied unchanged from the original instance. Because they describe the origin node, they are identical on every row with the same FROM. Arcs are directed, so the (i, j) and (j, i) rows usually differ in distance, speed, slope and energy. References -Michael Schneider, Andreas Stenger, and Dominik Goeke. The electric vehicle-routing problem with time windows and recharging stations. Transportation Sci-ence, 48(4):500–520, 2014. -Xinkai Wu et al. Electric vehicles’ energy consumption measurement and esti-mation. Transportation Research Part D: Transport and Environment, 34:52–67,2015.