Affiliations: [a] Laboratoire Hubert Curien UMR CNRS 5516, Institut Henri Fayol, Mines Saint Étienne, Saint Étienne, France. E-mails: [email protected], [email protected] | [b] LIMOS UMR CNRS 6158, Institut Henri Fayol, Mines Saint Étienne, Saint Étienne, France. E-mail: [email protected] | [c] ONERA/DTIS, Université de Toulouse, 2 Avenue Edouard Belin, 31055, Toulouse Cedex 4, France. E-mail: [email protected]
Abstract: 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.
