| Title: | A two-stage construction heuristic approach for vehicle routing problem with split deliveries and pickups : case studies and performance comparison |
|---|
| Authors: | ID Jin, C. (Author)
ID Lu, L. J. (Author)
ID Min, J. N. (Author) |
|---|
| Files: |  APEM17-1_121-133.pdf (848,32 KB)
MD5: 4C55CEB6BD6B683AFAACAD21E23ADF1F
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FS - Faculty of Mechanical Engineering
|
|---|
| Abstract: | The vehicle routing problem with split deliveries and pickups is a hot research topic in recent years, where a customer can be served multiple times with split deliveries and pickups. The objective is to minimize the travel distance, use the fewest number of vehicles and increase the load rate, which will further reduce the carbon emissions that damage the environment. In this paper, we use a two-stage construction heuristic approach to solve this problem. First, partitioning algorithms based on the multi-restart-iterative sweep algorithm are adopted to partition the customer domain into sub-domains according to the vehicle capacity, and to determine the split points and the corresponding values. Second, a modified Clarke-Wright savings algorithm is used to check the possibility of each point in each route based on the load of each point and the vehicle load limitation. The three case studies with 12 instances per each from the reconstructed Solomon benchmark datasets were conducted to evaluate the effectiveness and feasibility of the proposed approaches-Unsplit, Both-Split and Enhanced-Both-Split. The comparison among these approaches reveals that the splits reduce the total travel cost and vehicles used, and increase the average loading rate considerably, especially when customers have larger demand values. Our computation results proves that the vehicle routing problem with split deliveries and pickups is highly beneficial for transportation and logistics enterprises. |
|---|
| Keywords: | vehicle routing, split deliveries and pickups, two-stage construction heuristic, clustering first and routing later, partitioning algorithms, modified Clarke-Wright savings algorithm |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Submitted for review: | 15.10.2021 |
|---|
| Article acceptance date: | 05.03.2022 |
|---|
| Publication date: | 29.04.2022 |
|---|
| Publisher: | Fakulteta za strojništvo, Inštitut za proizvodno strojništvo |
|---|
| Year of publishing: | 2022 |
|---|
| Number of pages: | str. 121-133 |
|---|
| Numbering: | Vol. 17, no. 1 |
|---|
| PID: | 20.500.12556/DKUM-97194  |
|---|
| UDC: | 658.5 |
|---|
| ISSN on article: | 1854-6250 |
|---|
| COBISS.SI-ID: | 269124355 |
|---|
| DOI: | 10.14743/apem2022.1.425 |
|---|
| Copyright: | Content from this work may be used under the terms of the Creative Commons Attribution 4.0 International Licence (CC BY 4.0). Any further distribution of this work must maintain attribution to the author(s) and the title of the work, journal citation, and DOI. |
|---|
| Publication date in DKUM: | 23.02.2026 |
|---|
| Views: | 162 |
|---|
| Downloads: | 1 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
