Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
font
Filter
×
2022
Rigas, Emmanouil S; Gerding, Enrico H; Stein, Sebastian; Ramchurn, Sarvapali D; Bassiliades, Nick
Mechanism design for efficient offline and online allocation of electric vehicles to charging stations Journal Article
In: Energies, vol. 15, no. 5, 2022, (Funding Information: Funding: This research study was co-financed by Greece and the European Union (European Social Fund–ESF) through the Operational Programme ?Human Resources Development, Education and Lifelong Learning? in the context of the project ?Reinforcement of Postdoctoral Researchers-2nd Cycle? (MIS-5033021), implemented by State Scholarships Foundation (IKY). Copyright 2022 Elsevier B.V., All rights reserved.).
Abstract | Links | BibTeX | Tags: Charging, Electric Vehicles, Fixed price, mechanism design, Scheduling, VCG
@article{soton455806,
title = {Mechanism design for efficient offline and online allocation of electric vehicles to charging stations},
author = {Emmanouil S Rigas and Enrico H Gerding and Sebastian Stein and Sarvapali D Ramchurn and Nick Bassiliades},
url = {https://eprints.soton.ac.uk/455806/},
year = {2022},
date = {2022-03-01},
journal = {Energies},
volume = {15},
number = {5},
abstract = {ensuremath<pensuremath>The industry related to electric vehicles (EVs) has seen a substantial increase in recent years, as such vehicles have the ability to significantly reduce total COensuremath<subensuremath>2ensuremath</subensuremath> emissions and the related global warming effect. In this paper, we focus on the problem of allocating EVs to charging stations, scheduling and pricing their charging. Specifically, we developed a Mixed Integer Program (MIP) which executes offline and optimally allocates EVs to charging stations. On top, we propose two alternative mechanisms to price the electricity the EVs charge. The first mechanism is a typical fixed-price one, while the second is a variation of the Vickrey?Clark?Groves (VCG) mechanism. We also developed online solutions that incrementally call the MIP-based algorithm and solve it for branches of EVs. In all cases, the EVs? aim is to minimize the price to pay and the impact on their driving schedule, acting as self-interested agents. We conducted a thorough empirical evaluation of our mechanisms and we observed that they had satisfactory scalability. Additionally, the VCG mechanism achieved an up to 2.2% improvement in terms of the number of vehicles that were charged compared to the fixed-price one and, in cases where the stations were congested, it calculated higher prices for the EVs and provided a higher profit for the stations, but lower utility to the EVs. However, in a theoretical evaluation, we proved that the variant of the VCG mechanism being proposed in this paper still guaranteed truthful reporting of the EVs? preferences. In contrast, the fixed-price one was found to be vulnerable to agents? strategic behavior as non-truthful EVs can charge instead of truthful ones. Finally, we observed the online algorithms to be, on average, at 95.6% of the offline ones in terms of the average number of serviced EVs.ensuremath</pensuremath>},
note = {Funding Information:
Funding: This research study was co-financed by Greece and the European Union (European Social Fund–ESF) through the Operational Programme ?Human Resources Development, Education and Lifelong Learning? in the context of the project ?Reinforcement of Postdoctoral Researchers-2nd Cycle? (MIS-5033021), implemented by State Scholarships Foundation (IKY).
Copyright 2022 Elsevier B.V., All rights reserved.},
keywords = {Charging, Electric Vehicles, Fixed price, mechanism design, Scheduling, VCG},
pubstate = {published},
tppubtype = {article}
}
ensuremath<pensuremath>The industry related to electric vehicles (EVs) has seen a substantial increase in recent years, as such vehicles have the ability to significantly reduce total COensuremath<subensuremath>2ensuremath</subensuremath> emissions and the related global warming effect. In this paper, we focus on the problem of allocating EVs to charging stations, scheduling and pricing their charging. Specifically, we developed a Mixed Integer Program (MIP) which executes offline and optimally allocates EVs to charging stations. On top, we propose two alternative mechanisms to price the electricity the EVs charge. The first mechanism is a typical fixed-price one, while the second is a variation of the Vickrey?Clark?Groves (VCG) mechanism. We also developed online solutions that incrementally call the MIP-based algorithm and solve it for branches of EVs. In all cases, the EVs? aim is to minimize the price to pay and the impact on their driving schedule, acting as self-interested agents. We conducted a thorough empirical evaluation of our mechanisms and we observed that they had satisfactory scalability. Additionally, the VCG mechanism achieved an up to 2.2% improvement in terms of the number of vehicles that were charged compared to the fixed-price one and, in cases where the stations were congested, it calculated higher prices for the EVs and provided a higher profit for the stations, but lower utility to the EVs. However, in a theoretical evaluation, we proved that the variant of the VCG mechanism being proposed in this paper still guaranteed truthful reporting of the EVs? preferences. In contrast, the fixed-price one was found to be vulnerable to agents? strategic behavior as non-truthful EVs can charge instead of truthful ones. Finally, we observed the online algorithms to be, on average, at 95.6% of the offline ones in terms of the average number of serviced EVs.ensuremath</pensuremath>
2018
Rigas, Emmanouil; Ramchurn, Sarvapali; Bassiliades, Nick
Algorithms for electric vehicle scheduling in large-scale mobility-on-demand schemes Journal Article
In: Artificial Intelligence, vol. 262, pp. 248–278, 2018.
Abstract | Links | BibTeX | Tags: Electric Vehicles, Heuristics, Mobility on Demand, optimisation, Scheduling
@article{soton422097,
title = {Algorithms for electric vehicle scheduling in large-scale mobility-on-demand schemes},
author = {Emmanouil Rigas and Sarvapali Ramchurn and Nick Bassiliades},
url = {https://eprints.soton.ac.uk/422097/},
year = {2018},
date = {2018-09-01},
journal = {Artificial Intelligence},
volume = {262},
pages = {248–278},
abstract = {We study a setting where Electric Vehicles (EVs) can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of customers that are serviced, or the total EV utilization. To do so, we characterise the optimisation problem as a max-flow problem in order to determine the set of feasible trips given the available EVs at each location. We then model and solve the EV-to-trip scheduling problem offline and optimally using Mixed Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP algorithm for medium to large problems and a greedy heuristic algorithm for very large problems. Moreover, we develop a tabu search-based local search technique to further improve upon and compare against the solution of the non-optimal algorithms. We study the performance of these algorithms in settings where either battery swap or battery charge at each station is used to cope with the EVs' limited driving range. Moreover, in settings where EVs need to be scheduled online, we propose a novel algorithm that accounts for the uncertainty in future trip requests. All algorithms are empirically evaluated using real-world data of locations of shared vehicle pick-up and drop-off stations. In our experiments, we observe that when all EVs carry the same battery which is large enough for the longest trips, the greedy algorithm with battery swap with the max-flow solution as a pre-processing step, provides the optimal solution. At the same time, the greedy algorithm with battery charge is close to the optimal (97% on average) and is further improved when local search is used. When some EVs do not have a large enough battery to execute some of the longest trips, the incremental-MIP generates solutions slightly better than the greedy, while the optimal algorithm is the best but scales up to medium sized problems only. Moreover, the online algorithm is shown to be on average at least 90% of the optimal. Finally, the greedy algorithm scales to 10-times more tasks than the incremental-MIP and 1000-times more than the static MIP in reasonable time.},
keywords = {Electric Vehicles, Heuristics, Mobility on Demand, optimisation, Scheduling},
pubstate = {published},
tppubtype = {article}
}
We study a setting where Electric Vehicles (EVs) can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of customers that are serviced, or the total EV utilization. To do so, we characterise the optimisation problem as a max-flow problem in order to determine the set of feasible trips given the available EVs at each location. We then model and solve the EV-to-trip scheduling problem offline and optimally using Mixed Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP algorithm for medium to large problems and a greedy heuristic algorithm for very large problems. Moreover, we develop a tabu search-based local search technique to further improve upon and compare against the solution of the non-optimal algorithms. We study the performance of these algorithms in settings where either battery swap or battery charge at each station is used to cope with the EVs' limited driving range. Moreover, in settings where EVs need to be scheduled online, we propose a novel algorithm that accounts for the uncertainty in future trip requests. All algorithms are empirically evaluated using real-world data of locations of shared vehicle pick-up and drop-off stations. In our experiments, we observe that when all EVs carry the same battery which is large enough for the longest trips, the greedy algorithm with battery swap with the max-flow solution as a pre-processing step, provides the optimal solution. At the same time, the greedy algorithm with battery charge is close to the optimal (97% on average) and is further improved when local search is used. When some EVs do not have a large enough battery to execute some of the longest trips, the incremental-MIP generates solutions slightly better than the greedy, while the optimal algorithm is the best but scales up to medium sized problems only. Moreover, the online algorithm is shown to be on average at least 90% of the optimal. Finally, the greedy algorithm scales to 10-times more tasks than the incremental-MIP and 1000-times more than the static MIP in reasonable time.
1.
Rigas, Emmanouil S; Gerding, Enrico H; Stein, Sebastian; Ramchurn, Sarvapali D; Bassiliades, Nick
Mechanism design for efficient offline and online allocation of electric vehicles to charging stations Journal Article
In: Energies, vol. 15, no. 5, 2022, (Funding Information: Funding: This research study was co-financed by Greece and the European Union (European Social Fund–ESF) through the Operational Programme ?Human Resources Development, Education and Lifelong Learning? in the context of the project ?Reinforcement of Postdoctoral Researchers-2nd Cycle? (MIS-5033021), implemented by State Scholarships Foundation (IKY). Copyright 2022 Elsevier B.V., All rights reserved.).
@article{soton455806,
title = {Mechanism design for efficient offline and online allocation of electric vehicles to charging stations},
author = {Emmanouil S Rigas and Enrico H Gerding and Sebastian Stein and Sarvapali D Ramchurn and Nick Bassiliades},
url = {https://eprints.soton.ac.uk/455806/},
year = {2022},
date = {2022-03-01},
journal = {Energies},
volume = {15},
number = {5},
abstract = {ensuremath<pensuremath>The industry related to electric vehicles (EVs) has seen a substantial increase in recent years, as such vehicles have the ability to significantly reduce total COensuremath<subensuremath>2ensuremath</subensuremath> emissions and the related global warming effect. In this paper, we focus on the problem of allocating EVs to charging stations, scheduling and pricing their charging. Specifically, we developed a Mixed Integer Program (MIP) which executes offline and optimally allocates EVs to charging stations. On top, we propose two alternative mechanisms to price the electricity the EVs charge. The first mechanism is a typical fixed-price one, while the second is a variation of the Vickrey?Clark?Groves (VCG) mechanism. We also developed online solutions that incrementally call the MIP-based algorithm and solve it for branches of EVs. In all cases, the EVs? aim is to minimize the price to pay and the impact on their driving schedule, acting as self-interested agents. We conducted a thorough empirical evaluation of our mechanisms and we observed that they had satisfactory scalability. Additionally, the VCG mechanism achieved an up to 2.2% improvement in terms of the number of vehicles that were charged compared to the fixed-price one and, in cases where the stations were congested, it calculated higher prices for the EVs and provided a higher profit for the stations, but lower utility to the EVs. However, in a theoretical evaluation, we proved that the variant of the VCG mechanism being proposed in this paper still guaranteed truthful reporting of the EVs? preferences. In contrast, the fixed-price one was found to be vulnerable to agents? strategic behavior as non-truthful EVs can charge instead of truthful ones. Finally, we observed the online algorithms to be, on average, at 95.6% of the offline ones in terms of the average number of serviced EVs.ensuremath</pensuremath>},
note = {Funding Information:
Funding: This research study was co-financed by Greece and the European Union (European Social Fund–ESF) through the Operational Programme ?Human Resources Development, Education and Lifelong Learning? in the context of the project ?Reinforcement of Postdoctoral Researchers-2nd Cycle? (MIS-5033021), implemented by State Scholarships Foundation (IKY).
Copyright 2022 Elsevier B.V., All rights reserved.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
ensuremath<pensuremath>The industry related to electric vehicles (EVs) has seen a substantial increase in recent years, as such vehicles have the ability to significantly reduce total COensuremath<subensuremath>2ensuremath</subensuremath> emissions and the related global warming effect. In this paper, we focus on the problem of allocating EVs to charging stations, scheduling and pricing their charging. Specifically, we developed a Mixed Integer Program (MIP) which executes offline and optimally allocates EVs to charging stations. On top, we propose two alternative mechanisms to price the electricity the EVs charge. The first mechanism is a typical fixed-price one, while the second is a variation of the Vickrey?Clark?Groves (VCG) mechanism. We also developed online solutions that incrementally call the MIP-based algorithm and solve it for branches of EVs. In all cases, the EVs? aim is to minimize the price to pay and the impact on their driving schedule, acting as self-interested agents. We conducted a thorough empirical evaluation of our mechanisms and we observed that they had satisfactory scalability. Additionally, the VCG mechanism achieved an up to 2.2% improvement in terms of the number of vehicles that were charged compared to the fixed-price one and, in cases where the stations were congested, it calculated higher prices for the EVs and provided a higher profit for the stations, but lower utility to the EVs. However, in a theoretical evaluation, we proved that the variant of the VCG mechanism being proposed in this paper still guaranteed truthful reporting of the EVs? preferences. In contrast, the fixed-price one was found to be vulnerable to agents? strategic behavior as non-truthful EVs can charge instead of truthful ones. Finally, we observed the online algorithms to be, on average, at 95.6% of the offline ones in terms of the average number of serviced EVs.ensuremath</pensuremath>
2.
Rigas, Emmanouil; Ramchurn, Sarvapali; Bassiliades, Nick
Algorithms for electric vehicle scheduling in large-scale mobility-on-demand schemes Journal Article
In: Artificial Intelligence, vol. 262, pp. 248–278, 2018.
@article{soton422097,
title = {Algorithms for electric vehicle scheduling in large-scale mobility-on-demand schemes},
author = {Emmanouil Rigas and Sarvapali Ramchurn and Nick Bassiliades},
url = {https://eprints.soton.ac.uk/422097/},
year = {2018},
date = {2018-09-01},
journal = {Artificial Intelligence},
volume = {262},
pages = {248–278},
abstract = {We study a setting where Electric Vehicles (EVs) can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of customers that are serviced, or the total EV utilization. To do so, we characterise the optimisation problem as a max-flow problem in order to determine the set of feasible trips given the available EVs at each location. We then model and solve the EV-to-trip scheduling problem offline and optimally using Mixed Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP algorithm for medium to large problems and a greedy heuristic algorithm for very large problems. Moreover, we develop a tabu search-based local search technique to further improve upon and compare against the solution of the non-optimal algorithms. We study the performance of these algorithms in settings where either battery swap or battery charge at each station is used to cope with the EVs' limited driving range. Moreover, in settings where EVs need to be scheduled online, we propose a novel algorithm that accounts for the uncertainty in future trip requests. All algorithms are empirically evaluated using real-world data of locations of shared vehicle pick-up and drop-off stations. In our experiments, we observe that when all EVs carry the same battery which is large enough for the longest trips, the greedy algorithm with battery swap with the max-flow solution as a pre-processing step, provides the optimal solution. At the same time, the greedy algorithm with battery charge is close to the optimal (97% on average) and is further improved when local search is used. When some EVs do not have a large enough battery to execute some of the longest trips, the incremental-MIP generates solutions slightly better than the greedy, while the optimal algorithm is the best but scales up to medium sized problems only. Moreover, the online algorithm is shown to be on average at least 90% of the optimal. Finally, the greedy algorithm scales to 10-times more tasks than the incremental-MIP and 1000-times more than the static MIP in reasonable time.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
We study a setting where Electric Vehicles (EVs) can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of customers that are serviced, or the total EV utilization. To do so, we characterise the optimisation problem as a max-flow problem in order to determine the set of feasible trips given the available EVs at each location. We then model and solve the EV-to-trip scheduling problem offline and optimally using Mixed Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP algorithm for medium to large problems and a greedy heuristic algorithm for very large problems. Moreover, we develop a tabu search-based local search technique to further improve upon and compare against the solution of the non-optimal algorithms. We study the performance of these algorithms in settings where either battery swap or battery charge at each station is used to cope with the EVs' limited driving range. Moreover, in settings where EVs need to be scheduled online, we propose a novel algorithm that accounts for the uncertainty in future trip requests. All algorithms are empirically evaluated using real-world data of locations of shared vehicle pick-up and drop-off stations. In our experiments, we observe that when all EVs carry the same battery which is large enough for the longest trips, the greedy algorithm with battery swap with the max-flow solution as a pre-processing step, provides the optimal solution. At the same time, the greedy algorithm with battery charge is close to the optimal (97% on average) and is further improved when local search is used. When some EVs do not have a large enough battery to execute some of the longest trips, the incremental-MIP generates solutions slightly better than the greedy, while the optimal algorithm is the best but scales up to medium sized problems only. Moreover, the online algorithm is shown to be on average at least 90% of the optimal. Finally, the greedy algorithm scales to 10-times more tasks than the incremental-MIP and 1000-times more than the static MIP in reasonable time.
2022
Rigas, Emmanouil S; Gerding, Enrico H; Stein, Sebastian; Ramchurn, Sarvapali D; Bassiliades, Nick
Mechanism design for efficient offline and online allocation of electric vehicles to charging stations Journal Article
In: Energies, vol. 15, no. 5, 2022, (Funding Information: Funding: This research study was co-financed by Greece and the European Union (European Social Fund–ESF) through the Operational Programme ?Human Resources Development, Education and Lifelong Learning? in the context of the project ?Reinforcement of Postdoctoral Researchers-2nd Cycle? (MIS-5033021), implemented by State Scholarships Foundation (IKY). Copyright 2022 Elsevier B.V., All rights reserved.).
Abstract | Links | BibTeX | Tags: Charging, Electric Vehicles, Fixed price, mechanism design, Scheduling, VCG
@article{soton455806,
title = {Mechanism design for efficient offline and online allocation of electric vehicles to charging stations},
author = {Emmanouil S Rigas and Enrico H Gerding and Sebastian Stein and Sarvapali D Ramchurn and Nick Bassiliades},
url = {https://eprints.soton.ac.uk/455806/},
year = {2022},
date = {2022-03-01},
journal = {Energies},
volume = {15},
number = {5},
abstract = {ensuremath<pensuremath>The industry related to electric vehicles (EVs) has seen a substantial increase in recent years, as such vehicles have the ability to significantly reduce total COensuremath<subensuremath>2ensuremath</subensuremath> emissions and the related global warming effect. In this paper, we focus on the problem of allocating EVs to charging stations, scheduling and pricing their charging. Specifically, we developed a Mixed Integer Program (MIP) which executes offline and optimally allocates EVs to charging stations. On top, we propose two alternative mechanisms to price the electricity the EVs charge. The first mechanism is a typical fixed-price one, while the second is a variation of the Vickrey?Clark?Groves (VCG) mechanism. We also developed online solutions that incrementally call the MIP-based algorithm and solve it for branches of EVs. In all cases, the EVs? aim is to minimize the price to pay and the impact on their driving schedule, acting as self-interested agents. We conducted a thorough empirical evaluation of our mechanisms and we observed that they had satisfactory scalability. Additionally, the VCG mechanism achieved an up to 2.2% improvement in terms of the number of vehicles that were charged compared to the fixed-price one and, in cases where the stations were congested, it calculated higher prices for the EVs and provided a higher profit for the stations, but lower utility to the EVs. However, in a theoretical evaluation, we proved that the variant of the VCG mechanism being proposed in this paper still guaranteed truthful reporting of the EVs? preferences. In contrast, the fixed-price one was found to be vulnerable to agents? strategic behavior as non-truthful EVs can charge instead of truthful ones. Finally, we observed the online algorithms to be, on average, at 95.6% of the offline ones in terms of the average number of serviced EVs.ensuremath</pensuremath>},
note = {Funding Information:
Funding: This research study was co-financed by Greece and the European Union (European Social Fund–ESF) through the Operational Programme ?Human Resources Development, Education and Lifelong Learning? in the context of the project ?Reinforcement of Postdoctoral Researchers-2nd Cycle? (MIS-5033021), implemented by State Scholarships Foundation (IKY).
Copyright 2022 Elsevier B.V., All rights reserved.},
keywords = {Charging, Electric Vehicles, Fixed price, mechanism design, Scheduling, VCG},
pubstate = {published},
tppubtype = {article}
}
ensuremath<pensuremath>The industry related to electric vehicles (EVs) has seen a substantial increase in recent years, as such vehicles have the ability to significantly reduce total COensuremath<subensuremath>2ensuremath</subensuremath> emissions and the related global warming effect. In this paper, we focus on the problem of allocating EVs to charging stations, scheduling and pricing their charging. Specifically, we developed a Mixed Integer Program (MIP) which executes offline and optimally allocates EVs to charging stations. On top, we propose two alternative mechanisms to price the electricity the EVs charge. The first mechanism is a typical fixed-price one, while the second is a variation of the Vickrey?Clark?Groves (VCG) mechanism. We also developed online solutions that incrementally call the MIP-based algorithm and solve it for branches of EVs. In all cases, the EVs? aim is to minimize the price to pay and the impact on their driving schedule, acting as self-interested agents. We conducted a thorough empirical evaluation of our mechanisms and we observed that they had satisfactory scalability. Additionally, the VCG mechanism achieved an up to 2.2% improvement in terms of the number of vehicles that were charged compared to the fixed-price one and, in cases where the stations were congested, it calculated higher prices for the EVs and provided a higher profit for the stations, but lower utility to the EVs. However, in a theoretical evaluation, we proved that the variant of the VCG mechanism being proposed in this paper still guaranteed truthful reporting of the EVs? preferences. In contrast, the fixed-price one was found to be vulnerable to agents? strategic behavior as non-truthful EVs can charge instead of truthful ones. Finally, we observed the online algorithms to be, on average, at 95.6% of the offline ones in terms of the average number of serviced EVs.ensuremath</pensuremath>
2018
Rigas, Emmanouil; Ramchurn, Sarvapali; Bassiliades, Nick
Algorithms for electric vehicle scheduling in large-scale mobility-on-demand schemes Journal Article
In: Artificial Intelligence, vol. 262, pp. 248–278, 2018.
Abstract | Links | BibTeX | Tags: Electric Vehicles, Heuristics, Mobility on Demand, optimisation, Scheduling
@article{soton422097,
title = {Algorithms for electric vehicle scheduling in large-scale mobility-on-demand schemes},
author = {Emmanouil Rigas and Sarvapali Ramchurn and Nick Bassiliades},
url = {https://eprints.soton.ac.uk/422097/},
year = {2018},
date = {2018-09-01},
journal = {Artificial Intelligence},
volume = {262},
pages = {248–278},
abstract = {We study a setting where Electric Vehicles (EVs) can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of customers that are serviced, or the total EV utilization. To do so, we characterise the optimisation problem as a max-flow problem in order to determine the set of feasible trips given the available EVs at each location. We then model and solve the EV-to-trip scheduling problem offline and optimally using Mixed Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP algorithm for medium to large problems and a greedy heuristic algorithm for very large problems. Moreover, we develop a tabu search-based local search technique to further improve upon and compare against the solution of the non-optimal algorithms. We study the performance of these algorithms in settings where either battery swap or battery charge at each station is used to cope with the EVs' limited driving range. Moreover, in settings where EVs need to be scheduled online, we propose a novel algorithm that accounts for the uncertainty in future trip requests. All algorithms are empirically evaluated using real-world data of locations of shared vehicle pick-up and drop-off stations. In our experiments, we observe that when all EVs carry the same battery which is large enough for the longest trips, the greedy algorithm with battery swap with the max-flow solution as a pre-processing step, provides the optimal solution. At the same time, the greedy algorithm with battery charge is close to the optimal (97% on average) and is further improved when local search is used. When some EVs do not have a large enough battery to execute some of the longest trips, the incremental-MIP generates solutions slightly better than the greedy, while the optimal algorithm is the best but scales up to medium sized problems only. Moreover, the online algorithm is shown to be on average at least 90% of the optimal. Finally, the greedy algorithm scales to 10-times more tasks than the incremental-MIP and 1000-times more than the static MIP in reasonable time.},
keywords = {Electric Vehicles, Heuristics, Mobility on Demand, optimisation, Scheduling},
pubstate = {published},
tppubtype = {article}
}
We study a setting where Electric Vehicles (EVs) can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of customers that are serviced, or the total EV utilization. To do so, we characterise the optimisation problem as a max-flow problem in order to determine the set of feasible trips given the available EVs at each location. We then model and solve the EV-to-trip scheduling problem offline and optimally using Mixed Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP algorithm for medium to large problems and a greedy heuristic algorithm for very large problems. Moreover, we develop a tabu search-based local search technique to further improve upon and compare against the solution of the non-optimal algorithms. We study the performance of these algorithms in settings where either battery swap or battery charge at each station is used to cope with the EVs' limited driving range. Moreover, in settings where EVs need to be scheduled online, we propose a novel algorithm that accounts for the uncertainty in future trip requests. All algorithms are empirically evaluated using real-world data of locations of shared vehicle pick-up and drop-off stations. In our experiments, we observe that when all EVs carry the same battery which is large enough for the longest trips, the greedy algorithm with battery swap with the max-flow solution as a pre-processing step, provides the optimal solution. At the same time, the greedy algorithm with battery charge is close to the optimal (97% on average) and is further improved when local search is used. When some EVs do not have a large enough battery to execute some of the longest trips, the incremental-MIP generates solutions slightly better than the greedy, while the optimal algorithm is the best but scales up to medium sized problems only. Moreover, the online algorithm is shown to be on average at least 90% of the optimal. Finally, the greedy algorithm scales to 10-times more tasks than the incremental-MIP and 1000-times more than the static MIP in reasonable time.
1.
Rigas, Emmanouil S; Gerding, Enrico H; Stein, Sebastian; Ramchurn, Sarvapali D; Bassiliades, Nick
Mechanism design for efficient offline and online allocation of electric vehicles to charging stations Journal Article
In: Energies, vol. 15, no. 5, 2022, (Funding Information: Funding: This research study was co-financed by Greece and the European Union (European Social Fund–ESF) through the Operational Programme ?Human Resources Development, Education and Lifelong Learning? in the context of the project ?Reinforcement of Postdoctoral Researchers-2nd Cycle? (MIS-5033021), implemented by State Scholarships Foundation (IKY). Copyright 2022 Elsevier B.V., All rights reserved.).
@article{soton455806,
title = {Mechanism design for efficient offline and online allocation of electric vehicles to charging stations},
author = {Emmanouil S Rigas and Enrico H Gerding and Sebastian Stein and Sarvapali D Ramchurn and Nick Bassiliades},
url = {https://eprints.soton.ac.uk/455806/},
year = {2022},
date = {2022-03-01},
journal = {Energies},
volume = {15},
number = {5},
abstract = {ensuremath<pensuremath>The industry related to electric vehicles (EVs) has seen a substantial increase in recent years, as such vehicles have the ability to significantly reduce total COensuremath<subensuremath>2ensuremath</subensuremath> emissions and the related global warming effect. In this paper, we focus on the problem of allocating EVs to charging stations, scheduling and pricing their charging. Specifically, we developed a Mixed Integer Program (MIP) which executes offline and optimally allocates EVs to charging stations. On top, we propose two alternative mechanisms to price the electricity the EVs charge. The first mechanism is a typical fixed-price one, while the second is a variation of the Vickrey?Clark?Groves (VCG) mechanism. We also developed online solutions that incrementally call the MIP-based algorithm and solve it for branches of EVs. In all cases, the EVs? aim is to minimize the price to pay and the impact on their driving schedule, acting as self-interested agents. We conducted a thorough empirical evaluation of our mechanisms and we observed that they had satisfactory scalability. Additionally, the VCG mechanism achieved an up to 2.2% improvement in terms of the number of vehicles that were charged compared to the fixed-price one and, in cases where the stations were congested, it calculated higher prices for the EVs and provided a higher profit for the stations, but lower utility to the EVs. However, in a theoretical evaluation, we proved that the variant of the VCG mechanism being proposed in this paper still guaranteed truthful reporting of the EVs? preferences. In contrast, the fixed-price one was found to be vulnerable to agents? strategic behavior as non-truthful EVs can charge instead of truthful ones. Finally, we observed the online algorithms to be, on average, at 95.6% of the offline ones in terms of the average number of serviced EVs.ensuremath</pensuremath>},
note = {Funding Information:
Funding: This research study was co-financed by Greece and the European Union (European Social Fund–ESF) through the Operational Programme ?Human Resources Development, Education and Lifelong Learning? in the context of the project ?Reinforcement of Postdoctoral Researchers-2nd Cycle? (MIS-5033021), implemented by State Scholarships Foundation (IKY).
Copyright 2022 Elsevier B.V., All rights reserved.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
ensuremath<pensuremath>The industry related to electric vehicles (EVs) has seen a substantial increase in recent years, as such vehicles have the ability to significantly reduce total COensuremath<subensuremath>2ensuremath</subensuremath> emissions and the related global warming effect. In this paper, we focus on the problem of allocating EVs to charging stations, scheduling and pricing their charging. Specifically, we developed a Mixed Integer Program (MIP) which executes offline and optimally allocates EVs to charging stations. On top, we propose two alternative mechanisms to price the electricity the EVs charge. The first mechanism is a typical fixed-price one, while the second is a variation of the Vickrey?Clark?Groves (VCG) mechanism. We also developed online solutions that incrementally call the MIP-based algorithm and solve it for branches of EVs. In all cases, the EVs? aim is to minimize the price to pay and the impact on their driving schedule, acting as self-interested agents. We conducted a thorough empirical evaluation of our mechanisms and we observed that they had satisfactory scalability. Additionally, the VCG mechanism achieved an up to 2.2% improvement in terms of the number of vehicles that were charged compared to the fixed-price one and, in cases where the stations were congested, it calculated higher prices for the EVs and provided a higher profit for the stations, but lower utility to the EVs. However, in a theoretical evaluation, we proved that the variant of the VCG mechanism being proposed in this paper still guaranteed truthful reporting of the EVs? preferences. In contrast, the fixed-price one was found to be vulnerable to agents? strategic behavior as non-truthful EVs can charge instead of truthful ones. Finally, we observed the online algorithms to be, on average, at 95.6% of the offline ones in terms of the average number of serviced EVs.ensuremath</pensuremath>
2.
Rigas, Emmanouil; Ramchurn, Sarvapali; Bassiliades, Nick
Algorithms for electric vehicle scheduling in large-scale mobility-on-demand schemes Journal Article
In: Artificial Intelligence, vol. 262, pp. 248–278, 2018.
@article{soton422097,
title = {Algorithms for electric vehicle scheduling in large-scale mobility-on-demand schemes},
author = {Emmanouil Rigas and Sarvapali Ramchurn and Nick Bassiliades},
url = {https://eprints.soton.ac.uk/422097/},
year = {2018},
date = {2018-09-01},
journal = {Artificial Intelligence},
volume = {262},
pages = {248–278},
abstract = {We study a setting where Electric Vehicles (EVs) can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of customers that are serviced, or the total EV utilization. To do so, we characterise the optimisation problem as a max-flow problem in order to determine the set of feasible trips given the available EVs at each location. We then model and solve the EV-to-trip scheduling problem offline and optimally using Mixed Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP algorithm for medium to large problems and a greedy heuristic algorithm for very large problems. Moreover, we develop a tabu search-based local search technique to further improve upon and compare against the solution of the non-optimal algorithms. We study the performance of these algorithms in settings where either battery swap or battery charge at each station is used to cope with the EVs' limited driving range. Moreover, in settings where EVs need to be scheduled online, we propose a novel algorithm that accounts for the uncertainty in future trip requests. All algorithms are empirically evaluated using real-world data of locations of shared vehicle pick-up and drop-off stations. In our experiments, we observe that when all EVs carry the same battery which is large enough for the longest trips, the greedy algorithm with battery swap with the max-flow solution as a pre-processing step, provides the optimal solution. At the same time, the greedy algorithm with battery charge is close to the optimal (97% on average) and is further improved when local search is used. When some EVs do not have a large enough battery to execute some of the longest trips, the incremental-MIP generates solutions slightly better than the greedy, while the optimal algorithm is the best but scales up to medium sized problems only. Moreover, the online algorithm is shown to be on average at least 90% of the optimal. Finally, the greedy algorithm scales to 10-times more tasks than the incremental-MIP and 1000-times more than the static MIP in reasonable time.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
We study a setting where Electric Vehicles (EVs) can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of customers that are serviced, or the total EV utilization. To do so, we characterise the optimisation problem as a max-flow problem in order to determine the set of feasible trips given the available EVs at each location. We then model and solve the EV-to-trip scheduling problem offline and optimally using Mixed Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP algorithm for medium to large problems and a greedy heuristic algorithm for very large problems. Moreover, we develop a tabu search-based local search technique to further improve upon and compare against the solution of the non-optimal algorithms. We study the performance of these algorithms in settings where either battery swap or battery charge at each station is used to cope with the EVs' limited driving range. Moreover, in settings where EVs need to be scheduled online, we propose a novel algorithm that accounts for the uncertainty in future trip requests. All algorithms are empirically evaluated using real-world data of locations of shared vehicle pick-up and drop-off stations. In our experiments, we observe that when all EVs carry the same battery which is large enough for the longest trips, the greedy algorithm with battery swap with the max-flow solution as a pre-processing step, provides the optimal solution. At the same time, the greedy algorithm with battery charge is close to the optimal (97% on average) and is further improved when local search is used. When some EVs do not have a large enough battery to execute some of the longest trips, the incremental-MIP generates solutions slightly better than the greedy, while the optimal algorithm is the best but scales up to medium sized problems only. Moreover, the online algorithm is shown to be on average at least 90% of the optimal. Finally, the greedy algorithm scales to 10-times more tasks than the incremental-MIP and 1000-times more than the static MIP in reasonable time.
Selected Publications
Multi-agent signal-less intersection management with dynamic platoon formation
No data available.
https://eprints.soton.ac.uk/478647/
@inproceedings{soton478647,
title = {Multi-agent signal-less intersection management with dynamic platoon formation},
author = {Phuriwat Worrawichaipat and Enrico Gerding and Ioannis Kaparias and Sarvapali Ramchurn},
url = {https://eprints.soton.ac.uk/478647/},
year = {2023},
date = {2023-05-01},
booktitle = {22nd International Conference on Autonomous Agents and Multiagent Systems (29/05/23 - 02/06/23)},
pages = {1542--1550},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
title = {Multi-agent signal-less intersection management with dynamic platoon formation},
author = {Phuriwat Worrawichaipat and Enrico Gerding and Ioannis Kaparias and Sarvapali Ramchurn},
url = {https://eprints.soton.ac.uk/478647/},
year = {2023},
date = {2023-05-01},
booktitle = {22nd International Conference on Autonomous Agents and Multiagent Systems (29/05/23 - 02/06/23)},
pages = {1542--1550},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
AI Foundation Models: initial review, CMA Consultation, TAS Hub Response
No data available.
https://eprints.soton.ac.uk/477553/
@misc{soton477553,
title = {AI Foundation Models: initial review, CMA Consultation, TAS Hub Response},
author = {Joshua Krook and Derek McAuley and Stuart Anderson and John Downer and Peter Winter and Sarvapali D Ramchurn},
url = {https://eprints.soton.ac.uk/477553/},
year = {2023},
date = {2023-06-01},
publisher = {University of Southampton},
keywords = {},
pubstate = {published},
tppubtype = {misc}
}
title = {AI Foundation Models: initial review, CMA Consultation, TAS Hub Response},
author = {Joshua Krook and Derek McAuley and Stuart Anderson and John Downer and Peter Winter and Sarvapali D Ramchurn},
url = {https://eprints.soton.ac.uk/477553/},
year = {2023},
date = {2023-06-01},
publisher = {University of Southampton},
keywords = {},
pubstate = {published},
tppubtype = {misc}
}
The effect of data visualisation quality and task density on human-swarm interaction
No data available.
https://eprints.soton.ac.uk/479970/
@inproceedings{soton479970,
title = {The effect of data visualisation quality and task density on human-swarm interaction},
author = {Ayodeji Abioye and Mohammad Naiseh and William Hunt and Jediah R Clark and Sarvapali D Ramchurn and Mohammad Soorati},
url = {https://eprints.soton.ac.uk/479970/},
year = {2023},
date = {2023-06-01},
booktitle = {Proceedings of the 2023 32nd IEEE International Conference on Robot and Human Interactive Communication (RO-MAN)},
publisher = {IEEE},
abstract = {Despite the advantages of having robot swarms, human supervision is required for real-world applications. The performance of the human-swarm system depends on several factors including the data availability for the human operators. In this paper, we study the human factors aspect of the human-swarm interaction and investigate how having access to high-quality data can affect the performance of the human-swarm system - the number of tasks completed and the human trust level in operation. We designed an experiment where a human operator is tasked to operate a swarm to identify casualties in an area within a given time period. One group of operators had the option to request high-quality pictures while the other group had to base their decision on the available low-quality images. We performed a user study with 120 participants and recorded their success rate (directly logged via the simulation platform) as well as their workload and trust level (measured through a questionnaire after completing a human-swarm scenario). The findings from our study indicated that the group granted access to high-quality data exhibited an increased workload and placed greater trust in the swarm, thus confirming our initial hypothesis. However, we also found that the number of accurately identified casualties did not significantly vary between the two groups, suggesting that data quality had no impact on the successful completion of tasks.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
title = {The effect of data visualisation quality and task density on human-swarm interaction},
author = {Ayodeji Abioye and Mohammad Naiseh and William Hunt and Jediah R Clark and Sarvapali D Ramchurn and Mohammad Soorati},
url = {https://eprints.soton.ac.uk/479970/},
year = {2023},
date = {2023-06-01},
booktitle = {Proceedings of the 2023 32nd IEEE International Conference on Robot and Human Interactive Communication (RO-MAN)},
publisher = {IEEE},
abstract = {Despite the advantages of having robot swarms, human supervision is required for real-world applications. The performance of the human-swarm system depends on several factors including the data availability for the human operators. In this paper, we study the human factors aspect of the human-swarm interaction and investigate how having access to high-quality data can affect the performance of the human-swarm system - the number of tasks completed and the human trust level in operation. We designed an experiment where a human operator is tasked to operate a swarm to identify casualties in an area within a given time period. One group of operators had the option to request high-quality pictures while the other group had to base their decision on the available low-quality images. We performed a user study with 120 participants and recorded their success rate (directly logged via the simulation platform) as well as their workload and trust level (measured through a questionnaire after completing a human-swarm scenario). The findings from our study indicated that the group granted access to high-quality data exhibited an increased workload and placed greater trust in the swarm, thus confirming our initial hypothesis. However, we also found that the number of accurately identified casualties did not significantly vary between the two groups, suggesting that data quality had no impact on the successful completion of tasks.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Demonstrating performance benefits of human-swarm teaming
Autonomous swarms of robots can bring robustness, scalability and adaptability to safety-critical tasks such as search and rescue but their application is still very limited. Using semi-autonomous swarms with human control can bring robot swarms to real-world applications. Human operators can define goals for the swarm, monitor their performance and interfere with, or overrule, the decisions and behaviour. We present the "Human And Robot Interactive Swarm'' simulator (HARIS) that allows multi-user interaction with a robot swarm and facilitates qualitative and quantitative user studies through simulation of robot swarms completing tasks, from package delivery to search and rescue, with varying levels of human control. In this demonstration, we showcase the simulator by using it to study the performance gain offered by maintaining a "human-in-the-loop'' over a fully autonomous system as an example. This is illustrated in the context of search and rescue, with an autonomous allocation of resources to those in need.
https://eprints.soton.ac.uk/479903/
@inproceedings{soton479903,
title = {Demonstrating performance benefits of human-swarm teaming},
author = {William Hunt and Jack Ryan and Ayodeji O Abioye and Sarvapali D Ramchurn and Mohammad D Soorati},
url = {https://eprints.soton.ac.uk/479903/},
year = {2023},
date = {2023-05-01},
booktitle = {Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems},
pages = {3062--3064},
publisher = {International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)},
abstract = {Autonomous swarms of robots can bring robustness, scalability and adaptability to safety-critical tasks such as search and rescue but their application is still very limited. Using semi-autonomous swarms with human control can bring robot swarms to real-world applications. Human operators can define goals for the swarm, monitor their performance and interfere with, or overrule, the decisions and behaviour. We present the "Human And Robot Interactive Swarm'' simulator (HARIS) that allows multi-user interaction with a robot swarm and facilitates qualitative and quantitative user studies through simulation of robot swarms completing tasks, from package delivery to search and rescue, with varying levels of human control. In this demonstration, we showcase the simulator by using it to study the performance gain offered by maintaining a "human-in-the-loop'' over a fully autonomous system as an example. This is illustrated in the context of search and rescue, with an autonomous allocation of resources to those in need.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
title = {Demonstrating performance benefits of human-swarm teaming},
author = {William Hunt and Jack Ryan and Ayodeji O Abioye and Sarvapali D Ramchurn and Mohammad D Soorati},
url = {https://eprints.soton.ac.uk/479903/},
year = {2023},
date = {2023-05-01},
booktitle = {Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems},
pages = {3062--3064},
publisher = {International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)},
abstract = {Autonomous swarms of robots can bring robustness, scalability and adaptability to safety-critical tasks such as search and rescue but their application is still very limited. Using semi-autonomous swarms with human control can bring robot swarms to real-world applications. Human operators can define goals for the swarm, monitor their performance and interfere with, or overrule, the decisions and behaviour. We present the "Human And Robot Interactive Swarm'' simulator (HARIS) that allows multi-user interaction with a robot swarm and facilitates qualitative and quantitative user studies through simulation of robot swarms completing tasks, from package delivery to search and rescue, with varying levels of human control. In this demonstration, we showcase the simulator by using it to study the performance gain offered by maintaining a "human-in-the-loop'' over a fully autonomous system as an example. This is illustrated in the context of search and rescue, with an autonomous allocation of resources to those in need.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
2022
Rigas, Emmanouil S; Gerding, Enrico H; Stein, Sebastian; Ramchurn, Sarvapali D; Bassiliades, Nick
Mechanism design for efficient offline and online allocation of electric vehicles to charging stations Journal Article
In: Energies, vol. 15, no. 5, 2022, (Funding Information: Funding: This research study was co-financed by Greece and the European Union (European Social Fund–ESF) through the Operational Programme ?Human Resources Development, Education and Lifelong Learning? in the context of the project ?Reinforcement of Postdoctoral Researchers-2nd Cycle? (MIS-5033021), implemented by State Scholarships Foundation (IKY). Copyright 2022 Elsevier B.V., All rights reserved.).
@article{soton455806,
title = {Mechanism design for efficient offline and online allocation of electric vehicles to charging stations},
author = {Emmanouil S Rigas and Enrico H Gerding and Sebastian Stein and Sarvapali D Ramchurn and Nick Bassiliades},
url = {https://eprints.soton.ac.uk/455806/},
year = {2022},
date = {2022-03-01},
journal = {Energies},
volume = {15},
number = {5},
abstract = {ensuremath<pensuremath>The industry related to electric vehicles (EVs) has seen a substantial increase in recent years, as such vehicles have the ability to significantly reduce total COensuremath<subensuremath>2ensuremath</subensuremath> emissions and the related global warming effect. In this paper, we focus on the problem of allocating EVs to charging stations, scheduling and pricing their charging. Specifically, we developed a Mixed Integer Program (MIP) which executes offline and optimally allocates EVs to charging stations. On top, we propose two alternative mechanisms to price the electricity the EVs charge. The first mechanism is a typical fixed-price one, while the second is a variation of the Vickrey?Clark?Groves (VCG) mechanism. We also developed online solutions that incrementally call the MIP-based algorithm and solve it for branches of EVs. In all cases, the EVs? aim is to minimize the price to pay and the impact on their driving schedule, acting as self-interested agents. We conducted a thorough empirical evaluation of our mechanisms and we observed that they had satisfactory scalability. Additionally, the VCG mechanism achieved an up to 2.2% improvement in terms of the number of vehicles that were charged compared to the fixed-price one and, in cases where the stations were congested, it calculated higher prices for the EVs and provided a higher profit for the stations, but lower utility to the EVs. However, in a theoretical evaluation, we proved that the variant of the VCG mechanism being proposed in this paper still guaranteed truthful reporting of the EVs? preferences. In contrast, the fixed-price one was found to be vulnerable to agents? strategic behavior as non-truthful EVs can charge instead of truthful ones. Finally, we observed the online algorithms to be, on average, at 95.6% of the offline ones in terms of the average number of serviced EVs.ensuremath</pensuremath>},
note = {Funding Information:
Funding: This research study was co-financed by Greece and the European Union (European Social Fund–ESF) through the Operational Programme ?Human Resources Development, Education and Lifelong Learning? in the context of the project ?Reinforcement of Postdoctoral Researchers-2nd Cycle? (MIS-5033021), implemented by State Scholarships Foundation (IKY).
Copyright 2022 Elsevier B.V., All rights reserved.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
ensuremath<pensuremath>The industry related to electric vehicles (EVs) has seen a substantial increase in recent years, as such vehicles have the ability to significantly reduce total COensuremath<subensuremath>2ensuremath</subensuremath> emissions and the related global warming effect. In this paper, we focus on the problem of allocating EVs to charging stations, scheduling and pricing their charging. Specifically, we developed a Mixed Integer Program (MIP) which executes offline and optimally allocates EVs to charging stations. On top, we propose two alternative mechanisms to price the electricity the EVs charge. The first mechanism is a typical fixed-price one, while the second is a variation of the Vickrey?Clark?Groves (VCG) mechanism. We also developed online solutions that incrementally call the MIP-based algorithm and solve it for branches of EVs. In all cases, the EVs? aim is to minimize the price to pay and the impact on their driving schedule, acting as self-interested agents. We conducted a thorough empirical evaluation of our mechanisms and we observed that they had satisfactory scalability. Additionally, the VCG mechanism achieved an up to 2.2% improvement in terms of the number of vehicles that were charged compared to the fixed-price one and, in cases where the stations were congested, it calculated higher prices for the EVs and provided a higher profit for the stations, but lower utility to the EVs. However, in a theoretical evaluation, we proved that the variant of the VCG mechanism being proposed in this paper still guaranteed truthful reporting of the EVs? preferences. In contrast, the fixed-price one was found to be vulnerable to agents? strategic behavior as non-truthful EVs can charge instead of truthful ones. Finally, we observed the online algorithms to be, on average, at 95.6% of the offline ones in terms of the average number of serviced EVs.ensuremath</pensuremath>
2018
Rigas, Emmanouil; Ramchurn, Sarvapali; Bassiliades, Nick
Algorithms for electric vehicle scheduling in large-scale mobility-on-demand schemes Journal Article
In: Artificial Intelligence, vol. 262, pp. 248–278, 2018.
@article{soton422097,
title = {Algorithms for electric vehicle scheduling in large-scale mobility-on-demand schemes},
author = {Emmanouil Rigas and Sarvapali Ramchurn and Nick Bassiliades},
url = {https://eprints.soton.ac.uk/422097/},
year = {2018},
date = {2018-09-01},
journal = {Artificial Intelligence},
volume = {262},
pages = {248–278},
abstract = {We study a setting where Electric Vehicles (EVs) can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of customers that are serviced, or the total EV utilization. To do so, we characterise the optimisation problem as a max-flow problem in order to determine the set of feasible trips given the available EVs at each location. We then model and solve the EV-to-trip scheduling problem offline and optimally using Mixed Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP algorithm for medium to large problems and a greedy heuristic algorithm for very large problems. Moreover, we develop a tabu search-based local search technique to further improve upon and compare against the solution of the non-optimal algorithms. We study the performance of these algorithms in settings where either battery swap or battery charge at each station is used to cope with the EVs' limited driving range. Moreover, in settings where EVs need to be scheduled online, we propose a novel algorithm that accounts for the uncertainty in future trip requests. All algorithms are empirically evaluated using real-world data of locations of shared vehicle pick-up and drop-off stations. In our experiments, we observe that when all EVs carry the same battery which is large enough for the longest trips, the greedy algorithm with battery swap with the max-flow solution as a pre-processing step, provides the optimal solution. At the same time, the greedy algorithm with battery charge is close to the optimal (97% on average) and is further improved when local search is used. When some EVs do not have a large enough battery to execute some of the longest trips, the incremental-MIP generates solutions slightly better than the greedy, while the optimal algorithm is the best but scales up to medium sized problems only. Moreover, the online algorithm is shown to be on average at least 90% of the optimal. Finally, the greedy algorithm scales to 10-times more tasks than the incremental-MIP and 1000-times more than the static MIP in reasonable time.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
We study a setting where Electric Vehicles (EVs) can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of customers that are serviced, or the total EV utilization. To do so, we characterise the optimisation problem as a max-flow problem in order to determine the set of feasible trips given the available EVs at each location. We then model and solve the EV-to-trip scheduling problem offline and optimally using Mixed Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP algorithm for medium to large problems and a greedy heuristic algorithm for very large problems. Moreover, we develop a tabu search-based local search technique to further improve upon and compare against the solution of the non-optimal algorithms. We study the performance of these algorithms in settings where either battery swap or battery charge at each station is used to cope with the EVs' limited driving range. Moreover, in settings where EVs need to be scheduled online, we propose a novel algorithm that accounts for the uncertainty in future trip requests. All algorithms are empirically evaluated using real-world data of locations of shared vehicle pick-up and drop-off stations. In our experiments, we observe that when all EVs carry the same battery which is large enough for the longest trips, the greedy algorithm with battery swap with the max-flow solution as a pre-processing step, provides the optimal solution. At the same time, the greedy algorithm with battery charge is close to the optimal (97% on average) and is further improved when local search is used. When some EVs do not have a large enough battery to execute some of the longest trips, the incremental-MIP generates solutions slightly better than the greedy, while the optimal algorithm is the best but scales up to medium sized problems only. Moreover, the online algorithm is shown to be on average at least 90% of the optimal. Finally, the greedy algorithm scales to 10-times more tasks than the incremental-MIP and 1000-times more than the static MIP in reasonable time.