Truck and drone routing problem with soft time windows.

Document Type : Research Paper

Authors

School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

Abstract

Due to narrow streets, dense traffic, and transportation restrictions, city logistics operations are under increasing pressure and need innovative approaches. Recently coordination of trucks and drones has been used as a new solution, which can improve the efficiency of city logistics operations. This paper also focuses on a truck and drone delivery system. As the major contributions, this paper develops a new mix integer programming model to formulate the hybrid truck and drone routing problem with soft time windows and proposes an effective two-phased metaheuristic algorithm. To evaluate the performance of the proposed metaheuristic, we carried out numerous computational experiments, where the results show the efficiency of the proposed metaheuristic. Finally; a detailed sensitivity analysis is performed.

Keywords

Main Subjects

References

Archetti, C., Guerriero, F. and Macrina, G. (2020). The Online Vehicle Routing Problem with Occasional Drivers, Computers and Operations Research, doi: https://doi.org/10.1016/j.cor.2020.105144.
Basso, R., Kulcsár, B. and Sanchez-Diaz, I. (2021). Electric vehicle routing problem with machine learning for energy prediction, Transportation Research Part B: Methodological, Volume 145, Pages 24-55, ISSN 0191-2615, https://doi.org/10.1016/j.trb.2020.12.007.
Bouman, P., Agatz, N. and Schmidt, M. Dynamic programming approaches for the traveling salesman problem with drone. Networks. 2018; 72: 528– 542. https://doi.org/10.1002/net.21864.
Carlsson, J. G. and Song, S. (2017). Coordinated Logistics with a Truck and a Drone, Management Science, 64(9):4052-4069.
Chang, Y. S., and Lee, H. J. (2018). Optimal Delivery Routing with Wider Drone-Delivery Areas along a Shorter Truck-Route, Expert Systems with Applications, doi: 10.1016/j.eswa.2018.03.032.
Chen, C., Demir, E., and Huang, Y. (2021). An Adaptive Large Neighborhood Search Heuristic for the Vehicle Routing Problem with Time Windows and Delivery Robots. European Journal of Operational Research. 2021, 294, 1164–1180.
Enthoven, D. L.J.U., Jargalsaikhan, B., Roodbergen , K. J., Broek, M. A.J. and Schrotenboer, A. H. (2020).The Two-Echelon Vehicle Routing Problem with Covering Options: City logistics with cargo bikes and parcel lockers, Computers and Operations Research, doi: https://doi.org/10.1016/j.cor.2020.104919.
Freitas, J. C. and Penna, P. H. V. (2019). A variable neighborhood search for flying sidekick traveling salesman problem, INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 00, 1-24, DOI: 10.1111/itor.12671.
Gmira, M., Gendreau, M., Lodi, A. and Potvin, J.-Y. (2021). Tabu Search for the Time-Dependent Vehicle Routing Problem with Time Windows on a Road Network. European Journal of Operational Research, 288, 129–140.
Grabenschweiger, J., Doerner, K.F., Hartl, R.F., and Savelsbergh, M.W.P. (2021). The Vehicle Routing Problem with Heterogeneous Locker Boxes. Central European Journal of Operations Research, 29, 113–142.
Hafezolkotob, A., Mahmoudi, R., and  Shariatmadari, M. (2017). Vehicle Routing Problem in Competitive Environment: Two-Person Nonzero Sum Game Approach. Journal of Industrial and Systems Engineering. Vol: 10, No. 2, 35-52.
Ham, A. M. (2018). Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming, Transportation Research Part C: Emerging Technologies, Volume 91, Pages 1-14.
Huang, Y., Zhao,L., Van Woensel,T. and J.-P. Gross. (2017). Time-dependent vehicle routing problem with path flexibility. Transportation Research Part B: Methodological, 95:169–195, 20.
Ichoua, S., Gendreau, M.  and Potvin, J. Y. (2003). Vehicle dispatching with timedependent travel times. European Journal of Operational Research, 144(2):379–396.
Jeong, H. Y., Song, B. D., Lee, S. (2019). Truck-drone hybrid delivery routing: Payload-energy dependency and No-Fly zones, International Journal of Production Economics, Volume 214, Pages 220-233, ISSN 0925-5273.
Karak, A. and Abdelghany, K. (2019). The hybrid vehicle-drone routing problem for pick-up and delivery services, Transportation Research Part C: Emerging Technologies, Volume 102, Pages 427-449, SSN 0968-090X, https://doi.org/10.1016/j.trc.2019.03.021.
Kitjacharoenchai, P., Min, B. and Lee, S. (2020). Two echelon vehicle routing problem with drones in last mile delivery, International Journal of Production Economics, Volume 225, , 107598, ISSN 0925-5273, https://doi.org/ 10.1016/j.ijpe.2019.107598.
Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi,M., Lee, S., Tanchoco, J. M.A. and  Brunese, P. A. (2019). Multiple traveling salesman problem with drones: Mathematical model and heuristic approach, Computers & Industrial Engineering, Volume 129, Pages 14-30, ISSN 0360-8352, https://doi.org/10.1016/j.cie.2019.01.020.
Kyriakakis, N. A., Stamadianos, T., Marinaki, M. and Marinakis, Y. (2022). The electric vehicle routing problem with drones: An energy minimization approach for aerial deliveries, Cleaner Logistics and Supply Chain, Volume 4, 100041, ISSN 2772-3909, https://doi.org/10.1016/j.clscn.2022.100041.
Leon-Blanco, J. M., Gonzalez-R, P.L., Andrade-Pineda, J. L., Canca, D. and Calle, M. (2022). A multi-agent approach to the truck multi-drone routing problem, Expert Systems with Applications, Volume 195, 116604, ISSN 0957-4174, https://doi.org/10.1016/j.eswa.2022.116604.
Letnik, T.,  Marksel, M.,  Luppino, G.,  Bardi, A. and  Božičnik, S. (2018). Review of Policies and Measures for Sustainable and Energy Efficient Urban Transport, Energy, doi: 10.1016/j..2018.08.096.
Li, H., Wang, H., Chen, J. and Bai, M. (2020). Two-echelon vehicle routing problem with time windows and mobile satellites, Transportation Research Part B: Methodological, Volume 138, , Pages 179-201, ISSN 0191-2615, https://doi.org/10.1016/j.trb.2020.05.010.
Luo, Z., Lio, Z. and Shi, J. (2017). A Two-Echelon Cooperated Routing Problem for a Ground Vehicle and Its Carried Unmanned Aerial Vehicle. Sensors, 17, 1144; doi:10.3390/s17051144.
Luo, Z., Poon, M., Zhang, Z., Liu, Z. and Lim, A. (2021). The Multi-visit Traveling Salesman Problem with Multi-Drones,Transportation Research Part C: Emerging Technologies, Volume 128,103172,ISSN 0968-090X,https://doi.org/10.1016/j.trc.2021.103172.
Malandraki, C.  and Daskin, M. (1992). Time dependent vehicle routing problems: formulations, properties and heuristic algorithms. Transportation Science, 26(3): 185–200.
Mathew, N., Smith, S. L. and Waslander, S. L. (2015). Planning Paths for Package Delivery in Heterogeneous Multirobot Teams, IEEE Transactions on Automation Science and Engineering, vol. 12, no. 4, pp. 1298-1308, doi: 10.1109/TASE.2015.2461213.
Murray, C. C. and Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery, Transportation Research Part C: Emerging Technologies, Volume 54, Pages 86-109, ISSN 0968-090X, https://doi.org/10.1016/j.trc.2015.03.005.
Murray, C. C. and Raj, R. (2020). The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones, Transportation Research Part C: Emerging Technologies, Volume 110, Pages 368-398, ISSN 0968-090X, https://doi.org/10.1016/j.trc.2019.11.003.
Orenstein, I., Raviv, T., Sadan, E. (2019). Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis. EURO J Transport Logist, 2019, 8(5):683–711.
Pan, B., Zhang, Z. and Lim, A. (2021). Multi-Trip Time-Dependent Vehicle Routing Problem with Time Windows. European Journal of Operational Researchs, 291, 218–231.
Pina-Pardo, J. C., Silva, D. F. and Smith, A. E. (2021). The traveling salesman problem with release dates and drone resupply, Computers & Operations Research, Volume 129, 105170, ISSN 0305-0548, https://doi.org/10.1016/j.cor.2020.105170.
Poikonen, S., and Golden, B. (2019). The Mothership and Drone Routing Problem. INFORMS Journal on Computing 32(2):249-262. https://doi.org/10.1287/ijoc.2018.0879.
Poikonen, S., Golden, B., and Wasil, E. (2019). A branch-and-bound approach to the traveling salesman problem with a drone. INFORMS Journal on Computing, 31(2), 335-346.
Raj, R. and Murray, C. (2020). The multiple flying sidekicks traveling salesman problem with variable drone speeds, Transportation Research Part C: Emerging Technologies, Volume 120, 102813, ISSN 0968-090X, https://doi.org/10.1016/j.trc.2020.102813.
Rabani, M., Abdolhamidi, D., Mokhtarzade, M., and Fatemi-Anaraki, S. (2021). Solving a bi-objective medicine distribution problem considering delivery to waste center using a hybrid clustering, mathematical modeling and NSGA-II approach. Journal of Industrial and Systems Engineering. Vol: 13, No. 2, 245-263.
Sacramento, D., Pisinger, D. and Ropke, S. (2019). An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones, Transportation Research Part C: Emerging Technologies, Volume 102, Pages 289-315.
Savelsbergh, M., Van Woensel, T., (2016). 50th anniversary invited article—city logistics: Challenges and 520 opportunities. Transportation Science 50 (2), 579–590.
Schermer, D., Moeini, M. and Wendt, O. (2019). A matheuristic for the vehicle routing problem with drones and its variants, Transportation Research Part C: Emerging Technologies, Volume 106, Pages 166-204, ISSN 0968-090X, https://doi.org/10.1016/j.trc.2019.06.016.
Setak, M., Habibi, M., Karimi, H. and Abedzadeh, M. (2015). A time-dependent vehicle routing problem in multigraph with FIFO property. Journal of Manufacturing Systems, 35:37 – 45.
Shojaie, A., Shariatmadaria, M. and Moradia, M. (2016). Competitive Vehicle Routing Problem with Time Windows and Stochastic Demands. Journal of Industrial and Systems Engineering. Vol. 9, 2, 102-112.
Sitek, P., Wikarek, J., Rutczynska-Wdowiak, K., Bocewicz, G., and Banaszak, Z. (2021). Optimization of Capacitated Vehicle Routing Problem with Alternative Delivery, Pick-Up and Time Windows: A Modified Hybrid Approach. Neurocomputing, 423, 670–678.
Ticha, H.B., Absi, N.  Feillet, D. and Quilliot, A. (2018). Multigraph Modeling and Adaptive Large Neighborhood Search for the Vehicle Routing Problem with Time Windows, Computers and Operations Research, doi: https://doi.org/10.1016/j.cor.20.
Tu, P. A., Dat, N. T. and Dung, P. Q. (2018). Traveling Salesman Problem with Multiple Drones, SoICT, 6–7, https://doi.org/10.1145/3287921.3287932.
Wang, D., Hu, P.,   Du, V., Zhou, P., Deng, T. and Hu, M. (2019). Routing and Scheduling for Hybrid Truck-Drone Collaborative Parcel Delivery With Independent and Truck-Carried Drones, IEEE Internet of Things Journal, vol. 6, no. 6, pp. 10483-10495, doi: 10.1109/JIOT.2019.2939397.
Zhou, L., Baldacci, R., Vigo, D. and Wang, X. (2017). A Multi-Depot Two Echelon Vehicle Routing Problem with Delivery Options Arising in the Last Mile Distribution, European Journal of Operational Research, doi: 10.1016/j.ejor.2017.08.011.
 

Files

History

  • Receive Date: 12 May 2023
  • Revise Date: 16 October 2023
  • Accept Date: 21 October 2023

Share

How to cite

Statistics