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: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9115005/ |
| _version_ | 1818857167727362048 |
|---|---|
| author | Wenzhe Yang Di Wang Wei Pang Ah-Hwee Tan You Zhou |
| author_facet | Wenzhe Yang Di Wang Wei Pang Ah-Hwee Tan You Zhou |
| author_sort | Wenzhe Yang |
| collection | DOAJ |
| 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-12-19T08:36:06Z |
| format | Article |
| id | doaj.art-e9a3b508c3fa410ba61e996b9f667078 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-19T08:36:06Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-e9a3b508c3fa410ba61e996b9f6670782022-12-21T20:29:03ZengIEEEIEEE Access2169-35362020-01-01811033611035010.1109/ACCESS.2020.30015909115005Goods Consumed During Transit in Split Delivery Vehicle Routing Problems: Modeling and SolutionWenzhe Yang0https://orcid.org/0000-0003-4415-512XDi Wang1https://orcid.org/0000-0002-3171-4001Wei Pang2https://orcid.org/0000-0002-1761-6659Ah-Hwee Tan3https://orcid.org/0000-0003-0378-4069You Zhou4https://orcid.org/0000-0003-0013-1281College of Computer Science and Technology, Jilin University, Changchun, ChinaJoint NTU-UBC Research Centre of Excellence in Active Living for the Elderly, Nanyang Technological University, SingaporeSchool of Mathematical and Computer Sciences, Heriot-Watt University, Edinburgh, U.KJoint NTU-UBC Research Centre of Excellence in Active Living for the Elderly, Nanyang Technological University, SingaporeCollege of Computer Science and Technology, Jilin University, Changchun, ChinaThis 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.https://ieeexplore.ieee.org/document/9115005/Split delivery vehicle routing problem (SDVRP)goods consumed during transitoptimizationant colony algorithms |
| spellingShingle | Wenzhe Yang Di Wang Wei Pang Ah-Hwee Tan You Zhou Goods Consumed During Transit in Split Delivery Vehicle Routing Problems: Modeling and Solution IEEE Access Split delivery vehicle routing problem (SDVRP) goods consumed during transit optimization ant colony algorithms |
| 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 | Split delivery vehicle routing problem (SDVRP) goods consumed during transit optimization ant colony algorithms |
| url | https://ieeexplore.ieee.org/document/9115005/ |
| work_keys_str_mv | AT wenzheyang goodsconsumedduringtransitinsplitdeliveryvehicleroutingproblemsmodelingandsolution AT diwang goodsconsumedduringtransitinsplitdeliveryvehicleroutingproblemsmodelingandsolution AT weipang goodsconsumedduringtransitinsplitdeliveryvehicleroutingproblemsmodelingandsolution AT ahhweetan goodsconsumedduringtransitinsplitdeliveryvehicleroutingproblemsmodelingandsolution AT youzhou goodsconsumedduringtransitinsplitdeliveryvehicleroutingproblemsmodelingandsolution |