To resolve challenges arising from traditional truck-based delivery systems, the integration of autonomous robots into last-mile delivery operations has recently received attention as a promising solution. This study addresses a hybrid truck-robots last-mile delivery system that encompasses both homogeneous and heterogeneous robots. To discuss battery management strategies for robots returning after rendezvousing with a truck, we propose mixed-integer linear programming models offering two options: battery recharging and battery swapping. We explore optimal solutions for truck and robot routes, as well as various robot combinations aimed at minimizing total delivery time. Additionally, we present a three-phased iterative heuristic algorithm designed to effectively solve large-sized problems. The proposed models are validated with application to Southern District, Ulsan, in the Republic of Korea, and Rapid City, South Dakota, in the U.S., serving as examples of urban and rural areas, respectively. Our findings demonstrate that the proposed truck-robots system, particularly with the battery-swapping option, can achieve up to a 50% reduction in total delivery time compared with traditional truck-only delivery systems, applicable to both urban and rural areas. Furthermore, our results underscore the importance of long driving range for the robots in urban areas for enhancing delivery system performance. We also conduct a sensitivity analysis to examine the impact of the following factors on delivery system performance: customer node size, robot speed, number of robots, and various robot ratios. This study helps fill the gap in the literature concerning hybrid truck-robot delivery systems, with implications for improving delivery efficiency and reducing total delivery time in urban areas.
KweonS. J.HwangS. W.LeeS.JoM. J.Demurrage Pattern Analysis Using Logical Analysis of Data: A Case Study of the Ulsan Port Authority. Expert Systems with Applications, Vol. 206, 2022, p. 117745. https://doi.org/10.1016/j.eswa.2022.117745.
HwangS. W.LeeS.KweonS. J.An Integrated Inventory and Distribution Problem for Alternative Fuel: A Matheuristic Approach. European Journal of Industrial Engineering, Vol. 15, No. 5, 2021, pp. 711–744. https://doi.org/10.1504/EJIE.2021.117331.
NaH. S.BanerjeeA.A Disaster Evacuation Network Model for Transporting Multiple Priority Evacuees. IIE Transactions, Vol. 47, No. 11, 2015, pp. 1287–1299. https://doi.org/10.1080/0740817X.2015.1040929.
7.
NaH. S.BanerjeeA.Agent-Based Discrete-Event Simulation Model for No-Notice Natural Disaster Evacuation Planning. Computers & Industrial Engineering, Vol. 129, 2019, pp. 44–55. https://doi.org/10.1016/j.cie.2019.01.022.
8.
VocciaS. A.CampbellA. M.ThomasB. W.The Same-Day Delivery Problem for Online Purchases. Transportation Science, Vol. 53, No. 1, 2019, pp. 167–184. https://doi.org/10.1287/trsc.2016.0732.
9.
BoysenN.FedtkeS.SchwerdfegerS.Last-Mile Delivery Concepts: A Survey from an Operational Research Perspective. OR Spectrum, Vol. 43, 2021, pp. 1–58. https://doi.org/10.1007/s00291-020-00607-8.
10.
BoysenN.SchwerdfegerS.WeidingerF.Scheduling Last-Mile Deliveries with Truck-Based Autonomous Robots. European Journal of Operational Research, Vol. 271, No. 3, 2018, pp. 1085–1099. https://doi.org/10.1016/j.ejor.2018.05.058.
11.
FiliopoulouE.BardakiC.BoukouvalasD.NikolaidouM.KourouthanassisP.Last-Mile Delivery Options: Exploring Customer Preferences and Challenges. Proc., 2022 17th International Workshop on Semantic and Social Media Adaptation & Personalization (SMAP), Corfu, Greece, IEEE, New York, 2022. https://doi.org/10.1109/SMAP56125.2022.9942122.
12.
HübnerA.HolzapfelA.KuhnH.ObermairE.Distribution in Omnichannel Grocery Retailing: An Analysis of Concepts Realized. In Operations in an Omnichannel World (GallinoS.MorenoA., eds.), Springer, Cham, 2019, pp. 283–310. https://doi.org/10.1007/978-3-030-20119-7_12.
FigliozziM.JenningsD.Autonomous Delivery Robots and Their Potential Impacts on Urban Freight Energy Consumption and Emissions. Transportation Research Procedia, Vol. 46, 2020, pp. 21–28. https://doi.org/10.1016/j.trpro.2020.03.159.
17.
Numan-Al-MobinA. M.LyK.AnjumM. N.NaH. S.Decision Making in Solid-State Battery Manufacturing. In Green Sustainable Process for Chemical and Environmental Engineering and Science (A. Smirnova, A. Numan-Al-Mobin, and Inamuddin, eds.), Elsevier, Amsterdam, 2023, pp. 263–293. https://doi.org/10.1016/B978-0-323-90635-7.00011-7.
18.
BakachI.CampbellA. M.EhmkeJ. F.A Two-Tier Urban Delivery Network with Robot-Based Deliveries. Networks, Vol. 78, No. 4, 2021, pp. 461–483. https://doi.org/10.1002/net.22024.
19.
WuY.DingY.DingS.SavariaY.LiM.Autonomous Last-Mile Delivery Based on the Cooperation of Multiple Heterogeneous Unmanned Ground Vehicles. Mathematical Problems in Engineering, Vol. 2021, No. 1, 2021, p. 5546581. https://doi.org/10.1016/j.ejor.2017.12.008.
20.
RjebA.GayonJ. P.NorreS.Sizing of a Heterogeneous Fleet of Robots in a Logistics Warehouse. Proc., 2021 IEEE 17th International Conference on Automation Science and Engineering (CASE), IEEE, New York, 2021, pp. 95–100. https://doi.org/10.1109/CASE49439.2021.9551422.
NaH. S.Numan-Al-MobinA. M. Machine Learning Approaches to Estimate the Health State of Next-Generation Energy Storage. In Green Sustainable Process for Chemical and Environmental Engineering and Science (A. Smirnova, A. Numan-Al-Mobin, and Inamuddin, eds.), Elsevier, Amsterdam, 2023, pp. 343–363. https://doi.org/10.1016/B978-0-323-90635-7.00002-6.
ZouB.XuX.De KosterR.Evaluating Battery Charging and Swapping Strategies in a Robotic Mobile Fulfillment System. European Journal of Operational Research, Vol. 267, No. 2, 2018, pp. 733–753. https://doi.org/10.1016/j.ejor.2017.12.008.
NaH. S.KweonS. J.ParkK.Characterization and Design for Last Mile Logistics: A Review of the State of the Art and Future Directions. Applied Sciences, Vol. 12, No. 1, 2021, p. 118. https://doi.org/10.3390/app12010118.
27.
KimJ.KweonS. J.HwangS. W.LeeS.Crowdsourcing Integration on the Last Mile Delivery Platform Considering Floating Population Data. Expert Systems with Applications, Vol. 248, 2024, p. 123312. https://doi.org/10.1016/j.eswa.2024.123312.
28.
WangY.ZhangD.LiuQ.ShenF.LeeL. H.Towards Enhancing the Last-Mile Delivery: An Effective Crowd-Tasking Model with Scalable Solutions. Transportation Research Part E: Logistics and Transportation Review, Vol. 93, 2016, pp. 279–293. https://doi.org/10.1016/j.tre.2016.06.002.
AgatzN.BoumanP.SchmidtM.Optimization Approaches for the Traveling Salesman Problem with Drone. Transportation Science, Vol. 52, No. 4, 2018, pp. 965–981. https://doi.org/10.1287/trsc.2017.0791.
34.
MurrayC. C.ChuA. G.The Flying Sidekick Traveling Salesman Problem: Optimization of Drone-Assisted Parcel Delivery. Transportation Research Part C: Emerging Technologies, Vol. 54, 2015, pp. 86–109. https://doi.org/10.1016/j.trc.2015.03.005.
35.
TangZ.HoeveW. J. V.ShawP.A Study on the Traveling Salesman Problem with a Drone. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research (RousseauL. M.StergiouK., eds.), Springer, Cham, 2019, pp. 557–564. https://doi.org/10.1007/978-3-030-19212-9_37.
36.
YurekE. E.OzmutluH. C.A Decomposition-Based Iterative Optimization Algorithm for Traveling Salesman Problem with Drone. Transportation Research Part C: Emerging Technologies, Vol. 91, 2018, pp. 249–262. https://doi.org/10.1016/j.trc.2018.04.009.
37.
ChangY. S.LeeH. J.Optimal Delivery Routing with Wider Drone-Delivery Areas Along a Shorter Truck-Route. Expert Systems with Applications, Vol. 104, 2018, pp. 307–317. https://doi.org/10.1016/j.eswa.2018.03.032.
38.
KimS.MoonI.Traveling Salesman Problem with a Drone Station. IEEE Transactions on Systems, Man, and Cybernetics: Systems, Vol. 49, No. 1, 2018, pp. 42–52. https://doi.org/10.1109/tsmc.2018.2867496.
39.
Moshref-JavadiM.LeeS.WinkenbachM.Design and Evaluation of a Multi-Trip Delivery Model with Truck and Drones. Transportation Research Part E: Logistics and Transportation Review, Vol. 136, 2020, p. 101887. https://doi.org/10.1016/j.tre.2020.101887.
40.
MurrayC. C.RajR.The Multiple Flying Sidekicks Traveling Salesman Problem: Parcel Delivery with Multiple Drones. Transportation Research Part C: Emerging Technologies, Vol. 110, 2020, pp. 368–398. https://doi.org/10.1016/j.trc.2019.11.003.
41.
SacramentoD.PisingerD.RopkeS.An Adaptive Large Neighborhood Search Metaheuristic for the Vehicle Routing Problem with Drones. Transportation Research Part C: Emerging Technologies, Vol. 102, 2019, pp. 289–315. https://doi.org/10.1016/j.trc.2019.02.018.
42.
SalamaM.SrinivasS.Joint Optimization of Customer Location Clustering and Drone-Based Routing for Last-Mile Deliveries. Transportation Research Part C: Emerging Technologies, Vol. 114, 2020, pp. 620–642. https://doi.org/10.1016/j.trc.2020.01.019.
43.
TuP. A.DatN. T.DungP. Q.Traveling Salesman Problem with Multiple Drones. Proc., Ninth International Symposium on Information and Communication Technology – SoICT 2018, Danang City, Viet Nam, December6–7, 2018. https://doi.org/10.1145/3287921.3287932.
44.
WangZ.SheuJ. B.Vehicle Routing Problem with Drones. Transportation Research Part B: Methodological, Vol. 122, 2019, pp. 350–364. https://doi.org/10.1016/j.trb.2019.03.005.
AlfandariL.LjubićI.da SilvaM. D. M.A Tailored Benders Decomposition Approach for Last-Mile Delivery with Autonomous Robots. European Journal of Operational Research, Vol. 299, No. 2, 2022, pp. 510–525. https://doi.org/10.1016/j.ejor.2021.06.048.
47.
HeimfarthA.OstermeierM.HübnerA.A Mixed Truck and Robot Delivery Approach for the Daily Supply of Customers. European Journal of Operational Research, Vol. 303, No. 1, 2022, pp. 401–421. https://doi.org/10.1016/j.ejor.2022.02.028.
48.
JenningsD.FigliozziM.Study of Sidewalk Autonomous Delivery Robots and Their Potential Impacts on Freight Efficiency and Travel. Transportation Research Record: Journal of the Transportation Research Board, 2019. 2673: 317–326.
49.
OstermeierM.HeimfarthA.HübnerA.Cost-Optimal Truck-and-Robot Routing for Last-Mile Delivery. Networks, Vol. 79, No. 3, 2022, pp. 364–389. https://doi.org/10.1002/net.22030.
50.
PoetingM.SchaudtS.ClausenU.A Comprehensive Case Study in Last-Mile Delivery Concepts for Parcel Robots. Proc., 2019 Winter Simulation Conference (WSC), National Harbor, MD, 2019. https://doi.org/10.1109/wsc40007.2019.9004811.
51.
PoetingM.SchaudtS.ClausenU.Simulation of an Optimized Last-Mile Parcel Delivery Network Involving Delivery Robots. In Advances in Production, Logistics and Traffic (ClausenU.LangkauS.KreuzF., eds.), Springer, Cham, 2019, pp. 1–19. https://doi.org/10.1007/978-3-030-135.
52.
SimoniM. D.KutanogluE.ClaudelC. G.Optimization and Analysis of a Robot-Assisted Last Mile Delivery System. Transportation Research Part E: Logistics and Transportation Review, Vol. 142, 2020, p. 102049. https://doi.org/10.1016/j.tre.2020.102049.
53.
ChenC.DemirE.HuangY.An Adaptive Large Neighborhood Search Heuristic for the Vehicle Routing Problem with Time Windows and Delivery Robots. European Journal of Operational Research, Vol. 294, No. 3, 2021, pp. 1164–1180. https://doi.org/10.1016/j.ejor.2021.02.027.
54.
ChenC.DemirE.HuangY.QiuR.The Adoption of Self-Driving Delivery Robots in Last Mile Logistics. Transportation Research Part E: Logistics and Transportation Review, Vol. 146, 2021, p. 102214. https://doi.org/10.1016/j.tre.2020.102214.
WooS.YoonS.KimJ.HwangS. W.KweonS. J.Optimal Cooling Shelter Assignment During Heat Waves Using Real-Time Mobile-Based Floating Population Data. Urban Climate, Vol. 38, 2021, p. 100874. https://doi.org/10.1016/j.uclim.2021.100874.
58.
YoonS.WooS.KimJ.HwangS. W.KweonS. J.The Location Routing Problem for Cooling Shelters During Heat Waves. Urban Climate, Vol. 44, 2022, p. 101138. https://doi.org/10.1016/j.uclim.2022.101138.
59.
KimE. K.YoonS.JungS. U.KweonS. J.Optimizing Urban Park Locations with Addressing Environmental Justice in Park Access and Utilization by Using Dynamic Demographic Features Derived from Mobile Phone Data. Urban Forestry & Urban Greening, Vol. 99, 2024, p. 128444. https://doi.org/10.1016/j.ufug.2024.128444.
60.
KubyM.LimS.The Flow-Refueling Location Problem for Alternative-Fuel Vehicles. Socio-Economic Planning Sciences, Vol. 39, No. 2, 2005, pp. 125–145. https://doi.org/10.1016/j.seps.2004.03.001.
61.
HwangS. W.KweonS. J.VenturaJ. A.Infrastructure Development for Alternative Fuel Vehicles on a Highway Road System. Transportation Research Part E: Logistics and Transportation Review, Vol. 77, 2015, pp. 170–183. https://doi.org/10.1016/j.tre.2015.02.011.
62.
VenturaJ. A.HwangS. W.KweonS. J.A Continuous Network Location Problem for a Single Refueling Station on a Tree. Computers & Operations Research, Vol. 62, 2015, pp. 257–265. https://doi.org/10.1016/j.cor.2014.07.017.
63.
AlverhedE.HellgrenS.IsakssonH.OlssonL.PalmqvistH.FlodénJ.Autonomous Last-Mile Delivery Robots: A Literature Review. European Transport Research Review, Vol. 16, No. 1, 2024, p. 4. https://doi.org/10.1186/s12544-023-00629-7.
64.
EngholmA.PernestålA.KristofferssonI.Cost Analysis of Driverless Truck Operations. Transportation Research Record: Journal of the Transportation Research Board, 2020. 2674: 511–524.
HwangS. W.KweonS. J.VenturaJ. A.Locating Alternative-Fuel Refueling Stations on a Multi-Class Vehicle Transportation Network. European Journal of Operational Research, Vol. 261, No. 3, 2017, pp. 941–957. https://doi.org/10.1016/j.ejor.2017.02.036.
67.
HwangS. W.KweonS. J.VenturaJ. A.An Alternative Fuel Refueling Station Location Model Considering Detour Traffic Flows on a Highway Road System. Journal of Advanced Transportation, Vol. 2020, 2020, p. 9473831. https://doi.org/10.1155/2020/9473831.
68.
KweonS. J.HwangS. W.VenturaJ. A.A Continuous Deviation-Flow Location Problem for an Alternative-Fuel Refueling Station on a Tree-Like Transportation Network. Journal of Advanced Transportation, Vol. 2017, 2017, p. 1705821. https://doi.org/10.1155/2017/1705821.
69.
KimJ.KweonS. J.HwangS. W.Spatial Equality and Equity for Effective Emergency Water Distribution System: Points of Distribution. Journal of Water Resources Planning and Management, Vol. 147, No. 3, 2021, p. 04020111. https://doi.org/10.1061/(ASCE)WR.1943-5452.0001318.
70.
KimJ.KweonD.KweonS. J.Emergency Water Distribution Systems to Improve Spatial Equality and Spatial Equity in a Heterogeneous Community with Differing Mobility Characteristics. International Journal of Disaster Risk Reduction, Vol. 112, 2024, p. 104730. https://doi.org/10.1016/j.ijdrr.2024.104730.
71.
YuS.PuchingerJ.SunS.Van-Based Robot Hybrid Pickup and Delivery Routing Problem. European Journal of Operational Research, Vol. 298, No. 3, 2022, pp. 894–914. https://doi.org/10.1016/j.ejor.2021.06.009.
72.
Roca-RiuM.CaoJ.DakicI.MenendezM.Designing Dynamic Delivery Parking Spots in Urban Areas to Reduce Traffic Disruptions. Journal of Advanced Transportation, Vol. 2017, 2017, p. 6296720. https://doi.org/10.1155/2017/6296720.
JallerM.PahwaA.Urban Freight Delivery and Loading Spaces. U.S. Department of Transportation, 2020. https://rosap.ntl.bts.gov/view/dot/57281. Accessed February 19, 2025.
76.
YuS.PuchingerJ.Collaborative Truck–Robot Deliveries: Challenges, Models, and Methods. Annals of Operations Research, Vol. 336, 2024, pp. 1–38. https://doi.org/10. 1007/s10479-024-06127-w.
77.
NaH. S.BanerjeeA. An Agent-Based Discrete Event Simulation Approach for Modeling Large-Scale Disaster Evacuation Network. Proc., Winter Simulation Conference (WSC), Savannah, GA, 2014, pp. 1516–1526. https://doi.org/10.1109/WSC.2014.7020004.
78.
NaH. S.GraceR.Influence of Social Networks and Opportunities for Social Support on Evacuation Destination Decision-Making. Safety Science, Vol. 147, 2022, p. 105564. https://doi.org/10.1016/j.ssci.2021.105564.
79.
GraceR.NaH. S.Relocation and Social Support During Large-Scale Evacuations. Natural Hazards Review, Vol. 25, No. 2, 2024, p. 04024008. https://doi.org/10.1061/NHREFO.NHENG-1874.
80.
NaH. S.Studies in Large-Scale Evacuation Network Flow Stochastic Optimization Under Social Influence. PhD dissertation. The Pennsylvania State University, University Park, 2019.
81.
VenturaJ. A.KweonS. J.HwangS. W.TormayM.LiC.Energy Policy Considerations in the Design of an Alternative-Fuel Refueling Infrastructure to Reduce GHG Emissions on a Transportation Network. Energy Policy, Vol. 111, 2017, pp. 427–439. https://doi.org/10.1016/j.enpol.2017.09.035.
82.
BokY.LeeN. K.JoS.LeeS.KweonS. J.NaH. S.The Production Scheduling Problem Employing Non-Identical Parallel Machines with Due Dates Considering Carbon Emissions and Multiple Types of Energy Sources. Expert Systems with Applications, Vol. 238, 2024, p. 121990. https://doi.org/10.1016/j.eswa.2023.121990.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
