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 journalArticle

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

Fingerprint

Vehicle routing
Genetic algorithms
Logistics
Customer satisfaction
Scheduling
Industry

Keywords

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

Cite this

Ho, William ; Ho, George T.S. ; Ji, Ping ; Lau, Henry C.W. / A hybrid genetic algorithm for the multi-depot vehicle routing problem. In: Engineering Applications of Artificial Intelligence. 2008 ; Vol. 21, No. 4. pp. 548-557.
@article{b4e46ac401f54d6d9429e2f126be258c,
title = "A hybrid genetic algorithm for the multi-depot vehicle routing problem",
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.",
keywords = "logistics, distribution management, vehicle routing problem, multiple depots, hybrid genetic algorithm",
author = "William Ho and Ho, {George T.S.} and Ping Ji and Lau, {Henry C.W.}",
year = "2008",
month = "6",
doi = "10.1016/j.engappai.2007.06.001",
language = "English",
volume = "21",
pages = "548--557",
journal = "Engineering Applications of Artificial Intelligence",
issn = "0952-1976",
publisher = "Elsevier",
number = "4",

}

A hybrid genetic algorithm for the multi-depot vehicle routing problem. / Ho, William; Ho, George T.S.; Ji, Ping; Lau, Henry C.W.

In: Engineering Applications of Artificial Intelligence, Vol. 21, No. 4, 06.2008, p. 548-557.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Ho, William

AU - Ho, George T.S.

AU - Ji, Ping

AU - Lau, Henry C.W.

PY - 2008/6

Y1 - 2008/6

N2 - 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.

AB - 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.

KW - logistics

KW - distribution management

KW - vehicle routing problem

KW - multiple depots

KW - hybrid genetic algorithm

UR - http://www.scopus.com/inward/record.url?scp=43549084845&partnerID=8YFLogxK

U2 - 10.1016/j.engappai.2007.06.001

DO - 10.1016/j.engappai.2007.06.001

M3 - Article

VL - 21

SP - 548

EP - 557

JO - Engineering Applications of Artificial Intelligence

JF - Engineering Applications of Artificial Intelligence

SN - 0952-1976

IS - 4

ER -