Goods consumed during transit in split delivery vehicle routing problems : modeling and solution
This article presents the modeling and solution of an extended type of split delivery vehicle routing problem (SDVRP). In SDVRP, the demands of customers need to be met by efficiently routing a given number of capacitated vehicles, wherein each customer may be served multiple times by more than one...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/145637 |
| _version_ | 1811692594049056768 |
|---|---|
| author | Yang, Wenzhe Wang, Di Pang, Wei Tan, Ah-Hwee Zhou, You |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Yang, Wenzhe Wang, Di Pang, Wei Tan, Ah-Hwee Zhou, You |
| author_sort | Yang, Wenzhe |
| collection | NTU |
| description | This article presents the modeling and solution of an extended type of split delivery vehicle routing problem (SDVRP). In SDVRP, the demands of customers need to be met by efficiently routing a given number of capacitated vehicles, wherein each customer may be served multiple times by more than one vehicle. Furthermore, in many real-world scenarios, consumption of vehicles en route is the same as the goods being delivered to customers, such as food, water and fuel in rescue or replenishment missions in harsh environments. Moreover, the consumption may also be in virtual forms, such as time spent in constrained tasks. We name such a real-world SDVRP as Split Delivery Vehicle Routing Problem with Goods Consumed during Transit (SDVRP-GCT). In this paper, we give mathematical formulas to model SDVRP-GCT and provide solutions by extending three ant colony algorithms. To the best of our knowledge, this is the first research work specifically focussing on the SDVRP-GCT problem and its solutions. To assess the effectiveness of our proposed ant colony algorithms, we first apply them on widely adopted SDVRP benchmarking instances on different scales and their correspondingly extended SDVRP-GCT instances. Then, we formulate a real-world SDVRP-GCT instance for further assessment. Based on the extensive experimental results, we discuss the pros and cons of our proposed solutions and subsequently suggest their preferable application scenarios. In summary, our proposed solutions are shown as highly efficient in solving SDVRP-GCT instances. |
| first_indexed | 2024-10-01T06:38:16Z |
| format | Journal Article |
| id | ntu-10356/145637 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:38:16Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-10356/1456372020-12-30T07:34:46Z Goods consumed during transit in split delivery vehicle routing problems : modeling and solution Yang, Wenzhe Wang, Di Pang, Wei Tan, Ah-Hwee Zhou, You School of Computer Science and Engineering Joint NTU-WeBank Research Centre on FinTech Joint NTU-UBC Research Centre of Excellence in Active Living for the Elderly (LILY) Engineering::Computer science and engineering Split Delivery Vehicle Routing Problem Goods Consumed During Transit This article presents the modeling and solution of an extended type of split delivery vehicle routing problem (SDVRP). In SDVRP, the demands of customers need to be met by efficiently routing a given number of capacitated vehicles, wherein each customer may be served multiple times by more than one vehicle. Furthermore, in many real-world scenarios, consumption of vehicles en route is the same as the goods being delivered to customers, such as food, water and fuel in rescue or replenishment missions in harsh environments. Moreover, the consumption may also be in virtual forms, such as time spent in constrained tasks. We name such a real-world SDVRP as Split Delivery Vehicle Routing Problem with Goods Consumed during Transit (SDVRP-GCT). In this paper, we give mathematical formulas to model SDVRP-GCT and provide solutions by extending three ant colony algorithms. To the best of our knowledge, this is the first research work specifically focussing on the SDVRP-GCT problem and its solutions. To assess the effectiveness of our proposed ant colony algorithms, we first apply them on widely adopted SDVRP benchmarking instances on different scales and their correspondingly extended SDVRP-GCT instances. Then, we formulate a real-world SDVRP-GCT instance for further assessment. Based on the extensive experimental results, we discuss the pros and cons of our proposed solutions and subsequently suggest their preferable application scenarios. In summary, our proposed solutions are shown as highly efficient in solving SDVRP-GCT instances. Nanyang Technological University Published version This work was supported in part by the National Natural Science Foundation of China under Grant 61772227, Grant 61972174, and Grant 61972175, in part by the Science and Technology Development Foundation of Jilin Province under Grant 20180201045GX,Grant 20200201300JC, and Grant 20180414012GH, in part by the Jilin Development and Reform Commission Fund underGrant 2020C020-2, and in part by the Joint NTU-WeBank Research Centre on Fintech, Nanyang Technological University, Singapore, under Award NWJ-2019-002. 2020-12-30T07:34:46Z 2020-12-30T07:34:46Z 2020 Journal Article Yang, W., Wang, D., Pang, W., Tan, A.-H., & Zhou, Y. (2020). Goods consumed during transit in split delivery vehicle routing problems : modeling and solution. IEEE Access, 8, 110336-110350. doi:10.1109/ACCESS.2020.3001590 2169-3536 https://hdl.handle.net/10356/145637 10.1109/ACCESS.2020.3001590 8 110336 110350 en NWJ-2019-002 IEEE Access © 2020 IEEE. This journal is 100% open access, which means that all content is freely available without charge to users or their institutions. All articles accepted after 12 June 2019 are published under a CC BY 4.0 license, and the author retains copyright. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, as long as proper attribution is given. application/pdf |
| spellingShingle | Engineering::Computer science and engineering Split Delivery Vehicle Routing Problem Goods Consumed During Transit Yang, Wenzhe Wang, Di Pang, Wei Tan, Ah-Hwee Zhou, You Goods consumed during transit in split delivery vehicle routing problems : modeling and solution |
| title | Goods consumed during transit in split delivery vehicle routing problems : modeling and solution |
| title_full | Goods consumed during transit in split delivery vehicle routing problems : modeling and solution |
| title_fullStr | Goods consumed during transit in split delivery vehicle routing problems : modeling and solution |
| title_full_unstemmed | Goods consumed during transit in split delivery vehicle routing problems : modeling and solution |
| title_short | Goods consumed during transit in split delivery vehicle routing problems : modeling and solution |
| title_sort | goods consumed during transit in split delivery vehicle routing problems modeling and solution |
| topic | Engineering::Computer science and engineering Split Delivery Vehicle Routing Problem Goods Consumed During Transit |
| url | https://hdl.handle.net/10356/145637 |
| work_keys_str_mv | AT yangwenzhe goodsconsumedduringtransitinsplitdeliveryvehicleroutingproblemsmodelingandsolution AT wangdi goodsconsumedduringtransitinsplitdeliveryvehicleroutingproblemsmodelingandsolution AT pangwei goodsconsumedduringtransitinsplitdeliveryvehicleroutingproblemsmodelingandsolution AT tanahhwee goodsconsumedduringtransitinsplitdeliveryvehicleroutingproblemsmodelingandsolution AT zhouyou goodsconsumedduringtransitinsplitdeliveryvehicleroutingproblemsmodelingandsolution |