IDEAS home Printed from https://ideas.repec.org/a/gam/jsusta/v15y2023i20p15118-d1264357.html
   My bibliography  Save this article

Multi-Traveler Salesman Problem for Unmanned Vehicles: Optimization through Improved Hopfield Neural Network

Author

Listed:
  • Song Liu

    (Institute for Intelligent Optimization of Comprehensive Transportation Systems, Chongqing Jiaotong University, Chongqing 400074, China
    School of Traffic and Transportation, Chongqing Jiaotong University, Chongqing 400074, China)

  • Xinhua Gao

    (School of Traffic and Transportation, Chongqing Jiaotong University, Chongqing 400074, China)

  • Liu Chen

    (Chongqing Survey Institute, Chongqing 401121, China)

  • Sihui Zhou

    (School of Traffic and Transportation, Chongqing Jiaotong University, Chongqing 400074, China)

  • Yong Peng

    (School of Traffic and Transportation, Chongqing Jiaotong University, Chongqing 400074, China)

  • Dennis Z. Yu

    (The David D. Reh School of Business, Clarkson University, Potsdam, NY 13699, USA)

  • Xianting Ma

    (Institute for Intelligent Optimization of Comprehensive Transportation Systems, Chongqing Jiaotong University, Chongqing 400074, China
    School of Traffic and Transportation, Chongqing Jiaotong University, Chongqing 400074, China)

  • Yan Wang

    (T.Y.LIN International Group Chongqing, Chongqing 401121, China)

Abstract

In response to the COVID-19 pandemic, communities utilize unmanned vehicles to minimize person-to-person contact and lower the risk of infection. This paper addresses the critical considerations of these unmanned vehicles’ maximum load capacity and service time, formulating them as constraints within a multi-traveling salesman problem (MTSP). We propose a comprehensive optimization approach that combines a genetic simulated annealing algorithm with clustering techniques and an improved Hopfield neural network (IHNN). First, the MTSP is decomposed into multiple independent TSPs using the fuzzy C-means clustering algorithm based on a genetic simulated annealing algorithm (SA-GA-FCM). Subsequently, the HNN is employed to introduce the data transformation technique and dynamic step factor to prepare more suitable inputs for the HNN training process to avoid the energy function from falling into local solutions, and the simulated annealing algorithm is introduced to solve multiple TSP separately. Finally, the effectiveness of the proposed algorithm is verified by small-scale and large-scale instances, and the results clearly demonstrate that each unmanned vehicle can meet the specified constraints and successfully complete all delivery tasks. Furthermore, to gauge the performance of our algorithm, we conducted ten simulation comparisons with other combinatorial optimization and heuristic algorithms. These comparisons indicate that IHNN outperforms the algorithms mentioned above regarding solution quality and efficiency and exhibits robustness against falling into local solutions. As presented in this paper, the solution to the unmanned vehicle traveling salesman problem facilitates contactless material distribution, reducing time and resource wastage while enhancing the efficiency of unmanned vehicle operations, which has profound implications for promoting low-carbon sustainable development, optimizing logistics efficiency, and mitigating the risk of pandemic spread.

