Vehicle routing problems are highly complex problems. The proposals to solve them traditionally concern the optimization of conventional criteria, such as the number of mobilized vehicles and the total costs. However, in online vehicle routing problems, the optimization of the response time to the connected travelers is at least as important as the optimization of the classical criteria. Multi-agent systems on the one hand and greedy insertion heuristics on the other are among the most promising approaches to this end. In this paper, we propose a multi-agent system coupled with a regret insertion heuristic. We focus on the real-time dispatching of the travelers' requests to the vehicles and its efficiency. A dispatching protocol determines which agents perform the computation to answer the travelers' requests. We evaluate three dispatching protocols: centralized, decentralized and hybrid. We compare them experimentally based on their response time to online travelers. Two computational types are implemented: a sequential implementation and a distributed implementation. The results show the superiority of the centralized dispatching protocol in the sequential implementation (32.80% improvement in average compared to the distributed dispatching protocol) and the superiority of the hybrid dispatching protocol in the distributed implementation (59.66% improvement in average, compared with the centralized dispatching protocol).


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Dispatching Requests for Agent-Based Online Vehicle Routing Problems with Time Windows


    Beteiligte:

    Erscheinungsdatum :

    2020-01-01


    Anmerkungen:

    Journal of computing and information technology ; ISSN 1330-1136 (Print) ; ISSN 1846-3908 (Online) ; Volume 28 ; Issue 1


    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    Selective vehicle routing problem with reserved requests and time windows

    Zheng, Wenjia / Zou, Yujian / Sun, Liucheng | IEEE | 2023



    Self-imposed time windows in vehicle routing problems

    JABALI, OLA / Leus, Roel / van Woensel, Tom et al. | BASE | 2015

    Freier Zugriff

    Hierarchical reinforcement learning for vehicle routing problems with time windows

    Wang, Yunli / Sun, Sun / Li, Wei | BASE | 2021

    Freier Zugriff

    Offline—Online Approximate Dynamic Programming for Dynamic Vehicle Routing with Stochastic Requests

    Ulmer, Marlin W. / Goodson, Justin C. / Mattfeld, Dirk C. et al. | British Library Online Contents | 2019