A Heuristic Solution Method for Multi-Depot Vehicle Routing-Based Waste Collection Problems
This paper addresses waste collection problems in which urban household and solid waste are brought from waste collection points to waste disposal plants. The collection of waste from the collection points herein is modeled as a multi-depot vehicle routing problem (MDVRP), aiming at minimizing the t...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-04-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/10/7/2403 |
| _version_ | 1797571724980518912 |
|---|---|
| author | Yanjun Shi Lingling Lv Fanyi Hu Qiaomei Han |
| author_facet | Yanjun Shi Lingling Lv Fanyi Hu Qiaomei Han |
| author_sort | Yanjun Shi |
| collection | DOAJ |
| description | This paper addresses waste collection problems in which urban household and solid waste are brought from waste collection points to waste disposal plants. The collection of waste from the collection points herein is modeled as a multi-depot vehicle routing problem (MDVRP), aiming at minimizing the total transportation distance. In this study, we propose a heuristic solution method to address this problem. In this method, we firstly assign waste collection points to waste disposal plants according to the nearest distance, then each plant solves the single-vehicle routing problem (VRP) respectively, assigning customers to vehicles and planning the order in which customers are visited by vehicles. In the latter step, we propose the sector combination optimization (SCO) algorithm to generate multiple initial solutions, and then these initial solutions are improved using the merge-head and drop-tail (MHDT) strategy. After a certain number of iterations, the optimal solution in the last generation is reported. Computational experiments on benchmark instances showed that the initial solutions obtained by the sector combination optimization algorithm were more abundant and better than other iterative algorithms using only one solution for initialization, and the solutions with distance gap were obtained using the merge-head and drop-tail strategy in a lower CPU time compared to the Tabu search algorithm. |
| first_indexed | 2024-03-10T20:45:36Z |
| format | Article |
| id | doaj.art-16ad89b2c0774aafbcbf50b58f7a854d |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T20:45:36Z |
| publishDate | 2020-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-16ad89b2c0774aafbcbf50b58f7a854d2023-11-19T20:21:17ZengMDPI AGApplied Sciences2076-34172020-04-01107240310.3390/app10072403A Heuristic Solution Method for Multi-Depot Vehicle Routing-Based Waste Collection ProblemsYanjun Shi0Lingling Lv1Fanyi Hu2Qiaomei Han3Department of Mechanical Engineering, Dalian University of Technology, Dalian 116024, ChinaDepartment of Mechanical Engineering, Dalian University of Technology, Dalian 116024, ChinaDepartment of Mechanical Engineering, Dalian University of Technology, Dalian 116024, ChinaDepartment of Mechanical Engineering, Dalian University of Technology, Dalian 116024, ChinaThis paper addresses waste collection problems in which urban household and solid waste are brought from waste collection points to waste disposal plants. The collection of waste from the collection points herein is modeled as a multi-depot vehicle routing problem (MDVRP), aiming at minimizing the total transportation distance. In this study, we propose a heuristic solution method to address this problem. In this method, we firstly assign waste collection points to waste disposal plants according to the nearest distance, then each plant solves the single-vehicle routing problem (VRP) respectively, assigning customers to vehicles and planning the order in which customers are visited by vehicles. In the latter step, we propose the sector combination optimization (SCO) algorithm to generate multiple initial solutions, and then these initial solutions are improved using the merge-head and drop-tail (MHDT) strategy. After a certain number of iterations, the optimal solution in the last generation is reported. Computational experiments on benchmark instances showed that the initial solutions obtained by the sector combination optimization algorithm were more abundant and better than other iterative algorithms using only one solution for initialization, and the solutions with distance gap were obtained using the merge-head and drop-tail strategy in a lower CPU time compared to the Tabu search algorithm.https://www.mdpi.com/2076-3417/10/7/2403multi-depot vehicle routing problemsector combination optimization algorithmmerge-head and drop-tail strategy |
| spellingShingle | Yanjun Shi Lingling Lv Fanyi Hu Qiaomei Han A Heuristic Solution Method for Multi-Depot Vehicle Routing-Based Waste Collection Problems Applied Sciences multi-depot vehicle routing problem sector combination optimization algorithm merge-head and drop-tail strategy |
| title | A Heuristic Solution Method for Multi-Depot Vehicle Routing-Based Waste Collection Problems |
| title_full | A Heuristic Solution Method for Multi-Depot Vehicle Routing-Based Waste Collection Problems |
| title_fullStr | A Heuristic Solution Method for Multi-Depot Vehicle Routing-Based Waste Collection Problems |
| title_full_unstemmed | A Heuristic Solution Method for Multi-Depot Vehicle Routing-Based Waste Collection Problems |
| title_short | A Heuristic Solution Method for Multi-Depot Vehicle Routing-Based Waste Collection Problems |
| title_sort | heuristic solution method for multi depot vehicle routing based waste collection problems |
| topic | multi-depot vehicle routing problem sector combination optimization algorithm merge-head and drop-tail strategy |
| url | https://www.mdpi.com/2076-3417/10/7/2403 |
| work_keys_str_mv | AT yanjunshi aheuristicsolutionmethodformultidepotvehicleroutingbasedwastecollectionproblems AT linglinglv aheuristicsolutionmethodformultidepotvehicleroutingbasedwastecollectionproblems AT fanyihu aheuristicsolutionmethodformultidepotvehicleroutingbasedwastecollectionproblems AT qiaomeihan aheuristicsolutionmethodformultidepotvehicleroutingbasedwastecollectionproblems AT yanjunshi heuristicsolutionmethodformultidepotvehicleroutingbasedwastecollectionproblems AT linglinglv heuristicsolutionmethodformultidepotvehicleroutingbasedwastecollectionproblems AT fanyihu heuristicsolutionmethodformultidepotvehicleroutingbasedwastecollectionproblems AT qiaomeihan heuristicsolutionmethodformultidepotvehicleroutingbasedwastecollectionproblems |