Suggested Citation

  • Song Liu & Xinhua Gao & Liu Chen & Sihui Zhou & Yong Peng & Dennis Z. Yu & Xianting Ma & Yan Wang, 2023. "Multi-Traveler Salesman Problem for Unmanned Vehicles: Optimization through Improved Hopfield Neural Network," Sustainability, MDPI, vol. 15(20), pages 1-25, October.
    • Handle: RePEc:gam:jsusta:v:15:y:2023:i:20:p:15118-:d:1264357
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2071-1050/15/20/15118/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2071-1050/15/20/15118/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Ilias Vlachos & Rodrigo Martinez Pascazzi & George Zobolas & Panagiotis Repoussis & Mihalis Giannakis, 2023. "Lean manufacturing systems in the area of Industry 4.0: a lean automation plan of AGVs/IoT integration," Post-Print hal-04004536, HAL.
    2. Kloster, Konstantin & Moeini, Mahdi & Vigo, Daniele & Wendt, Oliver, 2023. "The multiple traveling salesman problem in presence of drone- and robot-supported packet stations," European Journal of Operational Research, Elsevier, vol. 305(2), pages 630-643.
    3. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    4. Xiaxia Ma & Wenliang Bian & Wenchao Wei & Fei Wei, 2022. "Customer-Centric, Two-Product Split Delivery Vehicle Routing Problem under Consideration of Weighted Customer Waiting Time in Power Industry," Energies, MDPI, vol. 15(10), pages 1-23, May.
    5. Monika Stoma & Agnieszka Dudziak & Jacek Caban & Paweł Droździel, 2021. "The Future of Autonomous Vehicles in the Opinion of Automotive Market Users," Energies, MDPI, vol. 14(16), pages 1-19, August.
    6. He, Pengfei & Hao, Jin-Kao, 2023. "Memetic search for the minmax multiple traveling salesman problem with single and multiple depots," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1055-1070.
    7. José Alejandro Cornejo-Acosta & Jesús García-Díaz & Julio César Pérez-Sansalvador & Carlos Segura, 2023. "Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems," Mathematics, MDPI, vol. 11(13), pages 1-25, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yin, Yunqiang & Li, Dongwei & Wang, Dujuan & Ignatius, Joshua & Cheng, T.C.E. & Wang, Sutong, 2023. "A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1125-1144.
    2. Xinhua Gao & Song Liu & Yan Wang & Dennis Z. Yu & Yong Peng & Xianting Ma, 2024. "Consideration of Carbon Emissions in Multi-Trip Delivery Optimization of Unmanned Vehicles," Sustainability, MDPI, vol. 16(6), pages 1-26, March.
    3. Yin, Yunqiang & Yang, Yongjian & Yu, Yugang & Wang, Dujuan & Cheng, T.C.E., 2023. "Robust vehicle routing with drones under uncertain demands and truck travel times in humanitarian logistics," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    4. Yi-Kuei Lin & Cheng-Fu Huang & Yi-Chieh Liao, 2019. "Reliability of a stochastic intermodal logistics network under spoilage and time considerations," Annals of Operations Research, Springer, vol. 277(1), pages 95-118, June.
    5. Zhang, Ying & Qi, Mingyao & Miao, Lixin & Liu, Erchao, 2014. "Hybrid metaheuristic solutions to inventory location routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 70(C), pages 305-323.
    6. Lu, Quan & Dessouky, Maged M., 2006. "A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 175(2), pages 672-687, December.
    7. Babagolzadeh, Mahla & Zhang, Yahua & Abbasi, Babak & Shrestha, Anup & Zhang, Anming, 2022. "Promoting Australian regional airports with subsidy schemes: Optimised downstream logistics using vehicle routing problem," Transport Policy, Elsevier, vol. 128(C), pages 38-51.
    8. Cheng, Chun & Adulyasak, Yossiri & Rousseau, Louis-Martin, 2020. "Drone routing with energy function: Formulation and exact algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 364-387.
    9. Gutiérrez-Jarpa, Gabriel & Desaulniers, Guy & Laporte, Gilbert & Marianov, Vladimir, 2010. "A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows," European Journal of Operational Research, Elsevier, vol. 206(2), pages 341-349, October.
    10. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2018. "Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 52(5), pages 1174-1190, October.
    11. Hernandez, Florent & Feillet, Dominique & Giroudeau, Rodolphe & Naud, Olivier, 2016. "Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 249(2), pages 551-559.
    12. Pradhananga, Rojee & Taniguchi, Eiichi & Yamada, Tadashi & Qureshi, Ali Gul, 2014. "Bi-objective decision support system for routing and scheduling of hazardous materials," Socio-Economic Planning Sciences, Elsevier, vol. 48(2), pages 135-148.
    13. Ehmke, Jan Fabian & Campbell, Ann M. & Thomas, Barrett W., 2018. "Optimizing for total costs in vehicle routing in urban areas," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 242-265.
    14. Luca Maria Gambardella & Marco Dorigo, 2000. "An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 237-255, August.
    15. Gronalt, Manfred & Hartl, Richard F. & Reimann, Marc, 2003. "New savings based algorithms for time constrained pickup and delivery of full truckloads," European Journal of Operational Research, Elsevier, vol. 151(3), pages 520-535, December.
    16. Qi, Mingyao & Lin, Wei-Hua & Li, Nan & Miao, Lixin, 2012. "A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 248-257.
    17. Neves-Moreira, Fábio & Almada-Lobo, Bernardo & Guimarães, Luís & Amorim, Pedro, 2022. "The multi-product inventory-routing problem with pickups and deliveries: Mitigating fluctuating demand via rolling horizon heuristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    18. Baldacci, Roberto & Mingozzi, Aristide & Roberti, Roberto, 2012. "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, Elsevier, vol. 218(1), pages 1-6.
    19. Calvete, Herminia I. & Gale, Carmen & Oliveros, Maria-Jose & Sanchez-Valverde, Belen, 2007. "A goal programming approach to vehicle routing problems with soft time windows," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1720-1733, March.
    20. Zhiping Zuo & Yanhui Li & Jing Fu & Jianlin Wu, 2019. "Human Resource Scheduling Model and Algorithm with Time Windows and Multi-Skill Constraints," Mathematics, MDPI, vol. 7(7), pages 1-18, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jsusta:v:15:y:2023:i:20:p:15118-:d:1264357. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.