Show simple item record

hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorFROGER, Aurélien
hal.structure.identifierPolitecnico di Milano [Milan] [POLIMI]
dc.contributor.authorJABALI, Ola
hal.structure.identifierHEC Montréal [HEC Montréal]
dc.contributor.authorMENDOZA, Jorge E.
hal.structure.identifierHEC Montréal [HEC Montréal]
hal.structure.identifierUniversity of Bath [Bath]
dc.contributor.authorLAPORTE, Gilbert
dc.date.accessioned2024-04-04T02:43:06Z
dc.date.available2024-04-04T02:43:06Z
dc.date.issued2022
dc.identifier.issn0041-1655
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191305
dc.description.abstractEnMuch of the existing research on electric vehicle routing problems (E-VRPs) assumes that the charging stations (CSs) can simultaneously charge an unlimited number of electric vehicles, but this is not the case. In this research, we investigate how to model and solve E-VRPs taking into account these capacity restrictions. In particular, we study an E-VRP with non-linear charging functions, multiple charging technologies, en route charging, and variable charging quantities, while explicitly accounting for the capacity of CSs expressed in the number of chargers. We refer to this problem as the E-VRP with non-linear charging functions and capacitated stations (E-VRP-NL-C). This problem advances the E-VRP literature by considering the scheduling of charging operations at each CS. We first introduce two mixed integer linear programming formulations showing how CS capacity constraints can be incorporated into E-VRP models. We then introduce an algorithmic framework to the E-VRP-NL-C, that iterates between two main components: a route generator and a solution assembler. The route generator uses an iterated local search algorithm to build a pool of high-quality routes. The solution assembler applies a branch-and-cut algorithm to select a subset of routes from the pool. We report on computational experiments comparing four different assembly strategies on a large and diverse set of instances. Our results show that our algorithm deals with the CS capacity constraints effectively. Furthermore, considering the well-known uncapacitated version of the E-VRP-NL-C, our solution method identifies new best-known solutions for 80 out of 120 instances.
dc.description.sponsorshipOptimisation des Tournées de Véhicules Electriques - ANR-15-CE22-0005
dc.language.isoen
dc.publisherINFORMS
dc.subject.enMatheuristic
dc.subject.enMixed integer linear programming
dc.subject.enElectric vehicle routing
dc.subject.enNon-linear charging function
dc.subject.enSynchronization constraints
dc.subject.enIterated local search
dc.subject.enBranch-and-cut
dc.subject.ennon-linear charging function
dc.subject.ensynchronization constraints
dc.subject.enmixed integer linear programming
dc.subject.enmatheuristic
dc.subject.eniterated local search
dc.subject.enbranch-and-cut
dc.title.enThe electric vehicle routing problem with capacitated charging stations
dc.typeArticle de revue
dc.identifier.doi10.1287/trsc.2021.1111
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalTransportation Science
bordeaux.page460-482
bordeaux.volume56
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue2
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-02386167
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-02386167v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Transportation%20Science&rft.date=2022&rft.volume=56&rft.issue=2&rft.spage=460-482&rft.epage=460-482&rft.eissn=0041-1655&rft.issn=0041-1655&rft.au=FROGER,%20Aur%C3%A9lien&JABALI,%20Ola&MENDOZA,%20Jorge%20E.&LAPORTE,%20Gilbert&rft.genre=article


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record