{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T09:29:15Z","timestamp":1768901355332,"version":"3.49.0"},"reference-count":52,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2024,2,17]],"date-time":"2024-02-17T00:00:00Z","timestamp":1708128000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"JSPS KAKENHI","award":["JP21H04558"],"award-info":[{"award-number":["JP21H04558"]}]},{"name":"JSPS KAKENHI","award":["JP22K04163"],"award-info":[{"award-number":["JP22K04163"]}]},{"name":"JSPS KAKENHI","award":["JP23H01430"],"award-info":[{"award-number":["JP23H01430"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Future Internet"],"abstract":"<jats:p>A pickup and delivery problem by multiple agents has many applications, such as food delivery service and disaster rescue. In this problem, there are cases where fuels must be considered (e.g., the case of using drones as agents). In addition, there are cases where demand forecasting should be considered (e.g., the case where a large number of orders are carried by a small number of agents). In this paper, we consider an online pickup and delivery problem considering fuel and demand forecasting. First, the pickup and delivery problem with fuel constraints is formulated. The information on demand forecasting is included in the cost function. Based on the orders, the agents\u2019 paths (e.g., the paths from stores to customers) are calculated. We suppose that the target area is given by an undirected graph. Using a given graph, several constraints such as the moves and fuels of the agents are introduced. This problem is reduced to a mixed integer linear programming (MILP) problem. Next, in online optimization, the MILP problem is solved depending on the acceptance of orders. Owing to new orders, the calculated future paths may be changed. Finally, by using a numerical example, we present the effectiveness of the proposed method.<\/jats:p>","DOI":"10.3390\/fi16020064","type":"journal-article","created":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T05:10:04Z","timestamp":1708405804000},"page":"64","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Optimization of Pickup and Delivery Problem Considering Feasibility"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-0466-339X","authenticated-orcid":false,"given":"Ryo","family":"Matsuoka","sequence":"first","affiliation":[{"name":"Graduate School of Information Science and Technoloty, Hokkaido University, Sapporo 060-0814, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3358-0254","authenticated-orcid":false,"given":"Koichi","family":"Kobayashi","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science and Technoloty, Hokkaido University, Sapporo 060-0814, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7190-6609","authenticated-orcid":false,"given":"Yuh","family":"Yamashita","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science and Technoloty, Hokkaido University, Sapporo 060-0814, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2024,2,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/J.ENG.2016.02.012","article-title":"Smart cities as cyber-physical social systems","volume":"2","author":"Cassandras","year":"2016","journal-title":"Engineering"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1109\/TRO.2006.889492","article-title":"Temporal logic planning and control of robotic swarms by hierarchical abstractions","volume":"23","author":"Kloetzer","year":"2007","journal-title":"IEEE Trans. Robot."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1370","DOI":"10.1109\/TRO.2009.2030225","article-title":"Temporal-logic-based reactive mission and motion planning","volume":"25","author":"Fainekos","year":"2009","journal-title":"IEEE Trans. Robot."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1372","DOI":"10.1002\/rnc.1715","article-title":"Linear temporal logic vehicle routing with applications to multi-UAV mission planning","volume":"21","author":"Karaman","year":"2011","journal-title":"Int. J. Robust Nonlinear Control"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Ulusoy, A., Smith, S.L., Ding, X.C., and Belta, C. (2012, January 14\u201318). Robust multi-robot optimal path planning with temporal logic constraints. Proceedings of the 2012 IEEE International Conference on Robotics and Automation, Saint Paul, MN, USA.","DOI":"10.1109\/ICRA.2012.6224792"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/j.automatica.2013.11.030","article-title":"LTL receding horizon control for finite deterministic systems","volume":"50","author":"Ding","year":"2014","journal-title":"Automatica"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Raman, V., Donz\u00e9, A., Maasoumy, M., Murray, R.M., Sangiovanni-Vincentelli, A., and Seshia, S.A. (2014, January 15\u201317). Model predictive control with signal temporal logic specifications. Proceedings of the 53rd IEEE Conference on Decision and Control, Los Angeles, CA, USA.","DOI":"10.1109\/CDC.2014.7039363"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/j.ifacol.2015.10.326","article-title":"Distributed multi-agent persistent surveillance under temporal logic constraints","volume":"48","author":"Aksaray","year":"2015","journal-title":"IFAC-PapersOnLine"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1587\/transfun.E98.A.626","article-title":"Optimal control of multi-vehicle systems with temporal logic constraints","volume":"E98-A","author":"Kobayashi","year":"2015","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/j.automatica.2016.04.006","article-title":"Multi-agent planning under local LTL specifications and event-based synchronization","volume":"70","author":"Tumova","year":"2016","journal-title":"Automatica"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1177\/0278364918774135","article-title":"Simultaneous task allocation and planning for temporal logic goals in heterogeneous multi-robot systems","volume":"37","author":"Schillinger","year":"2018","journal-title":"Int. J. Robot. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1587\/transfun.2021MAP0003","article-title":"Optimal control of timed Petri nets under temporal logic constraints with generalized mutual exclusion","volume":"105","author":"Fujita","year":"2022","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"110849","DOI":"10.1109\/ACCESS.2022.3216043","article-title":"Optimal Control of Colored Timed Petri Nets Under Generalized Mutual Exclusion Temporal Constraints","volume":"10","author":"Fujita","year":"2022","journal-title":"IEEE Access"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1658","DOI":"10.1587\/transinf.2021FOP0003","article-title":"Finite-Horizon Optimal Spatio-Temporal Pattern Control under Spatio-Temporal Logic Specifications","volume":"105","author":"Kinugawa","year":"2022","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1109\/LCSYS.2020.2980552","article-title":"Reinforcement learning of control policy for linear temporal logic specifications using limit-deterministic generalized B\u00fcchi automata","volume":"4","author":"Oura","year":"2020","journal-title":"IEEE Control Syst. Lett."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1587\/transfun.2023KEP0016","article-title":"Reinforcement Learning for Multi-Agent Systems with Temporal Logic Specifications","volume":"E107-A","author":"Terashima","year":"2024","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1306","DOI":"10.1109\/JPROC.2006.876930","article-title":"Decentralized cooperative aerial surveillance using fixed-wing miniature UAVs","volume":"94","author":"Beard","year":"2006","journal-title":"Proc. IEEE"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Nigam, N., and Kroo, I. (2008, January 27\u201329). Persistent surveillance using multiple unmanned air vehicles. Proceedings of the 2008 IEEE Aerospace Conference, Orlando, FL, USA.","DOI":"10.1109\/AERO.2008.4526242"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s10472-010-9193-y","article-title":"Multi-robot area patrol under frequency constraints","volume":"57","author":"Elmaliach","year":"2009","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Fu, J.G.M., and Ang, M.H. (2009, January 14\u201317). Probabilistic ants (PAnts) in multi-agent patrolling. Proceedings of the 2009 IEEE\/ASME International Conference on Advanced Intelligent Mechatronics, Singapore.","DOI":"10.1109\/AIM.2009.5229880"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/s10846-009-9326-x","article-title":"Matrix-based discrete event control for surveillance mobile robotics","volume":"56","author":"Naso","year":"2009","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Ding, X.C., Belta, C., and Cassandras, C.G. (2010, January 15\u201317). Receding horizon surveillance with temporal logic specifications. Proceedings of the 49th IEEE Conference on Decision and Control (CDC), Atlanta, GA, USA.","DOI":"10.1109\/CDC.2010.5717131"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1236","DOI":"10.1109\/TCST.2011.2167331","article-title":"Control of multiple UAVs for persistent surveillance: Algorithm and flight test results","volume":"20","author":"Nigam","year":"2011","journal-title":"IEEE Trans. Control Syst. Technol."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1109\/TRO.2011.2179580","article-title":"On cooperative patrolling: Optimal trajectories, complexity analysis, and approximation algorithms","volume":"28","author":"Pasqualetti","year":"2012","journal-title":"IEEE Trans. Robot."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1659","DOI":"10.1109\/TAC.2014.2359712","article-title":"An optimal control approach to the multi-agent persistent monitoring problem in two-dimensional spaces","volume":"60","author":"Lin","year":"2014","journal-title":"IEEE Trans. Autom. Control"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Kajita, K., and Konaka, E. (2018, January 21\u201323). Hard-to-predict routing algorithm from intruders for autonomous surveillance robots. Proceedings of the IECON 2018-44th Annual Conference of the IEEE Industrial Electronics Society, Washington, DC, USA.","DOI":"10.1109\/IECON.2018.8591272"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1587\/transfun.2019MAP0011","article-title":"Dynamic Surveillance by Multiple Agents with Fuel Constraints","volume":"E103-A","author":"Masuda","year":"2020","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"3796","DOI":"10.1109\/TAES.2020.2983532","article-title":"MILP formulation for aircraft path planning in persistent surveillance","volume":"56","author":"Zuo","year":"2020","journal-title":"IEEE Trans. Aerosp. Electron. Syst."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/S0005-1098(99)00214-9","article-title":"Constrained model predictive control: Stability and optimality","volume":"36","author":"Mayne","year":"2000","journal-title":"Automatica"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"2967","DOI":"10.1016\/j.automatica.2014.10.128","article-title":"Model predictive control: Recent developments and future promise","volume":"50","author":"Mayne","year":"2014","journal-title":"Automatica"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"24884","DOI":"10.1109\/ACCESS.2021.3057485","article-title":"Unmanned aerial vehicle path planning algorithm based on deep reinforcement learning in large-scale and dynamic environments","volume":"9","author":"Xie","year":"2021","journal-title":"IEEE Access"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s10846-021-01548-2","article-title":"Solving reward-collecting problems with UAVs: A comparison of online optimization and Q-learning","volume":"104","author":"Liu","year":"2022","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0377-2217(91)90319-Q","article-title":"The pickup and delivery problem with time windows","volume":"54","author":"Dumas","year":"1991","journal-title":"Eur. J. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1016\/S0305-0548(02)00051-5","article-title":"A genetic algorithm for the vehicle routing problem","volume":"30","author":"Baker","year":"2003","journal-title":"Comput. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s11301-008-0033-7","article-title":"A survey on pickup and delivery problems: Part I: Transportation between customers and depot","volume":"58","author":"Parragh","year":"2008","journal-title":"J. Betriebswirtschaft"},{"key":"ref_36","unstructured":"Salzman, O., and Stern, R. (2020, January 9\u201313). Research challenges and opportunities in multi-agent path finding and multi-agent pickup and delivery problems. Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, Auckland, New Zealand."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"101942","DOI":"10.1016\/j.tre.2020.101942","article-title":"Adaptive large neighborhood search for the time-dependent profitable pickup and delivery problem with time windows","volume":"138","author":"Sun","year":"2020","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"104987","DOI":"10.1016\/j.cor.2020.104987","article-title":"A review of vehicle routing with simultaneous pickup and delivery","volume":"122","author":"Laporte","year":"2020","journal-title":"Comput. Oper. Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1109\/JAS.2020.1003204","article-title":"Solving multitrip pickup and delivery problem with time windows and manpower planning using multiobjective algorithms","volume":"7","author":"Wang","year":"2020","journal-title":"IEEE\/CAA J. Autom. Sin."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1153","DOI":"10.1016\/j.ejor.2020.07.049","article-title":"Pickup and delivery problem with recharging for material handling systems utilising autonomous mobile robots","volume":"289","author":"Jun","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_41","first-page":"23609","article-title":"A hierarchical reinforcement learning based optimization framework for large-scale dynamic pickup and delivery problems","volume":"34","author":"Ma","year":"2021","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/j.ejor.2009.04.024","article-title":"Dynamic pickup and delivery problems","volume":"202","author":"Berbeglia","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/j.cie.2014.02.002","article-title":"Congestion-aware dynamic routing in automated material handling systems","volume":"70","author":"Bartlett","year":"2014","journal-title":"Comput. Ind. Eng."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"105046","DOI":"10.1016\/j.cor.2020.105046","article-title":"A dynamic path planning approach for dense, large, grid-based automated guided vehicle systems","volume":"123","author":"Fransen","year":"2020","journal-title":"Comput. Oper. Res."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"103837","DOI":"10.1016\/j.trc.2022.103837","article-title":"Evacuation route planning for alternative fuel vehicles","volume":"143","author":"Purba","year":"2022","journal-title":"Transp. Res. Part Emerg. Technol."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1177\/03611981231171156","article-title":"Refueling Station Location Model to Support Evacuation of Alternative Fuel Vehicles","volume":"2678","author":"Purba","year":"2024","journal-title":"Transp. Res. Rec."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/j.tre.2014.10.005","article-title":"Proactive vehicle routing with inferred demand to solve the bikesharing rebalancing problem","volume":"72","author":"Regue","year":"2014","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"102147","DOI":"10.1016\/j.tre.2020.102147","article-title":"Real-time demand forecasting for an urban delivery platform","volume":"145","author":"Hess","year":"2021","journal-title":"Transp. Res. Part Logist. Transp. Rev."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Matsuoka, R., Kobayashi, K., and Yamashita, Y. (2023, January 10\u201313). Online Optimization of Pickup and Delivery Problem Considering Demand Forecasting. Proceedings of the 2023 IEEE 12th Global Conference on Consumer Electronics, Nara, Japan.","DOI":"10.1109\/GCCE59613.2023.10315380"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/S0005-1098(98)00178-2","article-title":"Control of systems integrating logic, dynamics, and constraints","volume":"35","author":"Bemporad","year":"1999","journal-title":"Automatica"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"1670","DOI":"10.1016\/j.jprocont.2012.07.003","article-title":"Deterministic finite automata representation for model predictive control of hybrid systems","volume":"22","author":"Kobayashi","year":"2012","journal-title":"J. Process Control"},{"key":"ref_52","unstructured":"Williams, H.P. (2013). Model Building in Mathematical Programming, John Wiley & Sons."}],"container-title":["Future Internet"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-5903\/16\/2\/64\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:01:18Z","timestamp":1760104878000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-5903\/16\/2\/64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,17]]},"references-count":52,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,2]]}},"alternative-id":["fi16020064"],"URL":"https:\/\/doi.org\/10.3390\/fi16020064","relation":{},"ISSN":["1999-5903"],"issn-type":[{"value":"1999-5903","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,17]]}}}