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

Mahdi Zargayouna, Besma Zeddini

Abstract


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).

 


Keywords


vehicle routing problems, Multi-agent systems, Insertion heuristics

Full Text:

PDF


Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

Crossref Similarity Check logo

Crossref logologo_doaj