Open AccessPerformance Comparison of Two-phase LP-based Heuristic Methods for Capacitated Vehicle Routing Problem with Three Objectives
Author(s) -
Sophea Horng,
Pisal Yenradee
Publication year - 2020
Publication title -
warasan witsawakammasat, chulalongkorn university
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.246
H-Index - 20
ISSN - 0125-8281
DOI - 10.4186/ej.2020.24.5.145
Subject(s) - cluster analysis , heuristic , vehicle routing problem , overtime , mathematical optimization , travelling salesman problem , computer science , cluster (spacecraft) , operations research , routing (electronic design automation) , engineering , mathematics , artificial intelligence , economics , computer network , labour economics , programming language
This paper develops a two-phase LP-based heuristic for the Capacitated Vehicle Routing Problem (CVRP). It considers three objectives: (1) minimizing the total costs of fuel consumption and overtime, (2) maximizing the total personal relationships between customers and drivers, and (3) balancing the delivery weights of vehicles. The two-phase LP-based heuristic (cluster-first route-second) is proposed. First, in the clustering stage, three LP-based clustering models (denoted by C1, C2, and C3) are developed. Customers are grouped into clusters based on real distances between the customers for C1, personal relationships between the customers and drivers for C2, and the delivery weights of vehicles for C3. Second, in the routing stage, an LP-based traveling salesman problem model is used to form a route for each cluster, to minimize the total costs of fuel consumption and overtime labor. The experimental results from a case study of Thai SMEs show that when the C2 clustering model is applied, the performances are the best. Significant contributions of this paper include: (1) it is an original paper that proposes the C2 clustering model, and it has the best performances based on the experimental results, and (2) the proposed two-phase LP-based heuristic methods are suitable for practical use by SMEs since the required computational time is short, and it has multiple models with different objectives that can be selected to match a user's requirements.