# Online Optimization of Pickup and Delivery Problem Considering Feasibility
## 1 Introduction  
There has been much attention paid to control technologies for realizing a smart city [1]. In a smart city, many services using control technologies should be developed, such as transportation, energy distribution, healthcare, environmental monitoring, business, commerce, emergency response, and social activities. Moreover, in control technologies for a smart city, a cyber-physical system (CPS) plays an important role. A CPS is a system where physical and information components are deeply connected through a communication network. In a smart city, multiple physical components such as mobile robots are controlled by information systems, such as cloud servers. Hence, a plant in a smart city is modeled as a CPS. Thus, in a smart city and a CPS, it is important to develop a control method for multiple agents. In this paper, we focus on a control method for multiple agents. Control of multiple agents has several applications and has been widely studied. In the control of multiple agents, there are several problem settings, such as the achievement of cooperative tasks and surveillance (patrol). A control specification in cooperative tasks may be given by linear temporal logic formulas [2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16]. Temporal logic is a logical system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time (for example, \"I will eventually be hungry\"). The surveillance problem is to find agents' paths patrolling a given area as evenly as possible [17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28]. In problem settings on the control of multiple agents, model predictive control (MPC) is frequently used (see, e.g., [9; 22; 27]). MPC is a control method in which the control input is generated by solving at each time the finite-time optimal control problem (see, e.g., [29; 30]). In other words, the control input is calculated based on the prediction using a mathematical model. MPC was frequently used in the control of chemical plants. In recent years, with the development of computers, MPC has been used in the control of several systems, such as automobiles. In the case where a target area is unknown and is changed in time, a model-free approach such as machine learning is effective (see, e.g., [31; 32]). In this paper, we suppose that a target area is fixed and use a model-based approach. In this paper, we focus on the pickup and delivery problem as one of the control problems of multiple agents. In recent years, the food delivery market has been expanding through the coronavirus epidemic. Efficient delivery from the restaurant to the customer is becoming more and more important. Such a problem of efficiently delivering goods received at a certain location to the desired location is called a pickup and delivery problem (see, e.g., [33; 34; 35; 36; 37; 38; 39; 40; 41]). Especially, the problem of updating routes by solving optimization problems at regular intervals is called an online pickup and delivery problem, which has been studied extensively in recent years (see, e.g., [42; 43; 44]). In pickup and delivery problems, it is important to use electric vehicles and drones as agents. Electric vehicles and drones have the disadvantage of severe battery constraints. Hence, fuel constraints must be considered in pickup and delivery problems. In [45; 46], a modeling method to handle the fueling of vehicles has been proposed. A fuel constraint in the proposed method is basically the same as in [45; 46]. Refueling is different. In this paper, the fuel of a vehicle immediately becomes full by changing the battery. Furthermore, when electric vehicles and drones are used, demand forecasting is important (see, e.g., [47; 48]). This is because more efficient moves are needed due to battery constraints. For example, many agents can be placed in advance at points where demand is concentrated. To the best of our knowledge, few results have been obtained.