A hybrid of K-means and genetic algorithm to solve a bi-objective green delivery and pick-up problem

ABSTRACT

Emissions of hazardous greenhouse gases from vehicles poses a remarkable threat to the environment. This study considers a bi-objective green delivery and pick-up problem wherein vehicle fuel burnt per distance, as a CO₂ emission metric, and fixed costs of the fleet are minimized. A mathematical model is devised to obtain exact solutions. A hybrid three-step metaheuristic approach is devised to tackle large-size instances. To generate initial solutions, customers are clustered based on their locations using k-means algorithm. Afterward, a genetic algorithm is used for solving a traveling salesman problem within each cluster. Finally, NSGA-II is incorporated to concatenate clusters, obtained from the initial solution, while generating non-dominated solutions by performing a trade-off between costs and emissions. Random problem instances are generated and solved to make a comparison between the performance of hybrid methodology against NSGA-II, MOPSO, and multi-objective dragonfly algorithm. Results indicate the hybrid approach’s superiority to others.

Graphical Abstract

KEYWORDS:

• Green
• Vehicle Routing Problem
• Delivery & Pick-up
• Clustering
• Genetic Algorithm

Disclosure statement

No potential conflict of interest was reported by the author(s).