Metaheuristics Approaches to Solve the Employee Bus Routing Problem With Clustering-Based Bus Stop Selection

Abstract

Vehicle routing problem (VRP) is a complex problem in the Operations Research topic. School bus routing (SBR) is one of the application areas of VRP. It is also possible to examine the employee bus routing problem in the direction of SBR problem. This chapter presents a case study with data taken from a retail company for capacitated employee bus routing problem. A mathematical model was developed based on minimizing the total bus route distance. The number and location of bus stops were determined using k-means and fuzzy c-means clustering algorithms. LINGO optimization software was utilized to solve the mathematical model. Then, due to NP-Hard nature of the bus routing problem, simulated annealing (SA) and genetic algorithm (GA)-based approaches were proposed to solve the real-world problem. Finally, the performances of the proposed approaches were evaluated by comparing with classical heuristics such as saving algorithm and nearest neighbor algorithm. The numerical results showed that the proposed GA-based approach with k-means performed better than other approaches.

Key Terms in this Chapter

Vehicle Routing Problem: A classical problem in operation research, which is one of the most challenging combinatorial optimization tasks.

K-Means Clustering: One of the simplest and popular unsupervised machine learning algorithms, which group similar data points together.

Saving Algorithm: One of the most known heuristics for vehicle routing problem.

Simulated Annealing: An optimization method, which mimics the slow cooling of metals.

Metaheuristic: A master strategy that guides and modifies other heuristics to produce solutions beyond those that are normally generated in a quest for local optimality.

Heuristic: An optimization method that tries to exploit problem-specific knowledge and for which we have no guarantee that it finds the optimal solution.

Genetic Algorithm: A metaheuristic, which is inspired by the theory of Darvin on natural selection and evaluation.