Meta-Heuristic Methods for Multi-Depot Vehicle Routing Problem

Abstract

The multi-depot vehicle routing problem (MDVRP) has been known as an NP-hard problem. It Is hard

and complexity to find the optimum solutions. The Objective of this research is to find the multi-depot vehicle

routing solution that minimize total distance. The problem is defined as a capacitate veh1cle and a single

vehicle for each depot. The problem can be solved by using cluster-first route-second concept. The first.

cluster is the discriminate analysis by distance measure. The second is vehicle routing arrangement by using

meta-heuristic method. The experiment is defined by the MDVRP instance with 100 nodes of customer The

vehicle capacity is equal to 400 units per tour. The algorithm start with phase 1, define four depots for this

instance and find the best locations and allocations. This step, we use the discriminate analysis on MsEXCEL.

Phase 2 is vehicle routing arrangement by using the hybrid algorithm and then compared the results

with the simulated annealing algorithm and the genetic algorithm. It is determining the solutions and shows

graphically disperse by using MATLAB computing software. The experimental results show clearly that the hybrid algorithm can be found the minimum solution for this problem example.