Scalability for Multivehicle Coordination With Dial-a-Ride Application

• 成果类型: Article
• 署名作者: Zhang, Wentao; Hu, Guoqiang; Zhang, Hui; Wang, Yaonan
• 署名单位: Nanyang Technological University; Hunan University; Nanyang Technological University; Hunan University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2025.3573251
• 发表日期: 2025
• 关键词: decomposition; optimization; time

摘要

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 article formulates the DARP into an architecture that 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.