Si trova su / Altri legami
© 2021 – IOS Press.On–Demand Transport (ODT) systems have attracted increasing attention in recent years. Traditional centralized dispatching can achieve optimal solutions, but NP–Hard complexity makes it unsuitable for online and dynamic problems. Centralized and decentralized heuristics can achieve fast, feasible solution at run–time with no guarantee on the quality. Starting from a feasible not optimal solution, we present in this paper a new solution model (ORNInA) consisting of two parallel coordination processes. The first one is a decentralized insertion–heuristic based algorithm to build vehicle schedules in order to solve a particular case of the dynamic Dial–A–Ride–Problem (DARP) as an ODT system, in which vehicles communicate via Vehicle–to–vehicle communication (V2V) and make decentralized decisions. The second coordination scheme is a continuous optimization process namely Pull–demand protocol, based on combinatorial auctions, in order to improve the quality of the global solution achieved by decentralized decision at run–time by exchanging resources between vehicles (k–opt). In its simplest implementation, k is set to 1 so that vehicles can exchange only one resource at a time. We evaluate and analyze the promising results of our contributed techniques on synthetic data for taxis operating in Saint–Étienne city, against a classical decentralized greedy approach and a centralized one that uses a classical mixed–integer linear program (MILP) solver.
