The multiple vehicle routing problem (mVRP) concerns the scheduling of multiple vehicles so as to visit some locations of interest. We study a dynamic version of mVRP where the travel costs are not a priori known and may vary at runtime. Moreover, we introduce energy-related constraints which make the problem more complex. Vehicles have only finite energy reserves, which gradually diminish as they move between different locations, but can also gain some energy at specific depot locations. The objective is to visit all locations of interest as fast as possible without any vehicle exhausting its energy. We propose an online algorithm based on the Large Neighbourhood Search (LNS) heuristic. We evaluate the algorithm for different topologies and degrees of vehicle autonomy. Our results show that it achieves significantly better results than an offline algorithm that produces a safe schedule based on worst-case cost estimates.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Dynamic Multiple Vehicle Routing under Energy Capacity Constraints*


    Contributors:


    Publication date :

    2020-09-20


    Size :

    2062329 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Dynamic Multicast Routing Algorithm Satisfying Multiple QoS Constraints

    Li, W. / Zengzhi, L. / Chengqian, S. | British Library Online Contents | 2004


    VEHICLE ROUTING WITH COMPARTMENTS UNDER PRODUCT INCOMPATIBILITY CONSTRAINTS

    Tasar, Bahar / Eliiyi, Deniz Tursel / Kandiller, Levent | BASE | 2019

    Free access

    Optimizing vehicle routing and scheduling under time constraints

    Bala Karlo / Bandecchi Michele / Brcanov Dejan et al. | DOAJ | 2024

    Free access

    Modelling Airline Network Routing and Scheduling under Airport Capacity Constraints

    Evans, A. / Schafer, A. / Dray, L. et al. | British Library Conference Proceedings | 2008


    Vehicle Routing with Compartments Under Product Incompatibility Constraints

    Tasar, Bahar / Türsel Eliiyi, Deniz / Kandiller, Levent | BASE | 2019

    Free access