A hybrid genetic algorithm for the multi-depot vehicle routing problem

William Ho, George T.S. Ho, Ping Ji, Henry C.W. Lau

Research output: Contribution to journalArticlepeer-review

Abstract

The distribution of finished products from depots to customers is a practical and challenging problem in logistics management. Better routing and scheduling decisions can result in higher level of customer satisfaction because more customers can be served in a shorter time. The distribution problem is generally formulated as the vehicle routing problem (VRP). Nevertheless, there is a rigid assumption that there is only one depot. In cases, for instance, where a logistics company has more than one depot, the VRP is not suitable. To resolve this limitation, this paper focuses on the VRP with multiple depots, or multi-depot VRP (MDVRP). The MDVRP is NP-hard, which means that an efficient algorithm for solving the problem to optimality is unavailable. To deal with the problem efficiently, two hybrid genetic algorithms (HGAs) are developed in this paper. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method and the nearest neighbor heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different problem sizes. It is proved that the performance of HGA2 is superior to that of HGA1 in terms of the total delivery time.
Original languageEnglish
Pages (from-to)548-557
Number of pages10
JournalEngineering Applications of Artificial Intelligence
Volume21
Issue number4
DOIs
Publication statusPublished - Jun 2008

Keywords

  • logistics
  • distribution management
  • vehicle routing problem
  • multiple depots
  • hybrid genetic algorithm

Fingerprint

Dive into the research topics of 'A hybrid genetic algorithm for the multi-depot vehicle routing problem'. Together they form a unique fingerprint.

Cite this