A Quantum Approach to the Problem of Charging Electric Cars on a Motorway
In this paper, the problem of charging electric motor vehicles on a motorway is considered. Charging points are located alongside the motorway. It is assumed that there are a number of vehicles on a given section of a motorway. In the motorway, there are several nodes, and for each vehicle, the ente...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-12-01
|
| Series: | Energies |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1996-1073/16/1/442 |
| _version_ | 1797625822314496000 |
|---|---|
| author | Rafał Różycki Joanna Józefowska Krzysztof Kurowski Tomasz Lemański Tomasz Pecyna Marek Subocz Grzegorz Waligóra |
| author_facet | Rafał Różycki Joanna Józefowska Krzysztof Kurowski Tomasz Lemański Tomasz Pecyna Marek Subocz Grzegorz Waligóra |
| author_sort | Rafał Różycki |
| collection | DOAJ |
| description | In this paper, the problem of charging electric motor vehicles on a motorway is considered. Charging points are located alongside the motorway. It is assumed that there are a number of vehicles on a given section of a motorway. In the motorway, there are several nodes, and for each vehicle, the entering and the leaving nodes are known, as well as the time of entrance. For each vehicle, we know the total capacity of its battery, and the current amount of energy in the battery when entering the motorway. It is also assumed that for each vehicle, there is a finite set of speeds it can use when traveling the motorway. The speed is chosen when entering the motorway, and cannot be changed before reaching the charging station. For each speed, there is given a corresponding power usage; the higher the speed, the larger the power usage. Each vehicle can only use one charger, and when its battery is full, the amount of energy is sufficient for reaching the outgoing node. We look for a feasible solution to the problem, i.e., a solution in which no vehicle has to wait for a charger. The problem is formulated as a problem of scheduling independent, nonpreemptable jobs in parallel, unrelated machines under an additional doubly constrained resource, which is power. Quantum approaches to solve the defined problem are proposed. They use the quantum approximate optimization algorithm and the quantum annealing technique. A computational experiment is presented and discussed. Some conclusions and directions for future research are given. |
| first_indexed | 2024-03-11T10:01:54Z |
| format | Article |
| id | doaj.art-5b11ce8697f8446b8cdd206b3318c4d4 |
| institution | Directory Open Access Journal |
| issn | 1996-1073 |
| language | English |
| last_indexed | 2024-03-11T10:01:54Z |
| publishDate | 2022-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Energies |
| spelling | doaj.art-5b11ce8697f8446b8cdd206b3318c4d42023-11-16T15:19:12ZengMDPI AGEnergies1996-10732022-12-0116144210.3390/en16010442A Quantum Approach to the Problem of Charging Electric Cars on a MotorwayRafał Różycki0Joanna Józefowska1Krzysztof Kurowski2Tomasz Lemański3Tomasz Pecyna4Marek Subocz5Grzegorz Waligóra6Institute of Computing Science, Poznan University of Technology, 60-965 Poznan, PolandInstitute of Computing Science, Poznan University of Technology, 60-965 Poznan, PolandPoznan Supercomputing and Networking Center, Institute of Bioorganic Chemistry of the Polish Academy of Sciences, 61-139 Poznan, PolandInstitute of Computing Science, Poznan University of Technology, 60-965 Poznan, PolandInstitute of Computing Science, Poznan University of Technology, 60-965 Poznan, PolandPoznan Supercomputing and Networking Center, Institute of Bioorganic Chemistry of the Polish Academy of Sciences, 61-139 Poznan, PolandInstitute of Computing Science, Poznan University of Technology, 60-965 Poznan, PolandIn this paper, the problem of charging electric motor vehicles on a motorway is considered. Charging points are located alongside the motorway. It is assumed that there are a number of vehicles on a given section of a motorway. In the motorway, there are several nodes, and for each vehicle, the entering and the leaving nodes are known, as well as the time of entrance. For each vehicle, we know the total capacity of its battery, and the current amount of energy in the battery when entering the motorway. It is also assumed that for each vehicle, there is a finite set of speeds it can use when traveling the motorway. The speed is chosen when entering the motorway, and cannot be changed before reaching the charging station. For each speed, there is given a corresponding power usage; the higher the speed, the larger the power usage. Each vehicle can only use one charger, and when its battery is full, the amount of energy is sufficient for reaching the outgoing node. We look for a feasible solution to the problem, i.e., a solution in which no vehicle has to wait for a charger. The problem is formulated as a problem of scheduling independent, nonpreemptable jobs in parallel, unrelated machines under an additional doubly constrained resource, which is power. Quantum approaches to solve the defined problem are proposed. They use the quantum approximate optimization algorithm and the quantum annealing technique. A computational experiment is presented and discussed. Some conclusions and directions for future research are given.https://www.mdpi.com/1996-1073/16/1/442electric motor vehiclebattery chargingpowerenergyschedulingparallel unrelated machines |
| spellingShingle | Rafał Różycki Joanna Józefowska Krzysztof Kurowski Tomasz Lemański Tomasz Pecyna Marek Subocz Grzegorz Waligóra A Quantum Approach to the Problem of Charging Electric Cars on a Motorway Energies electric motor vehicle battery charging power energy scheduling parallel unrelated machines |
| title | A Quantum Approach to the Problem of Charging Electric Cars on a Motorway |
| title_full | A Quantum Approach to the Problem of Charging Electric Cars on a Motorway |
| title_fullStr | A Quantum Approach to the Problem of Charging Electric Cars on a Motorway |
| title_full_unstemmed | A Quantum Approach to the Problem of Charging Electric Cars on a Motorway |
| title_short | A Quantum Approach to the Problem of Charging Electric Cars on a Motorway |
| title_sort | quantum approach to the problem of charging electric cars on a motorway |
| topic | electric motor vehicle battery charging power energy scheduling parallel unrelated machines |
| url | https://www.mdpi.com/1996-1073/16/1/442 |
| work_keys_str_mv | AT rafałrozycki aquantumapproachtotheproblemofchargingelectriccarsonamotorway AT joannajozefowska aquantumapproachtotheproblemofchargingelectriccarsonamotorway AT krzysztofkurowski aquantumapproachtotheproblemofchargingelectriccarsonamotorway AT tomaszlemanski aquantumapproachtotheproblemofchargingelectriccarsonamotorway AT tomaszpecyna aquantumapproachtotheproblemofchargingelectriccarsonamotorway AT mareksubocz aquantumapproachtotheproblemofchargingelectriccarsonamotorway AT grzegorzwaligora aquantumapproachtotheproblemofchargingelectriccarsonamotorway AT rafałrozycki quantumapproachtotheproblemofchargingelectriccarsonamotorway AT joannajozefowska quantumapproachtotheproblemofchargingelectriccarsonamotorway AT krzysztofkurowski quantumapproachtotheproblemofchargingelectriccarsonamotorway AT tomaszlemanski quantumapproachtotheproblemofchargingelectriccarsonamotorway AT tomaszpecyna quantumapproachtotheproblemofchargingelectriccarsonamotorway AT mareksubocz quantumapproachtotheproblemofchargingelectriccarsonamotorway AT grzegorzwaligora quantumapproachtotheproblemofchargingelectriccarsonamotorway |