Scalability for Multivehicle Coordination With Dial-a-Ride Application

Abstract

When confronting a practical dial-a-ride problem (DARP), addressing the transportation demands of joining and removal at any operational time is of practical significance yet a theoretical challenge. To this end, this paper formulates the DARP into an architecturethat integrates a physical agent (vehicle or robot) and an information decision that suffers from a fluctuation of vector fields with respect to mixed-integer linear programming (MILP). Specifically, physical agents ensure that vehicles can interact with their neighbors to service the transportation demands, whereas information decision-making ensures a feasible vehicle route with minimal routing cost, despite the presence of fluctuations in transportation demand. For centralized open MILP, the feasibility is determined by the boundedness of a nonempty intersection generated by the involved half planes and the entire associated vector field. A resource allocation method is subsequently used, and the equivalence between the primal and dual programs is also studied. In this context, the problem at hand is abstracted into a framework of multivehicle coordination in which agents (vehicles) may be removed or added at any operational time. Afterward, conditions guaranteeing definiteness as well as computing the unique optimal solution via the cutting plane and split disjunction are derived. The considered DARP is deemed solvable, provided that the lower bound of fluctuation, the number of vehicles removed, the interacting topology and the effect of agent removal satisfy certain relations. The effectiveness of the proposed method is illustrated via a numerical instance.