A multitasking ant system for multi-depot pick-up and delivery location routing problem with time window
Abstract Instant delivery service has brought great convenience to our modern life. In order to improve its efficiency, multi-depot pick-up-and-delivery location routing problem with time windows (MDPDLRPTW) is proposed in this paper. Existing works related to MDPDLRPTW focus on obtaining a depot lo...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer
2025-01-01
|
| Series: | Complex & Intelligent Systems |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s40747-024-01750-3 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1823861456972546048 |
|---|---|
| author | Haoyuan Lv Ruochen Liu Jianxia Li |
| author_facet | Haoyuan Lv Ruochen Liu Jianxia Li |
| author_sort | Haoyuan Lv |
| collection | DOAJ |
| description | Abstract Instant delivery service has brought great convenience to our modern life. In order to improve its efficiency, multi-depot pick-up-and-delivery location routing problem with time windows (MDPDLRPTW) is proposed in this paper. Existing works related to MDPDLRPTW focus on obtaining a depot location scheme by clustering and perform route planning on it through single-task optimization. They are powerless to simultaneously explore the solution spaces of multiple routing tasks under different location schemes. Furthermore, ignoring the potential general knowledge among different schemes leads to redundant optimization. In this work, MDPDLRPTW is modeled as a multi-transformation optimization (MTFO) problem and a novel two-stage algorithm based on multitasking ant system (MTAS) is designed to solve it. In the first stage, a clustering algorithm based on spatio-temporal feature is used to group similar customer pairs, and the clustering centers are set as warehouses. Afterward, multiple localization schemes are selected through non-dominated sorting based on spatio-temporal density. In the second stage, MTAS concurrently optimizes multiple routing tasks based on these location schemes, each task is assigned to an ant system solver. Furthermore, MTAS achieves knowledge sharing among all routing tasks through adaptive similarity measurement and cross-task pheromone fusion strategy. The former can dynamically capture the relationship between tasks to adjust the transfer strength of task pairs, and the latter realizes adaptive knowledge transfer by pheromone-matrix mixing. Experimental results show that MTAS can efficiently utilize the common knowledge to achieve competitive performance. |
| format | Article |
| id | doaj-art-35248efcddc24508bf0980aa6ab029ac |
| institution | Kabale University |
| issn | 2199-4536 2198-6053 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Springer |
| record_format | Article |
| series | Complex & Intelligent Systems |
| spelling | doaj-art-35248efcddc24508bf0980aa6ab029ac2025-02-09T13:01:08ZengSpringerComplex & Intelligent Systems2199-45362198-60532025-01-0111212110.1007/s40747-024-01750-3A multitasking ant system for multi-depot pick-up and delivery location routing problem with time windowHaoyuan Lv0Ruochen Liu1Jianxia Li2Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, Xidian UniversityKey Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, Xidian UniversityKey Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, Xidian UniversityAbstract Instant delivery service has brought great convenience to our modern life. In order to improve its efficiency, multi-depot pick-up-and-delivery location routing problem with time windows (MDPDLRPTW) is proposed in this paper. Existing works related to MDPDLRPTW focus on obtaining a depot location scheme by clustering and perform route planning on it through single-task optimization. They are powerless to simultaneously explore the solution spaces of multiple routing tasks under different location schemes. Furthermore, ignoring the potential general knowledge among different schemes leads to redundant optimization. In this work, MDPDLRPTW is modeled as a multi-transformation optimization (MTFO) problem and a novel two-stage algorithm based on multitasking ant system (MTAS) is designed to solve it. In the first stage, a clustering algorithm based on spatio-temporal feature is used to group similar customer pairs, and the clustering centers are set as warehouses. Afterward, multiple localization schemes are selected through non-dominated sorting based on spatio-temporal density. In the second stage, MTAS concurrently optimizes multiple routing tasks based on these location schemes, each task is assigned to an ant system solver. Furthermore, MTAS achieves knowledge sharing among all routing tasks through adaptive similarity measurement and cross-task pheromone fusion strategy. The former can dynamically capture the relationship between tasks to adjust the transfer strength of task pairs, and the latter realizes adaptive knowledge transfer by pheromone-matrix mixing. Experimental results show that MTAS can efficiently utilize the common knowledge to achieve competitive performance.https://doi.org/10.1007/s40747-024-01750-3MDPDLRPTWEvolutionary multitasking optimizationAnt systemNegative transfer |
| spellingShingle | Haoyuan Lv Ruochen Liu Jianxia Li A multitasking ant system for multi-depot pick-up and delivery location routing problem with time window Complex & Intelligent Systems MDPDLRPTW Evolutionary multitasking optimization Ant system Negative transfer |
| title | A multitasking ant system for multi-depot pick-up and delivery location routing problem with time window |
| title_full | A multitasking ant system for multi-depot pick-up and delivery location routing problem with time window |
| title_fullStr | A multitasking ant system for multi-depot pick-up and delivery location routing problem with time window |
| title_full_unstemmed | A multitasking ant system for multi-depot pick-up and delivery location routing problem with time window |
| title_short | A multitasking ant system for multi-depot pick-up and delivery location routing problem with time window |
| title_sort | multitasking ant system for multi depot pick up and delivery location routing problem with time window |
| topic | MDPDLRPTW Evolutionary multitasking optimization Ant system Negative transfer |
| url | https://doi.org/10.1007/s40747-024-01750-3 |
| work_keys_str_mv | AT haoyuanlv amultitaskingantsystemformultidepotpickupanddeliverylocationroutingproblemwithtimewindow AT ruochenliu amultitaskingantsystemformultidepotpickupanddeliverylocationroutingproblemwithtimewindow AT jianxiali amultitaskingantsystemformultidepotpickupanddeliverylocationroutingproblemwithtimewindow AT haoyuanlv multitaskingantsystemformultidepotpickupanddeliverylocationroutingproblemwithtimewindow AT ruochenliu multitaskingantsystemformultidepotpickupanddeliverylocationroutingproblemwithtimewindow AT jianxiali multitaskingantsystemformultidepotpickupanddeliverylocationroutingproblemwithtimewindow |