Analysis of vehicle routing problem using various particle swarm optimization techniques

Abstract

Combinatorial Optimization Problems (COP) are NP-hard (Non-Deterministic) problems that are difficult to solve in polynomial time. Many real-time problems are combinatorial that are of routing or scheduling type. These problems may either be deterministic or probabilistic depending on the availability of values. The main objective of these problems is to find a serve of sequence of customers that will minimize the cost of service. The cost may be the travelling time / travelling distance / servicing time. Finding an optimal or near optimal solution is a challenging task. The Vehicle Routing Problem (VRP) is a combinatorial optimization problem that is considered in this thesis. The thesis comprises a snapshot of PSO techniques including variations in algorithm and its applications in the area of Vehicle Routing Problem (VRP). The main objective of this research is to propose hybrid algorithm using PSO for solving VRP, an important COP and the efficient and effective representation of particles to solve VRP. The space and time complexity of the algorithms are to be reduced by means of this hybrid algorithm. Genetic Algorithm (GA), PSO and HPSO are developed to solve VRPSD. The costs obtained by HPSO are best when compared to PSO and GA. PSO is combined with a Modified k-means algorithm (MK-HPSO) to solve deterministic VRP. Route-first and cluster-second is the strategy first adapted in HPSO, but as the problem size grows it become stale. So in the other two approaches cluster-first and route-second is adapted. It reduces the problem size and can provide better solution when the problem grows in its size. The scope for the future studies is that the proposed approaches can be tested for other COP with multi-objective, other types of VRP such as VRPTW, VRPPD etc., Task assignment and Job-scheduling problems. NPSO can be used for solving assignment or partitioning problems, and PSO can be incorporated with Simulated Annealing (SA) and Tabu Search (TS) to avoid trapping into local optima. newline newline newline