کنترل مسیر پیش بینی شده برای سیستم های رسیدگی چمدان خودکار با استفاده از برنامه ریزی خطی عدد صحیح مختلط

State-of-the-art baggage handling systems transport luggage in an automated way using destination coded vehicles (DCVs). These vehicles transport the bags at high speeds on a network of tracks. In this paper we consider the problem of controlling the route of each DCV in the system. In general this results in a nonlinear, nonconvex, mixed-integer optimization problem, usually very expensive in terms of computational effort. Therefore, we present an alternative approach for reducing the complexity of the computations by simplifying and approximating the nonlinear optimization problem by a mixed-integer linear programming (MILP) problem. The advantage is that for MILP problems solvers are available that allow us to efficiently compute the global optimal solution. The solution of the MILP problem can then be used as a good initial starting point for the original nonlinear optimization problem. We use model predictive control (MPC) for solving the route choice problem. To assess the performance of the proposed (nonlinear and MILP) formulations of the MPC optimization problem, we consider a benchmark case study, the results being compared for several scenarios.

Modern baggage handling systems in airports transport luggage at high speeds using destination coded vehicles (DCVs) that transport the bags in an automated way on a network of tracks. The DCV-based baggage handling system has two levels of control. The low-level controllers ensure the coordination and synchronization when loading a bag onto a DCV, in order to avoid damaging the bags or blocking the system, and when unloading it to the corresponding end point. Low-level controllers also compute the velocity of the DCVs such that collisions are avoided. These low-level controllers are typically Proportional Integral Derivative (PID) controllers and logic controllers that can stop the DCV when necessary. Higher-level controllers compute the route assignment for each bag in the network. Currently, the DCVs are routed through the system using routing schemes based on preferred routes. These routing schemes can be adapted to respond to the occurrence of predefined events. However, as argued in de Neufville (1994), the patterns of loads on the system are highly variable, depending on e.g. the season, time of the day, type of aircraft at each gate, number of passengers for each flight. Therefore, we do not consider predefined preferred routes. Instead we develop advanced control methods to determine the optimal routing in case of dynamic demand. For applications such as automated guided vehicles route planning or traffic route guidance, the route assignment problem has been addressed in e.g. Gang et al., 1996 and Kaufman et al., 1998. The optimal AGV or traffic guidance routes are the shortest-path or the shortest-time routes. Since we want the bags to arrive at their end point within given time windows, the problem of routing DCVs cannot be solved using the methods for routing of AGVs or traffic flows. The problem of routing the DCVs of a baggage handling system is presented in Fay, 2005 and Hallenborg and Demazeau, 2006. The solution proposed in Fay (2005) uses an analogy to data transmission through internet, but without presenting any experimental results, while in Hallenborg and Demazeau (2006) a multi-agent approach is developed. However, the later reference is not focused on control approaches for computing the optimal route of DCVs, but on designing a multi-agent hierarchy for baggage handling systems and analyzing the communication requirements. The goal of our work is to develop and compare efficient control approaches for route choice control of each individual DCV. Theoretically, the maximum performance of such a DCV-based baggage handling system would be obtained if one computes the optimal routes using optimal control (Lewis, 1986). However, as shown in Tarău et al. (2008), this control method becomes intractable in practice due to the heavy computation burden. Therefore, in order to make a trade-off between computational effort and optimality, in Tarău et al. (2009), we have developed centralized and decentralized model predictive control (MPC). MPC is an on-line model-based predictive control design method, see e.g. Maciejowski (2002), that uses a receding horizon principle. As the results confirmed, centralized MPC requires high computation time to determine a solution. The use of decentralized control lowers the computation time, but this comes at the cost of suboptimality. In this paper we investigate whether the computational effort required for computing the route of each DCV by using centralized MPC can be lowered by using mixed-integer linear programming (MILP). The large computation time obtained in previous work comes from solving nonlinear, nonconvex, mixed-integer optimization problems. Note that such problems may also have multiple local minima and are NP-hard, and therefore, difficult to solve. So, the main contribution of this paper is that we rewrite the route choice problem as an MILP problem, for which efficient solvers are available. The solution of this MILP will then be used as an initial starting point for the original nonlinear optimization problem. The paper is organized as follows. Section 2 briefly introduces the concepts of MPC and MILP that will be used later on in solving the route choice problem. In Section 2 we also briefly recapitulate an event-driven route choice model that we have developed in Tarău et al. (2008). Afterwards, in Section 3 we simplify the model of Section 2 by considering streams of bags instead of individual bags, and we show that this model can be written in the mixed-integer linear form. In Section 4, we propose two formulations for the MPC optimization problem. The first formulation corresponds to the nonlinear route choice problem, while the second one corresponds to the MILP route choice problem. For a simple case study, we compare of the proposed formulations. The analysis of the simulation results is elaborated in Section 5. The results indicate that computing the DCV routing using the original nonlinear formulation for the MPC optimization problem gives better performance than using the MILP formulation, but at the cost of significantly higher computational efforts. To reduce the computation time while obtaining good results, we solve the original MPC optimization problem, but using at each step the local solution of the corresponding MILP formulation as initial guess. Finally, Section 6 are drawn and directions of future research are presented.

We have considered the problem of efficiently computing (sub)optimal routes for destination coded vehicle (DCV) that transport bags in an airport on a “mini” railway network. This results in a nonlinear, nonconvex, mixed-integer optimization problem that is very expensive to solve in terms of computational effort. Therefore, we have proposed an alternative approach for reducing the complexity of the computations by approximating the nonlinear optimization problem by a mixed-integer linear programming (MILP) problem. The advantage is that for MILP problems solvers are available that allow us to efficiently compute the global optimal solution. These two formulations of the optimization problem have been used to compute the route of DCVs using model predictive control (MPC) for a benchmark case study. Simulation results confirm that computing the route choice using the original nonlinear formulation for the MPC optimization problem gives usually better performance than using the MILP formulation, but at the cost of significantly higher computational efforts. To reduce the computation time while obtaining good results, one can solve the original MPC optimization problem, but using at each step the local solution of the corresponding MILP formulation as initial guess. In future work we will apply this method to more complex case studies and scenarios. We will perform sensitivity analysis on the deviation with respect to the desired outflow and the queues length. Furthermore, we will also consider reducing the computation time by developing hierarchical route choice control.