A solver for fixed route vehicle charging problems
Project description
frvcpy: An Open-Source Solver for the FRVCP
Fast optimal solutions to rich FRVCPs
What is an FRVCP?
Given an elctric vehicle (EV) that's been assigned some sequence of locations to visit (a fixed route), the fixed route vehicle charging problem (FRVCP) is the problem of finding the optimal insertion of recharging operations into the route that minimize the time required for the EV to traverse that route in an energy-feasible manner.
Installation
In a virtual environment with Python 3.6+, frvcpy can be installed via
pip install frvcpy
Example problem instances are available in the instances
directory on the project's homepage. For easy access to the example files, we recommend cloning the repository.
Using frvcpy
With a compatible instance file (see the schema), solve the FRVCP from a Python script:
from frvcpy import solver
route = [0,40,12,33,38,16,0] # route to make energy feasible
q_init = 16000 # vehicle's initial energy level
# using an existing instance from file
frvcp_solver = solver.Solver("instances/frvcpy-instance.json", route, q_init)
# run the algorithm
duration, feas_route = frvcp_solver.solve()
print(f"Duration: {duration:.4}")
# Duration: 7.339
print(f"Energy-feasible route:\n{feas_route}")
# Energy-feasible route:
# [(0, None), (40, None), (12, None), (33, None), (48, 6673.379615520617), (38, None), (16, None), (0, None)]
Or from the command line:
frvcpy --instance=instances/frvcpy-instance.json --route=0,40,12,33,38,16,0 --qinit=16000
# Duration: 7.339
# Energy-feasible route:
# [(0, None), (40, None), (12, None), (33, None), (48, 6673.379615520617), (38, None), (16, None), (0, None)]
Instance Translation
Instance translation is available for some E-VRP instances formatted according to the VRP-REP specification.
Translation can be done with the Python API via
from frvcpy import translator
# Option 1) make instance object to be passed directly to the solver
frvcp_instance = translator.translate("instances/vrprep-instance.xml")
# Option 2) write the translated instance to file
frvcp_instance = translator.translate("instances/vrprep-instance.xml", to_file="instances/my-new-instance.json")
Or with the command line (only option is to write the translated instance to file):
frvcpy-translate instances/vrprep-instance.xml instances/my-new-instance.json
Translation requirements for VRP-REP instances
frvcpy's translator assumes VRP-REP instances are formatted similarly to the Montoya et al. (2017) instances:
- CSs are identified as
<node>
elements having attributetype="2"
- Charging stations nodes have a
<custom>
child element which contains acs_type
element - For each unique CS type
t
appearing in thosecs_type
elements, there exists a chargingfunction
element with attributecs_type=t
- These
function
elements are part of acharging_functions
element in avehicle_profile
'scustom
element - The depot has node ID 0, the N customers have IDs {1, ..., N}, and the CSs have IDs {N+1, ..., N+C}
A good example of such an instance is the example VRP-REP instance in the repository.
Here is a smaller example meeting these requirements:
<?xml version="1.0" encoding="UTF-8"?>
<instance>
<network>
<nodes>
<node id="0" type="0">
<cx>74.83</cx>
<cy>51.85</cy>
</node>
<node id="1" type="1">
<cx>68.77</cx>
<cy>75.69</cy>
</node>
<node id="11" type="2">
<cx>57.0</cx>
<cy>57.04</cy>
<custom>
<cs_type>fast</cs_type>
</custom>
</node>
</nodes>
<euclidean/>
<decimals>14</decimals>
</network>
<fleet>
<vehicle_profile type="0">
<departure_node>0</departure_node>
<arrival_node>0</arrival_node>
<speed_factor>25.0</speed_factor>
<custom>
<consumption_rate>0.125</consumption_rate>
<battery_capacity>16.0</battery_capacity>
<charging_functions>
<function cs_type="fast">
<breakpoint>
<battery_level>0.0</battery_level>
<charging_time>0.0</charging_time>
</breakpoint>
<breakpoint>
<battery_level>13.6</battery_level>
<charging_time>0.317</charging_time>
</breakpoint>
<breakpoint>
<battery_level>15.2</battery_level>
<charging_time>0.383</charging_time>
</breakpoint>
<breakpoint>
<battery_level>16.0</battery_level>
<charging_time>0.517</charging_time>
</breakpoint>
</function>
</charging_functions>
</custom>
</vehicle_profile>
</fleet>
<requests>
<request id="1" node="1">
<service_time>0.5</service_time>
</request>
</requests>
</instance>
The Solver
To solve FRVCPs, frvcpy implements the labeling algorithm from Froger et al. (2019), providing optimal solutions in low runtime. The algorithm accommodates realistic problem features such as nonlinear charging functions, heterogeneous charging station technologies, and multiple CS visits between stops.
Additional information
For more information about the algorithm used in the solver, see Froger et al. (2019).
For a write-up of the package: Manuscript in preparation, coming soon
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for frvcpy-0.1.0rc2-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3775b39c2d21228fd8200749a0d8e6500d9f08bea609349bcc43401bc837bf56 |
|
MD5 | efd0fe79c4b797c1dc19babddfa9c53b |
|
BLAKE2b-256 | b0eb42330bad862540463aba2cbd0692e0150fec56a66c739c56e5863f3d7cdc |