Advances in Production Engineering & Management
Volume 14 | Number 1 | March 2019 | pp 125–135
https://doi.org/10.14743/apem2019.1.316
Maximum-minimum distance clustering method for split-delivery vehicle-routing problem: Case studies and performance comparisons
Min, J.N.; Jin, C.; Lu, L.J.
ABSTRACT AND REFERENCES (PDF) |
FULL ARTICLE TEXT (PDF)
A B S T R A C T
The split-delivery vehicle-routing problem in which delivery to a demand point can be served by any number of vehicles is an important branch of classic VRP. Objective function is used to minimise travel distance while using the lowest number of vehicles. According to the maximum-minimum distance clustering method, a three-stage algorithm is proposed. First, the maximum-minimum distance method is employed to cluster customer points into the lowest number of groups. Second, according to the maximum vehicle capacity, the load demand in each group is adjusted to create suitable customer points in each clustering group by adopting 'push-out' and 'pull-in' operations. Third, a tabu search is used and an optimised route for each group is generated to minimise the total travel distance. Numerical experiments, some on the benchmark data set, are presented to verify the feasibility and effectiveness of the proposed algorithm. The computational results show that the performance of the proposed algorithm is better in terms of both optimised travel distance and less computation time when the problem size is less than 75. The results also show that when the customer points are in a cluster distribution around the depot, the algorithm achieves better performance.
A R T I C L E I N F O
Keywords • Split-delivery vehicle-routing problem; Maximum-minimum distance method; Load-demand adjustment; Route optimisation; Tabu search; Clustering first and routing later
Corresponding author • Jin, C.
Article history • Received 5 December 2018, Revised 12 February 2019, Accepted 25 February 2019
Published on-line • 23 March 2019
E X P O R T C I T A T I O N
» RIS format (EndNote, ProCite, RefWorks, and most other reference management software)
» BibTeX (JabRef, BibDesk, and other BibTeX-specific software)
» Plain text
