Electric-Vehicle Routing Problem with Time Windows (EVRPTW)

Solver for the Electric Vehicle Routing Problem with Time Windows.

Image Source

Problem description

In the E-VRPTW, a set of customers must be served by a fleet of battery electric vehicles (BEV). The E-VRPTW extends the well-know VRPTW, where customers must be served within a given time window, by the restriction of reduced operating range of the vehicles and the possibility to recharge at certain station to increase this range. The assumption of flat terrain and constant travel speed holds in the E-VRPTW. The objective function is to minimize the total travel distance.

More formal, the EVRPTW is defined on a complete directed graph G = (V,A) consisting of a set of depot, customer, and recharging station nodes and a set of edges. Each edge (i, j) has a distance d_ij and a travel time t_ij associated and each traveled edge consumes the amount of r x d_ij of the remaining battery charge of the vehicle, where r denotes the constant charge consumption rate. Furthermore, a set of homogeneous vehicles is given, where each vehicle has a maximal capacity of C and is located, full loaded at the depot. Each node has a positive demand q_i, a service time s_i and a time window [ e_i, l_i ] assigned. The service must start within the given time window (thus, finishing the service could be later than l_i). At recharging stations, the difference between the present charge level and the battery capacity Q is recharged (always loaded until battery is full) with a constant recharging rate of g. Note, that it is allowed to visit recharging stations more than once.

The aim is to construct routes, such that all customers are visited exactly once and served within their given time window. All routes must begin and end in the depot and the vehicle capacity and battery capacity must be respected. The objective function is to minimize the total traveled distance.

Implementation Details

Our E-VRPTW Solver consists of two parts:

1. Construction heuristic: Time-Oriented, Nearest-Neighbor Heuristic (Solomon 1987)
2. Metaheuristic: For this part, we tried to implement a Hybrid VNS/TS metaheuristic proposed in the paper The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations, however our solution is not the most efficient one and requires further optimizations (especially in route representation)

Model objects like EVRPTWInstance, Customer, Node have been copied from the E-VRPTW Solution Verifier (Java) implemented by @ghiermann.

See our presentation slides for more details.

Usage

See Main.kt for instance/plotting/performance-recording customizations.

Contributions

Special thanks to my dear friend and colleague David Molnar for participating in this project:

David Molnar 🤔 💻 ⚠️

License

This project is licensed under the MIT License. Feel free to use, extend or fit it to your needs.