A hybrid genetic algorithm for the multi-depot vehicle routing problem
A hybrid genetic algorithm for the multi-depot vehicle routing problem
复制标题
DOI：
10.1016/j.engappai.2007.06.001
复制
发表时间：
2008-06-01
影响因子：
8
通讯作者：
Lau, Henry C. W.
中科院分区：
文献类型：
--
作者：
Ho, William;Ho, George T. S.;Lau, Henry C. W.
成品从仓库到客户的配送是物流管理中的一个实际而又具有挑战性的问题。更好的路由和调度决策可以导致更高水平的客户满意度，因为更多的客户可以在更短的时间内提供服务。配送问题通常被表述为车辆路径问题（VRP）。然而，有一个严格的假设，即只有一个仓库。例如，如果一家物流公司有一个以上的仓库，VRP就不适合。为了解决这一问题，本文研究了多车场车辆路径问题，即多车场车辆路径问题（MDVRP）。MDVRP是NP难的，这意味着没有一个有效的算法来解决问题的最优性。为了有效地处理该问题，本文提出了两种混合遗传算法。HGA之间的主要区别是初始解在HGA 1中随机生成。Clarke和Wright保存方法和最近邻启发式被纳入HGA 2的初始化过程。计算研究进行了比较不同的问题大小的算法。结果表明，HGA 2在总交货时间上优于HGA 1，具有上级性能。(c)2007爱思唯尔有限公司版权所有。
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. (c) 2007 Elsevier Ltd. All rights reserved.