An adaptive large neighborhood search heuristic for the Electric Vehicle Scheduling Problem

M. Wen, Esben Linde, Stefan Røpke, P. Mirchandani, Allan Larsen

    Research output: Contribution to journalJournal articleResearchpeer-review

    115 Downloads (Pure)

    Abstract

    This paper addresses the Electric Vehicle Scheduling Problem (E-VSP), in which a set of timetabled bus trips, each starting from and ending at specific locations and at specific times, should be carried out by a set of electric buses or vehicles based at a number of depots with limited driving ranges. The electric vehicles are allowed to be recharged fully or partially at any of the given recharging stations. The objective is to firstly minimize the number of vehicles needed to cover all the timetabled trips, and secondly to minimize the total traveling distance, which is equivalent to minimizing the total deadheading distance. A mixed integer programming formulation as well as an Adaptive Large Neighborhood Search (ALNS) heuristic for the E-VSP are presented. ALNS is tested on newly generated E-VSP benchmark instances. Result shows that the proposed heuristic can provide good solutions to large E-VSP instances and optimal or near-optimal solutions to small E-VSP instances.
    Original languageEnglish
    JournalComputers & Operations Research
    Volume76
    Pages (from-to)73-83
    Number of pages11
    ISSN0305-0548
    DOIs
    Publication statusPublished - 2016

    Keywords

    • Electric vehicles
    • Large neighborhood search
    • Partial charging
    • Vehicle scheduling

    Cite this

    @article{5d145ce3509c42c3a51e8d88cc4e45c9,
    title = "An adaptive large neighborhood search heuristic for the Electric Vehicle Scheduling Problem",
    abstract = "This paper addresses the Electric Vehicle Scheduling Problem (E-VSP), in which a set of timetabled bus trips, each starting from and ending at specific locations and at specific times, should be carried out by a set of electric buses or vehicles based at a number of depots with limited driving ranges. The electric vehicles are allowed to be recharged fully or partially at any of the given recharging stations. The objective is to firstly minimize the number of vehicles needed to cover all the timetabled trips, and secondly to minimize the total traveling distance, which is equivalent to minimizing the total deadheading distance. A mixed integer programming formulation as well as an Adaptive Large Neighborhood Search (ALNS) heuristic for the E-VSP are presented. ALNS is tested on newly generated E-VSP benchmark instances. Result shows that the proposed heuristic can provide good solutions to large E-VSP instances and optimal or near-optimal solutions to small E-VSP instances.",
    keywords = "Electric vehicles, Large neighborhood search, Partial charging, Vehicle scheduling",
    author = "M. Wen and Esben Linde and Stefan R{\o}pke and P. Mirchandani and Allan Larsen",
    year = "2016",
    doi = "10.1016/j.cor.2016.06.013",
    language = "English",
    volume = "76",
    pages = "73--83",
    journal = "Computers & Operations Research",
    issn = "0305-0548",
    publisher = "Pergamon Press",

    }

    An adaptive large neighborhood search heuristic for the Electric Vehicle Scheduling Problem. / Wen, M.; Linde, Esben; Røpke, Stefan; Mirchandani, P.; Larsen, Allan.

    In: Computers & Operations Research, Vol. 76, 2016, p. 73-83.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - An adaptive large neighborhood search heuristic for the Electric Vehicle Scheduling Problem

    AU - Wen, M.

    AU - Linde, Esben

    AU - Røpke, Stefan

    AU - Mirchandani, P.

    AU - Larsen, Allan

    PY - 2016

    Y1 - 2016

    N2 - This paper addresses the Electric Vehicle Scheduling Problem (E-VSP), in which a set of timetabled bus trips, each starting from and ending at specific locations and at specific times, should be carried out by a set of electric buses or vehicles based at a number of depots with limited driving ranges. The electric vehicles are allowed to be recharged fully or partially at any of the given recharging stations. The objective is to firstly minimize the number of vehicles needed to cover all the timetabled trips, and secondly to minimize the total traveling distance, which is equivalent to minimizing the total deadheading distance. A mixed integer programming formulation as well as an Adaptive Large Neighborhood Search (ALNS) heuristic for the E-VSP are presented. ALNS is tested on newly generated E-VSP benchmark instances. Result shows that the proposed heuristic can provide good solutions to large E-VSP instances and optimal or near-optimal solutions to small E-VSP instances.

    AB - This paper addresses the Electric Vehicle Scheduling Problem (E-VSP), in which a set of timetabled bus trips, each starting from and ending at specific locations and at specific times, should be carried out by a set of electric buses or vehicles based at a number of depots with limited driving ranges. The electric vehicles are allowed to be recharged fully or partially at any of the given recharging stations. The objective is to firstly minimize the number of vehicles needed to cover all the timetabled trips, and secondly to minimize the total traveling distance, which is equivalent to minimizing the total deadheading distance. A mixed integer programming formulation as well as an Adaptive Large Neighborhood Search (ALNS) heuristic for the E-VSP are presented. ALNS is tested on newly generated E-VSP benchmark instances. Result shows that the proposed heuristic can provide good solutions to large E-VSP instances and optimal or near-optimal solutions to small E-VSP instances.

    KW - Electric vehicles

    KW - Large neighborhood search

    KW - Partial charging

    KW - Vehicle scheduling

    U2 - 10.1016/j.cor.2016.06.013

    DO - 10.1016/j.cor.2016.06.013

    M3 - Journal article

    VL - 76

    SP - 73

    EP - 83

    JO - Computers & Operations Research

    JF - Computers & Operations Research

    SN - 0305-0548

    ER -